牛客練習賽138(首篇萬字題解？？？)

賽時成績如下：

?1.?小s的簽到題

小s拿到了一個比賽榜單，他要用最快的速度找到簽到題，但是小s腦子還是有點暈，請你幫幫小s，助力他找到簽到題。
比賽榜單是一個 2?行 n?列的表格：
第一行是 n?個大寫字母，代表題號；
第二行是 n?個字符串，對應每一道題目的通過人數和提交人數，字符串由兩個整數構成，整數之間使用字符 ‘/’ 隔開。
我們定義，通過人數最多的題目是簽到題。請你找到簽到題的題號并輸出。特別地，如果有多個簽到題，輸出題號字母表順序最小的那道。

輸入描述:

第一行輸入一個正整數 n(2≤n≤26)，表示題目數量。
第二行輸入 n 個兩兩不同的大寫字母，表示每一道題的題號。
第三行輸入 n 個字符串，表示每一道題的通過人數和提交人數。每個字符串格式為 a/b，其中 a 表示通過人數，b 表示提交人數。保證 0≤a≤b≤10^9
輸出描述:
輸出一個大寫字母，表示簽到題的題號。
示例1
輸入
11
A B C D E F G H I J K
116/212 3/12 117/282 15/35 90/419 7/44 83/446 48/150 35/229 25/116 5/10
輸出
C

解題思路：只需要比較a的大小, 然后記錄下標, 輸出A相對于下標的偏移量后字符即可(其實第二行輸入沒什么用)

