Codeforces Round #563 (div.2)

手速场，ABC太简单导致非常无聊。自己还因为智障wa了几次。

这段时间比较忙，没怎么发博客。之后几天会把之前打过的比赛都发了。

题目链接：https://codeforces.com/contest/1174

A：

一激动写错maxn了，本来可以两分钟a掉的sb题。

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson curPos<<1
15 #define rson curPos<<1|1
16 /* namespace */
17 using namespace std;
18 /* header end */
19 
20 int n;
21 const int maxn = 2e3 + 10;
22 int a[maxn];
23 
24 int main() {
25     cin >> n; n *= 2;
26     rep1(i, 1, n) cin >> a[i];
27     sot(a, n);
28     int sum1 = 0, sum2 = 0;
29     rep1(i, 1, n / 2) sum1 += a[i];
30     rep1(i, n / 2 + 1, n) sum2 += a[i];
31     if (sum1 == sum2) return puts("-1"), 0;
32     rep1(i, 1, n) cout << a[i] << " ";
33     puts("");
34     return 0;
35 }

View Code

B：

脑筋急转弯题。一开始还以为是贪心，其实举几个例子就能发现：如果同时存在至少一个奇数和偶数，那么数组必然可以变得有序。否则输出原数组即可。

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson curPos<<1
15 #define rson curPos<<1|1
16 /* namespace */
17 using namespace std;
18 /* header end */
19 
20 const int maxn = 1e5 + 10;
21 int n, a[maxn], f1 = 0, f2 = 0;
22 
23 int main() {
24     cin >> n;
25     rep1(i, 1, n) {
26         cin >> a[i];
27         if (a[i] & 1) f1 = 1; else f2 = 1;
28     }
29     if (f1 && f2) sot(a, n);
30     rep1(i, 1, n) cout << a[i] << " ";
31     puts("");
32     return 0;
33 }

View Code

C：

构造长度为n-1的数组(下标从2开始)，对于任意两个下标i,j，若互质，则a[i]!=a[j]。

这下标赤裸裸暗示质数筛。

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson curPos<<1
15 #define rson curPos<<1|1
16 /* namespace */
17 using namespace std;
18 /* header end */
19 
20 //O(n)质数筛
21 //生成2~n的质数存在ans数组里，tot是质数个数，数组下标从1开始
22 const int maxn = 1e5 + 10; //最多可以判断的质数范围
23 bool valid[maxn];
24 int prime[maxn], tot = 0, cnt = 0;
25 void getPrime(int n, int &tot, int *ans) {
26     tot = 0;
27     memset(valid, 1, sizeof(valid));
28     for (int i = 2; i <= n; i++) {
29         if (valid[i]) ans[++tot] = i;
30         for (int j = 1; (j <= tot) && (i * ans[j] <= n); j++) {
31             valid[i * ans[j]] = false;
32             if (i % ans[j] == 0) break;
33         }
34     }
35 }
36 
37 int n, ans[maxn];
38 
39 int check() {
40     rep1(i, 2, n)
41     if (ans[i] == -1) return 0;
42     return 1;
43 }
44 
45 int main() {
46     cin >> n;
47     getPrime(n, tot, prime);
48     memset(ans, -1, sizeof(ans));
49     while (!check()) {
50         int curr = prime[++cnt];
51         for (int i = curr; i <= n; i += curr) ans[i] = cnt;
52     }
53     rep1(i, 2, n) cout << ans[i] << " ";
54     puts("");
55     return 0;
56 }

View Code

D：

又是个构造题。给定n和x，要构造一个尽可能长的数组a，满足1≤ai<2n。且对于任意非空区间，满足区间内异或和不等于0和x。

既然是异或和，那么可以考虑构造数组的前缀异或和来帮助解题。那么原题就变成：构造数组的前缀异或和数组，满足对于数组的任意一对元素，异或和不等于0和x。

这里要讨论x是否小于n的情况：

　　若小于，则对于a(1<=a<2^n)，唯一存在b(1<=b<2^n)，使得a xor b=x。那么在[1,x)∪(x,2^n)这2^n-2个数中，有2^n-1对数，每对只能取一个数来构成答案，所以答案长度为2^n-1。

　　若大于，则对于a(1<=a<2^n)，都不存在b(1<=b<2^n)，使得a xor b=x。那么1,2,3,...,2^n-2,2^n-1就是一个可行解。

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson curPos<<1
15 #define rson curPos<<1|1
16 /* namespace */
17 using namespace std;
18 /* header end */
19 
20 int n, last, x;
21 
22 int main() {
23     cin >> n >> x;
24     n = 1 << n;
25     cout << (x < n ? n / 2 : n) - 1 << endl;
26     rep0(i, 1, n)
27     if (i < (i ^ x)) {
28         cout << (i ^ last) << " ";
29         last = i;
30     }
31     puts("");
32     return 0;
33 }

View Code

E：

标题跟GCD相关，结果却是个dp，太难了。题解via. yang12138

F：

图论交互题。题解via. yang12138