NOIP2016总结

Day1：

T1：模拟；

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<string>

 #include<ctime>

 #include<cmath>

 #include<set>

 #include<map>

 #include<queue>

 #include<algorithm>

 #include<iomanip>

 using namespace std;

 #define FILE "toy"

 #define up(i,j,n) for(int i=(j);i<=(n);i++)

 #define pii pair<int,int>

 #define LL long long

 namespace IO{

     char buf[<<],*fs,*ft;

     int gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?-:*fs++;}

     int read(){

         int ch=gc(),f=,x=;

         while(ch<''||ch>''){if(ch=='-')f=;ch=gc();}

         while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=gc();}

         return f?-x:x;

     }

 }using namespace IO;

 const int maxn=;

 int n,m;

 int a[maxn];

 char s[maxn][];

 int main(){

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

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

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

     up(i,,n-)scanf("%d %s",&a[i],s[i]);

     int x,y,now=;

     up(i,,m){

         scanf("%d%d",&x,&y);

         if(x==a[now])now=(now-y+n)%n;

         else now=(now+y)%n;

     }

     printf("%s",s[now]);

     return ;

 }

T2:

这次noip2016最难的题？

考场上只急着打暴力了，没有好好思考；

实际上想了之后还是很简单的；

这题的关键是理清思路，题目上的特点是 若一条路径已走的时间若与当前节点的值相等，这一点的答案加1；

最暴力的思路当然是dfs Q遍，先判断这个点是否在这条路径上，然后判断已走的距离是不是等于当前点的权值，都符合的话ans++；

如何化简条件？

我们可以发现当若有一条从x->y的路径是一条链，且dep[x]<dep[y]，则若dep[i]-dep[x]=v[i]，则该点ans++；

这可以变形成dep[i]-v[i]=dep[x]，左边只与点i自身有关；

经过了这样的转化，我们发现可以这样做，将一个路径拆成从x->lca和lca->y两个链，然后可以仿照上面的方法，用dep与v[i]的关系做。

但做到了这一步仍然没什么卵用；

我们是否可以把目光转移，从看一条路径到看每个点？

对每个点而言，我们需要计算的是，它自身dep[i]±v[i]正好匹配经过它的路径所要求的的值的路径的数目；

这很绕，实际上对路径只有两个要求，第一个是经过它，第二个是路径与这个点可以匹配；

怎么维护？

第一个，维护只经过它的路径的值的集合；

第二个，在集合中快速找到符合要求的值的数目；

满足这两个要求，第一个可以用离线的方法维护，第二个可以在dfs的途中顺便维护一个桶，这个桶里存的就是经过它的路径的值的集合，然后可以O(1)查询；

这里面还有一个地方需要注意，每次桶从一颗子树出来的时候会带着这颗子树的信息，再进入另一个桶的时候会出现问题，解决方案是作差，先记录一下当前的ans值，待遍历完所有子树，再记录一下当前的ans，两个的差值即为所求；