#include <bits/stdc++.h>
using namespace std;
int main(){int n;cin >> n;vector<char> ids(n);for(int i = 0; i < n; i++){cin >> ids[i];}string s=""; int maxIdx=0;cin>>s;long long pos=s.find('/');string a=s.substr(0,pos);for(int i=1;i<n;i++){cin>>s;long long pos=s.find('/');string tmp=s.substr(0,pos); //字符串比較的是字典序而非大小if(stoll(tmp)>stoll(a)){a=tmp;maxIdx=i;}}cout<<(char)('A'+maxIdx)<<endl;return 0;
}

?2.?行列改寫

題目描述

小柒最近獲得了一個長度為?n?的數組?{r1,r2,…,rn} 和一個長度為?m?的數組?{c1,c2,…,cm}。他想用這兩個數組來生成一個 n 行 m?列的二維數組，初始時，二維數組中每個元素的值均為?0，隨后，他一共會進行 n+m 次操作，每次操作從以下兩種覆蓋方式中選擇一種進行：
行覆蓋：選擇一個未被選中過的行，記為 i，將第?i?行的所有元素變為?ri?；
?列覆蓋：選擇一個未被選中過的列，記為?j，將第?j?列的所有元素變為?cj?。
小柒希望最終的二維數組中所有元素之和最大，請你幫他計算這個最大值。

輸入描述:

第一行輸入兩個正整數?n,m(1≤n,m≤105)代表 r 數組和 c 數組的長度。?
第二行輸入?n?個正整數?r1,r2,…,rn(1≤ri≤106)代表?r?數組的數值。?
第三行輸入?m?個正整數?c1,c2,…,cm(1≤ci≤106)代表?c?數組的數值。
輸出描述:
輸出一個整數，代表最終的二維數組中所有元素之和的最大值。
示例1
輸入
3 3
1 2 3
1 2 3
輸出
22

解題思路：初始時, 為一個n*m的二維數組, 最多操作m+n次, 選中第i行, 該行所有元素變為ri, 選中第j列, 該列所有元素變為cj, 對于每個格子(i,j), 最終的值取決于最后一次覆蓋它的操作, 如果最終是行覆蓋就為ri, 列覆蓋的話就為cj, 行/列的順序是無所謂的, 對于每一行來說, 我們先用行覆蓋, 如果列覆蓋有更優的, 我們再用列覆蓋進行調整, 代碼實現上, 我們先對c數組進行排序,???在遍歷r數組的同時, 去c數組中找到第一個>r[i]的數, 那么它左側的元素就用ri(行覆蓋), 右側的數就用cj(列覆蓋), (右側是連續數組, 我們可以用前綴和進行統計), 單行的總和就為

k*r[i]+(prefix[m]-prefix[k])

可以有人會有疑問，那如果我在第一行我用列覆蓋，那在考慮第二行的時候, 會不會受影響啊？

其實是不會的, 這就是我上面的提到的行/列順序是沒有順序的, 第二行覆蓋在第一行的列覆蓋之前操作，就解決了這個問題 (這題有點硬控我啊)

#include <bits/stdc++.h>
using namespace std;
int main(){int n, m;cin >> n >> m;vector<int> a(n), b(m);for(int i = 0; i < n; i++) cin >> a[i];for(int i = 0; i < m; i++) cin >> b[i];sort(b.begin(), b.end());vector<long long> prefix(m + 1, 0);for(int j = 0; j < m; j++){prefix[j + 1] = prefix[j] + b[j];}long long total_B = prefix[m];long long ans = 0;for(int i = 0; i < n; i++){int k = upper_bound(b.begin(), b.end(), a[i]) - b.begin();ans += (long long)k * a[i] + (total_B - prefix[k]);}cout << ans << endl;return 0;
}

?3.?樹上替身追趕游戲

本題與《E.圖上替身追趕游戲》共享部分題目背景，我們建議您重新閱讀題面。

給定一棵由 n?個點和 n?1 條邊組成的樹，結點編號為 1～n。Saki 和 Miku 在樹上的點之間移動，模擬追趕游戲，初始時兩個人都在節點 k。
游戲分若干回合進行，由你扮演 Saki。每回合包含以下步驟：
1.?Saki 移動：記回合開始時 Saki（你）在節點 a，你必須選擇一個與 a?相鄰的節點 b?并移動至 b；
2.?Saki 放置替身：Saki（你）不想被 Miku 追上，所以你必須選擇一個與節點 b 相鄰的節點 c?放置一個替身，該替身僅在本回合內存在；
3.?Miku 追趕：Miku 將替身視為 Saki 的位置并據此行動：
若 Miku 本就位于替身所在的節點 c，她停留不動；
否則，Miku 在其當前節點的相鄰節點中，選擇到節點 c?距離最近的節點 d 并移動到該節點（換句話說，點 d?是 Miku 所在的位置到點 c?的最短路徑中的下一個節點）。
游戲在 Saki 首次移動后開始計為第 1?回合。如果在任何時刻 Saki 與 Miku 重合，游戲立即結束。
請計算，如果你采取最優策略，最多能夠將游戲進行到第幾回合？

輸入描述:

第一行輸入兩個正整數 n,k(2≤n≤105;?1≤k≤n)，表示樹的結點數、雙方起始位置。此后 n?1 行，第 iii 行輸入兩個整數 ui,vi(1≤ui,vi≤n)，表示第 i 條樹邊連接第 ui?個點和第 vi? 個點。保證給定的邊構成一棵樹。

輸出描述:

輸出一個整數，表示 Saki 最多能夠堅持到第幾回合結束。

示例1

輸入

5 1

1 2

1 3

1 4

1 5
輸出
2
在這個樣例中，其中一種最優策略的移動狀況如下：

1.?Saki 移動到 2?號結點；
2.?Saki 在 1?號結點放置替身；
3.?Miku 停留不動。
第二回合：
1.?Saki 移動到 1號結點。
此時，她與 Miku 重合，游戲結束。
我們可以證明，不存在比 2?回合堅持更久的策略。

解題思路：看不懂題意的，可以直接看樣例畫個圖, 求(重合)能堅持多少個回合

Saki 應該盡可能往遠離 Miku 的方向跑，即往樹的最深處跑
因為樹的直徑決定了 Saki 最多能跑多遠

代碼實現上:

計算 Miku 的最短距離（d_M）：
從初始點 k 出發，BFS 計算 Miku 到所有節點的最短距離
計算 Saki 的最短距離（d_S）：
Saki 每回合可以移動一步，但必須保證 d_S[u] + 1 <= d_M[v]（即 Saki 不能跑到 Miku 已經能更快到達的地方）
最大回合數：
Saki 能跑的最遠距離 max_d，回合數 = max_d + 1（因為第 max_d 步時 Miku 會追上)

