19.7.29 NOIP模拟10

话说这次三道考试题直接可以连成一个段子：我一个辣鸡，连模板都不会打，只能跪倒在大佬面前;

T1 辣鸡

但是我实在是太辣鸡了，最后干的T1，时间不够用，连暴力都没打对，无奈之下交了一个qj程序，60分（rp分）

正解？没有正解，正解就是一个大暴力，$ O(n^2) $直接出乎我的意料，这.......我真的是太辣鸡了;

如此暴力的题，本人就懒得沾代码了;

T2 模板

一看题目名，我就知道这道题是最难的，没有办法，只能先留坑，因为我还没改过来呜呜呜　～

UPD:

经过我的一上午的努力，终于70 了，虽然还没有AC但是我先来更一下缓解一下疲劳：

T2首先我们可以想得到的就是一个大暴力，复杂度玄学，所以只有前面的30分;

我是考试时候的代码，30（动用了我会的STL，发现STL真的很好片分）（大佬请自动忽略一下30分方法！）

别人的30分思路都很正常，但是我的30分思路非常奇葩：

首先，建树（恩，没什么特别的，然后开maxn个set和vector）先dfs一遍（我在后期调试时候发现的bug，需要dfs记录一下fa）

然后，利用树上差分的思想，其实就是这个点到1节点，不不用lca，所以吗两上还是很好吗的;

然后，记得给push进去的操作都打上时间戳，然后排序（是不是是非常的暴力？）

把排完序的0（vector里是0）到min（题中要求的大小，vector.size()）insert进set;

这些操作都可以在另一个dfs中实现，所以整个暴力只需要dfs两遍，但是dfs内部的复杂度异常的大;

最后统计答案的时候就输出set.size();

本来dfs里带上dfs的复杂度就不好算，而且带上了STL，反正我是算不出来我打的暴力的复杂度，所以我也不证明复杂度了。

30分代码：

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<cstdlib>

 #include<set>

 #include<algorithm>

 #include<vector>

 using namespace std;

 #define debug(x) cout<<x<<" debug!"<<endl;

 #define LL long long

 #define re register

 const int L=<<|;

 char buffer[L],*S,*T;

 #define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++)

 inline int read(){

     re int a=,b=;char t;

     do{t=getchar();if(t=='-')a=-;}while(t>''||t<'');

     do{b=b*-''+t;t=getchar();}while(t>=''&&t<='');

     return a*b;

 }

 const int maxn=1e6;

 int n,m,tt,q;

 int head[maxn],ver[maxn],nxt[maxn],tot;

 inline void add(re int x,re int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;}

 int vanum[maxn];

 bool vc[maxn],vvc[maxn];

 int fa[maxn];

 struct G{

 int c,t;

 };

 vector<G>d[maxn];

 set<int>w[maxn];

 bool v[maxn];

 int qe=;

 bool cmp(G a,G b){return a.t<b.t;}

 void dfsz(re int x)

 {

     vc[x]=;

     for(re int i=head[x];i;i=nxt[i])

     {

         re int y=ver[i];

         if(vc[y])continue;

         fa[y]=x;

         dfsz(y);

     }

 }

 void dfs(re int x)

 {

     v[x]=;

     for(re int i=head[x];i;i=nxt[i])

     {

         re int y=ver[i];

         if(v[y]||y==fa[x])continue;

         dfs(y);

         for(re int j=;j<d[y].size();j++)

             d[x].push_back(d[y][j]);

         sort(d[y].begin(),d[y].end(),cmp);

         for(re int k=;k<min(vanum[y],(int)d[y].size());k++)

             w[y].insert(d[y][k].c);

     }

 }

 void dfs2(int x)

 {

     vvc[x]=;

     for(int i=head[x];i;i=nxt[i])

     {

         int y=ver[i];

         if(vvc[y]||y==fa[x])continue;

         dfs2(y);

         for(set<int>::iterator it =w[y].begin();it!=w[y].end();it++)

             w[x].insert(*it);

     }

 }

 void qjj()

 {

     re int ca,col;

     m=read();

     for(re int i=;i<=m;i++)

     {

         ca=read(),col=read();

         w[ca].insert(col);

     }

     dfs2();

     q=read();

     re int xi=;

     for(re int i=;i<=q;i++)

     {

         xi=read();

         printf("%d\n",w[xi].size());

     }

 }

 int main()

 {

     //freopen("T2.txt","r",stdin);

     n=read();

     int u,v;

     for(re int i=;i<=n-;i++)

     {

         u=read(),v=read();

         add(u,v),add(v,u);

     }

     dfsz();

     for(re int i=;i<=n;i++)

     vanum[i]=read();

     m=read();

     re int ca,col;

     for(re int i=;i<=m;i++)

     {

         ca=read(),col=read();

         G ooo;

         ooo=(G){col,++tt};

         d[ca].push_back(ooo);

     }

     q=read();

     re int xi=;

     dfs();

     sort(d[].begin(),d[].end(),cmp);

     for(re int k=;k<min(vanum[],(int)d[].size());k++)

         w[].insert(d[][k].c);

     for(re int i=;i<=q;i++)

     {

         xi=read();

         printf("%d\n",w[xi].size());

     }

 }

