A：Design Tutorial: Learn from Math

题意：给一个N>=12，求两个合数A,B使得A+B=N.

题解：N是偶数就是4，N-4，是奇数就是9，N-9

1 #include 
      
        2  3 #include 
       
         4  5 #include 
        
          6  7 #include 
         
           8  9 #include 
          
           10 11 12 13 using namespace std;14 15 int n;16 17 int main()18 19 {20 21     scanf("%d",&n);22 23     if (n%2==0) printf("4 %d\n",n-4);24 25     else printf("9 %d\n",n-9);26 27     return 0;28 29 }
          
         
        
       
      

B：Design Tutorial: Learn from Life

题意：N个人在一层要坐电梯，第i个人要到第Ai层，电梯最多同时K个人，电梯从i层到j层消耗|i-j|的能量，求最少需要多少能量。

题解：明显一次要坐满K个人，且这一次消耗的能量为MAX(a[i])-1，于是贪心按照A[i]的顺序从大到小每次K个人上去即可。

1 #include 
      
        2  3 #include 
       
         4  5 #include 
        
          6  7 #include 
         
           8  9 #include 
          
           10 11 12 13 using namespace std;14 15 int n,k,a[5000],dq,ans;16 17 int main()18 19 {20 21     scanf("%d%d",&n,&k);22 23     for (int i=1;i<=n;++i) scanf("%d",&a[i]);24 25     sort(a+1,a+n+1);26 27     dq=n;28 29     while (dq)30 31     {32 33         ans+=2*a[dq]-2;34 35         if (dq>k) dq-=k;else dq=0;36 37     }38 39     printf("%d",ans);40 41     return 0;42 43 }
          
         
        
       
      

 

C：Design Tutorial: Make It Nondeterministic

题意：给出N个人的名字，每个人名字有两部分xi和yi 可任选其一代表他,再给出一个1到n的序列a1,a2,...an，问能不能找到一种对于每个人名字的取法使得这N个人名字的字典序为{a}

题解：假设前i-1个已满足给定的字典序，且第i-1个位置的名字为s,我们假设Xai<Yai，显然若Xai>s 则第i个人的名字应取为Xai，这样既满足前面要求，

也能使得后面位置的选择更多，即为贪心的策略！于是我们从头到尾扫一遍取每个位置满足条件的较小的名字即可。

1 #include 
      
         2   3 #include 
       
          4   5 #include 
        
           6   7 #include 
         
            8   9 #include 
          
            10  11 #include 
           
             12 13 using namespace std; 14 15 int n,x[200000]; 16 17 int now; 18 19 string a[200000],b[200000]; 20 21 int main() 22 23 { 24 25 scanf("%d",&n); 26 27 for (int i=1;i<=n;++i) 28 29 { 30 31 cin>>a[i]>>b[i]; 32 33 //cout<
            
             <<" "<
             
              <
              
               b[i]) swap(a[i],b[i]); 36 37 //cout<
               
                <<" "<
                
                 <
                 
                  a[x[i-1]]) 56 57 { 58 59 now=1; 60 61 continue; 62 63 } 64 65 if (b[x[i]]>a[x[i-1]]) 66 67 { 68 69 now=2; 70 71 continue; 72 73 } 74 75 }else 76 77 { 78 79 if (a[x[i]]>b[x[i-1]]) 80 81 { 82 83 now=1; 84 85 continue; 86 87 } 88 89 if (b[x[i]]>b[x[i-1]]) 90 91 { 92 93 now=2; 94 95 continue; 96 97 } 98 99 }100 101 printf("NO\n");102 103 return 0;104 105 }106 107 printf("YES\n");108 109 return 0;110 111 }
                 
                
               
              
             
            
           
          
         
        
       
      

D：Design Tutorial: Inverse the Problem

题意：给出树上N个点间的任意两点间距离，问是否存在这样的一棵树。

题解：对于每个点，离他最近的点肯定是和他直接连边的！

 所以对于每个点i，找到离他最近的点k，再来检查每个节点j是不是有abs(dist[i][j]-dist[k][j])=dist[i][j]即可！

因为树上任意两点间路径唯一，且j不是在k子树中就是在k子树外，所以上式若树存在则必成立！

由此可得到每个点和他最近的点相连的边，若是这样连完后还少边，则根据dist数据可直接构造合法解，因为有前面的式子都成立的话必然存在可行解！

1 #include 
      
        2  3 #include 
       
         4  5 #include 
        
          6  7 #include 
         
           8  9 #include 
          
           10 11 int map[2500][2500];12 13 int n,flag;14 15 int main()16 17 {18 19     scanf("%d",&n);20 21     for (int i=1;i<=n;++i)22 23         for (int j=1;j<=n;++j) scanf("%d",&map[i][j]);24 25     flag=1;26 27     for (int i=1;i<=n;++i)28 29         for (int j=1;j<=n;++j)30 31         {32 33             if (map[i][j]!=map[j][i]) flag=0;34 35             if (map[i][j]==0&&i!=j) flag=0;36 37         }38 39     for (int i=1;i<=n;++i)40 41     {42 43         int dqmin=19950920,dq=1;44 45         for (int j=1;j<=n;++j) if (i!=j&&map[i][j]
          
         
        
       
      

F：Design Tutorial: Change the Goal

题意：给出两个序列{x}和{y}，现在可在x数列做如下操作使得xi^=xj，求一个操作序列(i,j)使得操作后xi=yi

/*题解：我们发现通过xor操作把序列X转换成Z之后，我们可以通过xor操作把Z还原成X！因为若最后一步是a^=b 则再让a^=b则a就成功还原了这一步的操作，

依次逆推回去即可还原原数列，由此我们不难想到一个做法：将X和Y都变换成一个序列Z，则X到Y即可变为X变换成Z，Z还原成Y的过程！

然后不难想到，最好的Z数列即为：1,2,4,8,....,2^30

然后就是如何把X转换成Z，就是xor版高斯消元的过程啊~

于是我们先把X按照过程变换成一个1,2,4,8....的数列 再把Y按照过程变换成1,2,4,8,.....的数列

突然发现了些问题。。*/

http://mudream.logdown.com/posts/236851/codeforce-472-design-tutorial-change-the-goal 参考自这里。。