题解Codeforces Round #595 (Div. 3)（CF1249）

开题1小时（雾）严重影响我的提交以及做题心情。。我刚开题就发现有人阿克了。。

实际上这场div3真心简单良心很休闲。

A：送分题，先排序，每次枚举一下这个数可以加到哪个集合里，加进去就行。

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #define it register int
 4 #define il inline
 5 using namespace std;
 6 const int N=1000005;
 7 int a[N],o[N],n,ans,T;
 8 il void fr(int &num){
 9     num=0;char c=getchar();int p=1;
10     while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar();
11     while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
12     num*=p;
13 }   
14 int main(){  
15     fr(T);
16     while(T--){
17         fr(n),ans=0;
18         for(it i=1;i<=n;++i) fr(a[i]);
19         sort(a+1,a+1+n);
20         for(it i=1,fl;i<=n;++i){
21             fl=1;
22             for(it j=1;j<=ans;++j)
23                 if(a[i]-o[j]>1) o[j]=a[i],fl=0,j=ans+1;
24             if(fl) o[++ans]=a[i];
25         }
26         printf("%d
",ans);
27     }
28     return 0;
29 }

View Code

B：双倍经验送分题。直接跑tarjan，输出每个强连通分量的大小就可以了。注意多测清空。

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #define it register int
 4 #define il inline
 5 using namespace std;
 6 const int N=1000005;
 7 int h[N],o[N],n,ans,T,u,v,nxt[N],adj[N],sz[N],dfn[N],low[N],ti,i,s[N],t,top,tot;
 8 bool ins[N];
 9 il void fr(int &num){
10     num=0;char c=getchar();int p=1;
11     while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar();
12     while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
13     num*=p;
14 }   
15 il void add(){
16     nxt[++t]=h[u],h[u]=t,adj[t]=v;
17 }
18 il int Min(it p,it q){
19     return p<q?p:q;
20 }
21 il void scc(it x){
22     dfn[x]=low[x]=++ti,s[++top]=x,ins[x]=true;
23     for(it i=h[x],j;i;i=nxt[i]) !dfn[j=adj[i]]?scc(j),low[x]=Min(low[x],low[j]):low[x]=Min(low[x],ins[j]?dfn[j]:low[x]);
24     if(dfn[x]==low[x]){
25         it v;++tot;
26         do{
27             v=s[top--],ins[v]=false,o[v]=tot,++sz[tot];
28         }while(x!=v&&top);
29     }
30 }
31 int main(){   
32     fr(T);
33     while(T--){
34         fr(n);
35         for(u=1;u<=n;++u) fr(v),add();
36         for(it i=1;i<=n;++i) if(!dfn[i]) scc(i);
37         for(it i=1;i<=n;++i) printf("%d ",sz[o[i]]);
38         putchar('
');
39         for(it i=1;i<=n;++i) dfn[i]=low[i]=o[i]=sz[i]=h[i]=ins[i]=s[i]=0;
40         t=top=ti=tot=0;
41     }
42     return 0;
43 }

View Code

C：双倍经验送分题。很显然>=n的最大的只要把n里面所有的3的幂去除，然后把剩下未选中的挑一个最小的且比去除之后的n大的加入答案就行。注意到样例里面给的最大的那个是3^38.

 1 #include<stdio.h>
 2 #include<queue>
 3 #include<algorithm>
 4 #define it register int
 5 #define il inline
 6 using namespace std;
 7 const int N=1000005; 
 8 typedef long long ll; 
 9 ll pw[N],ans,n,T;
10 bool inq[N];
11 il void fr(ll &num){
12     num=0;char c=getchar();int p=1;
13     while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar();
14     while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
15     num*=p;
16 }   
17 int main(){  
18     pw[0]=1ll;for(it i=1;i<=38;++i) pw[i]=pw[i-1]*3;
19     fr(T);
20     while(T--){
21         fr(n),ans=0;
22         for(it i=0;i<=38;++i) inq[i]=0;
23         for(it i=38;i>=0;--i) if(n>pw[i]) n-=pw[i],ans+=pw[i],inq[i]=1;
24         for(it i=0;i<=38;++i) if(inq[i]) ans-=pw[i]; else{ans+=pw[i];break;}
25         printf("%I64d
",ans);
26     }
27     return 0;
28 }

View Code

D：双倍经验，有点难度。考场降智，先打了一个树状数组，用小号交，一发WA了，二发WA了。赶紧换个思路，写了线段树。唯一需要注意的地方就是先排序，先排r再排l，从小到大。

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #define it register int
 4 #define il inline
 5 using namespace std;
 6 const int N=1000005;
 7 int o[N],ans,s[N],add[N],u,v,x,cnt,k,n,maxn;
 8 il int Max(it p,it q){
 9     return p>q?p:q;
10 }
11 struct ky{
12     int l,r,id;
13     bool operator<(const ky&p)const{
14         return r^p.r?r<p.r:l<p.l;
15     }
16 }a[N];
17 il void fr(int &num){
18     num=0;char c=getchar();int p=1;
19     while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar();
20     while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
21     num*=p;
22 }   
23 il void pd(it l,it r,it rt){
24     it mid=l+r>>1;
25     add[rt<<1]+=add[rt],add[rt<<1|1]+=add[rt],s[rt<<1]+=add[rt],s[rt<<1|1]+=add[rt],add[rt]=0;
26 }
27 il void upd(it l,it r,it rt){
28     if(l>v||r<u) return;
29     if(l>=u&&r<=v){
30         s[rt]+=x,add[rt]+=x;return;
31     }
32     if(add[rt]) pd(l,r,rt);
33     it mid=l+r>>1;
34     upd(l,mid,rt<<1),upd(mid+1,r,rt<<1|1),s[rt]=Max(s[rt<<1],s[rt<<1|1]);
35 }
36 il void q(it l,it r,it rt){ 
37     if(l>v||r<u) return;
38     if(l>=u&&r<=v){ 
39         ans=Max(ans,s[rt]);return;
40     }
41     if(add[rt]) pd(l,r,rt);
42     it mid=l+r>>1;
43     q(l,mid,rt<<1),q(mid+1,r,rt<<1|1),s[rt]=Max(s[rt<<1],s[rt<<1|1]);
44 }
45 int main(){  
46     fr(n),fr(k);
47     for(it i=1;i<=n;++i) fr(a[i].l),fr(a[i].r),a[i].id=i,maxn=(a[i].r>maxn?a[i].r:maxn);
48     sort(a+1,a+1+n);x=1; ;
49     for(it i=1;i<=n;++i){
50         u=a[i].l,v=a[i].r,ans=0;
51         q(1,maxn,1); 
52         ans<k?upd(1,maxn,1),0:o[++cnt]=a[i].id;
53     }
54     printf("%d
",cnt);
55     sort(o+1,o+1+cnt);
56     for(it i=1;i<=cnt;++i) printf("%d ",o[i]);
57     return 0;
58 }

View Code

E：一道弱智dp，比D还简单。出题人应该在E的tag上加一个“开题顺序”。设f[i][0],f[i][1]表示选择楼梯和电梯的状态，直接按照题意模拟就行。

 1 #include<stdio.h>
 2 #define it register int
 3 #define il inline
 4 const int N=1000005;
 5 il void fr(int &num){
 6     num=0;char c=getchar();int p=1;
 7     while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar();
 8     while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
 9     num*=p;
10 }   
11 il int Min(it p,it q){
12     return p<q?p:q;
13 }
14 int a[N],b[N],f[N][2],n,c;
15 int main(){  
16     fr(n),fr(c);--n;
17     for(it i=1;i<=n;++i) fr(a[i]);
18     for(it i=1;i<=n;++i) fr(b[i]);
19     f[0][1]=1e9;
20     for(it i=1;i<=n;++i) f[i][0]=Min(f[i-1][0],f[i-1][1])+a[i],f[i][1]=Min(f[i-1][0]+c,f[i-1][1])+b[i];
21     printf("0 ");for(it i=1;i<=n;++i) printf("%d ",Min(f[i][0],f[i][1]));
22     return 0;
23 }

View Code

F：比E还傻的一题，n<=200直接暴力找……

我们考虑，假设现在选择节点u，那么我们把和u距离不超过k的节点都不选。但我们不能够保证u就是最优解，于是把和u距离不超过k的节点的价值都减去a[u]。这时候我们再向上寻找，假设某个节点v和u距离不超过k，而a[v]现在值>0（减去a[u]之后），那我们肯定选择a[v]不选择a[u]。于是我们的答案加上现在的a[v]，实际上就相当于补上a[u]比a[v]小的那一部分，然后再从v开始Dfs，做和u一样的处理。叶子节点没有孩子满足dp的无后效性，所以肯定是从叶子开始。

 1 #include<stdio.h>
 2 #include<vector>
 3 #define it register int
 4 #define il inline
 5 using namespace std;
 6 const int N=1000005; 
 7 int n,k,a[N],h[N],nxt[N],adj[N],t,nw,u,v,d[N],ans;
 8 vector<int> g[N];
 9 il void add(){
10     nxt[++t]=h[u],h[u]=t,adj[t]=v,nxt[++t]=h[v],h[v]=t,adj[t]=u;
11 }
12 il void dfs(it x,it fa){
13     g[d[x]=d[fa]+1].push_back(x);//同一深度放在一起
14     for(it i=h[x],j;i;i=nxt[i])
15         if((j=adj[i])!=fa) dfs(j,x);
16 }
17 il void fr(int &num){
18     num=0;char c=getchar();int p=1;
19     while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar();
20     while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
21     num*=p;
22 }   
23 il void Dfs(it x,it fa,it dep){
24     a[x]-=nw;
25     if(dep==k) return;//距离不超过k
26     for(it i=h[x],j;i;i=nxt[i])
27         if((j=adj[i])!=fa) Dfs(j,x,dep+1);
28 }
29 int main(){  
30     fr(n),fr(k);
31     for(it i=1;i<=n;++i) fr(a[i]);
32     for(it i=1;i<n;++i) fr(u),fr(v),add();
33     dfs(1,0);
34     for(it i=n;i;--i)
35         for(it j=0,sz=g[i].size(),x;j<sz;++j)
36             if((x=a[g[i][j]])>0) nw=x,ans+=x,Dfs(g[i][j],0,0);
37     printf("%d",ans);
38     return 0;
39 }

View Code

看来以后打Div3应该先开EF后开D。。。

今天的比赛应该加个tag“开题顺序”。（吐槽出题人是不是顺序随的看心情的？）

真实难度大约是：A<E<B<F<C<D。。。

赶在官方题解出来之前把自己的题解写完了！开心。完结撒花。

upd：评论区有人对F进行提问，所以新增了一些解释。看不懂的同学欢迎提出问题。