Codeforces Round #651 (Div. 2)

Tsukkomi

好久没上 Codeforces ,家里的网络平时连镜像都上不去 orz
今天试了一下居然又能打开了,随便找了一场 Div.2 玩玩 qwq


Problem A. Maximum GCD

Description

给定 nn (2n106)\left(2\leq n\leq10^6\right) ,求 max1a<bngcd(a,b)\max\limits_{1\leq a<b\leq n}\gcd\left(a,b\right) .
tt (1t102)\left(1\leq t\leq10^2\right) 组测试。

Solution

签到题。

a=n2, b=2aa=\left\lfloor\frac n2\right\rfloor,\ b=2a 即可,则 gcd(a,b)=n2\gcd\left(a,b\right)=\left\lfloor\frac n2\right\rfloor .

时间复杂度:O(t)\mathcal O\left(t\right) .

Code

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
using namespace std;

int t, n;

int main(void) {
scanf("%d", &t);
while (t--) scanf("%d", &n), printf("%d\n", n / 2);
return 0;
}

Problem B. GCD Compression

Description

给定长度为 2n2n (2n103)\left(2\leq n\leq10^3\right) 的序列 aa (1ai103)\left(1\leq a_i\leq10^3\right) .
现可通过以下操作生成长度为 n1n-1 的序列 bb

  • 初始时 bb 为空,先从 aa 中选取两个元素删去。
  • 不断从 aa 中选两元素 ax,aya_x,a_y 删去并将 ax+aya_x+a_y 加入 bb ,直至 aa 为空。

要求 gcd(b1,b2,,bn1)>1\gcd\left(b_1,b_2,\dots,b_{n-1}\right)>1 ,求生成 bb 的一种方案并输出所有二元组 (x,y)\left(x,y\right) .
tt (1t10)\left(1\leq t\leq10\right) 组测试。

Solution

简单的 构造题

设序列 aa 中共 cntcnt 个奇数元素,分情况考虑:

  • cntcnt 为奇数时,从 aa 中删去元素 一奇一偶
  • cntcnt 为偶数时,从 aa 中删去两个 奇偶性相同 的元素。

显然可将 aa 中奇偶性相同的元素两两配对,则 gcd(b1,b2,,bn1)2>1\gcd\left(b_1,b_2,\dots,b_{n-1}\right)\geq2>1 .

时间复杂度:O(tn)\mathcal O\left(tn\right) .

Code

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
#include <bits/stdc++.h>
using namespace std;

int t, n;
vector<int> idx[2];

void solve(void);

int main(void) {
scanf("%d", &t);
while (t--) solve();
return 0;
}

void solve(void) {
scanf("%d", &n), n <<= 1, idx[0].clear(), idx[1].clear();
for (int i = 1, a; i <= n; i++) scanf("%d", &a), idx[a & 1].push_back(i);
if (idx[1].size() & 1) idx[0].pop_back(), idx[1].pop_back();
else {
int x = idx[0].empty() ? 1 : 0;
idx[x].pop_back(), idx[x].pop_back();
}
for (int i = 0; i < 2; i++)
for (int j = 0; j < idx[i].size(); j += 2)
printf("%d %d\n", idx[i][j], idx[i][j + 1]);
}

Problem C. Number Game

Description

给定整数 nn (1n109)\left(1\leq n\leq10^9\right) ,两人玩一个游戏,规则如下:

  • 两人轮流从以下操作中选一种进行:
    • dn, 2d, d>1\exists d\mid n,\ 2\nmid d,\ d>1 ,令 n=ndn=\frac nd .
    • n>1n>1 ,令 n=n1n=n-1 .
  • 轮到某人时若无法操作,则轮到的人输。

若先手必胜输出字符串 Ashishgup ,否则输出字符串 FastestFinger .
tt (1n102)\left(1\leq n\leq10^2\right) 组测试。

Solution

简单的 博弈题

n=2kdn=2^kd (k0, 2d)\left(k\geq0,\ 2\nmid d\right) ,分情况考虑:

  • k1k\neq1 时,显然若 d>1d>1 则先手必胜,否则先手必败。
  • k=1k=1 时,显然若 d=1d=1 则先手必胜,否则若 dd 为素数则先手必败。
    否则设 d=mpd=mp (m>1, pprime)\left(m>1,\ p\in prime\right) ,先手令 n=nmn=\frac nm 即可必胜。

时间复杂度:O(tn)\mathcal O\left(t\sqrt n\right) .

