北京交通大学第三届C语言积分赛

作者有言在先：
题解的作用是交流思路，不是抄作业的。可以把重点放在思路分析上而不是代码上，毕竟每个人的代码风格是不一样的，看别人的代码就跟做程序填空题一样。先看明白思路再看代码。
还有就是，deepseek真的很好用！！！

A - Lazy Narek

题目翻译

题目描述

Narek 太懒了，不想自己编写这场比赛的第 3 道题目。他的朋友 Artur 建议他使用 ChatGPT。ChatGPT 生成了 ( n ) 道题目，每道题目由 ( m ) 个字母组成，因此 Narek 有 ( n ) 个字符串。为了增加难度，他通过选择其中的一些字符串（可能一个都不选）并按顺序将它们连接起来，形成一个新字符串。他对这道题目的解题概率定义为 ( score_n - score_c )，其中 ( score_n ) 是 Narek 的得分，( score_c ) 是 ChatGPT 的得分。

Narek 通过从左到右检查选中的字符串来计算 ( score_n )。他首先寻找字母 "n"，然后是 "a"、"r"、"e" 和 "k"。每当找到这些字母的所有出现后，他给 ( score_n ) 加 5，然后从当前位置继续寻找下一个 "n"（他不会回溯，而是继续从当前位置开始）。

在 Narek 完成之后，ChatGPT 会扫描整个字符串，对于 Narek 未使用的每个字母 "n"、"a"、"r"、"e" 或 "k"，给 ( score_c ) 加 1。

输入

第一行输入一个整数t（1 ≤ t ≤ 10⁵），表示测试用例的数量。
每个测试用例的第一行输入两个整数 n, m（1 ≤ n, m ≤ 10³），分别表示字符串的数量和每个字符串的长度。
接下来 ( n ) 行，每行输入一个长度为 ( m ) 的字符串，仅包含小写英文字母。
所有测试用例的 n × m 的总和不超过 ( 10⁶ )。

输出

对于每个测试用例，输出一个整数，表示 ( score_n - score_c ) 的最大值。

示例

输入

4
5 2
nn
aa
rr
ee
kk
1 5
narek
1 4
nare
5 7
nrrarek
nrnekan
uuuuuuu
ppppppp
nkarekz

输出

解释

第一个测试用例：Narek 可以选择不选任何字符串，此时得分为 0。如果选择所有字符串，则会形成字符串 nnaarreekk。Narek 可以找到所有的字母，得分为 5；而 ChatGPT 会对未使用的字母各加 1，得分为 5。因此，最终得分为 ( 5 - 5 = 0 )。
第三个测试用例：Narek 如果选择字符串 nare，由于缺少 "k"，无法完成完整的单词 "narek"，因此得分为 0，而 ChatGPT 会对未使用的 4 个字母各加 1，得分为 4。结果为 ( 0 - 4 = -4 )。因此，最佳选择是不选任何字符串，得分为 0。
第四个测试用例：Narek 需要选择第一个和最后一个字符串，形成 nrrareknkarekz。他可以找到所有的字母，得分为 10，而 ChatGPT 会对未使用的 3 个字母各加 1，得分为 3。因此，最终得分为 ( 10 - 3 = 7 )。

B String Task

题目翻译

Petya 开始参加编程课程。在第一节课上，他的任务是编写一个简单的程序。该程序需要完成以下功能：对于给定的由大写和小写拉丁字母组成的字符串，程序需要：

删除所有元音字母，
在每个辅音字母前插入一个字符 .，
将所有大写辅音字母替换为对应的小写字母。

元音字母包括 A, O, Y, E, U, I，其余字母为辅音字母。程序的输入是一个字符串，输出是经过处理后的单个字符串。

请帮助 Petya 完成这个简单的任务。

输入

第一行是 Petya 程序的输入字符串。该字符串仅由大写和小写拉丁字母组成，长度在 1 到 100 之间（包括 1 和 100）。

输出

打印处理后的字符串。保证该字符串不为空。

示例

输入

tour

输出

.t.r

输入

Codeforces

输出

.c.d.f.r.c.s

输入

aBAcAba

输出

.b.c.b

分析

任务：

剔除掉所有aeiouy
剩余字母输出前先输出.
转化为小写字母在输出

优化任务

由于原字符串涉及大小写，而输出只有小写，且为了方便第一项任务的判断，我们对任务转化一下顺序，先进行3操作。

遍历字符串，查看每一个是否合法，合法则输出。

代码及注释

