Codeforces Global Round 14 A B C D E 题解

发布日期：2021-05-07 10:36:05 浏览次数：27 分类：精选文章

本文共 6001 字，大约阅读时间需要 20 分钟。

游记：

开始没有理解A的题意，之后发现没有重复元素，20分钟才过......

B的规律一开始想的过于简单，WA了一发，后来才过

C的规律大概想到了，但是每次结束开始没有把答案清零WA了一次，一个半小时过了

DE两道题感觉都有思路，都尝试打一打，最后一个小时十分钟过了D，E放了

题解：

A. Phoenix and Gold

题意：

已知n个互不相同的数字，求一种排列方式，使得任意位置的前缀和都不是x

分析：

从互不相同入手，如果当前排列使得某位置前缀和是x，只需将该位置后面的元素与前面元素掉换位置即可

当且仅当所有数字之和恰等于x，无解（因为无法调换后方元素）

时间复杂度：

O(Tn)

参考程序：

#pragma GCC optimize(3)#pragma GCC optimize(2)#pragma GCC optimize("Ofast")#pragma GCC target("avx,avx2,fma")#pragma GCC optimization("unroll-loops")#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            #define max(a,b) (a>b?a:b)using namespace std;const int maxn=1e4+10;int n,t,x,num[maxn],pre[maxn]; int main(){ scanf("%d",&t); while(t--){ scanf("%d%d",&n,&x); for(int i=1;i<=n;i++) { scanf("%d",num+i); pre[i]=pre[i-1]+num[i]; } for(int i=1;i<=n;i++) if(pre[i]==x) { if(i!=n){ swap(num[i],num[i+1]); break; } else { printf("NO\n"); goto end; } } printf("YES\n"); for(int i=1;i<=n;i++)printf("%d ",num[i]); printf("\n"); end:; } }

B. Phoenix and Puzzle

题意：

n个完全相同的等腰直角三角形，是否可以组成正方形

分析：

显然，单个正方形只能由以下两种方式形成

由这两种正方形可以形成其他正方形

这里注意，由于左边图形边长是直角边，右边边长是斜边，所以不能够混搭

时间复杂度：

O(T)

参考程序：

#pragma GCC optimize(3)#pragma GCC optimize(2)#pragma GCC optimize("Ofast")#pragma GCC target("avx,avx2,fma")#pragma GCC optimization("unroll-loops")#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            #define max(a,b) (a>b?a:b)using namespace std;const int maxn=1e4+10;int n,t,x ;int check(int num){ int s=sqrt(num); return s*s==num;}int main(){ scanf("%d",&t); while(t--){ scanf("%d",&n); if(n&1){ printf("NO\n"); continue; } if(check(n/2)){ printf("YES\n"); goto end; }else{ if(n%4==0){ if(check(n/4)){ printf("YES\n"); goto end; } } } printf("NO\n"); end:; } }

C. Phoenix and Towers

题意：

n个小于等于x的数字，分为m组，请问是否可以使得每组和的差都小于等于x

分析：

如果i组为当前和是p，且其是最小的组，那么将下一个数字分给i组一定可行

即：p≤q，且若z≤x，那么一定有p+z≤q+x

最后遍历检查即可

时间复杂度：

O(T)

参考程序：

#pragma GCC optimize(3)#pragma GCC optimize(2)#pragma GCC optimize("Ofast")#pragma GCC target("avx,avx2,fma")#pragma GCC optimization("unroll-loops")#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            #define max(a,b) (a>b?a:b)using namespace std;const int maxn=1e5+10;int n,t,m,x,ans[maxn],h[maxn];struct arr{ int id,h; bool operator < (const arr &x)const{ return x.h
            
             b.h;}int main(){ scanf("%d",&t); while(t--){ memset(h,0,sizeof(h)); scanf("%d%d%d",&n,&m,&x); for(int i=1;i<=n;i++){ scanf("%d",&me[i].h); me[i].id=i; } sort(me+1,me+1+n,cmp); priority_queue
             
               q; for(int i=1;i<=m;i++){ xx.h=0,xx.id=i; q.push(xx); } for(int i=1;i<=n;i++){ xx=q.top(); q.pop(); h[xx.id]+=me[i].h; ans[me[i].id]=xx.id; xx.h=h[xx.id]; q.push(xx); } sort(h+1,h+1+m);// printf(" ");for(int i=1;i<=m;i++) printf("%d ",h[i]);printf("\n"); for(int i=1;i
              
               x){ printf("NO\n"); goto end; } } printf("YES\n"); for(int i=1;i<=n;i++) printf("%d ",ans[i]); printf("\n"); end:; } }

D. Phoenix and Socks

题意：

n只带颜色的袜子，其中l只左脚，r只右脚，每次操作，可以使得左右属性互换或者更换颜色，问最少多少次能够两两配对

分析：

如果可以配对，则直接配对，买双袜子花费0

如果同颜色且同脚，或不同颜色且不同脚，则将其配对，每双花费1

如果同脚且不同颜色，将其配对花费2

注意将3情况转化为2情况，可以优化答案，例如：

但是最优情况应该是：

时间复杂度：

O(T*乱搞)