然后，我就开始了漫漫优化路，整个我先是把我的STL想办法替换掉，当然我的set是去不掉的（我有不会打红黑树）所以我还是T

但是，我忽然发现，我考试的时候没有看数据范围（我真晕！）所以我没有看见k==1e5的情况;

其实按照我的qj技术，把这些点qj掉是可以的，所以，我就挂着我上面的暴力把程序交到70分，然后看了，某丁的线段树合并，才知道我里整洁其实很远，（其实是沉迷STL函数无法自拔），然后找丁丁学习了一下，总算是打出了类似正解的程序，（其实也是qj），特别感谢moudinggg，所以，不要沉迷与自己的错解，有时这样会使你离正解越来越远;

具体的就是线段树合并，类似与之前的雨天的尾巴那道题，但是仔细一看就知道有很大的不同，其实就是线段树合并的思想;

70分代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<set>

 #include<cmath>

 using namespace std;

 #define re register

 #define LL long long

 const LL maxn=(int)(4e5+)*;

 inline LL read()

 {

     re LL a=,b=;char t;

     do{t=getchar();if(t=='-')a=-;}while(t>''||t<'');

     do{b=b*-''+t;t=getchar();}while(t>=''&&t<='');

     return a*b;

 }

 set<LL>st[maxn];

 LL head[maxn],ver[maxn],vvt[maxn],nxt[maxn];

 LL n,m,q,tot,tm[maxn],vanum[maxn],col[maxn],d[maxn],ans[maxn];

 vector<LL>tw[];

 LL col1[][],fa[maxn],colll[maxn],pos[maxn],b[maxn];

 LL rt[maxn],sum[maxn],L[maxn],R[maxn],ls[maxn],rs[maxn],W[maxn],cnt;

 inline void add(LL x,LL y){vvt[++tot]=x;ver[tot]=y;nxt[tot]=head[x];head[x]=tot;}

 bool v1[maxn],v2[maxn];

 void dfs1(LL x)

 {

     v1[x]=;

     for(LL i=head[x];i;i=nxt[i])

     {

         LL y=ver[i];

         if(v1[y])continue;

         fa[y]=x;

         dfs1(y);

     }

 }

 void build(LL &rt,LL l,LL r,LL w)

 {

     if(!rt)

     {

         rt=++cnt;

         L[rt]=l;

         R[rt]=r;

     }

     LL mid=l+r>>;

     if(l==r)

     {

         if(sum[rt]==)return ;

         else

         {

             sum[rt]=;

             W[rt]=w;

             return ;

         }

     }

     if(w<=mid) build(ls[rt],l,mid,w);

     else build(rs[rt],mid+,r,w);

     sum[rt]=sum[ls[rt]]+sum[rs[rt]];

 }

 LL merge(LL x,LL y)

 {

     if(!x||!y)return x+y;

     if(L[x]==R[x]&&L[x]==L[y]&&R[x]==R[y])return x;

     ls[x]=merge(ls[x],ls[y]);

     rs[x]=merge(rs[x],rs[y]);

     sum[x]=sum[ls[x]]+sum[rs[x]];

     return x;

 }

 void dfs2(LL x)

 {

     v2[x]=;

     for(LL i=head[x];i;i=nxt[i])

     {

         LL y=ver[i];

         if(v2[y])continue;

         dfs2(y);

         rt[x]=merge(rt[x],rt[y]);

     }

     ans[x]=sum[rt[x]];

 }

 int main()

 {

     //freopen("simple2.txt","r",stdin);

     n=read();

     for(LL i=,x,y;i<n;i++)

         x=read(),y=read(),add(x,y),add(y,x);

     for(LL i=;i<=n;i++) scanf("%lld",&vanum[i]);

     m=read();

     dfs1();

     for(LL i=,x,y;i<=m;i++) pos[i]=read(),colll[i]=read(),b[i]=colll[i];

     sort(b+,b++m);

     LL sz=unique(b+,b+m+)-b-;

     for(LL i=;i<=m;i++) colll[i]=lower_bound(b+,b+sz+,colll[i])-b;

     if(n<=1e3&&m<=1e3)

     {

         for(LL i=;i<=m;i++)

         {

             LL x=pos[i],y=colll[i];

             while(x)

             {

                 if(!col1[x][y]&&ans[x]<vanum[x]) ans[x]++;

                 else if(vanum[x]>ans[x]) vanum[x]--;

                 col1[x][y]=;

                 x=fa[x];

             }

         }

         q=read();

         for(LL i=,x;i<=q;i++)

         {

             x=read();

             printf("%lld\n",ans[x]);

         }

         return ;

     }

     for(LL i=,x,y;i<=m;i++)

         build(rt[pos[i]],,sz,colll[i]);

     dfs2();

     q=read();

     for(LL i=,x;i<=q;i++)

     {

         x=read();

         printf("%lld\n",ans[x]);

     }

 }

