ACM | “华为杯”杭州电子科技大学2023新生编程大赛

1001

Problem Description

jjy 每天都有很多课要上，但是回寝室玩游戏同样是一件非常重要的事。如果 jjy 当天的课程数超过 \(5\) 节，他将感到非常疲惫，以至于没有精力启动任何游戏。

jjy 今天有 \(n\) 节课要上，同时想玩一款名为 \(s\) 的游戏。如果 jjy 今晚能启动该游戏，请输出游戏的名称，否则输出 sleep。

Input

测试点包含多组数据。第一行包含一个整数 \(T(1<=T<=100)\) ，表示数据组数。

每组数据仅有一行，包含一个整数 \(n\) 和一个字符串 \(s (1≤n≤10，1≤∣s∣≤20)\) ，分别表示 jjy 今天的课程数和今晚想玩的游戏的名称。

Output

每组数据包含一个字符串，如果 jjy 今晚能启动他想玩的游戏，输出游戏名称，否则输出 sleep。

Sample Input

2
6 genshinimpact
5 codeforces

Sample Output

sleep
codeforces

Hint

样例共有两组数据：

第一组数据，jjy 的课程数超过了 \(5\) 节，因此他不能启动 genshinimpact。

第二组数据，jjy 的课程数不超过 \(5\) 节，因此他可以启动 codeforces。

1002

Problem Description 如果一个字符串可以表示成 \(SS^RS\) 的形式，那么称其是完美的。其中， \(S^R\)表示字符串 \(S\) 翻转后的结果，具体来说，如果 \(S\) 为 \(S_1S_2...S_{|S|}\) ，那么 \(S^R\) 为 \(S_{|S|}S_{|S|-1}...S_1\) （∣S∣ 表示字符串 \(S\) 的长度）。

给定一个由小写字母组成的字符串 \(L\) ，求 \(L\) 的最长的完美子串的长度，如果 \(L\) 没有完美子串，请输出 \(0\) 。字符串 \(S\) 是字符串 \(T\) 的子串当且仅当存在两个整数 \(i\) 和 \(j（1≤i≤j≤∣T∣）\) ，使 \(T_iT_{i+1}...T_j\) 和 \(S\) 相同。

Input

测试点包含多组数据。第一行包含一个整数 \(T（1≤T≤5）\) ，表示数据组数。

每组数据包含一个由小写字母组成的字符串 \(L（1≤∣L∣≤2×10^5）\)

Output

每组数据包含一行，表示最长的完美子串的长度。如果没有完美子串，则输出 \(0\) 。

Sample Input

5
abccbbc
aabbaab
abc
abcaacbbcaabbaab
aaaaaaaaa

Sample Output

6
6
0
9
9

Hint

样例共有五组数据：

第一组数据，最长的完美子串可以是 \(bccbbc\) ，长度为 \(6\) 。

第二组数据，最长的完美子串可以是 \(abbaab\)，长度为 \(6\) 。

第三组数据，\(s\) 没有完美子串，因此答案为 \(0\)。

第四组数据，最长的完美子串可以是 \(bcaacbbca\) ，长度为 \(9\) 。

第五组数据，最长的完美子串为 \(s\) 本身，长度为 \(9\) 。

可以证明，每组数据都不存在更长的完美子串。

1003

Problem Description

L 来到了一座罪恶之国。罪恶之国由 \(n\) 个城市和 \(m\) 条单向道路组成，其中没有一条路径能经过一个城市两次，并且任何两个城市之间最多只有一条直接连接的道路。

罪恶之国的每个城市都有一个罪恶值 \(a_i\) 。L 希望离开这里，不幸的是，当 L 的罪恶值超过 \(k\) 时，L 将永远留在这个国家。L 可以选择从任何城市出发，并且他初始的罪恶值为出发城市的罪恶值 \(a_i\) 。之后每当 L 到达一座城市时，L 的罪恶值将会乘上该城市的罪恶值 \(a_i\) 。

L 因为天天“云顶，启动！”，所以已经不想动脑了。于是 L 来问你，一共有多少条不同的路径，使得 L 的罪恶值最后不超过 \(k\) 。两条路径不同当且仅当其对应的城市序列不同，且允许存在起点和终点相同的路径。

请输出答案对 \(998244353\) 取模后的结果。

Input

测试点包含多组数据。第一行包含一个整数 \(T（1≤T≤5）\) ，表示数据组数。每组数据输入格式如下：

第一行包含三个整数 \(n,m\) 和 \(k（1≤n,m≤1000，1≤k≤10^9）\)，分别表示城市的数量、道路的数量和罪恶值的上限。

第二行包含 \(n\) 个整数 \(a_1,a_2,...,a_n（1≤a_i≤10^9）\)，分别表示每个城市的罪恶值。

接下来 \(m\) 行，每行包含两个不同的整数 \(u\) 和 \(v（1≤u,v≤n）\)，表示存在一条 \(u\) 到 \(v\) 的单向道路，保证没有一条路径能经过一个城市两次，并且任何两个城市之间最多只有一条直接连接的道路。

Output

每组数据包含一个整数，表示路径数量对 \(998244353\) 取模后的结果。

Sample Input

1
4 6 99999999  
100 100 100 100  
1 2  
1 3  
2 3  
3 4  
2 4  
1 4

Sample Output

14

Hint

样例中，共有 \(14\) 条合法路径，分别是 [1,2,3]、[1,2,4]、[1,3,4]、[2,3,4]、[1,2]、[1,3]、[1,4]、[2,3]、[2,4]、[3,4]、[1]、[2]、[3] 和 [4]。只有路径 [1,2,3,4] 不符合条件。

1004

Problem Description