参考程序：

#pragma GCC optimize(3)#pragma GCC optimize(2)#pragma GCC optimize("Ofast")#pragma GCC target("avx,avx2,fma")#pragma GCC optimization("unroll-loops")#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            using namespace std;const int maxn=2e5+10;int n,t,l,r;int main(){ scanf("%d",&t); while(t--){ map
            
              col; int ans=0; scanf("%d%d%d",&n,&l,&r); for(int i=1,x;i<=l;i++){ scanf("%d",&x); col[x]++; } for(int i=1,x;i<=r;i++){ scanf("%d",&x); col[x]--; } int ml=0,mr=0,pl=0,pr=0; map
             
              ::iterator iter; iter = col.begin(); while(iter != col.end()) { int num=iter->second; if(num>0){ if(num&1){ ml++; num--; } pl+=num/2; }else if(num<0){ num*=-1; if(num&1){ mr++; num--; } pr+=num/2; } iter++; } if(ml==mr){ printf("%d\n",pr+pl+ml); continue; } if(ml
              
               =dt){ printf("%d\n",pr+mr+(pl-dt/2)); }else{ printf("%d\n",pr+mr); } }else{ int dt=ml-mr; if(pr*2>=dt){ printf("%d\n",pl+ml+(pr-dt/2)); }else{ printf("%d\n",pl+ml); } } }}

E. Phoenix and Computers

题意：

n台电脑排成一行，如果一台电脑前后都开机了，那么他也会自动开机，如果需要全部开机，有多少种方法

分析：

看到400的数据范围，考虑立方复杂度的算法，不难想到区间DP

状态设置：因为和元素对应信息无关，所以应该不是平时所考虑的dp[l][r]

发掘一些信息，题目所说的自动开机显然不可传递，那么对于任意区间，如果最后一步自动完成位置不同，那么会给答案带来不同的贡献

所以把区间长度和最后一步补全的位置作为状态设置

但是状态转移时注意:也有可能不需要使用自动，即，手动完成最后一步，这需要最后一步在最左边或最右边

那么不妨写出状态:f[len][cnt]表示长度为len-1台电脑，其中第cnt台是手动开机的

那么f[len][cnt]可以考虑链接一段长度为k的段，使其贡献累加在f[len+k+1][cnt+k]上

记为 $dp[len+k+1][cnt+k] += dp[len][cnt]*contribution[k]$

接下来考虑贡献的计算方法

假设对于长度k-1的区间，有x种方法，那么对于长度为k的区间，每次可以在左边或右边累加一个，所以其贡献为2x

可以将其放置到任何两个元素当中，所以一共有 $\binom{cnt+k}{k}$ 种方法

所以 $contribution[k]=\binom{cnt+k}{k}*2^{k-1}$

代码实现：

可以考虑先预处理排列组合C[r][n]和pow2[n]，之后长度从小到大递推过去

时间复杂度：

$O(n^3)$

参考程序：

#pragma GCC optimize(3)#pragma GCC optimize(2)#pragma GCC optimize("Ofast")#pragma GCC target("avx,avx2,fma")#pragma GCC optimization("unroll-loops")#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            using namespace std;const int maxn=410;long long C[maxn][maxn],f[maxn][maxn],mod,pow2[maxn],ans,pre[maxn],inv[maxn];int n;long long poww(long long a,long long b){ long long ans=1,ta=a; while(b){ if(b&1) ans=(ans*ta)%mod; ta=ta*ta%mod; b>>=1; } return ans;}void ini(){ pow2[0]=1; for(int i=1;i<=n;i++) pow2[i]=(pow2[i-1]<<1)%mod; pre[0]=inv[0]=1; for(int i=1;i<=n;i++){ pre[i]=(pre[i-1]*i)%mod; inv[i]=poww(pre[i],mod-2); } for(int i=0;i<=n;i++) for(int j=0;j<=i;j++) C[i][j]=pre[i]*inv[j]%mod*inv[i-j]%mod;}int main(){ scanf("%d%lld",&n,&mod); ini(); f[0][0]=1; for(int len=0;len<=n;len++) for(int cnt=0;cnt<=len;cnt++) for(int pos=1;pos+len<=n;pos++) f[len+pos+1][cnt+pos]=(f[len+pos+1][cnt+pos]+((f[len][cnt]*pow2[pos-1])%mod)*C[cnt+pos][pos])%mod; for(int i=0;i<=n;i++) ans=(ans+f[n+1][i])%mod; printf("%lld",ans); return 0;}

上一篇：Codeforces Round #719 (Div. 3) A B C D E F题解

下一篇：胶水语言Python与C/C++的相互调用

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

游记：

题解：

A. Phoenix and Gold

题意：

分析：

时间复杂度：

参考程序：

B. Phoenix and Puzzle

题意：

分析：

时间复杂度：

参考程序：

C. Phoenix and Towers

题意：

时间复杂度：

参考程序：

D. Phoenix and Socks

题意：

分析：

时间复杂度：

参考程序：

E. Phoenix and Computers

题意：

分析：

代码实现：

时间复杂度：

参考程序：

发表评论

最新留言

关于作者

推荐文章