30号上午就先更到这，我的坑还没填完，等我改AC在更！

UPD:我终于把这道题该过去了，说实话，这道题是非常的坑*;

就我之前提到的70分代码，能不能改到100呢？反正我是没有改到，然后只是利用了70分代码里线段树合并的思想，（但是这里是启发式合并），关于启发式合并，我记得sk学长好像在之前讲树套树的时候讲到过，当时一脸蒙蔽，完全不知道在干啥，现在终于知道了，其实就是暴力的把小的那颗线段树里的节点往另一棵里插，注意一定是小的往大的里插，这样才能有卓越的复杂度，然后，利用树链剖分的思想，其实就是利用了树链剖分里重儿子的概念，然后在合并（启发是合并，这里及后文简称合并）过程中只保留重儿子，而且轻儿子清空，这样就保证不会TLE，有些dalao一只TLE30左右，应该就是清掉了重儿子。总而言之，这道题很毒瘤，也然我看到了自己有很多的不足，我其实还是T2颓了代码，不然我是真的想不到正解，包括就像网上那个说的，要是NOIP六道题都是这个难度的，我还是滚回去文化课吧。（尽力不滚回去！）

我就把我颓的std放上来吧，我写了注释，不过应该是对的，不对的话就在评论区告诉我吧！

 //注释解释2019.7.29 T2模板

 //仅是本人自我理解;

 //copyright by zzyy;

 //注释创建者:lsc

 //powered by lsc;

 //----------------------*

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<map>

 #include<vector>

 #define maxn 401000

 using namespace std;

 int m,n,k,tot,first[maxn],w[maxn],ans[maxn],q,siz[maxn],color,son[maxn],t[maxn];

 int data[maxn*],tsiz[maxn*],lazy[maxn*];

 vector<int>bel[maxn],dr[maxn];

 map<int,int>judge;

 struct node{int to,next;}a[maxn*];

 inline void add(int x,int y){a[++tot]=(node){y,first[x]};first[x]=tot;}

 inline void pushdown(int x)//懒标记下放

 {

     if(lazy[x]==) return;

     lazy[x<<]=lazy[x<<|]=;

     lazy[x]=data[x<<]=data[x<<|]=tsiz[x<<]=tsiz[x<<|]=;

 }

 inline void pushup(int x)//信息上传

 {

     data[x]=data[x<<]+data[x<<|];

     tsiz[x]=tsiz[x<<]+tsiz[x<<|];

 }

 inline void update(int x,int l,int r,int val,int derta,int sum)//权值线段树的更新答案操作

 {

     data[x]+=derta,tsiz[x]+=sum;

     if(l==r) return ;

     int mid=(l+r)>>;

     pushdown(x);

     if(val<=mid) update(x<<,l,mid,val,derta,sum);

     else         update(x<<|,mid+,r,val,derta,sum);

     pushup(x);

 }

 inline int query(int x,int l,int r,int sum)//单点查询键值小于sum的值的个数;

 {

     if(sum<=) return ;

     if(l==r)   return data[x];

     int mid=(l+r)>>;

     pushdown(x);

     if(tsiz[x<<]<=sum)

         return data[x<<]+query(x<<|,mid+,r,sum-tsiz[x<<]);

     else

         return query(x<<,l,mid,sum);

 }

 inline void init_tim(int x)//打标记

 {

     data[]=siz[]=, lazy[]=;

     for(register int i=;i<bel[x].size();++i) t[bel[x][i]]=;//t是一个桶，保存键值的个数

 }

 inline void init_tree(int x)        //把x节点的操作插入到权值线段树中

 {

     for(register int i=;i<bel[x].size();++i)

     {

         int col=bel[x][i], tim=dr[x][i];

         if(!t[col]) update(,,m,tim,,),t[col]=tim;

         else if(t[col]>tim)

         {

             update(,,m,t[col],-,);

             update(,,m,tim,,);

             t[col]=tim;

         }

         update(,,m,tim,,);

     }

 }

 inline void insert(int x,int y)            //将y插入到x中，就是启发式合并

 {

     for(register int i=;i<bel[y].size();++i)

         bel[x].push_back(bel[y][i]),dr[x].push_back(dr[y][i]);

     bel[y].clear(), dr[y].clear();

 }

 inline void dfs_pre(int x,int dad)        //树链剖分

 {

     siz[x]=bel[x].size();

     for(register int i=first[x];i;i=a[i].next)

     {

         int to=a[i].to;

         if(to==dad) continue;

         dfs_pre(to,x); siz[x]+=siz[to];

         if(siz[son[x]]<siz[to]) son[x]=to;

     }

 }

 inline void dfs(int x,int dad)

 {

     for(register int i=first[x];i;i=a[i].next)

     {

         int to=a[i].to;

         if(son[x]==to||to==dad) continue;

         dfs(to,x);

         init_tim(to);

     }

     if(son[x]) dfs(son[x],x);

         init_tree(x);

     for(register int i=first[x];i;i=a[i].next)

     {

         int to=a[i].to;

         if(to==dad||to==son[x]) continue;

         init_tree(to);

     }

     ans[x]=query(,,m,w[x]);

     if(son[x])

     {

         insert(son[x],x);

         swap(bel[son[x]],bel[x]); swap(dr[son[x]],dr[x]);

         for(register int i=first[x];i;i=a[i].next)

         {

             int to=a[i].to;

             if(to==dad) continue;

             insert(x,to);

         }

     }

 }

 int main()

 {

     freopen("simple1.txt","r",stdin);

     scanf("%d",&n);

     for(register int i=,x,y;i<n;++i)

         scanf("%d%d",&x,&y), add(x,y),add(y,x);        //树建边

     for(register int i=;i<=n;++i)

         scanf("%d",&w[i]);                //限制条件

     scanf("%d",&m);

     for(register int i=,x,y;i<=m;++i)

     {

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

         if(!judge[y]) judge[y]=++color;        //将颜色种类离散化

         y=judge[y];//现在的y是离散化之后的y;

         bel[x].push_back(y), dr[x].push_back(i);//bel存的是颜色，dr存的是时间戳;

     }

     siz[]=-;

     dfs_pre(,);

     dfs(,);

     scanf("%d",&q);

     for(register int i=,x;i<=q;++i)

         scanf("%d",&x), printf("%d\n",ans[x]);

 }

