CF#736 div2
| 题目 | A | B | C | D | E | F1 | F2 |
|---|---|---|---|---|---|---|---|
| 通过情况 | AC | AC | AC | O | X | X | X |
| 难度 | 800 | 800 | 1400 | 1800 | 2500 | 2300 | 3300 |
A. Gregor and Cryptography
题面
略
解法
略
代码
1 | /* |
B. Gregor and the Pawn Game
题面
略
解法
模拟即可（原来以为会tle)
代码
1 | /* |
C. Web of Lies
题面
略
解法
这题卡了很久，有点想复杂了，以为是并查集，但是加边和删边同时出现确实不好处理，而且大概率会tle。
实际上只要统计每个点有没有与比他大的点相连就行。
代码
1 | /* |
D. Integers Have Friends
题面
略
解法
这题虽然一开始就想到了相邻的数做差，然后找最长的最大公约数不为1的一段，但是确实是题做少了，没有想到用ST表或者线段树来统计而用来奇怪的方法，导致比赛时WA。
代码
ST表1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75/*
* @题目: D. Integers Have Friends
* @算法: ST表
* @Author: Blore
* @Language: c++11
* @Date: 2021-08-02 16:49:39
* @LastEditors: Blore
* @LastEditTime: 2021-08-02 17:00:14
*/
using namespace std;
ll read()
{
ll p = 0, f = 1;
char c = getchar();
while (c < 48 || c > 57)
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= 48 && c <= 57)
p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
return p * f;
}
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll v[maxn];
ll f[maxn][logn + 1];
int Logn[maxn + 1];
void init_logn()
{
Logn[1] = 0;
Logn[2] = 1;
rep(i, 3, maxn) Logn[i] = Logn[i / 2] + 1;
}
ll query(int l, int r)
{
int s = Logn[r - l + 1];
return gcd(f[l][s], f[r - (1 << s) + 1][s]);
}
int main()
{
int t = read();
init_logn();
while (t--)
{
int n = read();
rep(i, 1, n) v[i] = read();
rep(i, 1, n - 1) f[i][0] = abs(v[i] - v[i + 1]);
rep(j, 1, logn)
{
for (int i = 1; i + (1 << j) - 1 <= n - 1; i++)
{
f[i][j] = gcd(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
int ans = 1;
for (int i = 1, j = 1; i <= n - 1; i++)
{
while (j <= i && query(j, i) == 1)
j++;
ans = max(ans, i - j + 2);
}
printf("%d\n", ans);
}
return 0;
}
线段树1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86/*
* @题目: D. Integers Have Friends
* @算法: 线段树
* @Author: Blore
* @Language: c++11
* @Date: 2021-08-01 23:47:16
* @LastEditors: Blore
* @LastEditTime: 2021-08-02 16:13:59
*/
using namespace std;
ll read()
{
ll p = 0, f = 1;
char c = getchar();
while (c < 48 || c > 57)
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= 48 && c <= 57)
p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
return p * f;
}
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll v[maxn], d[maxn];
ll t[maxn << 2];
void build(int rt, int l, int r)
{
if (l == r)
{
t[rt] = d[l];
return;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
t[rt] = gcd(t[rt << 1], t[rt << 1 | 1]);
}
ll query(int rt, int l, int r, int ql, int qr)
{
if (ql <= l && r <= qr)
{
return t[rt];
}
int mid = (l + r) >> 1;
ll tmp1 = 0, tmp2 = 0;
if (ql <= mid)
tmp1 = query(rt << 1, l, mid, ql, qr);
if (qr > mid)
tmp2 = query(rt << 1 | 1, mid + 1, r, ql, qr);
return gcd(tmp1, tmp2);
}
int main()
{
int t = read();
while (t--)
{
int n = read();
rep(i, 1, n) v[i] = read();
if (n == 1)
{
printf("1\n");
continue;
}
rep(i, 1, n - 1) d[i] = abs(v[i] - v[i + 1]);
build(1, 1, n - 1);
int ans = 1;
for (int i = 1, j = 1; i <= n - 1; i++)
{
while (j <= i && query(1, 1, n - 1, j, i) == 1)
j++;
ans = max(ans, i - j + 2);
}
printf("%d\n", ans);
}
return 0;
}