Code

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
#include <bits/stdc++.h>
using namespace std;

int t, n;
int k;

bool solve(void);
bool isprime(int x);

int main(void) {
scanf("%d", &t);
while (t--) puts(solve() ? "Ashishgup" : "FastestFinger");
return 0;
}

bool solve(void) {
scanf("%d", &n), k = 0;
while (!(n & 1)) n >>= 1, k++;
if (k ^ 1) return n > 1;
return n == 1 || !isprime(n);
}

bool isprime(int x) {
if (x < 2) return false;
if (x < 4) return true;
if (x % 6 != 1 && x % 6 != 5) return false;
for (int i = 5; i * i <= x; i += 6)
if (!(x % i) || !(x % (i + 2))) return false;
return true;
}

Problem D. Odd-Even Subsequence

Description

记序列 ss 的价值为 min{max(s1,s3,s5,),max(s2,s4,s6,)}\min\left\{\max\left(s_1,s_3,s_5,\dots\right),\max\left(s_2,s_4,s_6,\dots\right)\right\} .
给定长度为 nn (2n2×105)\left(2\leq n\leq2\times10^5\right) 的序列 aa (1ai109)\left(1\leq a_i\leq10^9\right) .
序列 aa 存在长度为 kk (2kn)\left(2\leq k\leq n\right) 且价值最小的子序列,求这个最小价值。

Solution

二分答案 ansans ,检查是否存在价值不超过 ansans 的子序列即可。

时间复杂度:O(nloga)\mathcal O\left(n\log a\right) .

Code

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
#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)

const int N = 2e5 + 5;
int n, k, a[N];
int l, r;

void solve(void);
bool check(int x);

int main(void) { return solve(), 0; }

void solve(void) {
scanf("%d%d", &n, &k), l = r = 1;
for (int i = 1; i <= n; i++) scanf("%d", a + i), r = max(r, a[i]);
while (l < r) check(mid) ? r = mid : l = mid + 1;
printf("%d\n", mid);
}

bool check(int x) {
for (int i = 0, ct = 0; i < 2; i++, ct = 0) {
for (int j = 1; j <= n; j++) ct += (ct & 1) == i || a[j] <= x;
if (ct >= k) return true;
}
return false;
}

Problem E. Binary Subsequence Rotation

Description

给定两个长度为 nn (1n106)\left(1\leq n\leq10^6\right)0101s,ts,t .
记下标集合 [n]={1,2,,n}\left[n\right]=\left\{1,2,\dots,n\right\} ,现可对 ss 进行一种操作:
S={i1,i2,,ik}[n]S=\left\{i_1,i_2,\dots,i_k\right\}\subseteq\left[n\right] ,令 si1=sik, sij=sij1s_{i_1}=s_{i_k},\ s_{i_j}=s_{i_{j-1}} (j=2,3,,k)\left(j=2,3,\dots,k\right) .
求将 ss 变为 tt 至少需要多少次操作,若 ss 不能变为 tt 输出 1-1 .

Solution

显然只有当组成 s,ts,t0,10,1 的数量分别相同时 ss 才能变为 tt .
若考虑对同一个 S[n]S\subseteq\left[n\right] 进行多次操作的情况,则非常复杂。
注意到这种情况可转化为对 [n]\left[n\right] 的若干不同子集分别进行一次操作。
于是可以考虑对 [n]\left[n\right] 的每个子集至多进行一次操作。
只考虑 s,ts,t 不同位的下标,贪心 即可。

时间复杂度:O(n)\mathcal O\left(n\right) .

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
int n, s[N];
int eq, ans, ct[2];

void solve(void);

int main(void) { return solve(), 0; }

void solve(void) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%1d", s + i);
for (int i = 1, t; i <= n; i++) {
scanf("%1d", &t);
if (t == s[i]) continue;
eq += t ? 1 : -1, ans += !ct[t ^ 1];
ct[t ^ 1] -= ct[t ^ 1] > 0, ct[t]++;
}
if (eq) return puts("-1"), void();
printf("%d\n", ans);
}

Problem F. The Hidden Pair

Description