100

T3 大佬

其实这道题考场上思路就接近正解，就发现一些考试的时候我会出现思路的瓶颈，然后其实再想一点点就可以出正解，然后，这道题就炸了，

T3题解里给了一堆扯*玩意，所以我不按题解说：

总的方案数就是$ m^k $然后这个数做分子（记得逆元）然后枚举最大的点数（劳累值)进行运算，（这部就是我的考试思路啊！）对于每一个

最大的劳累值，我们知道这可能的方案数是 $ i^k $然而其中存在不合法的方案数，即$ (i-1)^k $（可以想一想，这很好想）然后

$ (i^k-(i-1)^k)/(m^k) $就是最大劳累值是i的时候的概率，乘以w的映射值就是期望，这n-k+1天的情况都是一样的（由于难度是随机的，所以这些天都是一样的）那么$ ans=\sum((i^k-(i-1)^k)/(m^k)*w[i])*(n-k+1) $

然后这道题有一个测试点是k>n的情况，然后特判一下，你就愉快的收获了100分的好成绩（逃）

T1 T3比较简单，不沾代码！

这次考试我也是见证了rp的作用，就是qj都能拿到高分，其实我的qj第一次交的时候只有20分，当时我就只qj了第一个测试点和第二个测试点，后来我就想，反正也是qj就直接else一下printf一下累计和ans，本着反正能骗到就骗，骗不到拉到的心态加了一个else，然后出乎意料的是T1分数仅次于正解，但是仔细看解法和正解半毛钱关系没有，所以这次可能是rp在发挥作用，然后我也仔细想了一下，这次只是运气好，但是我并不能保证自己NOIP的时候运气好，难道没有技术，光指望qj就能拿省一？就能进省队？不存在的！所以还是要努力的提升自己的技术，用实力去换来幸运，这可能就是我从这次考试获得的启示吧！

巴特西

19.7.29 NOIP模拟10

最新文章

热门文章