#include <bits/stdc++.h>
using namespace std;
int main(){int n, k;cin >> n >> k;vector<vector<int>> a(n+1);for(int i = 1, x, y; i < n; i++){cin >> x >> y;a[x].push_back(y);a[y].push_back(x);}vector<int> d_M(n+1, -1);queue<int> p;d_M[k] = 0;p.push(k);while(!p.empty()){int u = p.front(); p.pop();for(int v : a[u]){if(d_M[v] == -1){d_M[v] = d_M[u] + 1;p.push(v);}}}vector<int> d_S(n+1, -1);long long max_d = 0;queue<int> q;d_S[k] = 0;q.push(k);while(!q.empty()){int u = q.front(); q.pop();for(int v : a[u]){if(d_S[v] == -1 && d_S[u] + 1 <= d_M[v]){d_S[v] = d_S[u] + 1;max_d = max<long long>(max_d, d_S[v]);q.push(v);}}}cout << (max_d + 1) << endl;return 0;
}

4. 全對！?

題目鏈接：登錄—專業IT筆試面試備考平臺_牛客網

小 S 有 n?個對錯機器人，每個對錯機器人的行為邏輯由一個長度不超過 16，僅由字符 ‘0’ 和 ‘1’ 構成的字符串表示。在本題中，我們記字符串的下標從 1 開始。
對于第 i 個機器人，記其初始字符串為 si，其會先將這個字符串無限重復拼接成一個無限長的循環字符串 si∞?。隨后，對于第 j 時刻，它會根據si∞? 的第 j 個字符來決定回答「對的」還是「不對」：
??,?如果 si∞? 的第 j 個字符為 ‘1’，則表示第 i 個機器人在第 j 秒回答「對的」；
?,?如果 si∞? 的第 j?個字符為 ‘0’，則表示第 i 個機器人在第 j 秒回答「不對」。
更具體地，如果某個機器人的初始字符串是 "10101" ，那么這個機器人會在第 1,3,5,6,8,10,11,… 秒回答「對的」，在第 2,4,7,9,12,… 秒回答「不對」。
請問是否存在一個時刻 t，使得所有機器人在第 t 秒都回答「對的」，這樣的時刻被稱為「全對時刻」。如果存在，輸出最小的「全對時刻」；否則，輸出 ?1。

解題思路：

舉個例子：

3
001
0110
10001

3個字符串都是無限循環的,?

001001001001001...

0110011001100110....

100011000110001...

輸出第一個全是1的時刻, 就是 6

往&運算上面思考(相同位置是1, '與'完仍然是1)即可, 模擬思路即可

代碼實現上, 由于單個字符串(在不無限循環情況下)不會超過16，

對于每個長度為L的字符串,? 我們需要記錄每個位置r是否都為1,?

eg:

110

101

111

?b[0]=1, b[1]=0, b[2]=0

a[3][0]=1, a[3][1]=0, a[3][2]=0

a[L][r]: 表示長度為L的字符串在第r個位置是否全為1

接著枚舉時間t?, 需要找到最小額的t,?使得對于所有 L（1~16）, t % L 對應的位置 r 滿足 a[L][r] = true

eg: 解釋一下這個% ,如果t=5, L=3, 5%3=2,檢查a[3][2]是否為true, L=4, 5%4=1, 檢查a[4][1]是否為 true, 如果所有L都滿足, 那么t=5就是一個解, 沒有解就輸出-1。

#include <bits/stdc++.h>
using namespace std;
const int M = 1000000;
int main(){int n; cin>>n;vector<vector<bool>> a(17);for(int i=1;i<=16;i++){a[i].resize(i,true);}for(int i = 0; i < n; i++){string s;cin >> s;int L = s.size();vector<bool> b(L, false);for(int r = 0; r < L; r++){if(s[r] == '1')b[r] = true;}for(int r = 0; r<L;r++){a[L][r] = a[L][r] & b[r];}}for(int l = 1; l <= 16; l++){bool f = false;for(bool x : a[l]) if(x){ f = true; break; }if(!f){cout << -1 << endl;return 0;}}for(int t = 1; t <= M; t++){bool f = true;for(int l= 1; l<=16;l++){int r = (t-1)%l;if(!a[l][r]){f = false;break;}}if(f){cout << t << endl;return 0;}}cout << -1 << endl;return 0;
}

