Codeforces Round #736 (Div. 2)
A. Gregor and Cryptography
题意
给定一个不小于 5 的质数 。找出 ，让 。
思路
质数 是奇数，所以模 2 余 1，模 也余 1。直接输出 2 和 就行。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mo = 998244353;
int T;
int main () {
scanf("%d", &T);
while(T--) {
int p;
scanf("%d", &p);
printf("%d %d\n", 2, p - 1);
}
return 0;
}B. Gregor and the Pawn Game
题意
棋盘上有上下两行兵，对手的兵不会移动。自己的兵可以向正前方的空格走，或者斜着吃掉对面的兵，问最多能有多少个兵到达对面一行。
思路
从左往右处理自己的兵，优先吃左边的兵，其次走到正前方的空格，最后才吃右边的兵。
左边的位置后面用不到了，能吃就先吃；正前方的空格也只属于当前这个兵。右边的兵可能还要留给后面的兵，所以最后再用。用 v 标记已经占用的位置即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 17;
int n, ans, T;
int v[maxn];
char s[maxn], t[maxn];
void Init(){
scanf("%d", &n);
for(int i = 1; i <= n; i++) v[i] = 0;
ans = 0;
scanf("%s", s + 1);
scanf("%s", t + 1);
for(int i = 1; i <= n; i++) {
if(t[i] == '1') {
if(i > 1 && s[i - 1] == '1' && !v[i - 1]) {
v[i - 1] = 1;
ans++;
}
else if(s[i] == '0' && !v[i]) {
v[i] = 1;
ans++;
}
else if(i < n && s[i + 1] == '1' && !v[i + 1]) {
v[i + 1] = 1;
ans++;
}
}
}
}
int main(){
scanf("%d", &T);
while(T--) {
Init();
printf("%d\n",ans);
}
return 0;
}C. Web of Lies
题意
贵族的编号越大，实力越强。如果一个贵族至少有一个朋友，而且所有朋友都比他强，他就会被杀掉；这个过程不断重复。还会动态增加或删除朋友关系，每次询问重新从当前完整关系图开始，求最终活下来的人数。
思路
只要有一个编号更大的朋友，自己最后就会被淘汰。顺着更大的编号往上走，最上面的人会留下来，下面的人则会依次满足被淘汰的条件。
所以只维护每个人比自己强的朋友集合。集合为空的人会留下来，答案就是这些人的数量。加边或删边时，只会影响编号较小的那个人，维护它的集合是否由空变非空、或由非空变空就行。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 17;
int n, ans, T, m;
set<int> s[maxn];
int main(){
scanf("%d%d", &n, &m);
ans = n;
for(int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
if(u > v) swap(u, v);
s[u].insert(v);
}
for(int i = 1; i <= n; i++) if(s[i].size()) ans--;
scanf("%d", &T);
while(T--) {
int t, u, v;
scanf("%d", &t);
if(t == 2) {
scanf("%d%d", &u, &v);
if(u > v) swap(u, v);
s[u].erase(v);
if(s[u].empty()) ans++;
}
else if(t == 1) {
scanf("%d%d", &u, &v);
if(u > v) swap(u, v);
if(s[u].empty()) ans--;
s[u].insert(v);
}
else {
printf("%d\n",ans);
}
}
return 0;
}D. Integers Have Friends
题意
给定一组互不相同的正整数。找最长的连续子数组，使得存在一个 ，让里面所有数模 的余数相同。
思路
把相邻两项作差。余数相同，就说明这些差都有同一个大于 1 的公因数，所以直接维护差分区间的 gcd，不用把每个差分的质因数都拆出来。
从左往右加入一个差分，把上一轮各段的 gcd 再和它取 gcd，并加上只含当前差分的新段。同一个 gcd 只留最早的起点，后面的起点不会更优。gcd 大于 1 时，差分长度加一就是原数组长度。
往左扩展时，gcd 每次严格变小至少减半，因此一轮只有 种状态，空间也只需要这些状态。单个数总是合法，答案从 1 开始。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 17;
ll a[maxn], b[maxn];
int T, n, ans;
vector<pair<ll, int>> s, t;
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for(int i = 1; i < n; i++) b[i] = abs(a[i + 1] - a[i]);
s.clear();
ans = 1;
for(int i = 1; i < n; i++) {
t.clear();
t.push_back({b[i], i});
for(auto &it : s) {
ll g = __gcd(it.first, b[i]);
if(t.back().first == g) {
t.back().second = min(t.back().second, it.second);
}
else t.push_back({g, it.second});
}
s.swap(t);
for(auto &it : s) if(it.first > 1) {
ans = max(ans, i - it.second + 2);
}
}
printf("%d\n", ans);
}
return 0;
}