Noip2016滚粗记QAQ

day1

XBG

#include<map>

#include<cstdio>

#include<string>

#include<string.h>

#include<iostream>

#include<algorithm>

using namespace std;

int d[123456];

char ty[123456][20];

int n,m;

//...

int main(){

    freopen("toy.in","r",stdin);

    freopen("toy.out","w",stdout);

    scanf("%d %d",&n,&m);

    for(int i=0;i<n;i++)scanf("%d%s",d+i,ty[i]);

    //for(int i=1;i<=n;i++)d[i]=d[i]?1:-1;

    int now=0;

    while(m--){

        int op,s;

        scanf("%d %d",&op,&s);

        if(!d[now]){

            if(op)now=(now+s)%n;

            else now=((now-s)%n+n)%n;

        }else{

            if(op)now=((now-s)%n+n)%n;

            else now=(now+s)%n;

        }

    }

    cout<<ty[now];

    return 0;

}

暴力30

子任务Si=1

以1为根统计每个子树里面1的个数

子任务链的写错了。

45分

#include<map>

#include<cstdio>

#include<string>

#include<vector>

#include<string.h>

#include<iostream>

#include<algorithm>

using namespace std;

struct edge{

    int to,next;

}e[601234];

int cnt,last[301234],dep[301234],w[301234],ans[301234];

int n,m;

int s[301234],t[301234];

void insert(int a,int b){

    e[++cnt]=(edge){b,last[a]};last[a]=cnt;

    e[++cnt]=(edge){a,last[b]};last[b]=cnt;

}

int fa[301234][20];

void dfs(int v,int f){

    //fa[v][0]=f;

    //for(int i=1;i<=20;i++)fa[v][i]=fa[fa[v][i-1]][i-1];

    for(int i=last[v];i;i=e[i].next){

        int b=e[i].to;if(b!=f){

            dep[b]=dep[v]+1;

            dfs(b,v);

        }

    }

}

int an[301234];

void dfs2(int v,int t,int f){

    fa[v][0]=f;

    //for(int i=1;i<=20;i++)fa[v][i]=fa[fa[v][i-1]][i-1];

    for(int i=last[v];i;i=e[i].next){

        int b=e[i].to;if(b!=f){

            dfs2(b,t,v);

            if(b==t){

                an[v]=i;

            }

            if(an[b]){

                an[v]=i;

            }

        }

    }

}

void dfs3(int s,int t){

    int v=s,ti=0;

    ans[s]+=(ti==w[s]);

    while(s!=t){

        s=e[an[s]].to;

        ++ti;

        ans[s]+=(ti==w[s]);

    }

}

int siz[301234];

void dfs4(int v,int f){

    //fa[v][0]=f;

    //for(int i=1;i<=20;i++)fa[v][i]=fa[fa[v][i-1]][i-1];

    for(int i=last[v];i;i=e[i].next){

        int b=e[i].to;if(b!=f){

            dep[b]=dep[v]+1;

            dfs4(b,v);

            siz[v]+=siz[b];

            //fprintf(stderr,"Debug (%d)=%d\n",v,siz[v]);

        }

    }

}

vector<int>vec[301234];

int main(){

    freopen("running.in","r",stdin);

    freopen("running.out","w",stdout);

    scanf("%d %d",&n,&m);

    for(int i=1,u,v;i<n;i++){

        scanf("%d %d",&u,&v);

        insert(u,v);

    }

    //dfs(1,0);

    for(int i=1;i<=n;i++)scanf("%d",w+i);

    for(int i=1;i<=m;i++)scanf("%d %d",s+i,t+i);

    if(n<=1000){

        for(int i=1;i<=m;i++){

            memset(an,0,sizeof(an));

            dfs2(s[i],t[i],0);

            dfs3(s[i],t[i]);

        }

        for(int i=1;i<=n;i++)printf("%d ",ans[i]);

    }else

    if(n%10==4){

        for(int i=1;i<=n;i++)if(t[i]>=s[i])vec[i].push_back(s[i]);

        for(int i=1;i<=n;i++){

            if(i-w[i]>=0){

                int Ans=vec[i-w[i]].size(),cnt=0;

                for(int x=0;x<Ans;x++){

                    if(t[vec[i-w[i]][x]]<i)cnt++;

                }

                ans[i]+=(Ans-cnt);

            }

        }

        //for(int i=1;i<=n;i++)printf("%d ",ans[i]);

        for(int i=1;i<=n;i++)vec[i].clear();

        for(int i=1;i<=n;i++)if(t[i]<s[i])vec[i].push_back(s[i]);

        for(int i=1;i<=n;i++){

            if(i+w[i]<=n){

                int Ans=vec[i+w[i]].size(),cnt=0;

                //fprintf(stderr,"at %d\n",Ans);

                for(int x=0;x<Ans;x++){

                    if(t[vec[i+w[i]][x]]>i){

                        cnt++;

                    }

                }

                ans[i]+=(Ans-cnt);

            }

        }

        for(int i=1;i<=n;i++)printf("%d ",ans[i]);

    }else {

        for(int i=1;i<=n;i++)siz[t[i]]++;

        dep[1]=0;

        dfs4(1,0);

        for(int i=1;i<=n;i++)printf("%d ",(w[i]==dep[i])*siz[i]);

    }

    return 0;//... //... //...

}

