NOIP2011提高组复赛day2解析
1.计算系数
题目：https://www.luogu.com.cn/problem/P1313
解析：
直接套用二项式定理，使用快速幂计算组合数
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e3+39+7,mod = 1e4+7;
ll fac[N],a,b,k,n,m;
void init(){
fac[0]=1;
for(int i=1;i<=1000;i++)fac[i]=(fac[i-1]*i)%mod;
}
ll quickPow(ll a,ll b,ll m){
ll ans=1;
while(b){
if(b&1)ans=((ans%m)*(a%m))%m;
a=((a%m)*(a%m))%m;
b>>=1;
}
return ans;
}
ll inv(ll a,ll m){
return quickPow(a,m-2,m);
}
int main(){
// freopen("factor.in","r",stdin);
// freopen("factor.out","w",stdout);
init();
cin>>a>>b>>k>>n>>m;
if(k<=1)cout<<1;
else cout<<fac[k]%mod*quickPow(a,n,mod)%mod*inv(fac[n],mod)%mod*quickPow(b,m,mod)%mod*inv(fac[m],mod)%mod;
return 0;
}
2.聪明的质监员
题目：https://www.luogu.com.cn/problem/P1314
解析：
使用二分枚举W，每次预处理前缀和，使用O(m)的复杂度进行验证
坑点：
二分的条件非常重要，正确的二分应该比较验证得到的结果与S比较，进行二分
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+39+7;
ll n,m,S,ans=1e18,maxW=0,w[N],v[N],L[N],R[N],sum[N],cnt[N];
ll calc(ll W){
sum[0]=cnt[0]=0;
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+(w[i]>=W?v[i]:0);
cnt[i]=cnt[i-1]+(w[i]>=W?1:0);
}
ll num=0;
for(int i=1;i<=m;i++)num+=(cnt[R[i]]-cnt[L[i]-1])*(sum[R[i]]-sum[L[i]-1]);
return num;
}
int main(){
// freopen("qc.in","r",stdin);
// freopen("qc.out","w",stdout);
cin>>n>>m>>S;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
maxW=max(maxW,w[i]);
}
for(int i=1;i<=m;i++)cin>>L[i]>>R[i];
ll l=1,r=maxW;
while(l<=r){
ll mid=(l+r)/2;
ll num=calc(mid);
if(num>S)l=mid+1;
else r=mid-1;
ans=min(ans,llabs(S-num));
}
cout<<ans;
return 0;
}
3.观光公交
题目：https://www.luogu.com.cn/problem/P1315
解析：
贪心思路，定义几个数组，分别表示时间、前缀和、编号等，模拟k次，每次进行更改，最终就是答案
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e4+39+7;
ll n,m,k,ans,t[N],tt[N],l[N],r[N],ww[N],ss[N],ti[N],g[N];
int main(){
cin>>n>>m>>k;
for(int i=1;i<n;i++)cin>>t[i];
for(int i=1;i<=m;i++)cin>>tt[i]>>l[i]>>r[i];
for(int i=1;i<=m;i++){
ww[l[i]]=max(ww[l[i]],tt[i]);
ss[r[i]]++;
}
for(int i=1;i<=n;i++)ss[i]+=ss[i-1];
for(int i=2;i<=n;i++)ti[i]=max(ww[i-1],ti[i-1])+t[i-1];
for(int i=1;i<=m;i++)ans+=ti[r[i]]-tt[i];
if(!k){
cout<<ans;
return 0;
}
while(k--){
g[n]=n;g[n-1]=n;
for(int i=n-2;i>=1;i--){
if(ti[i+1]<=ww[i+1])g[i]=i+1;
else g[i]=g[i+1];
}
ll maxn=0,maxid=0;
for(int i=1;i<n;i++){
if(ss[g[i]]-ss[i]>maxn&&t[i]>0){
maxn=ss[g[i]]-ss[i];
maxid=i;
}
}
t[maxid]--;
ans-=maxn;
for(int i=1;i<=n;i++)ti[i]=max(ww[i-1],ti[i-1])+t[i-1];
}
cout<<ans;
return 0;
}