本文合作者：laybxc

题解持续补充…

赛事信息

名称 出题人 开始时间 时长 官方题解
Codeforces Round #709 (Div. 2, based on Technocup 2021 Final Round) Aleks5d
AndreySergunin
Diegogrc
Golovanov399
KAN
amethyst0		 Mar/21/2021
21:20 (UTC+8)		 02:15 Codeforces Round #709 Editorial

A. Prison Break

题目

题目描述

给出 a×ba \times b 的网格，问最少去掉多少条边，可以使得所有格子和外界连通。

输入格式

一行一个整数 t(1≤t≤100)t(1 \leq t \leq 100) ，表示数据组数。

第二行两个整数，表示参数 a，b(1≤a,b≤100)a，b(1 \leq a,b \leq 100) 。

输出格式

一个整数，表示答案

输入输出样例

输入
1
2
3
2
2 2
1 3
输出
1
2
4
3

说明/提示

两组测试数据，可以用以下方案：

img

img

解决方案

思路

代码

1

B. Restore Modulo

题目

题目描述

给出数组 aa ，问是否能按以下方法构造：

存在 n,m,c,sn,m,c,s ； n,m>0n,m>0 ； 0≤c<m0 \leq c<m ； s≥0s \geq 0 。

(1) a1=s%ma1 = s \% m

(2) ai=(ai−1+c)%m(1≤i≤n)a_i = (a_{i-1} + c) \% m \quad (1 \leq i \leq n) ;

如果存在，则找出最大的 mm ，以及任意符合要求的 cc

输入格式

第一行一个整数 t(1≤t≤105)t(1 \leq t \leq 10^5) 。

每组数据第一行一个整数 n(1≤n≤105)n(1 \leq n \leq 10^5) ，表示 aa 数组元素个数。

第二行 nn 个整数 a1，a2，…，an(1≤ai≤109)a_1，a_2，\dots，a_n(1≤a_i≤10^9) ，表示数组 aa 的元素。

输出格式

  • 如果不能，则输出 −1-1 。
  • 如果 mm 可以任意大，则输出 00 。
  • 如果是其他情况，则输出最大的 mm 和任何合法的 c(0≤c<m)c(0 \leq c < m) 。

输入输出样例

输入
1
2
3
4
5
6
7
8
9
10
11
12
13
6
6
1 9 17 6 14 3
3
4 2 2
3
7 3 4
3
2 2 4
5
0 1000000000 0 1000000000 0
2
1 1
输出
1
2
3
4
5
6
19 8
-1
-1
-1
2000000000 1000000000
0

说明/提示

解决方案

思路

代码

1

C. Basic Diplomacy

题目

题目描述

有 nn 个朋友， mm 天，每天找一个朋友玩，且和每个朋友玩的天数不能超过 ⌈m2⌉⌈\frac m 2⌉ 天。

给出每一个朋友具体在哪些天有空。判断是否有方案满足要求，是则给出方案。

输入格式

第一行一个整数 t(1≤t≤10000)t(1≤t≤10000) ，表示数据组数。

接下来每组数据第一行有两个整数 n，m(1≤n,m≤100000)n，m (1≤n,m≤100000)

接下来 mm 行中的第 ii 行有一个整数 kik_i ，其后接着 kik_i 个整数 fi1，fi2，…，fiki(1≤fij≤n)f_{i1}，f_{i2}，\dots，f_{ik_i}(1 \leq f_{ij} \leq n) ，表示第 ii 个朋友在第 fijf_{ij} 天有空。

保证每组数据的 kik_i 之和不超过 200000200000 。

输出格式

对于每组数据：

  • 如果没有合法方案，则输出NO。

  • 否则，第一行输出YES，第二行输出 mm 个整数 c1，c2，…，cmc_1，c_2，\dots，c_m ， cic_i 表示第i天找的朋友的编号。

所有朋友编号出现的次数都必须小于 ⌈m2⌉⌈\frac m 2⌉ 。如果有多种可能方案，输出任意一种即可。

输入输出样例

输入
1
2
3
4
5
6
7
8
9
10
11
2
4 6
1 1
2 1 2
3 1 2 3
4 1 2 3 4
2 2 3
1 3
2 2
1 1
1 1
输出
1
2
3
YES
1 2 1 1 2 3 
NO

说明/提示

解决方案

思路

代码

1

D. Playlist

题目

题目描述

李华有编号 1 n1~n 的 nn 首歌循环播放，每首歌都有一个自己的类型 aia_i 。当现在这首歌和上一首歌的类型的 gcdgcd 等于 11 时，他就会怒删当前这首歌，然后从后面那手歌重新开始听（也就是说不会删连续两首歌），求删除的歌的数量和删除的顺序。

输入格式

第一行一个整数 t(1≤t≤10000)t(1≤t≤10000) ，表示数据组数。

每组数据第一行一个整数 n(1≤n≤105)n(1≤n≤10^5) 。

接下来 nn 个整数 a1，a2，…，an(1≤ai≤109)a_1，a_2，\dots，a_n(1≤a_i≤10^9) 。

输出格式

对于每组数据，先输出一个整数 kk ，表示被删除的歌曲数，接着输出这 kk 首歌曲的编号

输入输出样例

输入
1
2
3
4
5
6
7
8
9
10
11
5
5
5 9 2 10 15
6
1 2 4 2 4 2
2
1 2
1
1
1
2
输出
1
2
3
4
5
2 2 3 
2 2 1 
2 2 1 
1 1 
0

说明/提示

解决方案

思路

代码

1

请参阅