作者有言在先：
題解的作用是交流思路，不是抄作業的。可以把重點放在思路分析上而不是代碼上，畢竟每個人的代碼風格是不一樣的，看別人的代碼就跟做程序填空題一樣。先看明白思路再看代碼。
還有就是，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

輸出

0
5
0
7

解釋

• 第一個測試用例：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 開始參加編程課程。在第一節課上，他的任務是編寫一個簡單的程序。該程序需要完成以下功能：對于給定的由大寫和小寫拉丁字母組成的字符串，程序需要：

1. 刪除所有元音字母，
2. 在每個輔音字母前插入一個字符 .，
3. 將所有大寫輔音字母替換為對應的小寫字母。

元音字母包括 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

分析

任務：

1. 剔除掉所有aeiouy
2. 剩余字母輸出前先輸出.
3. 轉化為小寫字母在輸出

優化任務

由于原字符串涉及大小寫，而輸出只有小寫，且為了方便第一項任務的判斷，我們對任務轉化一下順序，先進行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] 得到。

分析

由于只用給出一張情況就好，我們簡化億點點

1. 既然他打亂了數組b的順序，那我們就給他排序（從小到大）

2. 可以略微思考一下：a數組最小的那個數在b數組里面至少出現了n-1次，而且b數組中最小的數在a中肯定也是最小的（可以反證）

3. 那么我們是不是確定了a數組的一個數：b中的最小數也是a中的最小數

4. 如（2）所說，至少會出現n-1次，那如果出現了更多次，那說明這個最小數不止出現了一次。由于是最小值，那在b數組里至少出現了n-1+n-2=2n-3次，以此類推。若最小值只出現了n-1次，那么下一個數就是次小值了。

5. 由此可推出次小、次次小……次大、最大值。其中最大值可出現兩次，因為自己跟自己比還是自己大

優化分析

分析中的第（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 ) 名學生的分數。你可以訪問學校的數據庫，該數據庫存儲了所有學生的成績。

你可以修改每名學生的分數，但需要滿足以下條件：

1. 所有分數都是整數。
2. 每個分數滿足 ( 0 \leq a_i \leq m )。
3. 班級的平均分數保持不變。

你是第 ( 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 )）——學生的分數。

---

輸出

對于每個測試用例，輸出一個整數——滿足所有條件的情況下，你可以分配給自己的最高可能分數。

---

示例

輸入

2
4 10
1 2 3 4
4 5
1 2 3 4

輸出

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 ∈ { x 1 , x 2 , … , x n } \ s \in \{x_1, x_2, \dots, x_n\} ?s∈{x1?,x2?,…,xn?}，即 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 $(1\le t\le 10^4)$，表示測試用例的數量。
• 每個測試用例的第一行包含一個整數 n $(1\le n\le 2?10^5)$，表示點的數量。
• 第二行包含 n 個整數 $x_1,x_2,\dots ,x_n$ $(1\le x_i\le 10^9)$，表示點的坐標。
• 保證所有測試用例的 n 的總和不超過 $2?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），表示測試用例的數量。

對于每個測試用例：

1. 第一行為一個整數 n（1 ≤ n ≤ 100），表示字符串的長度。
2. 第二行為一個長度為 n 的字符串 s，僅由字符 '0' 和/或 '1' 組成。

---

輸出格式

對于每個測試用例，如果可以通過操作使字符串中 '0' 的數量嚴格大于 '1' 的數量，則輸出 "YES"；否則輸出 "NO"。

---

示例

輸入

3
2
00
2
11
2
10

輸出

YES
NO
YES

---

示例解釋

1. 第一個測試用例：字符串 "00" 中 '0' 的數量已經大于 '1' 的數量，因此輸出 "YES"。
2. 第二個測試用例：字符串 "11" 無法通過操作插入任何 '0'，因此輸出 "NO"。
3. 第三個測試用例：選擇 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

輸出

0
1
-1
79

---

示例解釋

1. 第一個測試用例：gcd(5, 15) = 5 > 1，因此它本身不是幸運的，幸運鏈的長度為 0。
2. 第二個測試用例：gcd(14, 38) = 2，因此幸運鏈僅包含 (13, 37)，長度為 1。
3. 第三個測試用例：gcd(8+k, 9+k) = 1 對所有 k ≥ 0 成立，因此幸運鏈可以無限長，輸出 -1。
4. 第四個測試用例：最長幸運鏈的長度為 79。

---

約束條件

• 輸入的對數 n 最多為 10⁶。
• 每對 (x, y) 滿足 1 ≤ x < y ≤ 10⁷。

分析

問題分析

我們需要為每對 (x, y) 計算由其誘導的最長幸運鏈的長度。幸運鏈的定義是鏈中的所有對 (x+k, y+k) 都必須滿足 gcd(x+k, y+k) = 1。如果鏈可以無限延伸，則輸出 -1；否則輸出鏈的長度。

---

關鍵觀察

1. 鏈的性質：
   鏈的形式為 (x+k, y+k)，其中 k 從 0 開始遞增。我們可以將鏈中的任意對表示為 (x+k, y+k)。

2. 最大公約數的性質：
   對于鏈中的每個對，有：

   $$\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)。

3. 問題轉化：
   我們需要找到最大的 k，使得對于所有 0 ≤ i ≤ k，都有 gcd(x+i, y - x) = 1。如果對于所有 k ≥ 0，都有 gcd(x+k, y - x) = 1，則鏈可以無限延伸，輸出 -1。

4. 終止條件：
   如果 gcd(x+k, y - x) > 1，則鏈在第 k 步終止，鏈的長度為 k。

---

算法思路

1. 特判：
   如果 gcd(x, y) > 1，則鏈的長度為 0，因為第一個對本身不滿足條件。
2. 計算 d = y - x：
   計算差值 d = y - x，因為 gcd(x+k, y+k) 的值取決于 gcd(x+k, d)。
3. 檢查 gcd(x+k, d)：
   • 如果 d = 1，則對于任意 k，gcd(x+k, 1) = 1，因此鏈可以無限延伸，輸出 -1。
   • 否則，我們需要找到最小的 k，使得 gcd(x+k, d) > 1。如果找不到這樣的 k，則鏈可以無限延伸，輸出 -1；否則輸出 k。
4. 查找最小的 k：
   我們需要找到最小的 k，使得 gcd(x+k, d) > 1。這可以轉化為找到使 x+k 與 d 有非 1 公約數的 k。
   • 找到 d 的所有質因數。
   • 對于每個質因數 p，計算最小的 k 使得 p 整除 x+k，即 k ≡ -x \mod p。
   • 取所有質因數對應的 k 的最小值。

---

算法步驟

1. 對于每對 (x, y)，計算 d = y - x。
2. 如果 d = 1，輸出 -1。
3. 否則，找到 d 的所有質因數。
4. 對于每個質因數 p，計算最小的 k 使得 p 整除 x+k，即 k = (p - x % p) % p。
5. 取所有質因數對應的 k 的最小值。如果存在這樣的 k，輸出 k；否則輸出 -1。

---

時間復雜度分析

1. 質因數分解：
   質因數分解的時間復雜度為 O(sqrt(d))，其中 d = y - x。
2. 總復雜度：
   對于 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;
}