NOIP 2011 题解+代码

这年的题是昨天写完的，但没有发博客。。。
依旧不贴题面了。

铺地毯。
简单模拟。倒着搜就行了，遇到第一个满足的就break掉。

#include<bits/stdc++.h>
using namespace std;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

const int N = 10000 + 10;

int n;

struct node{
    int x1,x2,y1,y2;
}a[N];

int main(){
    n=read();
    for(int i=1;i<=n;++i){
        int g,k; 
        a[i].x1=read(),a[i].y1=read(),g=read(),k=read();
        a[i].x2=a[i].x1+g-1,a[i].y2=a[i].y1+k-1;
    }
    int x=read(),y=read();
    for(int i=n;i>=1;--i){
        if(a[i].x1<=x&&a[i].x2>=x&&a[i].y1<=y&&a[i].y2>=y) {
            printf("%d\n",i);
            return 0;
        }
    }
    printf("-1\n");
    return 0;
}

选择客栈。
正解好像是dp，不过可以用st表来水。。用一个指针记录第一个人选i这个位置，第二个人至少应该选什么位置才会有满足条件的咖啡厅。再在输入的时候记录一个前缀和，表示到i这个位置风格为k的咖啡厅有多少个。每次移动指针，统计答案就行了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define ll long long
using namespace std;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

const int N = 200000 + 10;
const int P = 20;
const int K = 50 + 5;

inline int Min(int a,int b) {return a<b?a:b;}
inline int Max(int a,int b) {return a>b?a:b;}

int n,k,p;
int a[N],b[N],sum[N][K];
int logn[N],st[N][P];

void st_table(){
    logn[1]=0;
    for(int i=2;i<=n;++i) logn[i]=logn[i>>1]+1;
    for(int i=1;i<=n;++i) st[i][0]=a[i];
    for(int j=1;j<P;++j){
        for(int i=1;i+(1<<j)-1<=n;++i){
            st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
        }
    }
}

int query(int l,int r){
    int len=r-l+1;
    int k=logn[len];
    return min(st[l][k],st[r-(1<<k)+1][k]);
}

int main(){
    n=read(),k=read(),p=read();
    for(int i=0;i<k;++i) sum[0][i]=0;
    for(int i=1;i<=n;++i) {
        b[i]=read(),a[i]=read();
        for(int j=0;j<k;++j) sum[i][j]=sum[i-1][j]+(b[i]==j);
    }
    st_table();
    int tail=1;
    while(query(1,tail)>p) ++tail;
    ll ans=sum[n][b[1]]-sum[Max(tail-1,1)][b[1]];
    for(int i=2;i<=n;++i){
        tail=max(tail,i);
        while(query(i,tail)>p&&tail<n) ++tail;
        if(tail==n&&query(i,tail)>p) break;
        ans+=sum[n][b[i]]-sum[Max(tail-1,i)][b[i]];
    }
    cout<<ans<<endl;
    return 0;
}

玛雅游戏。
这个有毒！！它不让我过！！！
代码只有90分，但是数据在本机是能过的，以前（今天3月份）有AC的代码，也不想改了。
就是搜索，不剪枝也能过。注意如果有掉落或清除的话，掉落函数和清除函数就要一直调用，因为原来的掉落/清除可能会引发新的。

#include<bits/stdc++.h>
using namespace std;

const int N = 10;

int n;
int a[N][N],cnt[N];

bool check(){
    for(int i=0;i<5;++i)
    for(int j=0;j<7;++j)
    if(a[i][j]) return false;
    return true;
}

struct node{
    int step,x,y;
}b[100];

bool fallen(int i){
    bool flag=false;
    for(int j=6;j>0;--j){
        if(a[i][j]&&(!a[i][j-1])) flag=true,swap(a[i][j],a[i][j-1]);
    }
    return flag;
}

void fallen(){
    for(int i=0;i<5;++i){
        while(fallen(i));
    }
}

bool c[N][N];
bool clear(){
    memset(c,0,sizeof(c));
    for(int i=0;i<3;++i){
        for(int j=0;j<7;++j){
            if(a[i][j]!=0&&a[i][j]==a[i+1][j]&&a[i+1][j]==a[i+2][j]){
                c[i][j]=c[i+1][j]=c[i+2][j]=true;
            }
        }
    }
    for(int i=0;i<5;++i){
        for(int j=0;j<5;++j){
            if(a[i][j]!=0&&a[i][j]==a[i][j+1]&&a[i][j+2]==a[i][j+1]){
                c[i][j]=c[i][j+1]=c[i][j+2]=true;
            }
        }
    }
    bool flag=false;
    for(int i=0;i<5;++i){
        for(int j=0;j<7;++j){
            if(c[i][j]) a[i][j]=0,flag=true;
        }
    }
    return flag;
}

