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);
}

NOIP2011

原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/13021266.html