在大佬眼里就是道水题...

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<string>

 #include<ctime>

 #include<cmath>

 #include<set>

 #include<map>

 #include<queue>

 #include<algorithm>

 #include<iomanip>

 #include<queue>

 using namespace std;

 #define FILE "dealing"

 #define up(i,j,n) for(int i=(j);i<=(n);i++)

 #define pii pair<int,int>

 #define LL long long

 namespace IO{

     char buf[<<],*fs,*ft;

     int gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?-:*fs++;}

     int read(){

         int ch=gc(),f=,x=;

         while(ch<''||ch>''){if(ch=='-')f=;ch=gc();}

         while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=gc();}

         return f?-x:x;

     }

 }using namespace IO;

 const int maxn=;

 int n,m;

 struct node{

     int y,next,v;

 }e[maxn],u[maxn],v[maxn],q[maxn];

 int headu[maxn],headv[maxn],headq[maxn],lenu,lenv,lenq;

 int linkk[maxn],len=;

 int s[maxn],t[maxn],w[maxn];

 inline void insert(int x,int y,node* e,int* linkk,int& len,int v){e[++len].y=y;e[len].v=v;e[len].next=linkk[x];linkk[x]=len;}

 int top[maxn],siz[maxn],son[maxn],fa[maxn],dep[maxn],Lca[maxn],dfs_clock=;

 int f[maxn],flag[maxn];

 int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}

 int pre[maxn],low[maxn],id[maxn];

 void tarjan(int x){

     siz[x]=;

     pre[x]=++dfs_clock;

     id[dfs_clock]=x;

     flag[x]=;

     for(int i=linkk[x];i;i=e[i].next){

         if(e[i].y==fa[x])continue;

         fa[e[i].y]=x;

         dep[e[i].y]=dep[x]+;

         tarjan(e[i].y);

     }

     for(int i=headq[x];i;i=q[i].next){

         if(Lca[q[i].v])continue;

         if(flag[q[i].y]==)Lca[q[i].v]=q[i].y;

         else if(flag[q[i].y]==)Lca[q[i].v]=getf(q[i].y);

     }

     f[x]=fa[x];

     flag[x]=;

     low[x]=++dfs_clock;

     id[dfs_clock]=x;

 }

 void init(){

     n=read(),m=read();

     int x,y;

     up(i,,n-){x=read(),y=read();insert(x,y,e,linkk,len,);insert(y,x,e,linkk,len,);}

     up(i,,n)w[i]=read();

     up(i,,m){

         s[i]=read(),t[i]=read();

         insert(s[i],t[i],q,headq,lenq,i);

         insert(t[i],s[i],q,headq,lenq,i);

     }

     up(i,,n)f[i]=i;

     tarjan();

 }

 inline void make_tag(int s,int t,int st,bool flag){

     if(flag){

         insert(s,st,u,headu,lenu,);

         insert(t,st,u,headu,lenu,-);

     }

     else {

         insert(s,st,v,headv,lenv,);

         insert(t,st,v,headv,lenv,-);

     }

 }

 int ans[maxn];

 int cnt1[maxn<<],cnt2[maxn<<];

 int l[maxn];

 void slove(){

     up(i,,m){

         if(Lca[i]==s[i])make_tag(fa[s[i]],t[i],dep[s[i]],);

         else if(Lca[i]==t[i])make_tag(s[i],fa[t[i]],dep[s[i]],);

         else {

             make_tag(s[i],fa[Lca[i]],dep[s[i]],);

             make_tag(Lca[i],t[i],*dep[Lca[i]]-dep[s[i]],);

         }

     }

     memset(flag,,sizeof(flag));

     int x;

     for(int i=;i<=dfs_clock;i++){

         x=id[i];

         if(flag[x]){

             for(int i=headu[x];i;i=u[i].next){

                 if(u[i].v==-)cnt1[u[i].y+maxn]--;

                 else cnt1[u[i].y+maxn]++;

             }

             for(int i=headv[x];i;i=v[i].next){

                 if(v[i].v==)cnt2[v[i].y+maxn]--;

                 else cnt2[v[i].y+maxn]++;

             }

             ans[x]=cnt1[dep[x]+w[x]+maxn]+cnt2[dep[x]-w[x]+maxn]-l[x];

         }

         else {

             l[x]=cnt1[dep[x]+w[x]+maxn]+cnt2[dep[x]-w[x]+maxn];

             flag[x]=;

         }

     }

     up(i,,n)printf("%d%c",ans[i],i==n?'\n':' ');

 }

 int main(){

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

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

     init();

     slove();

     return ;

 }

顺便进行了一下求lca的速度测试：

只求LCA的话，树链剖分最快，tarjan次之，倍增最慢（经常被卡）；

还需要一些附加信息的话，tarjan无法处理，树链剖分效率很好，倍增效率太低；

代码长度上，树链剖分最长，lca次之，tarjan最短；

如果考场上只求lca的话，建议tarjan，很好写；

T3：

无力吐槽，这题让一心一意备考noip的人怎么受得了；

概率dp；

把概率扒下来其实就是一背包动规；