2^n*2^m暴力枚举所有申请和批准情况

暴力64，数组小了不然是72

要特判m<2

#include<map>

#include<cstdio>

#include<string>

#include<vector>

#include<string.h>

#include<iostream>

#include<algorithm>

using namespace std;

int n,m,v,e;

int c[333],d[333];

double k[333];/*

int min(int a,int b){

    return a<b?a:b;

}*/

struct zy{

    int i,cost;

}F[1234];

bool cmp(zy a,zy b){

    return a.cost>b.cost;

}

double brutef(){

    double ans=1e23;

    int _F=0;

    for(int i=1;i<=n;i++){

        int tmp=0;

        if(tmp>1)tmp=tmp+g[c[i-1]][c[i]]-g[c[i-1]][d[i]];

        if(tmp<n)tmp=tmp+g[c[i+1]][c[i]]-g[c[i+1]][d[i]];

        F[++_F]=(zy){i,-tmp};

    }

    sort(F+1,F+_F+1,cmp);

    int q[1234];

    memset(q,0,sizeof(q));

    for(int i=0;i<=m;i++){

        q[F[i].i]=1;double tmp2=0;

        for(int t=1;t<n;t++){

            int a=c[t],b=c[t+1];

            if(q[t])a=d[t];

            if(q[t+1])b=d[t+1];

            tmp2+=g[a][b];

        }

        //cout<<F[i].i<<","<<tmp2<<endl;

        ans=min(ans,tmp2);

    }

    return ans;

}

int main() {

    freopen("classroom.in","r",stdin);

    freopen("classroom.out","w",stdout);

    scanf("%d%d%d%d",&n,&m,&v,&e);

    for(int i=1;i<=n;i++)scanf("%d",c+i);

    for(int i=1;i<=n;i++)scanf("%d",d+i);

    bool xz2=1;

    for(int i=1;i<=n;i++)scanf("%lf",k+i),xz2=xz2&&(k[i]==1.0);

    for(int i=1;i<=v;i++)for(int j=1;j<=v;j++)g[i][j]=(i!=j)*(1<<20);

    for(int i=1;i<=e;i++){

        int a,b,w;

        scanf("%d %d %d",&a,&b,&w);

        g[a][b]=min(g[a][b],w);

        g[b][a]=min(g[b][a],w);

    }

    for(int p=1;p<=v;p++)for(int i=1;i<=v;i++)for(int j=1;j<=v;j++)g[i][j]=min(g[i][j],g[i][p]+g[p][j]);

    if(m<2){

        double ans=0,tmp=0;

        for(int i=1;i<n;i++){

            ans+=(g[c[i]][c[i+1]]);

        }

        tmp=ans;

        if(m)

        for(int x=1;x<=n;x++){

            //cout<<x<<" :\n";

            int res=0;

            for(int i=1;i<n;i++){

                int a=c[i],b=c[i+1];

                if(i==x)a=d[x];

                if(i+1==x)b=d[x];

                res+=g[a][b];

            }

            //cout<<res*k[x]+tmp*(1-k[x])<<endl;

            ans=min(ans,res*k[x]+tmp*(1-k[x]));

        }

        printf("%.2lf",(double)ans);

    }else if(n<=20&&m<=10){

        double ans=1e23;

        for(int i=0;i<(1<<n);i++){

            int p[30],q[33],cnt=0;

            for(int j=1;j<=n;j++)if(i&(1<<(j-1)))q[++cnt]=j;

            if(cnt<=m){

            //cerr<<"safe";

            memset(p,0,sizeof(p));

                double tmp=0;

                for(int j=0;j<(1<<cnt);j++){

                    double prob=1,tmp2=0;

                    for(int t=1;t<=cnt;t++){

                        if(j&(1<<(t-1))){

                            prob=prob*k[q[t]];

                            p[q[t]]=1;

                        }else {

                            prob=prob*(1-k[q[t]]);

                            p[q[t]]=0;

                        }

                    }

                    /*printf("(%d,%d)\n",i,j);

                    for(int t=1;t<=cnt;t++)cout<<q[t]<<"!!";cout<<endl;*/

                    for(int t=1;t<n;t++){

                        int a=c[t],b=c[t+1];

                        if(p[t])a=d[t];

                        if(p[t+1])b=d[t+1];

                        tmp2+=g[a][b];

                    }

                    //cout<<tmp2<<endl;;

                    tmp+=tmp2*prob;

                }

                //cout<<"---"<<tmp<<endl;

                ans=min(ans,tmp);

                }

            }//... 

        printf("%.2lf",(double)ans);

    }else{

        printf("%.2lf",(double)brutef());

    }

}

day2

XBG

#include<cstdio>

#include<algorithm>

#include<iostream>

using namespace std;

int t,k,n,m,c[2333][2333],s[2333][2333];

