A
1549A - Gregor and Cryptography
题目大意：
给定一个 (P) , (P) 是素数，任意找出两个基数 (a, b) 使得 (P~~mod~~a = P~~mod~~b)
(5leq Pleq 10^9) (2leq a,bleq P)
solution
无脑输出 (2) 和 (P - 1) 就好了
比赛时没看见 (P) 是素数 = =
B
1549B - Gregor and the Pawn Game
题目大意：
给出一个 (n imes n) 的棋盘，我方的所有旗子都在第 (n) 行，敌方的所有棋子都在第一行，问我方有多少棋子能走到第一行。
我方棋子行走的规则：
向正前方走，当且仅当正前方没有敌方棋子的时候 ((i, j) > (i - 1, j))
向对角线方向走，当且仅当对角线方向有敌方棋子的时候 ((i, j) > (i - 1, j - 1),(i, j) > (i - 1, j + 1))
solution
写的贪心水过去了 = =
贪心：先往正前方放，再放左边，最后放右边
复杂度：(O(n))
code
/*
work by:Ariel_
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#define rg register
using namespace std;
const int N = 2e5 + 7;
int read(){
int x = 0,f = 1; char c = getchar();
while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
return x*f;
}
int T, n, vis[N], ans;
char s[N], s2[N];
signed main(){
T = read();
while(T--) {
n = read();
scanf("%s", s + 1), scanf("%s", s2 + 1);
memset(vis, 0, sizeof vis); ans = 0;
for (int i = 1; i <= n; i++) {
if (s2[i] == '1'){
if (s[i] == '0') ans++;
else if(s[i - 1] == '1' && !vis[i - 1]) ans++, vis[i - 1] = 1;
else if(s[i + 1] == '1') ans++, vis[i + 1] = 1;
}
}
printf("%d
", ans);
}
puts("");
return 0;
}
solution 2
二分图最大匹配：
一个棋子有可能到达的终点只有三个，然后让每个棋子向能到达的终点连边，然后跑一个最大匹配就好了
复杂度：(O(nsqrt n))
C
题目大意：有 (n) 个有权值的点和 (m)条边，现在加边，删点和查询 (q) 次操作
加边：保证两个点之间本来没有边
删点：每次删的点满足：
1.它连的点的权值都比它大。
2.至少有一个点和它相连。
3.查询：输出没有被删除的点有哪些
(q, n,m leq 2 imes 10^5)
solution
结论：如果一个点连向一个比权值更大的点，这个点一定会被删，保留下的点所连向的点的权值一定都比它小。
证明： 如果一个点 (u) 连向了一个比它大的点 (v) ，(u) 想要保留下来，一定要连向一个权值比它小的点 (w)，同理，(w) 想要保留下来也要连向一个比它小的点，这样一直连到最后一定会连向最小的点，最小的点就没有点可以连了，推出矛盾。
code
/*
work by:Ariel_
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#define ll long long
#define rg register
using namespace std;
const int N = 3e5 + 7;
int read(){
int x = 0,f = 1; char c = getchar();
while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
return x*f;
}
int n, m, fag[N], Ans;
int main() {
n = read(),m = read();
for (int i = 1; i <= m; i++) {
int u = read(), v = read();
if (u > v) swap(u, v);
if (!fag[u]) Ans++;
fag[u]++;
}
int T = read();
while(T--) {
int opt = read();
if (opt == 1) {
int u = read(), v = read();
if (u > v) swap(u, v);
if (!fag[u]) Ans++;
fag[u]++;
}
if(opt == 2) {
int v = read(), u = read();
if (u > v) swap(u, v);
fag[u]--;
if(!fag[u]) Ans--;
}
if(opt == 3) printf("%d
", n - Ans);
}
return 0;
}
D
题目大意
给出一个长为 (n) 的序列 (a) ，找出一个的子序列，并且存在 (m) 使得序列中所有数 (mod~m) 都相等，最大化这个子序列。
(1leq n leq 2 imes10^5, 1 leq a_ileq10^{18})
solution
题目关键就是构造一个大小为 (n - 1) 的差分数组 (D)，其中 (D_i = abs(A_{i + 1}- A_i)) 。
如果给出一个子序列是合法的，那么任意两个元素差值的差一定 (m) 的倍数，因为 (A) 的每个元素不同，所以可以忽略 (D_i = 0) 的情况。
现在就可以转化为 (GCD) 问题，如果 ([A_i,A_j]) 是一个合法子序列，当且仅当 (GCD(D_i...D_{j - 1}) > 1) ，并且 (m) 就是这个 (GCD)
区间 (GCD) 用线段树或者 (RMQ) 实现。
时间复杂度：(O(nlogn imes log10^{18}))
code
/*
work by:Ariel_
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define rg register
#define int long long
using namespace std;
const int MAXN = 2e5 + 5;
int read(){
int x = 0,f = 1; char c = getchar();
while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
return x*f;
}
int a[MAXN], d[MAXN], T, n, f[MAXN][40];
int gcd(int x, int y) {
if (!y) return x;
return gcd(y, x % y);
}
int query(int l, int r) {
int k = (int)log2(double(r - l + 1));
return gcd(f[l][k], f[r - (1 << k) + 1][k]);
}
signed main(){
T = read();
while(T--) {
n = read();
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 1; i < n; i++) d[i] = abs(a[i + 1] - a[i]);
for (int i = 1; i < n; i++) f[i][0] = d[i];
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
f[i][j] = gcd(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
int sur = 1, ans = 1;
for (int i = 1; i < n; i++) {
while(sur <= i && query(sur, i) == 1) sur++;
ans = max(ans, i - sur + 2);
}
printf("%lld
", ans);
}
puts("");
return 0;
}