19.7.29 NOIP模拟10

时间:2022-12-17 10:44:21

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

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分代码:

 

19.7.29 NOIP模拟1019.7.29 NOIP模拟10
  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<cmath>
  5 #include<cstdlib>
  6 #include<set>
  7 #include<algorithm>
  8 #include<vector>
  9 using namespace std;
 10 #define debug(x) cout<<x<<" debug!"<<endl;
 11 #define LL long long
 12 #define re register
 13 const int L=1<<20|1;
 14 char buffer[L],*S,*T;
 15 #define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++)
 16 inline int read(){
 17     re int a=1,b=0;char t;
 18     do{t=getchar();if(t=='-')a=-1;}while(t>'9'||t<'0');
 19     do{b=b*10-'0'+t;t=getchar();}while(t>='0'&&t<='9');
 20     return a*b;
 21 }
 22 const int maxn=1e6;
 23 int n,m,tt,q;
 24 int head[maxn],ver[maxn],nxt[maxn],tot;
 25 inline void add(re int x,re int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;}
 26 int vanum[maxn];
 27 bool vc[maxn],vvc[maxn];
 28 int fa[maxn];
 29 struct G{
 30 int c,t;
 31 };
 32 vector<G>d[maxn];
 33 set<int>w[maxn];
 34 bool v[maxn];
 35 int qe=0;
 36 bool cmp(G a,G b){return a.t<b.t;}
 37 void dfsz(re int x)
 38 {
 39     vc[x]=1;
 40     for(re int i=head[x];i;i=nxt[i])
 41     {
 42         re int y=ver[i];
 43         if(vc[y])continue;
 44         fa[y]=x;
 45         dfsz(y);
 46     }
 47 }
 48 void dfs(re int x)
 49 {
 50     v[x]=1;
 51     for(re int i=head[x];i;i=nxt[i])
 52     {
 53         re int y=ver[i];
 54         if(v[y]||y==fa[x])continue;
 55         dfs(y);
 56         for(re int j=0;j<d[y].size();j++)
 57             d[x].push_back(d[y][j]);
 58         sort(d[y].begin(),d[y].end(),cmp);
 59         for(re int k=0;k<min(vanum[y],(int)d[y].size());k++)
 60             w[y].insert(d[y][k].c);
 61     }
 62 }
 63 void dfs2(int x)
 64 {
 65     vvc[x]=1;
 66     for(int i=head[x];i;i=nxt[i])
 67     {
 68         int y=ver[i];
 69         if(vvc[y]||y==fa[x])continue;
 70         dfs2(y);
 71         for(set<int>::iterator it =w[y].begin();it!=w[y].end();it++)
 72             w[x].insert(*it);
 73     }
 74 }
 75 void qjj()
 76 {
 77     re int ca,col;
 78     m=read();
 79     for(re int i=1;i<=m;i++)
 80     {
 81         ca=read(),col=read();
 82         w[ca].insert(col);
 83     }
 84     dfs2(1);
 85     q=read();
 86     re int xi=0;
 87     for(re int i=1;i<=q;i++)
 88     {    
 89         xi=read();
 90         printf("%d\n",w[xi].size());
 91     }
 92 }
 93 int main()
 94 {
 95     //freopen("T2.txt","r",stdin);
 96     n=read();
 97     int u,v;
 98     for(re int i=1;i<=n-1;i++)
 99     {
100         u=read(),v=read();
101         add(u,v),add(v,u);
102     }
103     dfsz(1);
104     for(re int i=1;i<=n;i++)
105     vanum[i]=read();
106     m=read();
107     re int ca,col;
108     for(re int i=1;i<=m;i++)
109     {
110         ca=read(),col=read();
111         G ooo;
112         ooo=(G){col,++tt};
113         d[ca].push_back(ooo);
114     }
115     q=read();
116     re int xi=0;
117     dfs(1);
118     sort(d[1].begin(),d[1].end(),cmp);
119     for(re int k=0;k<min(vanum[1],(int)d[1].size());k++)
120         w[1].insert(d[1][k].c);
121     for(re int i=1;i<=q;i++)
122     {    
123         xi=read();
124         printf("%d\n",w[xi].size());
125     }
126 }
30

 

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