int main(){

    freopen("problem.in","r",stdin);

    freopen("problem.out","w",stdout);

    scanf("%d%d",&t,&k);

    for(int i=0;i<=2000;i++)c[i][1]=i%k;

    for(int i=1;i<=2000;i++)

        for(int j=2;j<=i;j++)

            c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;

    for(int i=1;i<=2000;i++)

        for(int j=1;j<=2000;j++){

            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+(j<=i)*(!c[i][j]);

        }

    while(t--){

        scanf("%d %d",&n,&m);

        /*for(int i=1;i<=n;i++,puts(""))

            for(int j=1;j<=i;j++)printf("%d ",s[i][j]);

        */printf("%d\n",s[n][m]);

    }

    return 0;

}

拿三个队列，一个存x，一个存px，一个存x-px。

然后这三个队列是单调递减的，具体证明较简单。

#include<queue>

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

int n,m,q,u,v,t;double p;

int a[123456];

int PQ[123456],_PQ,od[7123456];

namespace solution{

    int x[7123456][2],y[7123456][2],z[7123456][2];

    int hx,hy,hz,tx,ty,tz;

    void init(){hx=hy=hz=1;tx=n;ty=tz=0;}

    void debug(int tim){

        for(int i=hx;i<=n;i++)printf("%d ",x[i][0]+q*(tim-x[i][1]));

        printf("!");for(int i=hy;i<=ty;i++)printf("%d ",y[i][0]+q*(tim-y[i][1]));

        printf("!");for(int i=hz;i<=tz;i++)printf("%d ",z[i][0]+q*(tim-z[i][1]));

        printf("!");

        puts("");

    }

    //wo hui zuo d2t2 ei

    void getres(){//debug(m);

        for(int i=1;i<=n+m;i++){

            int c=-12345;int *I;

            if(hx<=n)if(x[hx][0]+q*(m-x[hx][1])>c)c=x[hx][0]+q*(m-x[hx][1]),I=&hx;

            if(hy<=ty)if(y[hy][0]+q*(m-y[hy][1])>c)c=y[hy][0]+q*(m-y[hy][1]),I=&hy;

            if(hz<=tz)if(z[hz][0]+q*(m-z[hz][1])>c)c=z[hz][0]+q*(m-z[hz][1]),I=&hz;

            ++*I;

            if(!(i%t))printf("%d ",c);

        }

    }

    int main(){

        sort(a+1,a+n+1,greater<int>());//nlogn

        for(int i=1;i<=n;i++)x[i][0]=a[i];

        p=u;p/=v;

        init();

        for(int i=1;i<=m;i++){

            int c=-12345;

            int *I;

            if(hx<=n)if(x[hx][0]+q*(i-1-x[hx][1])>c)c=x[hx][0]+q*(i-1-x[hx][1]),I=&hx;

            if(hy<=ty)if(y[hy][0]+q*(i-1-y[hy][1])>c)c=y[hy][0]+q*(i-1-y[hy][1]),I=&hy;

            if(hz<=tz)if(z[hz][0]+q*(i-1-z[hz][1])>c)c=z[hz][0]+q*(i-1-z[hz][1]),I=&hz;

            int A,B;

            A=p*c;

            B=c-A;

            //printf("cut %d into(%d,%d)\n",c,A,B);

            y[++ty][0]=A;

            z[++tz][0]=B;

            z[tz][1]=y[ty][1]=i;

            ++*I;

            od[i]=c;

            //cerr<<"h..="<<hx<<endl;

            //debug(i);

        }

        for(int i=t;i<=m;i+=t)printf("%d ",od[i]);puts("");

        getres();

        return 0;

    }

}

int main(){

    freopen("earthworm.in","r",stdin);

    freopen("earthworm.out","w",stdout);

    //cerr<<sizeof(solution::x)*3;

    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);

    for(int i=1;i<=n;i++)scanf("%d",a+i);

    if(n<=1000&&m<=1000){

        for(int i=1;i<=n;i++)PQ[i]=a[i];_PQ=n;

        for(int _t=1;_t<=m;_t++){

            int mx=1;

            for(int i=2;i<=_PQ;i++)if(PQ[i]>PQ[mx])mx=i;

            int x=PQ[mx];

            PQ[mx]=(int)u*1.0/v*x;

            PQ[++_PQ]=x-PQ[mx];

            //printf("cut %d into(%d,%d)\n",x,PQ[mx],PQ[_PQ]);

            for(int i=1;i<_PQ;i++)if(i!=mx)PQ[i]+=q;

            od[_t]=x;

        }

        for(int i=t;i<=m;i+=t)printf("%d ",od[i]);

        sort(PQ+1,PQ+n+m+1,greater<int>());

        puts("");

        for(int i=t;i<=n+m;i+=t)printf("%d ",PQ[i]);

    }else

        solution::main();

    return 0;

}

枚举两个点作抛物线，预处理能过什么点

状压（即或的值为2^n-1)

注意处理单点，分数未知

~~riio写错了~~

总结：d1t2 d2t3暴力写错了很伤

d2t2很像我之前写的QingdaoRegional的G

最后100+45+64+100+100+?未完待续

巴特西

Noip2016滚粗记QAQ

day1

day2

最新文章

热门文章