#include<bits/stdc++.h>
using namespace std;const int M = 1000;
char s[M];
char cmp[] = "aoyeui";//非法字符bool check(char t){//判断是否合法for(int i=0 ; i<6 ; i++)if(t==cmp[i]) return false;return true;
}int main()
{scanf("%s", s);int len = strlen(s);for(int i=0 ; i<len ; i++){char c = s[i];if(c < 'a')c += 'a'-'A';//大小写转化if(!check(c)) continue;printf(".%c", c);//合法就输出}return 0;}

总结

时间复杂度：O(n)

~~没有什么含金量，下一题~~

C - Assembly via Minimums

题目翻译

Sasha 有一个包含 n 个整数的数组 a。他觉得无聊，于是对于所有的 i, j（i < j），他写下了 a_i 和 a_j 的最小值，得到了一个新的数组 b，其大小为 n⋅(n−1)/2。

例如，如果 a = [2, 3, 5, 1]，他会写下 [min(2, 3), min(2, 5), min(2, 1), min(3, 5), min(3, 1), min(5, 1)] = [2, 2, 1, 3, 1, 1]。

然后，他随机打乱了数组 b 的所有元素。

不幸的是，他忘记了数组 a，你的任务是恢复一个可能的数组 a，使得可以从它得到数组 b。

数组 a 的元素应处于 [−10^9, 10^9] 范围内。

输入

第一行包含一个整数 t（1 ≤ t ≤ 200）——测试用例的数量。

每个测试用例的第一行包含一个整数 n（2 ≤ n ≤ 10^3）——数组 a 的长度。

每个测试用例的第二行包含 n⋅(n−1)/2 个整数 b_1, b_2, …, b_{n⋅(n−1)/2}（−10^9 ≤ b_i ≤ 10^9）——数组 b 的元素。

保证所有测试用例中 n 的总和不超过 10^3，并且对于每个测试用例中的数组 b，存在一个原始的数组 a。

输出

对于每个测试用例，输出一个可能的长度为 n 的数组 a。

示例

输入

1
4
2 2 1 3 1 1

输出

2 3 5 1

解释

在示例中，给定的 b=[2,2,1,3,1,1]b = [2, 2, 1, 3, 1, 1]b=[2,2,1,3,1,1]，可以通过数组 a=[2,3,5,1]a = [2, 3, 5, 1]a=[2,3,5,1] 得到。

分析

由于只用给出一张情况就好，我们简化亿点点

既然他打乱了数组b的顺序，那我们就给他排序（从小到大）
可以略微思考一下：a数组最小的那个数在b数组里面至少出现了n-1次，而且b数组中最小的数在a中肯定也是最小的（可以反证）
那么我们是不是确定了a数组的一个数：b中的最小数也是a中的最小数
如（2）所说，至少会出现n-1次，那如果出现了更多次，那说明这个最小数不止出现了一次。由于是最小值，那在b数组里至少出现了n-1+n-2=2n-3次，以此类推。若最小值只出现了n-1次，那么下一个数就是次小值了。
由此可推出次小、次次小……次大、最大值。其中最大值可出现两次，因为自己跟自己比还是自己大

优化分析

分析中的第（4）点可以再优化一下。由于我们知道分析完最小值后的b数组中至少还有n-2个相同的最小值，且无论是否与最小值一致我们都需要将此数加入a数组，所以我们不用考虑这个数的值。

模型构建

采用单向指针扫描，向后推移指针的路径递减。详细内容见代码

代码及注释

#include<bits/stdc++.h>
using namespace std;const int M = 1e6;
int a[M], b[M];int main()
{int T; scanf("%d", &T);while(T--)//多组测试数据 {memset(a, 0, sizeof(a));memset(b, 0, sizeof(b)); int n, m;scanf("%d", &n); m = n*(n-1)/2;for(int i=0 ; i<m ; i++)scanf("%d", b+i);sort(b, b+m);int zz = 0;//指针，用于扫描b数组 for(int i=0 ; i<n ; i++){a[i] = b[zz];zz += n-i-1; }a[n-1] = b[m-1]; //最后一个值直接赋值for(int i=0 ; i<n ; i++)printf("%d ", a[i]);puts("");	}return 0;
}

总结

这题很难想，主要是把乱的数组有序化这点想明白就很简单。

D - Grade Allocation

题目翻译

有 ( n ) 名学生正在参加考试。考试的最高分为 ( m )。令 ( a_i ) 表示第 ( i ) 名学生的分数。你可以访问学校的数据库，该数据库存储了所有学生的成绩。

你可以修改每名学生的分数，但需要满足以下条件：

所有分数都是整数。
每个分数满足 ( 0 \leq a_i \leq m )。
班级的平均分数保持不变。

你是第 ( 1 ) 名学生，你希望最大化自己的分数。

请找到一个满足所有条件的最高可能分数，并将其分配给自己。

输入

每个测试包含多个测试用例。

第一行包含测试用例的数量 ( t )（( 1 \leq t \leq 200 )）。随后是每个测试用例的描述。

每个测试用例的第一行包含两个整数 ( n ) 和 ( m )（( 1 \leq n \leq 10^3 )，( 1 \leq m \leq 10^5 )）——分别是学生数量和最高可能分数。

每个测试用例的第二行包含 ( n ) 个整数 ( a_1, a_2, \dots, a_n )（( 0 \leq a_i \leq m )）——学生的分数。

输出

对于每个测试用例，输出一个整数——满足所有条件的情况下，你可以分配给自己的最高可能分数。

示例

输入

输出

10
5

解释

在第一个测试用例中，( a = [1, 2, 3, 4] )，平均分为 ( 2.5 )。你可以将数组修改为 ( [10, 0, 0, 0] )，平均分仍为 ( 2.5 )，且所有条件都满足。
在第二个测试用例中，( 0 \leq a_i \leq 5 )。你可以将数组修改为 ( [5, 1, 1, 3] )。你无法进一步增加 ( a_1 )，否则会违反条件 ( 0 \leq a_i \leq m )。

分析

任务

在保持平均分一致的情况下尽可能保证自己的（1号）的最高分，且不高于最高分

优化任务

均分一样 = 总分一样。总分一样，自己分越高，说明别人的分越低，最低就是0分。假设其余都是0分，那自己就是总分。注意，不要超过最高分。

代码及注释

#include<bits/stdc++.h>
using namespace std;typedef long long LL;int main()
{int T; scanf("%d", &T);while(T--){LL n, mx; scanf("%lld%lld", &n, &mx);LL sum = 0;for(int i=0 ; i<n ; i++){LL t; scanf("%lld", &t);sum += t;}printf("%lld\n", min(mx, sum));//不超过最高分的总分}return 0;}

总结

时间复杂度：O(nm)

~~没有什么含金量，下一题~~

E - Power of Points

题目翻译

你被给定位于数轴上的 n 个整数坐标点 $\ x_1, x_2, \dots, x_n$ 。

对于某个整数 s ，我们构造线段 $\ [s, x_1], [s, x_2], \dots, [s, x_n]$ 。注意，如果 $\ x_i < s $，那么线段看起来会是 $x_i, s]$ 。线段 $\ [a, b]$ 覆盖所有整数点 $\ a, a+1, a+2, \dots, b$ 。

我们定义点 p 的能量 $f_p$ 为与坐标 $\ p$ 相交的线段的数量。

你的任务是计算对于每个 $\ s \in \{x_1, x_2, \dots, x_n\}$ ，即 s 取值为给定点的坐标时，所有整数点 p 从 1 到 10⁹ 的 f_p 的总和。

例如，如果初始坐标为 ([1, 2, 5, 7, 1])，且我们选择 ( s = 5 )，则线段为：
$[1, 5], [2, 5], [5, 5], [5, 7], [1, 5]$

点的能量为：
$f_1 = 2, f_2 = 3, f_3 = 3, f_4 = 3, f_5 = 5, f_6 = 1, f_7 = 1, f_8 = 0, \dots, f_{10^9} = 0$
它们的总和为：
$2 + 3 + 3 + 3 + 5 + 1 + 1 = 18$

输入格式

第一行包含一个整数 t $\leq t \leq 10^4 )$ ，表示测试用例的数量。
每个测试用例的第一行包含一个整数 n $\leq n \leq 2 \cdot 10^5 )$ ，表示点的数量。
第二行包含 n 个整数 $\ x_1, x_2, \dots, x_n$ $\leq x_i \leq 10^9 )$ ，表示点的坐标。
保证所有测试用例的 n 的总和不超过 $\ 2 \cdot 10^5$ 。