5. 圖上替身追趕游戲?

為了甩開 Miku，你可以在游戲開始前發動一次「神之力」：在這棵樹上選擇不相鄰的兩個點 u,vu，隨后在這兩點之間加一條邊，使得樹變成一個無向圖，隨后，游戲在圖上進行！特別地，這樣操作后，如果 Miku 有多個滿足條件的點選擇，那么她一定會選擇下標最小的那個并進行移動。
求解，有多少種不同的「神之力」施展方法，使得 Saki（你）可以在神之力發動后，通過一系列操作，在某個回合結束時，可以和 Miku 不相鄰、不重合。

【注意】
與《C.樹上替身追趕游戲》不同的是，在本題中，任何時刻 Saki 和 Miku 重合，游戲都不會結束。
在 u,v 加邊和在 v,u加邊被視為同一種「神之力」施展方法。更具體地，如果兩次「神之力」選擇的點相同，視為同一種加邊方法。

輸入描述:

第一行輸入兩個正整數 n,k(2≤n≤105;?1≤k≤n)，表示樹的結點數、雙方起始位置。
此后 n?1 行，第 iii 行輸入兩個整數ui?,vi?(1≤ui?,vi?≤n)，表示第 i 條樹邊連接第 ui 個點和第 vi個點。保證給定的邊構成一棵樹。
輸出描述:
輸出一個整數，表示有多少種不同的「神之力」施展方法。

?此題是第三題的修改版

解題思路：樹形DP，比賽的時候看F題題目挺短的, 就直接寫F題, 這題沒看

可以通過手玩一下樣例發現，樹在加邊后會產生一個環，這個環是saki甩開miku的關鍵。當環的長度分別為4、5、6時，均可以通過一系列操作，使得在某個回合結束時，與miku不再相鄰或重合。

也就是說本題可以轉化為，計算給定樹中長度為3、4和5的簡單路徑的總數量。代碼采用樹形動態規劃（Tree DP）的思想來解決。

核心思路：

我們通過深度優先搜索（DFS）遍歷樹，并在DFS的過程中計算和累積路徑信息。關鍵在于定義DP狀態以及如何合并子樹信息。

其中變量 ans 最終累計了所有長度為3、4、5的簡單路徑的數量。通過一次DFS遍歷，利用 f[d][u] 數組存儲子樹內距離信息。在回溯時（即子節點DFS結束后），它首先利用當前 f[j][u]（代表“左側分支”）和 f[k-j][v]（代表“右側分支”，其中 v 是剛處理完的子節點）來組合路徑并更新 ans，然后才將 v 子樹的信息整合進 f[][u]，為后續的計算做準備。這種“先計算貢獻，再合并信息”的順序是樹形DP中常見的處理方式，確保了每個路徑只被計算一次且不會遺漏。

代碼

1. DP狀態定義：

f[k][u]：表示在以節點 u 為根的子樹中，與節點 u 距離為 k 的節點有多少個。

2. DFS過程詳解：

dfs(u, fa) 函數處理以 u 為當前節點，fa 為其父節點的情況。

初始化：

dep[u] = dep[fa] + 1：計算當前節點 u 的深度（根節點深度為1，其父節點0的深度為0）。
f[0][u] = 1：對于節點 u 本身，它與自身的距離為0。所以以 u 為根的子樹中，與 u 距離為0的節點只有 u 自己，數量為1。
遍歷子節點：對于 u 的每個子節點 v（v != fa）：

遞歸調用： dfs(v, u)。這會先計算完成以 v 為根的子樹中所有的 f[][v] 值。

路徑統計 (核心部分)：在從 dfs(v, u) 返回后，我們利用已經計算好的 f[][u]（包含 u 自身以及 u 的在 v 之前處理過的其他子樹的信息）和 f[][v]（包含 v 的子樹信息）來統計經過邊 (u,v) 的路徑。我們關注的路徑形態是 X - ... - u - v - ... - Y，其中：