但是,我忽然发现,我考试的时候没有看数据范围(我真晕!)所以我没有看见k==1e5的情况;

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

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

70分代码:

19.7.29 NOIP模拟1019.7.29 NOIP模拟10
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<vector>
  6 #include<set>
  7 #include<cmath>
  8 using namespace std;
  9 #define re register
 10 #define LL long long
 11 const LL maxn=(int)(4e5+10)*4;
 12 inline LL read()
 13 {
 14     re LL a=1,b=0;char t;
 15     do{t=getchar();if(t=='-')a=-1;}while(t>'9'||t<'0');
 16     do{b=b*10-'0'+t;t=getchar();}while(t>='0'&&t<='9');
 17     return a*b;
 18 }
 19 set<LL>st[maxn];
 20 LL head[maxn],ver[maxn],vvt[maxn],nxt[maxn];
 21 LL n,m,q,tot,tm[maxn],vanum[maxn],col[maxn],d[maxn],ans[maxn];
 22 vector<LL>tw[1010];
 23 LL col1[1010][1010],fa[maxn],colll[maxn],pos[maxn],b[maxn];
 24 LL rt[maxn],sum[maxn],L[maxn],R[maxn],ls[maxn],rs[maxn],W[maxn],cnt;
 25 inline void add(LL x,LL y){vvt[++tot]=x;ver[tot]=y;nxt[tot]=head[x];head[x]=tot;}
 26 bool v1[maxn],v2[maxn];
 27 void dfs1(LL x)
 28 {    
 29     v1[x]=1;
 30     for(LL i=head[x];i;i=nxt[i])
 31     {
 32         LL y=ver[i];
 33         if(v1[y])continue;
 34         fa[y]=x;
 35         dfs1(y);
 36     }
 37 }
 38 void build(LL &rt,LL l,LL r,LL w)
 39 {
 40     if(!rt) 
 41     {
 42         rt=++cnt;
 43         L[rt]=l;
 44         R[rt]=r;
 45     }
 46     LL mid=l+r>>1;
 47     if(l==r) 
 48     {
 49         if(sum[rt]==1)return ;
 50         else
 51         {    
 52             sum[rt]=1;
 53             W[rt]=w;
 54             return ;
 55         }
 56     }
 57     if(w<=mid) build(ls[rt],l,mid,w);
 58     else build(rs[rt],mid+1,r,w);
 59     sum[rt]=sum[ls[rt]]+sum[rs[rt]];
 60 }
 61 LL merge(LL x,LL y)
 62 {
 63     if(!x||!y)return x+y;
 64     if(L[x]==R[x]&&L[x]==L[y]&&R[x]==R[y])return x;
 65     ls[x]=merge(ls[x],ls[y]);
 66     rs[x]=merge(rs[x],rs[y]);
 67     sum[x]=sum[ls[x]]+sum[rs[x]];
 68     return x;
 69 }
 70 void dfs2(LL x)
 71 {
 72     v2[x]=1;
 73     for(LL i=head[x];i;i=nxt[i])
 74     {    
 75         LL y=ver[i];
 76         if(v2[y])continue;
 77         dfs2(y);
 78         rt[x]=merge(rt[x],rt[y]);
 79     }
 80     ans[x]=sum[rt[x]];
 81 }
 82 int main()
 83 {
 84     //freopen("simple2.txt","r",stdin);
 85     n=read();
 86     for(LL i=1,x,y;i<n;i++)
 87         x=read(),y=read(),add(x,y),add(y,x);
 88     for(LL i=1;i<=n;i++) scanf("%lld",&vanum[i]);
 89     m=read();
 90     dfs1(1);
 91     for(LL i=1,x,y;i<=m;i++) pos[i]=read(),colll[i]=read(),b[i]=colll[i];
 92     sort(b+1,b+1+m);
 93     LL sz=unique(b+1,b+m+1)-b-1;
 94     for(LL i=1;i<=m;i++) colll[i]=lower_bound(b+1,b+sz+1,colll[i])-b;
 95     if(n<=1e3&&m<=1e3)
 96     {
 97         for(LL i=1;i<=m;i++)
 98         {
 99             LL x=pos[i],y=colll[i];
100             while(x)
101             {
102                 if(!col1[x][y]&&ans[x]<vanum[x]) ans[x]++;
103                 else if(vanum[x]>ans[x]) vanum[x]--;
104                 col1[x][y]=1;
105                 x=fa[x];
106             }
107         }
108         q=read();
109         for(LL i=1,x;i<=q;i++)
110         {    
111             x=read();
112             printf("%lld\n",ans[x]);
113         }
114         return 0;
115     }
116     for(LL i=1,x,y;i<=m;i++) 
117         build(rt[pos[i]],1,sz,colll[i]);
118     dfs2(1);
119     q=read();
120     for(LL i=1,x;i<=q;i++)
121     {    
122         x=read();
123         printf("%lld\n",ans[x]);
124     }
125 }
70

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

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

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

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

 

