NOIP2011

鋪地毯

Link
模擬。

#include<cstdio>const int N=10007;int a[N],b[N],g[N],k[N];int read(){int x;scanf("%d",&x);return x;}int main(){    int n=read(),x,y;    for(int i=1;i<=n;++i) a[i]=read(),b[i]=read(),g[i]=read(),k[i]=read();    x=read(),y=read();    for(int i=n;i;--i) if(a[i]<=x&&x<=a[i]+g[i]&&b[i]<=y&&y<=b[i]+k[i]) return !printf("%d",i);    puts("-1");}

選擇客棧

Link
枚舉右邊的客棧的位置,同時記錄這個位置的左邊各個色調的客棧有\(cnt\)個。
同時我們還需要維護各個色調的客棧中到當前位置中存在合法咖啡店的有\(sum\)個,這可以通過維護左邊的最近的咖啡店位置來完成。
具體來講當我們到達一個色調為\(a\)的有合法咖啡點的客棧時,令\(sum_a\leftarrow cnt_a\)即可。

#include<cstdio>const int N=10007;int las[N],sum[N],cnt[N];int read(){int x;scanf("%d",&x);return x;}int main(){    int n=read(),m=(read(),read()),now=0, ans=0;    for(int i=1;i<=n;++i)    {int a=read(),b=read();if(b<=m) now=i;if(now>=las[a]) sum[a]=cnt[a];las[a]=i,ans+=sum[a],++cnt[a];    }    printf("%d",ans);}

Mayan游戲

Link
爆搜,沒寫。

計算系數

Link
二項式定理。

#include<cstdio>const int N=1007,P=10007;int C[N][N];int read(){int x;scanf("%d",&x);return x;}int pow(int a,int b){int c=1;for(;b;b>>=1,a=a*a%P)if(b&1)c=c*a%P;return c;}int main(){    int a=read()%P,b=read()%P,k=read(),n=read(),m=read();    for(int i=0;i<=k;++i) for(int j=C[i][0]=1;j<=i;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;    printf("%d",pow(a,n)*pow(b,m)%P*C[k][n]%P);}

聰明的質檢員

Link
先二分答案(判斷當前的\([y>s]\))。
檢查的話維護一下\([w_i\ge W],[w_i\ge W]v_i\)的前綴和即可。

#include<cctype>#include<cstdio>#include<cstring>#include<algorithm>using i64=long long;const int N=200007;i64 read(){i64 x=0;char c=getchar();while(isspace(c))c=getchar();while(isdigit(c))(x*=10)+=c&15,c=getchar();return x;}int n,m,l[N],r[N],w[N],v[N];i64 s,ans=1e18;int check(int W){    static int cnt[N];static i64 sum[N];i64 y=0;    memset(cnt+1,0,4*n),memset(sum+1,0,8*n);    for(int i=1;i<=n;++i) cnt[i]=cnt[i-1]+(w[i]>=W),sum[i]=sum[i-1]+(w[i]>=W)*v[i];    for(int i=1;i<=m;++i) y+=(cnt[r[i]]-cnt[l[i]])*(sum[r[i]]-sum[l[i]]);    return ans=std::min(ans,llabs(s-y)),y>s;}int main(){    n=read(),m=read(),s=read();    for(int i=1;i<=n;++i) w[i]=read(),v[i]=read();    for(int i=1;i<=m;++i) l[i]=read()-1,r[i]=read();    for(int l=0,r=1000000,mid;l<=r;) mid=(l+r)/2,check(mid)? l=mid+1:r=mid-1;    printf("%lld",ans);}