Codeforces Round #270 题解

A：Design Tutorial: Learn from Math

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

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

 1 #include <cstdio>
 2 
 3 #include <cmath>
 4 
 5 #include <iostream>
 6 
 7 #include <algorithm>
 8 
 9 #include <cstring>
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-4);
24 
25     else printf("9 %d
",n-9);
26 
27     return 0;
28 
29 }

View Code

B：Design Tutorial: Learn from Life

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

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

 1 #include <cstdio>
 2 
 3 #include <cmath>
 4 
 5 #include <iostream>
 6 
 7 #include <cstring>
 8 
 9 #include <algorithm>
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 }

View Code

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 <cstdio>
  2 
  3 #include <cmath>
  4 
  5 #include <iostream>
  6 
  7 #include <algorithm>
  8 
  9 #include <cstring>
 10 
 11 #include <string>
 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<<a[i]<<" "<<b[i]<<endl;
 34 
 35         if (a[i]>b[i]) swap(a[i],b[i]);
 36 
 37         //cout<<a[i]<<" "<<b[i]<<endl;
 38 
 39     }
 40 
 41     for (int i=1;i<=n;++i) scanf("%d",&x[i]);
 42 
 43     now=1;
 44 
 45     for (int i=2;i<=n;++i)
 46 
 47     {
 48 
 49         //cout<<a[x[i-1]];
 50 
 51         if (now==1) 
 52 
 53         {
 54 
 55         if (a[x[i]]>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
");
102 
103         return 0;
104 
105     }
106 
107     printf("YES
");
108 
109     return 0;
110 
111 }

View Code

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 <cstdio>
 2 
 3 #include <cmath>
 4 
 5 #include <cstring>
 6 
 7 #include <iostream>
 8 
 9 #include <algorithm>
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]<dqmin)
46 
47         {
48 
49             dqmin=map[i][j];
50 
51             dq=j;
52 
53         }
54 
55         for (int j=1;j<=n;++j) if (abs(map[i][j]-map[dq][j])!=map[i][dq]) flag=0;
56 
57     }
58 
59     if (flag) printf("YES");else printf("NO");
60 
61     return 0;
62 
63 }

View Code

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 参考自这里。。