AtCoder Grand Contest 030 Solution

A - Poisonous Cookies

签到。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long 
 5 ll a, b, c;
 6 
 7 int main()
 8 {
 9     while (scanf("%lld%lld%lld", &a, &b, &c) != EOF)
10     {
11         if (c <= a + b + 1) printf("%lld
", b + c);
12         else printf("%lld
", a + b + b + 1);
13     }
14     return 0;
15 }

View Code

B - Tree Burning

Unsolved.

题意：

在一个环上，长度为L, 刚开始在0点，有些点上有树

每次可以顺时针走或者逆时针走，每碰到一棵树这棵树就消失

然后可以又选择方向去走，直到所有树都消失，求最长路径

C - Coloring Torus

Upsolved.

题意：

要求构造一个$n cdot n的矩形，使得每个点都被染色，且只能用k种颜色，并且k种颜色都要有$

思路：

如果k是4的倍数，那么有一个显然的做法

比如说8

1 2 3 4

5 6 7 8

1 2 3 4

5 6 7 8

这样排下去，n取 k / 2

但是如果k不是4的倍数，我们可以通过移位，使得它合理

$当r = 0 ;mod; 2的时候，x = (r + c) ;; mod;; n$

$否则 x = n + (r + c) % n$

注意如果x大于k，要减去n

为什么这样是对的呢，不知道。。。不会证(逃

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int k;
 7     while (scanf("%d", &k) != EOF)
 8     {
 9         if (k <= 500)
10         {
11             printf("%d
", k);
12             for (int i = 1; i <= k; ++i) for (int j = 1; j <= k; ++j)
13                 printf("%d%c", i, " 
"[j == k]);
14         }
15         else
16         {
17             int n = (k + 3) / 4 * 2;
18             printf("%d
", n);
19             for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j)
20             {
21                 int x;
22                 if (i & 1) x = (i + j) % n;
23                 else x = n + (i + j) % n;  
24                 if (x >= k) x -= n;     
25                 printf("%d%c", x + 1, " 
"[j == n]);
26             }
27         }
28     }
29     return 0;
30 }

View Code

D - Inversion Sum

Unsolved.

题意：

给出一个序列，给出$q个x_i, y_i$ 每次有两种可能的操作

1° 交换$x_i, y_i位置上的数$

2° 什么也不做

这样一共有$2^q次可能的序列求所有可能序列的逆序数$