Codeforces Round #766 (Div. 2)
比赛链接：
https://codeforces.com/contest/1627
A. Not Shading
题意：
\(n\) 行 \(m\) 列的网格，每个格子是白色或者黑色，可以选择一个黑色的格子，将它整列或整行的格子都变成黑，问将第 \(r\) 行第 \(c\) 列的格子变成黑色最少需要多少步？
思路：
首先要判断有没有黑色格子，若没有，则无法实现，若有，要判断第 \(r\) 行 或者第 \(c\) 列有没有黑格子，有的话只需要一步，没有的话需要两步。
代码：
#include
using namespace std;
#define LL long long
const int N = 2e5 + 10;
const int mod = 1;
LL T;
string s;
void solve(){
int n, m, r, c, f = 0;
char a[55][55] = {};
cin >> n >> m >> r >> c;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> a[i][j];
if (a[i][j] == 'B') f = 1;
}
}
if (f == 0){
cout << "-1\n";
return;
}
if (a[r][c] == 'B'){
cout << "0\n";
return;
}
for (int i = 1; i <= n; i++){
if (a[i][c] == 'B'){
cout << "1\n";
return;
}
}
for (int j = 1; j <= m; j++){
if (a[r][j] == 'B'){
cout << "1\n";
return;
}
}
cout << "2\n";
}
int main(){
cin >> T;
while(T--)
solve();
return 0;
}
B. Not Sitting
题意：
在一个有 \(n\) 行 \(m\) 列个座位的地方，\(Tina\) 选择 \(k\) 个位置涂色，\(Rahul\) 选择一个没有被涂色的位置，然后 \(Tina\) 选择一个位置（除了 \(Rahul\) 选择的位置之外，可以随便选），\(Rahul\) 希望最后的位置尽可能靠近 \(Tina\)，而 \(Tina\) 则希望远离 \(Rahul\)。问当 \(Tina\) 涂了 \(k (k = 0, 1, 2, ... , n * m - 1)\) 个位置后，他们俩坐的位置之间的距离是多少，距离采用曼哈顿距离计算。
思路：
\(Rahul\) 先选择，他又希望离 \(Tina\) 近，那他肯定选择最中间的位置，这样才能保证 \(Tina\) 选择的位置肯定与自己最近，而 \(Tina\) 为了远离 \(Rahul\)，它肯定涂地图中间的位置，这样子 \(Rahul\) 选择的位置远离了中心， \(Tina\) 最后选择位置的时候才能远离 \(Rahul\)。
所以，若 \(Rahul\) 选择了 \((i, j)\) 这个位置，那么 \(Tina\) 一定会选择离这个坐标最远的一个角落。
同时，涂色是从 \(0 到 n * m - 1\) 个位置涂，假如，刚开始 \(Rahul\) 选择了一个位置（这个位置肯定是当前最优的位置），那么 \(Tina\) 下一次多出来的一个涂色机会就会去涂这个位置，这样一直迭代下去，所以 (i, j) 的选择就会是将该地方所有坐标都选了一遍。
代码：
#include
using namespace std;
#define LL long long
const int N = 2e5 + 10;
const int mod = 1;
int T, n, m;
string s;
void solve(){
scanf("%d%d", &n, &m);
vector a;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
a.push_back(max(i, n - i - 1) + max(j, m - j - 1));
sort(a.begin(), a.end());
for (int i = 0; i < n * m; i++)
cout << a[i] << " \n"[i == n * m - 1];
}
int main(){
cin >> T;
while(T--)
solve();
return 0;
}
C. Not Assigning
题意：
树上任意一条边的权重或两条相邻边的权重和都是一个质数的树被称作质数树，现有 \(n\) 个顶点，\(n - 1\) 条知道起点和终点，不知道权重的边的树，若能变成一个质数树，依次输出每条边的权重，若不能，输出 -1。
思路：
边的权重是质数，那么所有边的权重肯定是质数了。
两条边的权重和是质数，除了 2 以外的质数都是奇数，两个奇数的和就变成了偶数，是合数，就不符合质数树的性质了，所以质数树上两条边的组合一定是 2 和另一个质数进行组合，这就要求所有点的度要 <= 2。
除了 2 以外的质数可以是 3，5，11 等等（7 + 2 = 9，不是质数了，所以不行），我们可以选择 2 和 3 的组合。
然后只需要找到一个度为 1 的点，一遍 \(dfs\) 进行赋值就可以了。
代码：
#include
using namespace std;
const int N = 1e5 + 10;
bool val[N];
int T = 1, n, u, v, ans[N];
vector > e[N];
void dfs(int now, int p){
val[now] = true;
for (auto x : e[now]){
if (val[x.first]) continue;
ans[x.second] = p + 2;
dfs(x.first, p ^ 1);
}
}
void solve(){
scanf("%d", &n);
for (int i = 1; i <= n; i++){
val[i] = false;
e[i].clear();
}
for (int i = 1; i < n; i++){
scanf("%d%d", &u, &v);
e[u].push_back(make_pair(v, i));
e[v].push_back(make_pair(u, i));
}
for (int i = 1; i <= n; i++){
if (e[i].size() > 2){
cout << "-1\n";
return;
}
}
for (int i = 1; i <= n; i++){
if (e[i].size() == 1){
dfs(i, 0); //用 0 的话，可以通过位运算实现 0 和 1 的快速转化。
break;
}
}
for (int i = 1; i < n; i++)
cout << ans[i] << " \n"[i == n - 1];
}
int main(){
cin >> T;
while(T--)
solve();
return 0;
}
D. Not Adding
题意：
告诉你一个由 \(n\) 个不同数字组成的序列，每一步的操作中你可以选择序列中的两个不同的数，将它们的最大公约数加入这个序列中，然后用新的序列进行下一步操作，问最多能操作几次。
思路：
看到数据范围，可以想到对每一个数都判断一次能不能从序列中得到去计算总的操作次数。
而想要通过两个数的最大公约数得到当前这个数 \(x\)，那只能通过 \(x\) 的倍数去求，所以可以对序列中 \(x\) 的倍数求最大公约数，若结果等于 \(x\) 那么 \(x\) 就可以得到。
代码：
#include
using namespace std;
const int N = 1e6 + 10;
int T = 1, n, maxn, a, cnt = 0;
bool v[N];
void solve(){
scanf("%d", &n);
for (int i = 0; i < n; i++){
scanf("%d", &a);
maxn = max(maxn, a);
v[a] = true;
}
for (int i = 1; i <= maxn; i++){
if (!v[i]){
int p = 0;
for (int j = i; j <= maxn; j += i)
if (v[j])
p = __gcd(p, j);
if (p == i)
cnt++;
}
}
cout << cnt << "\n";
}
int main(){
while(T--)
solve();
return 0;
}