给定一棵 nn (2n103)\left(2\leq n\leq10^3\right) 个点的无根树,每条树边以 (u,v)\left(u,v\right) 的形式给出。
树边的边权均为 11 ,记 disu,vdis_{u,v} 为点 uu 到点 vv 的简单路径的长度。
现这 nn 个点中有两个隐藏点 s,hs,h ,可进行询问操作:
(?,c,a)\left(?,c,a\right) (1c,ain, a=c)\left(1\leq c,a_i\leq n,\ \left|a\right|=c\right) ,其中 a={a1,a2,,ac}a=\left\{a_1,a_2,\dots,a_c\right\} 是一个集合。
(?,c,a)\left(?,c,a\right) 表示求使得 d=disai,s+disai,fd=dis_{a_i,s}+dis_{a_i,f} 最小的二元组 (ai,d)\left(a_i,d\right) .
要求在 1111 次询问内求出隐藏点 s,hs,h ,输出三元组 (!,s,h)\left(!,s,h\right) .
tt (1t10)\left(1\leq t\leq10\right) 组测试,每组测试末需读入测试结果 Correct / Incorrect​ .
注意,询问非法返回二元组 (1,1)\left(-1,-1\right)s,hs,h 不正确测试结果为 Incorrect​ .

Solution

好玩的 交互题 ~

先取 a=[n]={1,2,,n}a=\left[n\right]=\left\{1,2,\dots,n\right\} 进行询问,得到二元组 (rt,len)\left(rt,len\right) .
rtrt 作为根结点将无根树转化为有根树,则 rtrts,hs,hLCAdiss,h=lendis_{s,h}=len .
记点 uu 的深度为 depudep_u ,集合 Si={u1un, depu=i}S_i=\left\{u\big|1\leq u\leq n,\ dep_u=i\right\} .
不妨设 depsdephdep_s\leq dep_hdeprt=0dep_{rt}=0 ,取 l=len2, r=lenl=\left\lceil\frac{len}2\right\rceil,\ r=len 二分dephdep_h .
设当前二分的答案为 kk ,检查 a=Ska=S_k 时询问结果 dd 是否等于 lenlen 即可。
这里至多用 logn2=9\left\lceil\log\frac n2\right\rceil=9 次询问操作即可得到 (h,deph)\left(h,dep_h\right) .
记点 uu'rtrthh 的简单路径上满足 depu=lendephdep_{u'}=len-dep_h 的点
a=Slendeph{u}a=S_{len-dep_h}-\left\{u'\right\} 进行询问即可得到点 ss .

时间复杂度:O(tnlogn)\mathcal O\left(tn\log n\right) .

Code

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
#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)

const int N = 1e3 + 5;
int t, n;
int edg, head[N], to[N << 1], nxt[N << 1];
vector<int> q, S[N];
set<int> L;
int rt, len, u, d, s, h, dep[N], far[N];
char ret[15];

void solve(void);
void add_edge(int u, int v);
void query(const vector<int> &a, int &u, int &d);
void dfs(int u, int f = 0);
bool check(int x);

int main(void) {
scanf("%d", &t);
while (t--) solve();
return 0;
}

void solve(void) {
scanf("%d", &n), q.clear(), L.clear();
edg = 1, memset(head, 0, (n + 1) * sizeof(int));
for (int i = 1, u, v; i < n; i++)
scanf("%d%d", &u, &v), add_edge(u, v), q.push_back(i);
q.push_back(n), query(q, rt, len), assert(~rt);
for (int i = 0; i <= n; i++) S[i].clear();
dep[0] = -1, dfs(rt);
int l = (len + 1) / 2, r = len;
while (l <= r) check(mid) ? l = mid + 1, h = u : r = mid - 1;
for (int u = h; u ^ rt; u = far[u]) L.insert(u);
q.clear(), d = len - dep[h];
for (int x : S[d]) L.find(x) == L.end() ? q.push_back(x) : void();
query(q, s, d), printf("! %d %d\n", s, h);
fflush(stdout), scanf("%s", ret + 1), assert(ret[1] == 'C');
}

inline void add_edge(int u, int v) {
to[++edg] = v, nxt[edg] = head[u], head[u] = edg;
to[++edg] = u, nxt[edg] = head[v], head[v] = edg;
}

void query(const vector<int> &a, int &u, int &d) {
printf("? %d", a.size());
for (int x : a) printf(" %d", x);
putchar('\n'), fflush(stdout), scanf("%d%d", &u, &d);
}

void dfs(int u, int f) {
dep[u] = dep[f] + 1, far[u] = f, S[dep[u]].push_back(u);
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (v ^ f) dfs(v, u);
}
}

inline bool check(int k) {
return !S[k].empty() ? query(S[k], u, d), assert(~u), d == len : false;
}

Welcome to my other publishing channels