X 是在 u 的子樹中（但在 v 的子樹之外，或者是 u 本身）的一個節點。
Y 是在 v 的子樹中的一個節點。
路徑 X - ... - u 的長度為 j。這樣的 X 有 f[j][u] 個。
路徑 v - ... - Y 的長度為 d。這樣的 Y 有 f[d][v] 個。
那么，完整路徑 X - ... - u - v - ... - Y 的長度為 j + 1 + d (1代表邊 (u,v) 的長度)。
代碼中的循環 k->(2, 5): 實際上是在枚舉 j+d 的值。

當 k = 2時，我們統計 j+d = 2，總路徑長度為 j+d+1 = 3。
當 k = 3時，我們統計 j+d = 3，總路徑長度為 j+d+1 = 4。
當 k = 4時，我們統計 j+d = 4，總路徑長度為 j+d+1 = 5。
內層循環 j->(0, k + 1): 枚舉了路徑 X - ... - u 的長度 j (即 d1)。

那么路徑 v - ... - Y 的長度 d (即 d2) 就必須是 k-j。
此時，符合條件的路徑數量為 f[j][u] * f[k-j][v]。將這個乘積累加到 ans。
注意：這里的 f[j][u] 尚未包含來自子樹 v 的貢獻，這正是我們想要的，因為它保證了路徑的兩個分支分別來自 u 的不同“方向”（一個方向是 v 子樹，另一個方向是 u 的其他子樹或 u 自身）。
更新 f[][u]：在統計完以 v 為一支的路徑后，需要將子樹 v 的信息合并到 f[][u] 中，以便后續 u 的其他兄弟子樹或者 u 的父節點使用。 j-> (0,5): f[j + 1][u] += f[j][v] 這條語句的含義是：如果一個節點 Z 在子樹 v 中，且與 v 的距離為 j（這樣的節點有 f[j][v] 個），那么節點 Z 與 u 的距離就是 j+1。所以，我們將 f[j][v] 的值累加到 f[j+1][u] 上。 j 從0到4，意味著 j+1 從1到5。這對應了 f 數組的維度。

DFS起始： dfs(1, 0) 從節點1開始DFS，假設節點0是節點1的虛擬父節點，其深度為0。

#include <bits/stdc++.h>
using namespace std;
int n, _;
vector<vector<int>> g;
vector<vector<long long>> f;
long long ans;
vector<int> dep;
void dfs(int u, int fa) {dep[u] = dep[fa] + 1;f[0][u] = 1;for (int v : g[u]) {if (v == fa) continue;dfs(v, u);for (int k = 2; k <= 4; ++k) {for (int j = 0; j <= k; ++j) {ans += f[j][u] * f[k - j][v];}}for (int j = 0; j < 5; ++j) {f[j + 1][u] += f[j][v];}}
}int main() {cin >> n >> _;g.assign(n + 1, {});for (int i = 0; i < n - 1; ++i) {int u, v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}f.assign(6, vector<long long>(n + 1, 0));dep.assign(n + 1, 0);ans = 0;dfs(1, 0);cout << ans << endl;return 0;
}

?6.素數回路

給定偶數 n，構造一個由1～n 這 n 個不同的整數構成環形數組 a，使得相鄰兩項的差均為奇素數。
奇素數是指除了 2 以外的素數，最小的四個奇素數是 3,5,7,11

輸入描述:

每個測試文件均包含多組測試數據。第一行輸入一個整數 T(1≤T≤105) 代表數據組數，每組測試數據描述如下：
在一行上輸入一個偶數 n(2≤n≤10^5)。
除此之外，保證單個測試文件的 n 之和不超過 2×10^5。
輸出描述:
對于每一組測試數據，新起一行。如果不存在合法的環形數組，直接輸出 ?1。否則，輸出 n個整數，表示構造的環形數組 a。
你需要保證數組 a 是一個由 1～n1 ?這 n 個不同的整數組成的數組，下標從 0 開始，滿足任取 0≤i<n，∣ai?a(i+1)?mod?n∣均為奇素數。

解題思路：輸入n，ai→[1,n], 排列滿足相鄰差是一個奇素數(除了2的素數)

我們從1開始考慮，如果n是奇數，例如n=5, 滿足題意的就是 1→4, 連不起，

...n=7,? 滿足題意的就為1 4 7 2? (從1開始,每次考慮3或者5)，還是不行，

n=8,? 滿足題意的就為1 4 7 2 5 8 3 6