jjy 最近对智能车很感兴趣，于是他去实验室借了一辆玩。不幸的是，他发现智能车没有装配电池。

于是 jjy 购买了 \(n\) 个电池，其中第 \(i\) 个电池能够提供 \(p_i\) 的电力，智能车需要恰好 \(C\) 的电力才能正常启动。另外，如果同时装配了两枚电力差距过大的电池，智能车可能会变得不稳定。

jjy 需要选择一些电池来启动智能车，并使装配的电池中电力的最大值和最小值相差最小，请你告诉他最小的差值。如果没有任何一种启动智能车的方案，请输出 \(-1\) 。

Input

测试点包含多组数据。第一行包含一个整数 \(T（1≤T≤10）\) ，表示数据组数。每组数据输入格式如下：

第一行包含两个整数 \(n\) 和 \(C（1≤n≤5×10^4，1≤C≤500）\)，分别表示电池的数量和启动智能车需要的电力。

第二行包含 \(n\) 个整数 \(p_1,p_2,...,p_n(1≤p_i≤C)\) ，分别表示每个电池提供的电力。

Output

每组数据包含一个整数，表示最小差值。如果没有任何一种启动智能车的方案，输出 \(-1\) 。

Sample Input

1
4 10
3 7 2 5

Sample Output

3

Hint

样例中，一种可行的方案是 [3,2,5]，差值为 \(3\) 。可以证明不存在差值更小的方案。

1005

Problem Description

给定一棵包含 \(n\) 个节点的带边权的树，树是一个无环的无向联通图。定义 \(xordist(u,v)\) 为节点 \(u\) 到 \(v\) 的简单路径上所有边权值的异或和。

有 \(q\) 次询问，每次给出 l r x，求 \(\sum_{i=l}^{r}{xordist(i,x)}\) 的值。

Input

测试点包含多组数据。第一行包含一个整数 \(T(1≤T≤10）\)，表示数据组数。每组数据的输入格式如下：

第一行包含一个整数 \(n(1≤n≤10^5)\)，表示节点的个数。

接下来 \(n−1\) 行，每行包含三个整数 \(u,v\) 和 \(w(1≤u,v≤n,0≤w<2^{30})\) ，表示 \(u\) 和 \(v\) 之间存在一条权值为 \(w\) 的无向边。保证输入是一棵树。

接下来一行，包含一个整数 \(q(1≤q≤10^5)\)，表示询问的次数。

接下来 \(q\) 行，每行包含三个整数 \(l,r\) 和 $x(1≤l≤r≤n,1≤x≤n)，分别表示每次询问的信息，其含义已在上文说明。

Output

每组数据包含 \(q\) 行，每行一个整数，表示每次询问的答案。

Sample Input

1
4
1 2 1
1 3 2
3 4 4
2
1 4 3
1 2 4

Sample Output

9
13

Hint

本题输入数据较多，建议大家使用关闭同步流后的 cin和 cout 输入输出。具体代码如下：

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
   
    // you code

    return 0;
}

样例中的树如下图所示：

对于第一个询问，答案为 \(2+1⨁2+4=2+3+4=9\) 。 对于第二个询问，答案为 \(2⨁4+1⨁2⨁4=6+7=13\) 。

1006

Problem Description

最近，M 迷上了打台球，他前几天被 \(L\) 爆杀了，现在正在苦练翻袋，他认为空心翻袋才是最牛的。

台球桌是一个 \(n×m\) 的矩形（保证 \(n\) 是偶数），其左上角位于坐标 \((0,0)\) 处，右下角位于坐标 \((n,m)\) 处。台球桌边缘有六个袋口，分别位于坐标 \((0,0)、(0,m)、(\frac{n}{2},0)、(\frac{n}{2},m)、(n,0)\) 和 \((n,m)\) 处。

此刻，台面上仅剩下一颗白球和一颗黑球，白球位于坐标 \((x_1,y_1)\) 的位置，黑球位于坐标 \((x_2,y_2)\) 的位置，保证白球和黑球位置不同且都不位于台球桌边缘。M 觉得这是个绝佳的机会，他用尽全力将白球对心击向黑球，此后黑球会沿连线方向运动（后续白球的运动情况忽略）。台球和袋口的体积忽略不计，一旦台球和袋口坐标重合将会直接入袋。台球碰到台球桌边缘将会沿镜面反射方向继续运动。

由于这是一次全力以赴的击打，黑球进入袋口前将不会停下，M 想知道黑球最终会经过几次反弹后进入哪个袋口，请输出反弹次数和入袋坐标。如果黑球永远无法入袋，请输出 \(-1\) 。

Input

测试点包含多组数据。第一行包含一个整数 \(T(1≤T≤5×10^4)\) ，表示数据组数。每组数据输入格式如下：

第一行包含两个整数 \(n\) 和 \(m(20≤n,m≤10^6,保证 n 是偶数)\) ，分别表示台球桌的长和宽。

第二行包含两个整数 \(x_1\) 和 \(y_1(0< x_1 < n, 0< y_1 < m)\) 表示白球的位置。

第三行包含两个整数 \(x_2\) 和 \(y_2(0< x_2 < n, 0< y_2 < m)\) 表示黑球的位置。

保证白球和黑球位置不同。

Output

每组数据包含一行，如果黑球能入袋，输出三个整数，表示反弹次数和入袋坐标，否则输出 \(-1\) 。

Sample Input

2
60 30
50 20
40 10
58 41
5 29
38 29

Sample Output

0 30 0
-1

Hint

样例共有两组数据：

第一组数据，黑球会直接进入位于 \((30,0)\) 的袋口。

第二组数据，可以证明黑球永远无法入袋。