具体的还是自己去体会(看代码)......

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<string>

 #include<ctime>

 #include<cmath>

 #include<set>

 #include<map>

 #include<queue>

 #include<algorithm>

 #include<iomanip>

 #include<queue>

 using namespace std;

 #define FILE "dealing"

 #define up(i,j,n) for(int i=(j);i<=(n);i++)

 #define pii pair<int,int>

 #define LL long long

 #define db double

 namespace IO{

     char buf[<<],*fs,*ft;

     int gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?-:*fs++;}

     int read(){

         int ch=gc(),f=,x=;

         while(ch<''||ch>''){if(ch=='-')f=;ch=gc();}

         while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=gc();}

         return f?-x:x;

     }

 }using namespace IO;

 const int maxn=;

 const db inf=100000000.0;

 int n,m,v,e,a[maxn],b[maxn];

 db k[maxn];

 int d[maxn][maxn];

 void init(){

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

     memset(d,,sizeof(d));

     up(i,,v)d[i][i]=;

     up(i,,n)scanf("%d",&a[i]);

     up(i,,n)scanf("%d",&b[i]);

     up(i,,n)scanf("%lf",&k[i]);

     int x,y,vv;

     up(i,,e){

         scanf("%d%d%d",&x,&y,&vv);

         if(d[x][y]>vv)d[x][y]=d[y][x]=vv;

     }

     up(g,,v)up(i,,v)up(j,,v)if(d[i][g]+d[g][j]<d[i][j])d[i][j]=d[i][g]+d[g][j];

 }

 db f[][][];

 void slove(){

     up(i,,n)up(j,,m)f[i][j][]=f[i][j][]=inf;

     f[][][]=f[][][]=;

     db duu,duv,dvu,dvv,ans=inf;

     up(i,,n)for(int j=;j<=i&&j<=m;j++){

         duu=d[a[i-]][a[i]],duv=d[a[i-]][b[i]],dvu=d[b[i-]][a[i]],dvv=d[b[i-]][b[i]];

         if(j!=i)f[i][j][]=min(f[i-][j][]+duu*(-k[i-])+dvu*k[i-],duu+f[i-][j][]);

         if(j)f[i][j][]=min(f[i-][j-][]+duu*(-k[i-])*(-k[i])+duv*(-k[i-])*k[i]+dvv*k[i]*k[i-]+dvu*k[i-]*(-k[i]),f[i-][j-][]+duv*k[i]+duu*(-k[i]));

     }

     for(int i=;i<=m;i++)ans=min(ans,min(f[n][i][],f[n][i][]));

     printf("%.2lf\n",ans);

 }

 int main(){

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

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

     init();

     slove();

     return ;

 }

Day2:

T1:

组合数，考场脑子一抽写了二维树状数组，但实际也没什么问题（实际这题的二维动规是有一定的风险的，有人因此挂了）；

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<string>

 #include<ctime>

 #include<cmath>

 #include<set>

 #include<map>

 #include<queue>

 #include<algorithm>

 #include<iomanip>

 using namespace std;

 #define FILE "problem"

 #define up(i,j,n) for(int i=(j);i<=(n);i++)

 #define pii pair<int,int>

 #define LL long long

 namespace IO{

     char buf[<<],*fs,*ft;

     int gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?-:*fs++;}

     int read(){

         int ch=gc(),f=,x=;

         while(ch<''||ch>''){if(ch=='-')f=;ch=gc();}

         while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=gc();}

         return f?-x:x;

     }

 }using namespace IO;

 const int maxn=,N=;

 int c[maxn][maxn];

 int sum[maxn][maxn];

 int T,k,n,m;

 int main(){

     //freopen(FILE".in","r",stdin);

     //freopen(FILE".out","w",stdout);

     T=read(),k=read();

     c[][]=;

     up(i,,N){

         c[i][]=;

         up(j,,i){

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

             sum[i][j]=sum[i-][j]+sum[i][j-]-sum[i-][j-]+(c[i][j]==?:);

         }

         up(j,i+,N)sum[i][j]=sum[i-][j]+sum[i][j-]-sum[i-][j-];

     }

     while(T--){

         n=read(),m=read();

         if(m>n)m=n;

         printf("%d\n",sum[n][m]);

     }

     return ;

 }

T2:

