Codeforces Round #738
A. Mocha and Math （位运算）
原题链接 ：https://codeforces.com/contest/1559/problem/A
大致题意
给定 n 个数的序列，可对其操作任意次。
一次操作即：
选取闭区间 [ l，r] ，对该区间反转后，将反转前后的两个区间上的数按照索引进行或运算。
求任意次操作后，序列中最大值的最小值。
思路
首先， “ 任意次操作 ” 保证了可以对序列中任取两个数进行或运算。
其次，或运算后，二进制数中 0 的个数只能是不变或者增多，不可能减少。
最后，可以保证的是经过有效次操作后，序列中所有数可以都化为同一个数，因为假如 a >= b ，a = a & b 后，a <= b。
故而，可以对 n 个数逐个进行判断二进制中 31 位中每一位是否为 0，标记后就可输出。
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <sstream>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#include <set>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <unordered_set>
#include <unordered_map>
using namespace std;
#define getlen(array) {return (sizeof(array) / sizeof(array[0]));}
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define MEM(x, y) memset(x, y, sizeof x)
#define rin int n; scanf("%d", &n)
#define rln ll n; scanf("%lld", &n)
#define rim int m; scanf("%d", &m)
#define rit int t; scanf("%d", &t)
#define ria int a; scanf("%d", &a)
#define sc scanf
#define pr printf
const int INF = 0x3f3f3f3f;
const int N = 110;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
bool st[60];
int main() {
//freopen("D:\\in.txt", "r", stdin);
rit;
while (t --) {
rin;
MEM(st, 0);
for (int i = 0; i < n; ++ i) {
ria;
for (int j = 0; j <= 30; ++ j) {
if (!((a >> j) & 1)) st[j] = true;
}
}
int ans = 0;
for (int i = 30; i >= 0; -- i) {
ans <<= 1;
if (!st[i]) ++ ans;
}
cout << ans << endl;
}
return 0;
}
B. Mocha and Red and Blue（找规律）
原题链接：https://codeforces.com/contest/1559/problem/B
大致题意
存在一个序列只有？、R 和 B 这三种字符，其中 ？ 可以用 R或者 B 替换。
假如存在两个相同的字符相邻，那么代价 ++。
求怎么在 ？ 放字母使得代价最小。
思路
诸如样例：?R???BR
假如全为 ？那么最小代价为 0，间接输出 RB 即可。
反之，先设我们找到第一个不为 ？的索引为 a，第二个为 b，那么 0 ~ a 之间的字符显然最小代价为 0，只需要从 a 不断交替字符到 0 即可。
剩下的，假如 s [ a ] == R ，那么 s [ a + 1 ] == B，直到指针遇到索引 b 时，直接判断会不会产生代价。
这样做可行是因为， s [ a + 1 ] == B，假如后面走到 b 位置不会产生代价，那么 代价为 0，假如产生了代价，那么代价为 1；
而如果反其道而行， s [ a + 1 ] == R，相应的代价是 2 和 1。
很显然，从贪心的角度来讲，每一次和前面一个字母取反是最优的做法。
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <sstream>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#include <set>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <unordered_set>
#include <unordered_map>
using namespace std;
#define getlen(array) {return (sizeof(array) / sizeof(array[0]));}
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define MEM(x, y) memset(x, y, sizeof x)
#define rin int n; scanf("%d", &n)
#define rln ll n; scanf("%lld", &n)
#define rim int m; scanf("%d", &m)
#define rit int t; scanf("%d", &t)
#define ria int a; scanf("%d", &a)
#define sc scanf
#define pr printf
const int INF = 0x3f3f3f3f;
const int N = 110;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
char s[N];
char color[2] = {'B', 'R'};
int main() {
//freopen("D:\\in.txt", "r", stdin);
rit;
while (t --) {
rin;
MEM(s, 0);
cin >> s;
int ans = 0;
int idx = 0;
int len = strlen(s);
bool flag = false;
for (int i = 0; i < len; ++ i) {
if (s[i] != '?') {
idx = i;
flag = true;
break;
}
}
if (!flag) {
int k = 0;
for (int i = 0; i < len; ++ i) {
s[i] = color[k];
k = (k + 1) % 2;
}
cout << s << endl;
}
else {
int k = 0;
if (s[idx] == 'B') k = 1;
for (int i = idx - 1; i >= 0; -- i) {
s[i] = color[k];
k = (k + 1) % 2;
}
for (int i = idx + 1; i < len; ++ i) {
if (s[i] == '?') {
k = 0;
if (s[i - 1] == 'B') k = 1;
s[i] = color[k];
}
// else {
// if (s[i] == s[i - 1]) ++ ans;
// }
}
cout << s << endl;
}
}
return 0;
}
C. Mocha and Hiking（分类讨论）
原题链接：https://codeforces.com/contest/1559/problem/C
大致题意
给定 n + 1 个点，有 i 指向 i + 1 的边 （1 <= i <= n - 1），也有从 i 与 n + 1 之间的边（1 <= i <= n），若为 0 是 i 指向 n + 1，若为 1 是 n + 1 指向 i。
问是否存在每个点都经过且只经过 1 次的路径。
思路
一开始没看明白第一类型的边是 1 <= i <= n - 1，意味着不一定有 n 指向 n + 1。
分类讨论：
① 存在 n + 1 指向 1 ，
② 存在 n 指向 n + 1
③ 给的第二类型的边中，存在相邻两条边的类型为 0 1
④ 其余情况输出 -1
只有 ① ~ ③ 可以把 n + 1 这个点插进去
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <sstream>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#include <set>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <unordered_set>
#include <unordered_map>
using namespace std;
#define getlen(array) {return (sizeof(array) / sizeof(array[0]));}
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define MEM(x, y) memset(x, y, sizeof x)
#define rin int n; scanf("%d", &n)
#define rln ll n; scanf("%lld", &n)
#define rim int m; scanf("%d", &m)
#define rit int t; scanf("%d", &t)
#define ria int a; scanf("%d", &a)
#define sc scanf
#define pr printf
const int INF = 0x3f3f3f3f;
const int N = 10010;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
int a[N];
int main() {
//freopen("D:\\in.txt", "r", stdin);
rit;
while (t --) {
rin;
for (int i = 1; i <= n; ++ i) {
cin >> a[i];
}
if (a[1] == 1) {
cout << n + 1;
for (int i = 1; i <= n; ++ i) cout << " " << i;
}
else if (a[n] == 0) {
for (int i = 1; i <= n; ++ i) cout << i << " ";
cout << n + 1;
}
else {
int idx = -1;
for (int i = 2; i <= n; ++ i) {
if (a[i] == 1 && a[i - 1] == 0) {
idx = i - 1;
break;
}
}
if (idx == -1) cout << -1;
else {
for (int i = 1; i <= idx; ++ i) cout << i << " ";
cout << n + 1;
for (int i = idx + 1; i <= n; ++ i) cout << " " << i;
}
}
cout << endl;
}
return 0;
}
D1. Mocha and Diana (Easy Version) （并查集）
原题链接：https://codeforces.com/contest/1559/problem/D1
大致题意
给定两张图，在第一张图添加边（u，v）后，假如第二张图不存在边（u，v），且添加后两张图皆不存在环，那么视为添加成功，求最大添加数量和添加方案。
思路
显然，没有环即为树，即要求的是添加最多边且为树的方案。
对于一棵已经成为子树来说，是不可以在树中添加任何边，所以只能是不同属于一棵子树才可以，故而用并查集标记每一个点属于哪个根节点即可。
由于数据范围为 1000，所以两层 for 暴力枚举添加的情况。
至于为什么两层 for 对于已经确定的新边来说为什么不会影响到后续添加的边，是因为添加边是把两个集合并在一起，假如连接边的点是 u 和 v，连接后并不影响 u 和 v 各自去连接别的点，只要第二张图不会出现矛盾即可。
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <sstream>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#include <set>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <unordered_set>
#include <unordered_map>
using namespace std;
#define getlen(array) {return (sizeof(array) / sizeof(array[0]));}
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define MEM(x, y) memset(x, y, sizeof x)
#define rin int n; scanf("%d", &n)
#define rln ll n; scanf("%lld", &n)
#define rim int m; scanf("%d", &m)
#define rit int t; scanf("%d", &t)
#define ria int a; scanf("%d", &a)
#define sc scanf
#define pr printf
const int INF = 0x3f3f3f3f;
const int N = 1010;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
int fa1[N], fa2[N];
int n, m1, m2;
int find(int a, int fa[]) {
if (fa[a] != a) fa[a] = find(fa[a], fa);
return fa[a];
}
int main() {
//freopen("D:\\in.txt", "r", stdin);
cin >> n >> m1 >> m2;
for (int i = 1; i <= n; ++ i) {
fa1[i] = i;
fa2[i] = i;
}
for (int i = 1; i <= m1; ++ i) {
int a, b;
cin >> a >> b;
int x = find(a, fa1), y = find(b, fa1);
fa1[x] = y;
}
for (int i = 1; i <= m2; ++ i) {
int a, b;
cin >> a >> b;
int x = find(a, fa2), y = find(b, fa2);
fa2[x] = y;
}
vector<PII> ans;
for (int i = 1; i <= n; ++ i) {
for (int j = i + 1; j <= n; ++ j) {
int a = find(i, fa1), b = find(j, fa1);
int c = find(i, fa2), d = find(j, fa2);
if (a != b && c != d) {
ans.push_back({i, j});
fa1[a] = b;
fa2[c] = d;
}
}
}
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); ++ i) {
cout << ans[i].first << " " << ans[i].second << endl;
}
return 0;
}