题目描述#

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

输入格式#

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

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

输出格式#

一个整数，表示答案

输入输出样例#

2
2 2
1 3

4
3

说明/提示#

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

思路#

代码#

题目描述#

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

存在 $n,m,c,s$ ； $n,m>0$ ； $0 \leq c<m$ ； $s \geq 0$ 。

(1) $a1 = s \% m$

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

如果存在，则找出最大的 $m$ ，以及任意符合要求的 $c$

输入格式#

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

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

第二行 $n$ 个整数 $a_1，a_2，\dots，a_n(1≤a_i≤10^9)$ ，表示数组 $a$ 的元素。

输出格式#

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

输入输出样例#

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

19 8
-1
-1
-1
2000000000 1000000000
0

说明/提示#

思路#

代码#

题目描述#

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

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

输入格式#

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

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

接下来 $m$ 行中的第 $i$ 行有一个整数 $k_i$ ，其后接着 $k_i$ 个整数 $f_{i1}，f_{i2}，\dots，f_{ik_i}(1 \leq f_{ij} \leq n)$ ，表示第 $i$ 个朋友在第 $f_{ij}$ 天有空。

保证每组数据的 $k_i$ 之和不超过 $200000$ 。

输出格式#

对于每组数据：

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

• 否则，第一行输出YES，第二行输出 $m$ 个整数 $c_1，c_2，\dots，c_m$ ， $c_i$ 表示第i天找的朋友的编号。

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

输入输出样例#

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

YES
1 2 1 1 2 3 
NO

说明/提示#

思路#

代码#

题目描述#

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

输入格式#

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

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

接下来 $n$ 个整数 $a_1，a_2，\dots，a_n(1≤a_i≤10^9)$ 。

输出格式#

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

输入输出样例#

5
5
5 9 2 10 15
6
1 2 4 2 4 2
2
1 2
1
1
1
2

2 2 3 
2 2 1 
2 2 1 
1 1 
0 

说明/提示#

思路#

代码#