Good Bye 2018 Solution

A. New Year and the Christmas Ornament

签到。

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

View Code

B. New Year and the Treasure Geolocation

签到。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 1010
 5 int n, x[N], y[N], a[N], b[N];
 6 
 7 int main()
 8 {
 9     while (scanf("%d", &n) != EOF)
10     {
11         for (int i = 1; i <= n; ++i) scanf("%d%d", x + i, y + i);
12         for (int i = 1; i <= n; ++i) scanf("%d%d", a + i, b + i);
13         sort(x + 1, x + 1 + n);
14         sort(y + 1, y + 1 + n);
15         sort(a + 1, a + 1 + n);
16         sort(b + 1, b + 1 + n);
17         printf("%d %d
", x[1] + a[n], y[1] + b[n]);
18     }
19     return 0;
20 }

View Code

C. New Year and the Sphere Transmission

Solved.

题意：

有一个环，长度为n，有n个点，标号为1-n,固定步长去走，求回到1的时候经过的点的标号总和多少

求出有多少个步长得到的这个标号总和不同，按从小到大顺序输出

思路：

如果步长是n的因数，那么可以在一轮走完，并且不同的因数走的路径不同，答案也不同

如果不是n的因数，那么一轮肯定走不完，到下一轮，相当于换个起点去走，也走不完，

直到起点回到1，这时候所有点都走完了，答案都是相同的

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 ll n;
 6 
 7 ll f(int an, int n)
 8 {
 9     return 1ll * (1 + an) * n / 2;
10 }
11 
12 int main()
13 {
14     while (scanf("%lld", &n) != EOF)
15     {
16         ll limit = sqrt(n) + 1;
17         vector <ll> res; res.push_back(1); res.push_back(n * (n + 1) / 2);
18         for (int i = 2; i <= limit; ++i) if (n % i == 0)
19         {
20             res.push_back(f(n + 1 - i, n / i));
21             res.push_back(f(n + 1 - n / i, i));
22         }
23         sort(res.begin(), res.end());
24         res.erase(unique(res.begin(), res.end()), res.end());
25         for (int i = 0, len = res.size(); i < len; ++i) printf("%lld%c", res[i], " 
"[i == len - 1]);
26     }
27     return 0;
28 }

View Code

D. New Year and the Permutation Concatenation

Solved.

题意：

给出一个n，如此构造一个序列，将他的所有排列按字典序大小放进去

问可以选多少个起点，使得以起点之后长度为n的子段的和为$frac {n cdot (n + 1)}{2}$

思路：

考虑两个相邻序列如果可以有这样的起点，那么必定是他们的公共前缀里的点，并且贡献就是公共前缀长度 + 1

再考虑我们固定一个公共前缀的长度为x，那么这样的排列一共有$(n - x)!$种

并且这些排列肯定是连续在一起的，那么就可以算贡献了

枚举公共前缀长度就好了

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 const ll MOD = (ll)998244353;
 6 int n;
 7 
 8 int main()
 9 {
10     while (scanf("%d", &n) != EOF)
11     {
12         if (n <= 2) 
13         {
14             printf("%d
", n);
15             continue;
16         }
17         ll res = n - 1;
18         for (int i = 2; i <= n; ++i) res = (res * i) % MOD;
19         ll tot = 1;
20         for (int i = n; i >= 3; --i)
21         {
22             tot = (tot * i) % MOD;
23             res = (res - tot + MOD) % MOD;
24         }
25         printf("%lld
", res);
26     }    
27     return 0;
28 }

View Code

E. New Year and the Acquaintance Estimation

Unsolved.

题意：

有n个点，给出每个点的度数，每个点最多去掉一个度，令$x = 去掉的度数之和$

求合法图中不同的$x个数，从小到大输出$