tags:
- 貪心
- 模擬
- NOIP
categories: - 信息學競賽
- 總結
計算系數
Solution
根據二項式定理,
\[ \begin{align} (a+b)^n=\sum_{k=0}^nC_{n}^{k}a^kb^{n-k} \end{align} \]
那么
\[ \begin{align}(ax+by)^k=&\sum_{p=0}^kC_{k}^p(ax)^p(by)^{k-p}\\ =&\sum_{p=0}^k(C_{k}^pa^pb^{k-p})x^py^{k-p} \end{align} \]
算\(a^n,b^m\)需要用快速冪.
可以根據組合式的遞推公式算組合數.
\[C_n^m=C_{n-1}^m+C_{n-1}^{m-1}\]
或者是利用組合數的定義式,但是因為有取余, 所以要用逆元.
\[C_n^m=\frac{n!\mod 10007}{m!(n-m)!\mod 10007}=n!\times m!(n-m)!^{-1}\mod 10007\]
其中\(m!(n-m)!^{-1}\)為逆元, 這個可以直接用費馬小定理, 正好前面寫了快速冪, 豈不是美滋滋.
Code
#include<cstdio>
#define N 1005
#define mod 10007
using namespace std;#define int long long
int c[N][N];
int a,b,k,n,m;
int pow(int x,int y){int ans=1,pas=x;while(y){if(y&1)ans*=pas%mod,ans%=mod;pas=(pas*pas)%mod;y>>=1;}return ans%mod;
}int dfs(int n,int m){if(!m)return c[n][m]=true;if(m==1)return c[n][m]=n;if(c[n][m])return c[n][m];if(n-m<m)m=n-m;return c[n][m]=(dfs(n-1,m)+dfs(n-1,m-1))%mod;
}main(){//freopen("factor.in","r",stdin);//freopen("factor.out","w",stdout);scanf("%lld%lld%lld%lld%lld",&a,&b,&k,&n,&m);c[1][0]=c[1][1]=1;a%=mod;b%=mod;int ans=1;ans*=(pow(a,n)*pow(b,m))%mod;if(n>m)n=m;ans*=dfs(k,n)%mod;ans%=mod;/*for(int i=1;i<=k;++i){for(int j=0;j<=i;++j)printf("%d ",c[i][j]);printf("\n");}*/printf("%lld",ans);return 0;
}聰明的質監員
Solution
二分一個\(W\)含義如圖所示, 有一個重要的性質是\(W\)越大\(Y\)就越小, 根據這個計算\(Y\), 如果\(Y>S\), 說明如果\(W\)再大些, \(Y>S\)的值可能會更小; 如果\(S>Y\), 說明如果\(W\)再小些, \(S-Y\)的值可能會更小.根據這來調整\(W\).計算\(Y\)時需要先算出滿足\(\sum\limits_{j}\left[w_j>W\right]w_j,\sum_{j}\left[w_j>W\right]1\)的前綴和, 暴力算當然不行.
Code
#include<cstdio>
#define inf 999999999999
#define N 200005
#define int long long
int ans;
int n,m,s;
int aaaa[N];
int sigma[N];
int v[N],w[N];
int le[N],ri[N];inline int abs(int s){return s>0?s:-s;
}
inline int min(int a,int b){return a<b?a:b;
}bool check(int W){sigma[0]=aaaa[0]=0ll;int an=0ll;for(int i=1;i<=n;++i){sigma[i]=sigma[i-1];aaaa[i]=aaaa[i-1];if(w[i]>=W)sigma[i]+=v[i],++aaaa[i];}for(int i=1;i<=m;++i)an+=(sigma[ri[i]]-sigma[le[i]-1])*(aaaa[ri[i]]-aaaa[le[i]-1]);an=an-s;ans=min(abs(an),ans);return an>0;
}main(){ans=inf;scanf("%lld%lld%lld",&n,&m,&s);for(int i=1;i<=n;++i)scanf("%lld%lld",&w[i],&v[i]);for(int i=1;i<=m;++i)scanf("%lld%lld",&le[i],&ri[i]);int l=0ll,r=s,mid;while(l<=r){mid=(l+r)>>1;if(check(mid))l=mid+1ll;else r=mid-1;}printf("%lld",ans);return 0;
}觀光公交
Solution
這個題看起來可以用dp做, 但是能不能做就是另一回事了, 但是現在知道它可以用貪心做.它是怎么做的呢?實際上非常好考慮.
首先, 每使用一次氮氣加速時, 目前在車上的有些人旅行時間會變短, 有些人會不變, 因為乘客上車的時間是不會改變的, 所以可能會在后面的某一站整車人都需要等一個乘客上車[判斷這個東西可以通過判斷從上一個點到達它的時間, 和最晚的乘客到達它的時間, 通過預處理完成這些操作], 在這之前下車的人旅行時間會變短.因此實際上這次氮氣加速只對不會受到等人上車影響的人有效, 也就是在它們上車之后直到下車都不會在某個站等別人上車的人是氮氣加速的受益者.
因此想要快速處理這些問題, 我們需要一個站最近的需要等人的站,一個站被到達的時間和在這個站接完所有乘客的時間, 因為一次加速的受益者是在加速后和到達需要等人的站之間下車的人數, 那么還需要通過前綴和快速求出在某段時間下車的人數.然后在每次加速之后, 兩個站之間的行駛時間被改變了, 那么其它站被到達(并且接到所有乘客)的時間也可能被改變了, 所以需要重新更新一下一個站被到達的時間.
不過并不知道為什么這樣的貪心策略是正確的?
Code
#include<algorithm>
#include<cstdio>
#define N 10005
using std::max;int n,m,k,ans;
int t[N],tm[N],l[N],r[N];
int ww[N],ws[N],ti[N],g[N];int main(){scanf("%d%d%d",&n,&m,&k);for(int i=1;i<n;i++)scanf("%d",&t[i]);for(int i=1;i<=m;i++)scanf("%d%d%d",&tm[i],&l[i],&r[i]);for(int i=1;i<=m;i++)ww[l[i]]=max(ww[l[i]],tm[i]),++ws[r[i]];for(int i=1;i<=n;i++)ws[i]=ws[i-1]+ws[i];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]]-tm[i];if(!k){printf("%d\n",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];int maxn=0,maxw=0;for(int i=1;i<n;i++)if(ws[g[i]]-ws[i]>maxn&&t[i]>0)maxn=ws[g[i]]-ws[i],maxw=i;t[maxw]--;ans-=maxn;for(int i=1;i<=n;i++)ti[i]=max(ww[i-1],ti[i-1])+t[i-1];}printf("%d\n",ans);return 0;
}
)