n=9,?1 → 4 → 7 → 2 → 5 → 8 → 3 → 6 → 9 → 1 最后一步不行

觀察可以得出, ai=1, 加上一個奇素數，就會變成偶數, 再加上一個奇素數就會變成奇數, 如果n是奇數, 最后一步就會變成奇數, 奇數-奇數=偶數, 就回不到起始點了

接下來，我們先將奇素數預處理一下，存到o_p這個數組中, 接著我們找一個奇素數p, ?使得 n - p 也是奇素數(這個是觀察出來的, 比如, n=8, n=10, n=12, 自己推導一下)

找到符合條件的p后,

構造環形數組：

使用公式：(cur - 1 + p) % n + 1 (eg: n=8)

cur=1 → (1-1+3)%8+1=4 → (4-1+3)%8+1=7 → (7-1+3)%8+1=2 → (2-1+3)%8+1=5 → (5-1+3)%8+1=8 → (8-1+3)%8+1=3 → (3-1+3)%8+1=6 → (6-1+3)%8+1=1。

最終數組：[1,4,7,2,5,8,3,6]。

檢查相鄰差：

|1-4|=3，|4-7|=3，|7-2|=5，|2-5|=3，|5-8|=3，|8-3|=5，|3-6|=3，|6-1|=5。

所有差都是奇素數，構造成功。(依舊硬控....)

#include <bits/stdc++.h>
using namespace std;
const int N = 200000; 
int main(){vector<bool> is_prime(N+1, true);is_prime[0] = is_prime[1] = false;for(int i = 2; i*i <= N; i++){if(is_prime[i]){for(int j = i*i; j <= N; j += i){is_prime[j] = false;}}}vector<int> o_p;for(int i = 3; i <= N; i += 2){if(is_prime[i]) o_p.push_back(i);}int T;cin >> T;while(T--){int n;cin >> n;if(n < 8 || n % 2 != 0){cout << -1 << endl;continue;}int p = -1;for(int x : o_p){if(x >= n) break;int y = n - x;if(y >= 3 && is_prime[y]){p = x;break;}} if(p == -1){cout << -1 << endl;continue;}vector<int> ans;int cur = 1;for(int i = 0; i < n; i++){ans.push_back(cur);cur = (cur - 1 + p) % n + 1;}cout << ans[0];for(int i = 1; i < n; i++) cout << ' ' << ans[i];cout << endl;}return 0;
}

7.k人訓練方陣

吹奏部有 n?名部員，saki 作為吹奏部的一員，負責從 n?名部員中選擇若干名部員組成「k?人方陣」來參加活動。這是指一個由吹奏部部員組成的表演方陣，首先必須有一個領隊站在前面，方陣有若干排（可以 0排），但每排必須是 k 個人。?
請你幫 Saki 計算一下有多少種不同的「k?人方陣」選法？由于答案可能很大，請將答案對 (109+7) 取模后輸出。
注意 saki 只要選出若干名部員，能夠組成「k?人方陣」就可以了，不需要去安排每個人的分工和站的位置，對是否是領隊不作區分。?

解題思路：組合數(快結束的時候, 套了一下板子, 超時了...)

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 1e7;
vector<long long> F, INV_fac;
int quPow(long long a, int n) {long long res = 1;while(n) {if(n & 1) res = res * a % MOD;a = a * a % MOD;n >>= 1;}return res;
}
void init(int MAXN) {F.resize(MAXN + 1,0);INV_fac.resize(MAXN + 1,0);F[0] = 1;for(int i = 1; i <= MAXN; i++)F[i] = F[i - 1] * i % MOD;INV_fac[MAXN] = quPow(F[MAXN], MOD - 2);for(int i = MAXN - 1; i >= 0; i--)INV_fac[i] = INV_fac[i + 1] * (i + 1) % MOD;
}
long long C(int n, int r) {if(r < 0 || r > n) return 0;return F[n] * INV_fac[r] % MOD * INV_fac[n - r] % MOD;
}
int main() {init(MAXN); int T;cin >> T;while(T--) {int n, k;cin >> n >> k;long long ans = 0;for(int r = 1; r <= n; r += k) {ans = (ans + C(n, r)) % MOD;}cout << ans << endl;}return 0;
}