【赛题整理】CF OTC2020 A~F Sol

碍于自身实力,只能整理到 $\rm F$ 了233.

A

给定两个均不含相同数字的序列,分别重排之后使得 $\forall i,a_i+b_i$ 均不同。

排序。排序的正确性在于令 $c_i=a_i+b_i$,$\forall i>1,c_i>c_{i-1}$ 保证了不同。

B

给定一个括号序列,求至少删除多少次使得原序列中不存在「好子序列」并输出删除方案,如果本身就没有「好子序列」则输出 $0$。

「好子序列」的定义是长度为 $2k$ 且 $1\sim k$ 都为 ( ,$k+1\sim 2k$ 都是 ) 的子序列。删除操作规定每次只能选择原序列中的一个「好子序列」并删除其中的全部元素。

$n\leq 5000$

发现显然至少删除一次即可。那么只需要记录每个左括号和右括号的位置,找一个位置 $p$ 使得前面的左括号和右面的右括号一样多且最大。$0$ 的情况是存在某个 $p$ 使得 $p$ 前缀都是 ) 并且 $p+1$ 后缀都是 ( 。判断一下即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main(){
cin >> (s + 1) ;
int n = strlen(s + 1) ;
for (int i = 1 ; i <= n ; ++ i){
if (s[i] == '(') l[++ l[0]] = i, sum[i] = sum[i - 1] ;
if (s[i] == ')') r[++ r[0]] = i, sum[i] = sum[i - 1] + 1 ;
}
for (int i = 0 ; i <= n ; ++ i)
if (sum[i] == i && sum[i] == sum[n]) return puts("0"), 0 ;
int L = 1, R = r[0] ;
while (1){
if (l[L] > r[R]) break ; ++ ans;
stk[++ tp] = l[L], stk[++ tp] = r[R] ;
L ++ ; R -- ; if (L > l[0] || !R) break ;
}
sort(stk + 1, stk + tp + 1) ;
cout << 1 << endl << ans * 2 << endl ;
for (int i = 1 ; i <= ans * 2 ; ++ i) cout << stk[i] << " " ;
}

C

给定序列 $a_i$,求 $\prod _{1\leq i<j\leq n}|a_i-a_j|\bmod m$ 。

$1\leq n\leq 10^5,m\leq 1000$ 。

妙妙题。发现直接做不容易并且 $m$ 很小,于是选择观察性质。考虑鸽笼原理,当 $n>m$ 时,必有两项 $a_i,a_j$ 模 $m$ 同余。所以如果 $n>m$ 答案就是 $0$,否则暴力即可。

1
2
3
4
5
6
7
8
9
10
int main(){
cin >> n >> m ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%lld", &base[i]) ;
if (n > m) return puts("0"), 0 ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = i + 1 ; j <= n ; ++ j)
(ans *= (LL)abs(base[i] - base[j])) %= m ;
cout << ans << endl ;
}

D

交互题。给定一个树,每次可以随便询问两个点 $p,q$ 的 $lca$ 。在询问至多 $\frac{n}{2}$ 次后找出树的根。

$1\leq n\leq 1000$

考虑从何处入手。发现对于一棵无根树,最容易辨别的就是叶子。那么只需要每次找出两个当前 $\deg$ 为 $1$ 的点,询问 $lca$ 并删除即可。这样次数一定是 $\lfloor\frac{n}{2}\rfloor$。如果 $p,q$ 有一个点为根,那么存在一个是两一个的祖先,这时输出即可。

这还是第一次在CF写交互题233

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
int ctn ;
struct Edge{
int to ;
int next ;
}E[N << 1] ;
int deg[N] ;
int cnt, n ;
int head[N] ;
queue <int> q ;

void add(int u, int v){
to(++ cnt) = v ;
next(cnt) = head[u] ;
head[u] = cnt ; ++ deg[v] ;
}

int main(){
cin.tie(0) ; cout.tie(0) ;
cin >> n ; int u, v ;
for (int i = 1 ; i < n ; ++ i){
scanf("%d%d", &u, &v) ;
add(u, v) ; add(v, u) ;
}
for (int i = 1 ; i <= n ; ++ i)
if (deg[i] == 1) q.push(i) ;
while (q.size() > 1){
int x = q.front() ; q.pop() ;
int y = q.front() ; q.pop() ; int w ;
cout << "? " << x << " " << y << endl ;
//cout.flush() ;
cin >> w ;
if (w == x || w == y){
cout << "! " << w << endl ;
cout.flush() ; return 0 ;
}
for (int i = head[x] ; i ; i = next(i))
if ((-- deg[to(i)]) == 1) q.push(to(i)) ;
for (int i = head[y] ; i ; i = next(i))
if ((-- deg[to(i)]) == 1) q.push(to(i)) ;
}
cout << "! " << q.front() << endl ;// cout.flush() ; return 0 ;
}

