Codeforces Round #306 (Div. 2) D.E. 解题报告-白红宇

Codeforces Round #306 (Div. 2) D.E. 解题报告

阅读量：5023 次

发布时间：2019-06-12

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

D题：Regular Bridge

乱搞。

构造

这题乱搞一下即可了。构造一个有桥并且每一个点的度数都为k的无向图。

方法非常多。也不好叙述。。

代码例如以下：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #define INF 0x3f3f3f3f#define LL long longconst int mod=1e9+7;using namespace std ;int main(){ int k, i, j; while(scanf("%d",&k)!=EOF){ if(k==1){ puts("YES\n2 1\n1 2"); continue ; } if(!(k&1)) { puts("NO"); continue ; } puts("YES"); printf("%d %d\n",2*k+4,(k+2)*k); printf("1 2\n1 %d\n",k+2); for(i=1;i<=(k-3)/2;i++){ printf("1 %d\n1 %d\n",i+2,k+2-i); } for(i=2;i<=k+2;i++){ for(j=i+1;j<=k+2;j++){ if(i==2&&j==k+2) continue ; if(i<=(k-3)/2+2&&i>=3&&i+j==k+4) continue ; printf("%d %d\n",i,j); } } printf("%d %d\n%d %d\n",k+3,k+4,k+3,2*k+4); for(i=1;i<=(k-3)/2;i++){ printf("%d %d\n%d %d\n",k+3,k+4+i,k+3,2*k+4-i); } for(i=k+4;i<=2*k+4;i++){ for(j=i+1;j<=2*k+4;j++){ if(i==k+4&&j==2*k+4) continue ; if(i>=k+5&&i<=k+4+(k-3)/2&&j+i==3*k+8) continue ; printf("%d %d\n",i,j); } } printf("1 %d\n",k+3); } return 0 ;}

E题：Brackets in Implications

乱搞。

构造。

首先能够注意到仅仅有1->0的结果为0.所以必需要构造出一个1->0来，所以最后一个必须为0，否则不管怎样也构造不出最后的0.然后仅仅要在最后一位的0前面构造出一个1就能够了，由于不管前面的结果是什么，仅仅要加上这个1。结果肯定为1，就能够跟最后一位的0构造出0来了。

然后再看第n-1位，第n-1位假设是1。那么就直接按原样输出就能够了。

这时候第n-1位为0.然后能够注意到第n-1位的前面仅仅要有1个0就能够了。由于0加上随意一个数都是1，所以能够变成这样的形式（0->(1->(1->(1……0))…)->0。

假如前面没有0的话，那么就是全是1。那么不管怎么构造也都是变成1->0->0。所曾经面必须有个0，而仅仅要有一个0，构造方法就出来了。

代码例如以下：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #define INF 0x3f3f3f3f#define LL long longconst int mod=1e9+7;using namespace std ;int a[1100000];int main(){ int n, i, pos, flag; while(scanf("%d",&n)!=EOF){ for(i=1;i<=n;i++){ scanf("%d",&a[i]); } if(a[n]){ puts("NO"); continue ; } if(n==1){ puts("YES\n0\n"); continue ; } if(a[n-1]){ puts("YES\n"); for(i=1;i<=n;i++){ printf("%d",a[i]); if(i!=n) printf("->"); } continue ; } if(n==2){ puts("NO"); continue ; } flag=0; for(i=n-2;i>=1;i--){ if(!a[i]){ flag=1; pos=i; break; } } if(!flag) { puts("NO"); continue ; } puts("YES"); for(i=1;i
             
              ",a[i]); } for(i=pos;i<=n-2;i++){ printf("(%d->",a[i]); } printf("%d",a[n-1]); for(i=pos;i<=n-2;i++){ printf(")"); } printf("->%d\n",a[n]); } return 0 ;}

转载于:https://www.cnblogs.com/bhlsheji/p/5197407.html

你可能感兴趣的文章