19.7.29 NOIP模拟1019.7.29 NOIP模拟10
  1 //注释解释2019.7.29 T2模板 
  2 //仅是本人自我理解;
  3 //copyright by zzyy;
  4 //注释创建者:lsc
  5 //powered by lsc;
  6 //----------------------*
  7 #include<cstdio>
  8 #include<cstring>
  9 #include<cstdlib>
 10 #include<algorithm>
 11 #include<map>
 12 #include<vector>
 13 #define maxn 401000
 14 using namespace std;
 15 int m,n,k,tot,first[maxn],w[maxn],ans[maxn],q,siz[maxn],color,son[maxn],t[maxn];
 16 int data[maxn*4],tsiz[maxn*4],lazy[maxn*4];
 17 vector<int>bel[maxn],dr[maxn];
 18 map<int,int>judge;
 19 struct node{int to,next;}a[maxn*2];
 20 inline void add(int x,int y){a[++tot]=(node){y,first[x]};first[x]=tot;}
 21 inline void pushdown(int x)//懒标记下放
 22 {
 23     if(lazy[x]==0) return;
 24     lazy[x<<1]=lazy[x<<1|1]=1;
 25     lazy[x]=data[x<<1]=data[x<<1|1]=tsiz[x<<1]=tsiz[x<<1|1]=0;
 26 }
 27 inline void pushup(int x)//信息上传
 28 {
 29     data[x]=data[x<<1]+data[x<<1|1];
 30     tsiz[x]=tsiz[x<<1]+tsiz[x<<1|1];
 31 }
 32 inline void update(int x,int l,int r,int val,int derta,int sum)//权值线段树的更新答案操作
 33 {
 34     data[x]+=derta,tsiz[x]+=sum;
 35     if(l==r) return ;
 36     int mid=(l+r)>>1;
 37     pushdown(x);
 38     if(val<=mid) update(x<<1,l,mid,val,derta,sum);
 39     else         update(x<<1|1,mid+1,r,val,derta,sum);
 40     pushup(x);
 41 }
 42 inline int query(int x,int l,int r,int sum)//单点查询键值小于sum的值的个数;
 43 {
 44     if(sum<=0) return 0;
 45     if(l==r)   return data[x];
 46     int mid=(l+r)>>1;
 47     pushdown(x);
 48     if(tsiz[x<<1]<=sum)
 49         return data[x<<1]+query(x<<1|1,mid+1,r,sum-tsiz[x<<1]);
 50     else
 51         return query(x<<1,l,mid,sum);
 52 }
 53 inline void init_tim(int x)//打标记
 54 {
 55     data[1]=siz[1]=0, lazy[1]=1;
 56     for(register int i=0;i<bel[x].size();++i) t[bel[x][i]]=0;//t是一个桶,保存键值的个数
 57 }
 58 inline void init_tree(int x)        //把x节点的操作插入到权值线段树中
 59 {
 60     for(register int i=0;i<bel[x].size();++i)
 61     {
 62         int col=bel[x][i], tim=dr[x][i];
 63         if(!t[col]) update(1,1,m,tim,1,0),t[col]=tim;
 64         else if(t[col]>tim)
 65         {
 66             update(1,1,m,t[col],-1,0);
 67             update(1,1,m,tim,1,0);
 68             t[col]=tim;
 69         }
 70         update(1,1,m,tim,0,1);
 71     }
 72 }
 73 inline void insert(int x,int y)            //将y插入到x中,就是启发式合并
 74 {
 75     for(register int i=0;i<bel[y].size();++i)
 76         bel[x].push_back(bel[y][i]),dr[x].push_back(dr[y][i]);
 77     bel[y].clear(), dr[y].clear();
 78 }
 79 
 80 inline void dfs_pre(int x,int dad)        //树链剖分
 81 {    
 82     siz[x]=bel[x].size();
 83     for(register int i=first[x];i;i=a[i].next)
 84     {    
 85         int to=a[i].to;
 86         if(to==dad) continue;
 87         dfs_pre(to,x); siz[x]+=siz[to];
 88         if(siz[son[x]]<siz[to]) son[x]=to;
 89     }
 90 }
 91 inline void dfs(int x,int dad)
 92 {
 93     for(register int i=first[x];i;i=a[i].next)
 94     {    
 95         int to=a[i].to;
 96         if(son[x]==to||to==dad) continue;
 97         dfs(to,x); 
 98         init_tim(to);
 99     }
100     if(son[x]) dfs(son[x],x);
101         init_tree(x);
102     for(register int i=first[x];i;i=a[i].next)
103     {
104         int to=a[i].to;
105         if(to==dad||to==son[x]) continue;
106         init_tree(to);
107     }
108     ans[x]=query(1,1,m,w[x]);
109     if(son[x])
110     {
111         insert(son[x],x);
112         swap(bel[son[x]],bel[x]); swap(dr[son[x]],dr[x]);
113         for(register int i=first[x];i;i=a[i].next)
114         {
115             int to=a[i].to;
116             if(to==dad) continue;
117             insert(x,to);
118         }
119     }
120 }
121 int main()
122 {
123     freopen("simple1.txt","r",stdin);
124     scanf("%d",&n);
125     for(register int i=1,x,y;i<n;++i) 
126         scanf("%d%d",&x,&y), add(x,y),add(y,x);        //树建边
127     for(register int i=1;i<=n;++i)    
128         scanf("%d",&w[i]);                //限制条件
129     scanf("%d",&m);
130     for(register int i=1,x,y;i<=m;++i)
131     {
132         scanf("%d%d",&x,&y);
133         if(!judge[y]) judge[y]=++color;        //将颜色种类离散化
134         y=judge[y];//现在的y是离散化之后的y;
135         bel[x].push_back(y), dr[x].push_back(i);//bel存的是颜色,dr存的是时间戳;
136     }
137     siz[0]=-1;  
138     dfs_pre(1,0);  
139     dfs(1,0);
140     scanf("%d",&q);
141     for(register int i=1,x;i<=q;++i) 
142         scanf("%d",&x), printf("%d\n",ans[x]);
143 }
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就能拿省一?就能进省队?不存在的!所以还是要努力的提升自己的技术,用实力去换来幸运,这可能就是我从这次考试获得的启示吧!