数学题目，需要证一下单调性（求个导如何？）

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<string>

 #include<ctime>

 #include<cmath>

 #include<set>

 #include<map>

 #include<queue>

 #include<algorithm>

 #include<iomanip>

 using namespace std;

 #define FILE "earthworm"

 #define up(i,j,n) for(int i=(j);i<=(n);i++)

 #define pii pair<int,int>

 #define LL long long

 namespace IO{

     char buf[<<],*fs,*ft;

     int gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?-:*fs++;}

     int read(){

         int ch=gc(),f=,x=;

         while(ch<''||ch>''){if(ch=='-')f=;ch=gc();}

         while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=gc();}

         return f?-x:x;

     }

 }using namespace IO;

 const int maxn=;

 const double E=0.0000001;

 int a[maxn],b[maxn],c[maxn];

 int ha,hb,hc,tb=,tc=;

 int n,m,u,v,t,q,d;

 LL pop(){

     int L;

     if(ha&&(a[ha]>=b[tb]||tb>hb)&&(a[ha]>=c[tc]||tc>hc))L=a[ha],ha--;

     else if(tb<=hb&&(b[tb]>=a[ha]||!ha)&&(b[tb]>=c[tc]||tc>hc))L=b[tb],tb++;

     else L=c[tc],tc++;

     return L;

 }

 int main(){

     n=read(),m=read(),q=read(),u=read(),v=read(),t=read();

     up(i,,n)a[i]=read();

     sort(a+,a+n+);

     ha=n;

     LL L,top=;

     up(i,,m){

         L=pop()+d;

         d+=q;

         if(top*t==i){printf("%lld ",L);top++;}

         b[++hb]=(int)(L*u/v)-d;

         c[++hc]=L-b[hb]-*d;

     }

     cout<<endl;

     top=;

     up(i,,m+n){

         L=pop();

         if(t*top==i){printf("%lld ",L+d);top++;}

     }

     return ;

 }

T3：

惭愧惭愧，考场不假思索，先打暴力......

后改记忆化，本质上都是状压dp；

吐槽的是，我同学写正解都被卡了一个n，而我写dfs，没有被卡掉......

实质上dfs会避免访问很多不可能出现的状态，所以效率比较高；

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<string>

 #include<ctime>

 #include<cmath>

 #include<set>

 #include<map>

 #include<queue>

 #include<algorithm>

 #include<iomanip>

 using namespace std;

 #define FILE "angrybirds"

 #define up(i,j,n) for(int i=(j);i<=(n);i++)

 #define pii pair<int,int>

 #define LL long long

 #define pdd pair<double,double>

 namespace IO{

     char buf[<<],*fs,*ft;

     int gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?-:*fs++;}

     int read(){

         int ch=gc(),f=,x=;

         while(ch<''||ch>''){if(ch=='-')f=;ch=gc();}

         while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=gc();}

         return f?-x:x;

     }

 }using namespace IO;

 inline bool chkmin(int &a,int b){return a>b?a=b,true:false;}

 inline bool chkmax(int &a,int b){return a<b?a=b,true:false;}

 const int maxn=,N=;

 const double E=0.00000001;

 int T,n,m;

 int ans;

 double x[maxn],y[maxn];

 inline bool c(double x,double y){return abs(x-y)<=E;}

 inline pdd slove(double q,double w,double e,double r){

     pdd dui;

     if(c(q,e))return make_pair(,);

     dui.first=(w*e-q*r)/(q*e*(q-e));

     if(dui.first+E>=)return make_pair(,);

     dui.second=(w*e-dui.first*q*q*e)/(q*e);

     return dui;

 }

 int f[];

 int dfs(int top,int vis){

     if(f[vis]!=-)return f[vis];

     if(top==n+)return f[vis]=;

     if((<<top-)&vis)return f[vis]=dfs(top+,vis);

     pdd p;

     f[vis]=n;

     int q=vis;

     up(i,top+,n){

         vis=q;

         if(!((<<i-)&vis)){

             p=slove(x[top],y[top],x[i],y[i]);

             if(!p.first)continue;

             vis=vis^(<<top-);

             vis=vis^(<<i-);

             up(j,top+,n){

                 if(vis&(<<j-))continue;

                 if(c(p.first*x[j]*x[j]+p.second*x[j],y[j]))vis=vis^(<<j-);

             }

             chkmin(f[q],dfs(top+,vis)+);

         }

     }

     vis=q;

     chkmin(f[vis],dfs(top+,vis^(<<top-))+);

     return f[vis];

 }

 int main(){

     //freopen(FILE".in","r",stdin);

     //freopen(FILE".out","w",stdout);

     scanf("%d",&T);

     while(T--){

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

         up(i,,n)scanf("%lf%lf",&x[i],&y[i]);

         if(!m||m==)ans=n;

         if(m==)ans=(n%)?(n/+):(n/+);

         memset(f,-,sizeof(f));

         cout<<dfs(,)<<endl;

     }

     return ;

 }

巴特西

NOIP2016总结

最新文章

热门文章