输出格式

对于每个测试用例，输出 n 个整数，其中第 i 个整数表示当 $s = x_i$ 时，所有点的能量 $f_p$ 的总和。

示例输入与输出

示例输入：

3
3
1 4 3
5
1 2 5 7 1
4
1 10 100 1000

示例输出：

8 7 6
16 15 18 24 16
1111 1093 1093 2893

代码（未完成）

#include<bits/stdc++.h>
using namespace std;const int M = 10000;
struct P{int place;int value;int front_ans, after_ans;int front_line, after_line;
}point[M];
int n, cnt[M];bool cmp1(P a, P b){return a.value <= b.value;
}int main()
{int T; scanf("%d", &T);while(T--){memset(point, 0, sizeof(point));memst(cnt, 0, sizeof(cnt));scanf("%d", &n);for(int i=0 ; i<n ; i++){scanf("%d", &point[i].value);cnt[point[i].value]++;if(point[i].value!=point[0].value)point[0].after_ans += point[i].value_ans, point[0].after_line++;point[i].place = i;}sort(point, point+n, cmp1); for(int i=0 ; i<n ; ){int t=i, cnt=0;while(point[i].value==point[t].value)t++, cnt++; P x = &point[i], y = &point[t];int dv = y.value-x.value;y.front_ans = x.front_ans+x.front_line*cnt+(y.value-x.value)*cnt;y.front_line = x.front_line+cnt;
//			y.after_ans = x.after_ans-x.after_line*cnti = t;} }return 0;}

F - Binary Imbalance

问题翻译

给定一个仅由字符 '0' 和/或 '1' 组成的字符串 s。

在一次操作中，你可以选择一个位置 i（从 1 到 |s|−1，其中 |s| 是当前字符串的长度）。然后在 s 的第 i 和第 i+1 个字符之间插入一个字符。如果 s_i = s_{i+1}，则插入 '1'；如果 s_i ≠ s_{i+1}，则插入 '0'。

问：是否可以通过任意次数的操作（包括不操作），使得字符串中 '0' 的数量严格大于 '1' 的数量？

输入格式

第一行为一个整数 t（1 ≤ t ≤ 100），表示测试用例的数量。

对于每个测试用例：

第一行为一个整数 n（1 ≤ n ≤ 100），表示字符串的长度。
第二行为一个长度为 n 的字符串 s，仅由字符 '0' 和/或 '1' 组成。

输出格式

对于每个测试用例，如果可以通过操作使字符串中 '0' 的数量严格大于 '1' 的数量，则输出 "YES"；否则输出 "NO"。

示例

输入

输出

YES
NO
YES

示例解释

第一个测试用例：字符串 "00" 中 '0' 的数量已经大于 '1' 的数量，因此输出 "YES"。
第二个测试用例：字符串 "11" 无法通过操作插入任何 '0'，因此输出 "NO"。
第三个测试用例：选择 i=1，在 '1' 和 '0' 之间插入一个 '0'，得到字符串 "100"，其中 '0' 的数量为 2，'1' 的数量为 1，因此输出 "YES"。

分析

由于期望0多一些，那么我们不加1

由于可以无限次加，那么只要有一位能加0，那必然会存在有限次操作使最终的0多于1

原数组若原本就0多，那就不用管了

代码以及注释

#include<bits/stdc++.h>
using namespace std;const int M = 1000;
char c[M];int main()
{int T; scanf("%d", &T);while(T--){bool flag = false;//默认不行int cnt_0=0, cnt_1=0, n;memset(c, 0, sizeof(c));scanf("%d%s", &n, c);for(int i=0 ; i<n ; i++){int a = c[i]-'0';if(a) cnt_1++;else cnt_0++;if(i && c[i]!=c[i-1])//找到了等插入0的位置flag = true;}if(cnt_0>cnt_1)	flag = true;//本来就符合if(flag) puts("YES");else puts("NO");}return 0;
}

G - Lucky Chains

题目翻译

我们称一对正整数 (x, y) 为幸运的，当且仅当它们的最大公约数等于 1，即 gcd(x, y) = 1。

我们定义由 (x, y) 诱导的链为一个序列，其中包含以下对：(x, y), (x+1, y+1), (x+2, y+2), …, (x+k, y+k)，其中 k ≥ 0 为整数。该链的长度为链中元素的数量，即 (k+1)。

如果该链中的所有对都是幸运的，那么我们称这条链为幸运链。

给定 n 对数 (x_i, y_i)，请为每对计算由其诱导的最长幸运链的长度。注意，如果 (x_i, y_i) 本身不是幸运的，则链的长度为 0。

输入格式

第一行为一个整数 n（1 ≤ n ≤ 10^6），表示对数。

接下来的 n 行，每行包含两个整数 x_i 和 y_i（1 ≤ x_i < y_i ≤ 10^7），表示第 i 对。

输出格式

输出 n 个整数，其中第 i 个整数表示由 (x_i, y_i) 诱导的最长幸运链的长度。如果该链可以无限长，则输出 -1。

示例

输入

4
5 15
13 37
8 9
10009 20000

输出

示例解释

第一个测试用例：gcd(5, 15) = 5 > 1，因此它本身不是幸运的，幸运链的长度为 0。
第二个测试用例：gcd(14, 38) = 2，因此幸运链仅包含 (13, 37)，长度为 1。
第三个测试用例：gcd(8+k, 9+k) = 1 对所有 k ≥ 0 成立，因此幸运链可以无限长，输出 -1。
第四个测试用例：最长幸运链的长度为 79。

约束条件

输入的对数 n 最多为 10⁶。
每对 (x, y) 满足 1 ≤ x < y ≤ 10⁷。

分析

问题分析

我们需要为每对 (x, y) 计算由其诱导的最长幸运链的长度。幸运链的定义是链中的所有对 (x+k, y+k) 都必须满足 gcd(x+k, y+k) = 1。如果链可以无限延伸，则输出 -1；否则输出链的长度。

关键观察

链的性质：
链的形式为 (x+k, y+k)，其中 k 从 0 开始递增。我们可以将链中的任意对表示为 (x+k, y+k)。
最大公约数的性质：
对于链中的每个对，有：

$\gcd⁡(x+k,y+k)=gcd⁡(x+k,(y+k)−(x+k))=gcd⁡(x+k,y−x)\gcd(x+k, y+k) = \gcd(x+k, (y+k) - (x+k)) = \gcd(x+k, y - x)gcd(x+k,y+k)=gcd(x+k,(y+k)−(x+k))=gcd(x+k,y−x)$

因此，gcd(x+k, y+k) 的值取决于 gcd(x+k, y - x)。
问题转化：
我们需要找到最大的 k，使得对于所有 0 ≤ i ≤ k，都有 gcd(x+i, y - x) = 1。如果对于所有 k ≥ 0，都有 gcd(x+k, y - x) = 1，则链可以无限延伸，输出 -1。
终止条件：
如果 gcd(x+k, y - x) > 1，则链在第 k 步终止，链的长度为 k。

算法思路

特判：
如果 gcd(x, y) > 1，则链的长度为 0，因为第一个对本身不满足条件。
计算 d = y - x：
计算差值 d = y - x，因为 gcd(x+k, y+k) 的值取决于 gcd(x+k, d)。
检查 gcd(x+k, d)：
- 如果 d = 1，则对于任意 k，gcd(x+k, 1) = 1，因此链可以无限延伸，输出 -1。
- 否则，我们需要找到最小的 k，使得 gcd(x+k, d) > 1。如果找不到这样的 k，则链可以无限延伸，输出 -1；否则输出 k。
查找最小的 k：
我们需要找到最小的 k，使得 gcd(x+k, d) > 1。这可以转化为找到使 x+k 与 d 有非 1 公约数的 k。
- 找到 d 的所有质因数。
- 对于每个质因数 p，计算最小的 k 使得 p 整除 x+k，即 k ≡ -x \mod p。
- 取所有质因数对应的 k 的最小值。

算法步骤

对于每对 (x, y)，计算 d = y - x。
如果 d = 1，输出 -1。
否则，找到 d 的所有质因数。
对于每个质因数 p，计算最小的 k 使得 p 整除 x+k，即 k = (p - x % p) % p。
取所有质因数对应的 k 的最小值。如果存在这样的 k，输出 k；否则输出 -1。

时间复杂度分析

质因数分解：
质因数分解的时间复杂度为 O(sqrt(d))，其中 d = y - x。
总复杂度：
对于 n 个测试用例，总复杂度为 O(n * sqrt(d_max))，在数据范围内可以接受。

代码及注释

#include<bits/stdc++.h>
using namespace std;const int M = 10000000; 
int zs[M/10], cnt_zs; 
bool flag[M+1];// 筛质数函数
void szs(){for (int i=2; i<=M; i++) {if (!flag[i]) {zs[cnt_zs++] = i;for (int j=2*i; j<=M; j+=i){flag[j] = true;}}}
}int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);
}int main() {szs();int n;scanf("%d", &n);while (n--) {int x, y;scanf("%d%d", &x, &y);int d = y - x;// 特判：d = 1，链可以无限延伸if (d == 1) {puts("-1");continue;}// 特判：gcd(x, y) != 1，链长度为 0if (gcd(x, y) != 1) {puts("0");continue;}// 初始化结果为最大值int res = M + 1;// 对 d 进行质因数分解for (int i=0; i<cnt_zs && zs[i]*zs[i]<=d; i++) {if (d % zs[i] == 0) {res = min(res, (zs[i]-(x%zs[i]))%zs[i]);while(d % zs[i] == 0) d /= zs[i];}}// 如果 d 本身是质数if(d>1) {res = min(res, (d-(x%d))%d);}printf("%d\n", res==M+1 ? -1 : res);}return 0;
}