E

构造一个序列 $a$ 满足如下:

1、长度为 $n$ 。

2、$\forall i, 1\leq a_i\leq 10^9$ 。

3、$\forall i>1,a_i>a_{i-1}$。

4、满足 $i<j<k$ 且 $a_i+a_j=a_k$ 的三元组 $(i,j,k)$ 数量恰好为 $m$。

$n\leq 5000,m\leq 10^9$ 。

比较自然的想法是从头开始填 $1,2,3\cdots$,因为这样容易填且满足条件。同时可以发现,这种构造方式是使得每个位置作为 $k$ 时,贡献三元组最多的方式:由于序列满足单调性,所以一定不存在前面的 $i,j$ 彼此有交。那么对于一个 $a_k=k$ 他可以贡献 $\lfloor \frac{k-1}{2}\rfloor$ 的答案。

考虑如果超出 $m$ 如何处理。假设当前答案超出了 $x$ 。对于一个 $k$ ,按照上述方式能够贡献 $\lfloor \frac{k-1}{2}\rfloor$ 的答案,那么如果想要只贡献 $\lfloor \frac{k-1}{2}\rfloor-x$ 的答案,就需要让其中的 $x$ 对 $(i,j)$ 无效。具体的,考虑令当前的 $k$ 变为 $k+2x$ ,那么考虑前 $k-1$ 个数里面最大的是 $k-1$ ,只能去匹配 $2x+1$,这样就会少掉 $2x$ 个可以用的数,答案变成了 $\lfloor\frac{k-1-2x}{2}\rfloor=\lfloor \frac{k-1}{2}\rfloor-x$ 。

那么补齐 $n$ 个数也很简单。只需要考虑如果当前填了的最大的数是 $j$ ,从 $10^9$ 向下按照 $2\cdot j$ 的步长递减即可。不难证明这样做是对的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main(){
std :: cin >> n >> m ;
for (int i = 1 ; i <= n ; ++ i){
ans[i] = i ; cnt += (i - 1) / 2 ;
if (cnt >= m){
int s = 1000000000 ;
ans[i] += 2 * (cnt - m) ;
for (int j = n ; j > i ; -- j)
ans[j] = (s -= (ans[i] + 1)) ;
gf = 1 ; break ;
}
}
if (gf)
for (int i = 1 ; i <= n ; ++ i)
printf("%d ", ans[i]) ;
else return puts("-1"), 0 ;
}

F

给定 $n$ 个数。每次可以选择将一个数 $+1$ 或 $-1$ 。求至少多少次使得整个序列的 $\gcd>1$ 。

$n\leq 10^5,a_i\leq 10^{12}$ 。

首先有一个结论,就是至多需要 $O(\frac{n}{2})$ 次操作就可以使得整个序列的 $\gcd>1$,因为永远可以把 $2$ 当做因子。那么就可以得出一个结论,至多只会有 $\frac{n}{2}$ 个数会被改掉,那么也就说明如果随机一个数的话,有 $\frac{1}{2}$ 的概率不会被改。所以可以将整个序列 shuffle 一下取前几十个check一下即可。

还有,cf的评测系统是windows,rand() 做种子的时候只能打乱前 $32767$ 项。所以需要 mt19937 做种子。

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
typedef long long LL ;

const int N = 200010 ;
const int M = 1000100 ;

int n ;
LL ans ;
int cnt ;
int pr[M] ;
LL base[N] ;
bool chk[M] ;
set <LL> facs ;

void sieve(){
for (int i = 2 ; i < M ; ++ i){
if (!chk[i]) pr[++ cnt] = i ;
for (int j = 1 ; j <= cnt ; ++ j){
if (pr[j] * i >= M) break ;
chk[i * pr[j]] = 1 ;
if (i % pr[j] == 0) break ;
}
}
}
void Ins(LL x){
if (x <= 1) return ;
for (int i = 1 ; i <= cnt ; ++ i)
if (x % pr[i] == 0){
facs.insert(pr[i]) ;
while (!(x % pr[i])) x /= pr[i] ;
}
if (x > 1) facs.insert(x) ;
}
LL calc(LL x){
LL ret = 0 ;
for (int i = 1 ; i <= n ; ++ i)
ret += base[i] >= x ? min(base[i] % x, - (base[i] % x) + x) : x - base[i] ;
//cout << ret << endl ;
return ret ;
}
int main(){
cin >> n ;
sieve() ; ans = n ;
random_device seed ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%lld", &base[i]) ;
mt19937 gg(seed()); shuffle(base + 1, base + n + 1, gg);
for (int i = 1 ; i <= 30 && i <= n ; ++ i)
Ins(base[i]), Ins(base[i] + 1), Ins(base[i] - 1) ;
for (LL res : facs) ans = min(ans, calc(res)) ; cout << ans << endl ;
}