bool dfs(int d){
    int c[N][N];
    while(1){
        fallen();
        if(!clear()) break; 
    }
    if(d>n){
        if(check()) return true;
        return false;
    }
    memcpy(c,a,sizeof(c));
    for(int i=0;i<5;++i)
    for(int j=0;j<7;++j){
        if(!a[i][j]) continue;
        int x=i+1,y=j;
        if(x<5&&a[x][y]!=a[i][j]) {
            swap(a[x][y],a[i][j]);
            if(dfs(d+1)) {
                b[d].step=1,b[d].x=i,b[d].y=j;
                return true;
            }
            memcpy(a,c,sizeof(a));
        }
        x=i-1,y=j;
        if(x>=0&&a[x][y]==0){
            swap(a[x][y],a[i][j]);
            if(dfs(d+1)) {
                b[d].step=-1,b[d].x=i,b[d].y=j;
                return true;
            }
            memcpy(a,c,sizeof(a));          
        }
    }
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<5;++i){
        int x;scanf("%d",&x);
        while(x){
            a[i][cnt[i]++]=x;
            scanf("%d",&x);
        }
    }
    if(!dfs(1)) {printf("-1");return 0;}
    for(int i=1;i<=n;++i)
    printf("%d %d %d\n",b[i].x,b[i].y,b[i].step);
    return 0;
}

计算系数
杨辉三角和快速幂。。。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1000 + 10;
const int mod = 10007;

ll c[N][N];
int a,b,k,n,m;

ll mpow(ll a,ll b){
    ll rt=1;
    for(rt;b;b>>=1,a=a*a%mod)
        if(b&1) rt=rt*a%mod;
    return rt;
}

int main(){
    for(int i=1;i<=1002;++i){
        for(int j=1;j<=i;++j){
            if(j==1||j==i) c[i][j]=1;
            else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
        }
    }
    scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
    ll ans=mpow(a,n)*mpow(b,m)%mod*c[k+1][1+k-n]%mod;
    cout<<ans<<endl;
    return 0;
}

聪明的质检员
二分答案，每次check的时候先更新一下前缀和。注意要记录s的前驱和后驱，然后比较哪个更接近。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define ll long long
using namespace std;

inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

const int N = 200000 + 10;

int n,m;
ll s;
int l[N],r[N],w[N],v[N];
ll c1[N],c2[N];

ll getans(ll ww){
    ll ans=0;
    c1[0]=c2[0]=0;
    for(int i=1;i<=n;++i){
        if(w[i]>=ww) c1[i]=c1[i-1]+1,c2[i]=c2[i-1]+v[i];
        else c1[i]=c1[i-1],c2[i]=c2[i-1];
    }
    for(int i=1;i<=m;++i){
        ll num=c1[r[i]]-c1[l[i]-1],sum=c2[r[i]]-c2[l[i]-1];
        ans+=1LL*num*sum;
    }
    return ans;
}

int main(){
    n=read(),m=read(),s=read();
    ll lf=1,rg=1;
    for(int i=1;i<=n;++i) w[i]=read(),v[i]=read(),rg=max(rg,1LL*w[i]);
    for(int i=1;i<=m;++i) l[i]=read(),r[i]=read();
    ll ans1=0,ans2=0;rg+=1;
    while(lf<=rg){
        ll mid=(lf+rg)/2;
        ll x=getans(mid);
        if(x<=s) ans2=x,rg=mid-1;
        else lf=mid+1,ans1=x;
    }
    printf("%lld\n",min(s-ans2,ans1-s));
    return 0;
}

观光公交。
这道题调了好久。我可能是废了。
贪心。很容易求出如果一个加速器都不使用花费的总时间。对于加速器，就一个一个地处理。每次找到两个站台之间的距离， 求出如果改变这个速度，会减少多少人的时间，然后求出一个合法的最大值（当速度已经变为0了，即使改变它会使更多人时间减少也不可取了），每次都减去这个最大值就行了。O（nk）居然能过。
之前想的各种复杂。因为到每一个站台都有一个能减少的最多的时间的限制，如果多余了这个时间其实还不如不使用加速器，然后就求出如果改变这段时间会有多少人受益。按人数来排序。但其实每次改变之后会有后效性，各种麻烦。。不如暴力改。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

const int N = 1000 + 10;
const int M = 10000 + 10;

int n,m,k;
int d[N],st[M],a[M],b[M],ed[M],com[N],mx[N];
int far[N],sum[N];
ll ans=0,ans1=0;

void zero(){
    com[1]=0;
    for(int i=2;i<=n;++i) com[i]=max(com[i-1],mx[i-1])+d[i-1];
    for(int i=1;i<=m;++i) ans+=com[b[i]]-st[i];
}

int main(){
    n=read(),m=read(),k=read();
    for(int i=1;i<n;++i) d[i]=read();
    for(int i=1;i<=m;++i) st[i]=read(),a[i]=read(),b[i]=read(),mx[a[i]]=max(mx[a[i]],st[i]),++sum[b[i]];
    zero();
    for(int i=2;i<=n;++i) sum[i]+=sum[i-1];
    while(k--){
        far[n]=n;       
        for(int i=n-1;i>=2;--i){
            if(mx[i]<com[i]) far[i]=far[i+1];
            else far[i]=i;
        }
        int mmax=0,pos;
        for(int i=2;i<=n;++i) if(sum[far[i]]-sum[i-1]>mmax&&d[i-1]) mmax=sum[far[i]]-sum[i-1],pos=i;
        if(mmax==0) break;
        ans1+=mmax;--d[pos-1];
        for(int i=2;i<=n;++i) com[i]=max(com[i-1],mx[i-1])+d[i-1];
    }
    printf("%lld\n",ans-ans1);
    return 0;
}