原题戳这里Codeforces Round #738 (Div. 2)
A. Mocha and Math
题目大意
-
通过对某个区间内的数进行题目所给操作
-
希望最小化序列中的最大值
思路
-
万恶的位运算竟然出现在第一题说明只要转个小弯就能看破 -
一个数和其他数做位与运算（以下自己结合运算特点想一想就能想通）
- 要么不变（与自己相同的数）
- 要么变小（与自己不同的数）
-
所以和别的元素相与时不亏的，所以全部与一遍就好啦
-
因为操作次数不限，所以一定能实现上述
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m, t;
int a[N];
int main()
{
cin >> t;
while(t --)
{
cin >> n;
for(int i = 0; i < n; i ++) cin >> a[i];
int ans = a[0];
for(int i = 1; i < n;i ++) ans &= a[i];
cout << ans << endl;
}
return 0;
}
B. Mocha and Red and Blue
题目大意
- 序列中出现一次连续的两个相同字符就有一个不完美度
- 求怎样涂色才能使不完美度最小
思路
- 容易想到两种字符尽量交错为最优解
- 那么问题来了，怎样能不漏的填完呢
- 正着填一遍再倒着填一遍就可以做到不漏
自己也觉得很神奇 - 全是问号的情况下交错输出即可
- 正着填一遍再倒着填一遍就可以做到不漏
代码
#include<bits/stdc++.h>
using namespace std;
int n, m, t;
string s;
int main()
{
cin >> t;
while(t --)
{
cin >> n;
s.clear();
cin >> s;
int flg = 1;
for(int i = 1; i < n; i ++)
{
if(s[i] == '?')
{
if(s[i - 1] == 'R') s[i] = 'B';
if(s[i - 1] == 'B') s[i] = 'R';
}
}
for(int i = n - 2; i >= 0; i --)
{
if(s[i] == '?')
{
if(s[i +1] == 'R') s[i] = 'B';
if(s[i + 1] == 'B') s[i] = 'R';
}
}
if(s[0] == '?')
{
for(int i = 0; i < n; i ++)
{
if(i & 1) cout << 'B';
else cout << 'R';
}
puts("");
continue;
}
cout << s << "\n";
}
return 0;
}
C. Mocha and HikingC. Mocha and Hiking
题目大意
-
n+1个村子由2n-1条道路相连 -
道路有两种
n-1条道路是从i村到i + 1村，所有1≤ i ≤ n-1a[i]为0表示可以从i村到i+1村，为1表示i + 1村可以到i村
-
问是否错在一条路径走完所有村子
思路
- 很容易发现存在连续的01序列就满足条件
- 但是以下两种情况需要注意
某人因为这个wa了好几发11110类也可以，按顺序访问村子的情况11111类也可以，先访问n+1村再依次访问其他
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n, m, t;
int a[N];
int main()
{
cin >> t;
while(t --)
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
a[n + 1] = 1;
int flg = 0, res = 1;
for(int i = 1; i <= n; i ++)
{
if(a[i] == 1);
if(a[i] == 0 && a[i + 1 ]== 1)
{
res = i;
flg = 1;
break;
}
}
if(flg)
{
for(int i = 1; i <= n; i ++)
{
if(i == res) cout << i << " " << n + 1 << " ";
else cout << i << " ";
}
puts("");
}
else if(!flg && a[1] == 1)
{
cout << n + 1 << " ";
for(int i = 1; i <= n; i ++) cout << i << " ";
puts(" ");
flg = 1;
}
else if(!flg) puts("-1");
}
return 0;
}
D1. Mocha and Diana (Easy Version)
题目大意
- 两人分别有n个点，最初这些点中有些被连成联通块
- 连词边的操作在两波分同时进行
- 已经在同一连通块中两点不能连
- 问最多可以连几条
思路
- 与连通块相关指向并查集
- 维护两个并查集，记录可连边即可
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m1, m2;
int p[N], q[N];
struct node
{
int x, y;
}pi[N];
int find1(int x)
{
if(p[x] != x) p[x] = find1(p[x]);
return p[x];
}
int find2(int x)
{
if(q[x] != x) q[x] = find2(q[x]);
return q[x];
}
int main()
{
cin >> n >> m1 >> m2;
for(int i = 1; i <= n; i ++) p[i] = i;
for(int i = 1; i <= n; i ++) q[i] = i;
while(m1 --)
{
int u, v;
cin >> u >> v;
p[find1(u)] = find1(v);
}
while(m2 --)
{
int u, v;
cin >> u >> v;
q[find2(u)] = find2(v);
}
int cnt = 0;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
{
int a1, a2, a3, a4;
if(i != j)
{
a1 = find1(i), a2 = find1(j);
a3 = find2(i), a4 = find2(j);
if(a1 != a2 && a3 != a4)
{
pi[cnt ++] = {i, j};
p[a1] = a2;
q[a3] = a4;
}
}
}
cout << cnt << "\n";
for(int i = 0; i < cnt ; i ++)
{
cout << pi[i].x << " " << pi[i].y << "\n";
}
return 0;
}
总结 耐心，细心，塌心，静心
