題目地址

https://codeforces.com/contest/2008

銳評

本次D3的前四題還是比較簡單的，沒啥難度區分，基本上差不多，屬于手速題。E的碼量比F大一些，實現略顯復雜一些。G的數學思維較明顯，如果很久沒有訓練這個知識點，可能會一下子反應不過來，比如說我，需要花一點點時間觀察，然后確認最優策略，整體不算太難，約等于D2的C題左右。H題較難，感覺原超過了D3 Rating范圍，需要一定的優化技巧，但也不是不可做，思維量也沒那么大。綜合評估，個人覺得整場難度中等偏上了。

題解

Problem A. Sakurako’s Exam

題目大意

給定$a(0\le a<10)$個整數$1$和$b(0\le b<10)$個整數$2$，每個整數可以選擇不變或者變為它的相反數，問是否存在一種情況滿足所有改變操作后，所有整數求和等于$0$？

題解思路：二進制枚舉/數學分類討論

首先，$a,b$最大不過$10$，最直接粗暴的方式是暴力枚舉出每個數的可能性，然后求和判斷即可，時間復雜度為$O(2^{a+b}\max (a,b))$。

采用上面的方式，好像有點冒進。當$a,b$都為$9$時，$2^{9+9}\times \max (9,9)=262144\times 9=2359296$，外面還套了個$t(1\le t\le 100)$，只給了$1s$的時限，極有可能會超時，好在過了，可能判定結束得早吧，勉強飄過。

重新來分析。$2$怎么消掉？只能用$1$個自己或者$2$個$1$。$1$呢？也只能用$1$個自己或者用自己$2$個去抵掉$1$個$2$。觀察發現$1$只能一對一對消失，所以當$a$為奇數時必然無解。因此$a$一定為偶數，所以它自己一定能相互抵消。我們考慮$2$怎么抵消，顯然$2$自己相互抵消是最好的，它最多只會多出來$1$個，然后問$1$借兩個就行，因此時間復雜度為$O(1)$。

參考代碼（C++）

二進制枚舉代碼

#include <bits/stdc++.h>
using namespace std;
int n, m;void solve() {cin >> n >> m;for (int i = 0, len = 1 << n; i < len; ++i) {int sum = 0;for (int j = 0; j < n; ++j) {if ((i >> j) & 1)++sum;else--sum;}for (int j = 0, siz = 1 << m; j < siz; ++j) {int sumt = 0;for (int k = 0; k < m; ++k) {if ((j >> k) & 1)sumt += 2;elsesumt -= 2;}if (sumt + sum == 0) {cout << "YES\n";return;}}}cout << "NO\n";
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t = 1;cin >> t;while (t--)solve();return 0;
}

數學分類討論代碼

#include <bits/stdc++.h>
using namespace std;
int n, m;void solve() {cin >> n >> m;if (n & 1)cout << "NO\n";else {m &= 1;cout << (n >= m ? "YES\n" : "NO\n");}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t = 1;cin >> t;while (t--)solve();return 0;
}

Problem B. Square or Not

題目大意

給定一個長度為$n(2\le n\le 2?10^5)$的字符串$s$，僅包含字符$0$和$1$。

問能否將這個字符串變化為$r$行$c$列的二維矩陣，其中要求$r=c且r\times c=n$，還要滿足字符串依次從左到右從上到下填充方格后，最外層邊界上的字符是$1$，不在最外層邊界上的字符是$0$。

題解思路：模擬 & 枚舉

先判斷$n$是不是一個平方數，如果不是，顯然就沒有答案。否則就枚舉一遍，判斷對應位置字符是不是符合要求即可，時間復雜度為$O(n)$。

參考代碼（C++）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200'005;
int n;
string str;void solve() {cin >> n >> str;int m = sqrt(n + 0.5);if (m * m != n)cout << "No\n";else {for (int i = 0; i < n; ++i) {int x = i / m, y = i % m;if (x == 0 || x == m - 1 || y == 0 || y == m - 1) {if (str[i] != '1') {cout << "No\n";return;}} else {if (str[i] != '0') {cout << "No\n";return;}}}cout << "Yes\n";}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t = 1;cin >> t;while (t--)solve();return 0;
}

Problem C. Longest Good Array

題目大意

構造一個嚴格單調遞增的數組，并且從左到右相鄰兩個數的差也要是嚴格單調遞增的。給定$l,r(1\le l\le r\le 10^9)$，表示該數組元素的數據范圍。問能構造的數組長度最大是多少？

題解思路：數學 & 枚舉

因為要保持嚴格單調遞增，不考慮數據范圍上限，那么顯然相鄰差的下限為$1$，相鄰差的序列形如$1,2,3,4,?$，顯然這是一個公差為$1$的等差數列，因為數組又要求嚴格單調遞增，假如最多$n$項，根據等差數列求和公式，則有最大數為$\frac{n(n?1)}{2}$。顯然，假如最大數據范圍為$lim$，構造的數組長度不會超過$\sqrt{lim}$。根據題目給定的數據范圍$10^9$可知，第一個數為$l$，然后直接枚舉構造就可以了，時間復雜度為$O(\sqrt{r?l+1})$（不嚴格）。

參考代碼（C++）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200'005;
int a[maxn];
int l, r;
int n;void solve() {cin >> l >> r;int id = 1, d = 1;a[0] = l;while (a[id - 1] + d <= r) {a[id] = a[id - 1] + d;++id;++d;}// cout << "res:" << a[id - 1] << '\n';cout << id << '\n';
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t = 1;cin >> t;while (t--)solve();return 0;
}

Problem D. Sakurako’s Hobby

題目大意

給定一個長度為$n(1\le n\le 2?10^5)$的排列$p_1,p_2,?,p_n(1\le p_i\le n)$。

有一個操作，假如是第$i$個位置，我們可以從位置$i$跳躍到位置$p_i$，即從位置$i$可以到達位置$p_i$，以此類推，我們可以重復跳躍過程到達某個位置。

再給定一個長度為$n$的字符串$s$，僅包含字符$0$和字符$1$，$0$表示黑色，$1$表示白色。字符串第$i$個位置的字符$s[i]$表示上述排列第$p_i$個位置為該字符，即為該位置的顏色。

求第$i(1\le i\le n)$個位置能到達的所有位置中位置顏色為黑色的有多少個？

題解思路：置換環 & 并查集

從一個點跳躍到另一個點，跳躍過的點就不能再跳躍，那么這個過程他肯定會終止，而且它會陷入一個循環。圖論中叫置換環（有興趣可以自行查閱）。我們可以模擬這個過程，然后一輪跳躍中的點為一組，他們可以互相到達。

那么怎么計算黑色個數呢？可以用并查集來解決這個問題，最終只需要計算出每個位置$i$所在組的代表元的黑色個數，即是這一位置的答案，整體時間復雜度為$O(n)$（并查集接近線性，實際不是，跟阿克曼函數有關，這里并不嚴格）。

參考代碼（C++）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200'005;
struct dsu {int p[maxn], siz[maxn];int n;void init(int n) {this->n = n;for (int i = 0; i < n; ++i)p[i] = i, siz[i] = 1;}int findp(int x) {return p[x] == x ? x : p[x] = findp(p[x]);}bool unionp(int x, int y) {int fx = findp(x);int fy = findp(y);if (fx == fy)return false;if (siz[fx] >= siz[fy]) {p[fy] = fx;siz[fx] += siz[fy];} else {p[fx] = fy;siz[fy] += siz[fx];}return true;}bool same(int x, int y) {return findp(x) == findp(y);}int sizep(int x) {return siz[findp(x)];}
} d;
int a[maxn], cnt[maxn];
bool vis[maxn];
string str;
int n;void solve() {cin >> n;for (int i = 0; i < n; ++i) {cin >> a[i];--a[i];vis[i] = false;cnt[i] = 0;}cin >> str;d.init(n);for (int i = 0; i < n; ++i)if (!vis[i]) {int p = i;do {vis[p] = true;d.unionp(i, p);p = a[p];} while (!vis[p]);}for (int i = 0; i < n; ++i)if (str[i] == '0')++cnt[d.findp(a[i])];for (int i = 0; i < n; ++i)cout << cnt[d.findp(i)] << (" \n"[i == n - 1]);
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t = 1;cin >> t;while (t--)solve();return 0;
}

Problem E. Alternating String

題目大意

交替串的定義：給定兩個字符$a$和$b$（$a,b$可以相同），形如$ababab?$且長度為偶數的字符串。

現在給你一個長度為$n(1\le n\le 2?10^5)$的字符串$s$（只包含小寫英文字母）。你可以進行如下兩個操作。

1.刪除某個位置上的字符（注意：此操作最多只能用一次）。

2.將某個位置上的字符替換為任意的小寫英文字母。

問如何用最少的上述操作次數，使得該字符串為交替串？

題解思路：前后綴分解 & 前/后綴和 & 枚舉

假如當前字符串長度為偶數，因為操作1最多只能用一次，而題目要求最終長度要為偶數，所以這種情況下就不能使用操作1，只能使用操作2。因此，我們只需要統計出奇數位置和偶數位置每個字母都分別有多少個，最后枚舉將奇/偶數位置換成每個字母需要的操作次數取最小值即可。

假如當前字符串長度為奇數，因為操作1最多只能用一次，而題目要求最終長度要為偶數，所以這種情況下操作1就必須要使用了。因此，我們可以枚舉刪除的字符位置，然后將左右兩邊的字符串拼接起來，使用上面原始串長度為偶數一樣的處理方式，將左右兩邊的計數匯總起來，然后枚舉將奇/偶數位置換成每個字母需要的操作次數取最小值即可（注意，因為缺失了一個位置，所以這個位置后面位置所處的位置奇偶性發生了變化，計數要取對立位置的）。

為了處理簡單些，我同時求了前綴和和后綴和，整體時間復雜度為$O(n)$（忽略了小寫英文字母個數26，實際是否能通過還是要考慮這個常數的）。

參考代碼（C++）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200'005;
const int mod = 1'000'000'007;
int cp[maxn][2][26], cs[maxn][2][26];
string str;
int n;int qpow(int a, int b) {int ans = 1;while (b) {if (b & 1)ans = 1LL * ans * a % mod;a = 1LL * a * a % mod;b >>= 1;}return ans;
}void solve() {cin >> n >> str;for (int i = 0; i < n; ++i) {for (int j = 0; j < 26; ++j) {cp[i + 1][0][j] = cp[i][0][j];cp[i + 1][1][j] = cp[i][1][j];}++cp[i + 1][i & 1][str[i] - 'a'];}for (int j = 0; j < 26; ++j)cs[n][0][j] = cs[n][1][j] = 0;for (int i = n - 1; i >= 0; --i) {for (int j = 0; j < 26; ++j) {cs[i][0][j] = cs[i + 1][0][j];cs[i][1][j] = cs[i + 1][1][j];}++cs[i][(n - 1 - i) & 1][str[i] - 'a'];}int ans = n;if (n & 1) {for (int i = 0; i < n; ++i) {vector<vector<int>> cnt(2, vector<int>(26, 0));for (int j = 0; j < 26; ++j) {cnt[0][j] += cp[i][0][j];cnt[1][j] += cp[i][1][j];}for (int j = 0; j < 26; ++j) {cnt[0][j] += cs[i + 1][1][j];cnt[1][j] += cs[i + 1][0][j];}int maxe = 0, maxo = 0;for (int j = 0; j < 26; ++j) {maxe = max(maxe, cnt[0][j]);maxo = max(maxo, cnt[1][j]);}ans = min(ans, n - maxe - maxo);}} else {int maxe = 0, maxo = 0;for (int i = 0; i < 26; ++i) {maxe = max(maxe, cp[n][0][i]);maxo = max(maxo, cp[n][1][i]);}ans = min(ans, n - maxe - maxo);}cout << ans << '\n';
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t = 1;cin >> t;while (t--)solve();return 0;
}

Problem F. Sakurako’s Box

題目大意

給定一個長度為$n(2\le n\le 10^5)$的數組$a_1,a_2,?,a_n(0\le a_i\le 10^9)$。

問隨機選擇兩個不同位置的數，求這兩個數乘積的數學期望是多少？

題解思路：數學期望 & 費馬小定理 & 前/后綴和

根據數學期望的定義，有下式。
$$E(x)=p_{12}?(a_1?a_2)+p_{13}?(a_1?a_3)+?+p_{(n?1)n}?(a_{n?1}?a_n)=\sum _{i=1}^{n?1}\sum _{j=i+1}^n{p}_{ij}?(a_i?a_j)$$
$p_{ij}$都是相等的（因為概率相同），即為$\frac{1}{C_n^2}$。合并同類項后，得到如下公式。
$$E(x)=\frac{1}{C_n^2}?(a_1?\sum _{i=2}^n{a}_i+a_2?\sum _{j=3}^n{a}_j+?+a_{n?1}?\sum _{k=n}^n{a}_k)$$
觀察式子，很顯然就是前/后綴和，問題得解。至于怎么消掉分數，可以看我上一篇文章《快速冪》，時間復雜度為$O(n)$（快速冪的指數是固定的，所以是常數）。

參考代碼（C++）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200'005;
const int mod = 1'000'000'007;
int a[maxn], suf[maxn];
int n;int qpow(int a, int b) {int ans = 1;while (b) {if (b & 1)ans = 1LL * ans * a % mod;a = 1LL * a * a % mod;b >>= 1;}return ans;
}void solve() {cin >> n;for (int i = 0; i < n; ++i)cin >> a[i];suf[n - 1] = a[n - 1];for (int i = n - 2; i >= 0; --i)suf[i] = (suf[i + 1] + a[i]) % mod;int p = 0;for (int i = 1; i < n; ++i) {p += 1LL * a[i - 1] * suf[i] % mod;p %= mod;}p = (p << 1) % mod;int q = 1LL * n * (n - 1) % mod;cout << 1LL * p * qpow(q, mod - 2) % mod << '\n';
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t = 1;cin >> t;while (t--)solve();return 0;
}

Problem G. Sakurako’s Task

題目大意

給定兩個整數$n,k(1\le n\le 2?10^5,1\le k\le 10^9)$，再給定一個長度為$n$的數組$a_1,a_2,?,a_n(1\le a_i\le 10^9)$。

你可以進行如下操作任意次數（只要滿足條件可以一直進行下去）：

選擇兩個不同的下標$i$和$j$且$a_i\ge a_j$，然后對$a_i$進行賦值操作，$a_i=a_i?a_j$或者$a_i=a_i+a_j$。

你需要求出進行若干次操作后，這個數組缺失的第$k$小非負整數，并且盡可能讓這個數最大，這個數最大是多少？

數組缺失的第$k$小非負整數是什么？舉個例子，假如數組是$[1,2,3]$，那么缺失的第1小非負整數是0，第2小非負整數是4；假如數組是$[0,1,2,3,5,7]$，那么缺失的第1小非負整數是4，第2小非負整數是6。

題解思路：裴蜀定理 & 枚舉

首先要使得這個數盡可能大，那么比較小的數應該盡可能地多。因此加法操作看起來好像沒啥用哦。我們先只看減法操作，嘿，有點眼熟，好像更相減損術啊，那么是不是應該是求最大公約數。

通過上面的分析，這個減法操作最終得到的數好像有跡可循，進而聯想到裴蜀定理。我們先來看看裴蜀定理的定義。

對任意兩個整數$a$、$b$，設$d$是它們的最大公約數。那么關于未知數$x$和$y$的線性丟番圖方程（稱為裴蜀等式）：$ax+by=m$有整數解$(x,y)$當且僅當$m$是$d$的整數倍。裴蜀等式有解時必然有無窮多個解。

推廣到$n$個整數如下。

設$a_1,?,a_n$為$n$個整數，$d$是它們的最大公約數，那么存在整數$x_1,?,x_n$使得$x_1?a_1+?+x_n?a_n=d$。

上面定理說明了什么問題呢？它說明，對于兩個數，無論你怎么操作，最終操作后的這個數它一定是這兩個數的最大公約數的倍數，$n$個數也同樣如此，這樣就好辦了。

通過上面的分析，我們應該讓最大公約數盡可能小，這樣它的倍數才能占據盡可能多的位置。而多個數的最大公約數只可能減小，不可能變大，所以我們只需要對所有數取最大公約數，這樣就可以用有限次操作把所有數都變為最大公約數。其實這時候想象下，可以使用加法操作構造出首項為0，公差為最大公約數的等差數列（假如數組長度為1，首項不能為0，因為沒辦法操作）。

最后，我們只需要枚舉一下這個等差數列，看看空隙處能填多少個數，如果不夠，往最后補齊即可。整體時間復雜度為$O(nlogn)$（主要是求最大公約數的部分，枚舉部分時間復雜度為$O(n)$）。

參考代碼（C++）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200'005;
const int mod = 1'000'000'007;
int a[maxn], b[maxn];
int n, m;int qpow(int a, int b) {int ans = 1;while (b) {if (b & 1)ans = 1LL * ans * a % mod;a = 1LL * a * a % mod;b >>= 1;}return ans;
}void solve() {cin >> n >> m;int cd = 0;for (int i = 0; i < n; ++i) {cin >> a[i];cd = gcd(cd, a[i]);}b[0] = n == 1 ? cd : 0;for (int i = 1; i < n; ++i)b[i] = i * cd;int ans = 0, last = -1;for (int i = 0; i < n && m; ++i) {int cnt = b[i] - last - 1;int minv = min(cnt, m);m -= minv;ans = last + minv;last = b[i];}if (m)ans = last + m;cout << ans << '\n';
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t = 1;cin >> t;while (t--)solve();return 0;
}

Problem H. Sakurako’s Test

題目大意

給定兩個整數$n,q(1\le n,q\le 10^5)$，再給定一個長度為$n$的數組$a_1,a_2,?,a_n(1\le a_i\le n)$。

對于給定的一個整數$x$，你可以進行如下操作任意次數（只要滿足條件可以一直進行下去）：選擇一個下標$i$且$a_i\ge x$，然后對$a_i$進行賦值操作，$a_i=a_i?x$。

問，給定$q$個這樣的整數$x$，每行一個整數，你需要求進行若干次操作后，這個數組從小到大排序后的中位數最小可以是多少？

本題中位數定義為：對于偶數長度$n$，取第$\frac{n+2}{2}$個位置的數，對于奇數長度$n$，取第$\frac{n+1}{2}$個位置的數。

題解思路：預處理 & 前綴和 & 二分 & 調和級數

要使得中位數最小，那么經過處理后的數組的值應該是越小越好。根據操作的定義，最終對每個數執行若干次操作后的實際效果其實就是$a_i=a_i\mathrm{mod}x$。

本題的時限僅僅為1s，而$q,n$最大都可以為$10^5$。顯然，對于時間復雜度超過$O(qn)$的代碼都不足以通過此題（例如每個數都進行取模操作，然后排序，時間復雜度為$O(qnlogn)$）。

怎么優化呢？$q$我們肯定改變不了，畢竟讀入就要$q$。因此，我們只能寄希望于降低循環體內的查詢時間。因為當前查詢的是$x$，那么答案是多少呢？顯然，答案在區間$[0,x?1]$內，因為取模后所有數肯定是小于$x$的。我們知道排序后，數字都是從小到大的，那么中位數是否具有單調性呢？答案是肯定的。為什么呢？因為某個數$y$是中位數，意味著小于等于$y?1$的元素個數要小于上面中位數定義的位置，且小于等于$y$的元素個數要大于等于上面中位數定義的位置（第一個條件如果是大于等于，說明中位數位置被占了，$y$肯定不在那個位置上，顯然不可能是中位數；第二個條件如果是小于，那就說明，$y$都不夠填充到中位數的位置，中位數顯然最小是$y+1$），所以可以二分答案。

根據上面的分析，時間復雜度好像是$O(qlogx)$，有戲。咦？好像又不太對，我們必須用$O(1)$時間復雜度檢查出上面提到的計數問題是否合法。$n$個數，$O(1)$？逗我，臣妾做不到啊！先放棄，考慮下這個問題的普通做法，最樸素的當然是一個一個枚舉，顯然不可行！我們注意到，對于小于等于某個數$y$的元素個數，當元素數據范圍限定在某個區間內，我們可以用空間換取時間。例如，本題$1\le a_i\le n$，我們用$cn{t}_i$表示數組中有多少個數等于$i$，那么我們把小于等于$i$的計數加起來就是整個數組中小于等于$i$的元素個數，該問題可以用前綴和線性解決。

好像還是沒啥用啊？問題依舊沒解決。別急，我們繼續看。對于題目中每個詢問的$x$，其實將$n$分為了很多類似上面前綴和計數的塊，其中每個塊求小于等于某個數的個數可以$O(1)$求出來，請看如下規律。
$$0,1,?,x?1,x,x+1,?,2?x?1,2?x,2?x+1,?,3?x?1,3?x,3?x+1,?$$
對$x$取模后，得到如下規律。
$$0,1,?,x?1,0,1,?,x?1,0,1,?,x?1,0,1,?$$
根據上面的規律，對于每個要查詢的$x$，我們將$n$分成了$?\frac{n}{x}?$塊（向上取整）。對于每一塊可以用前綴和在$O(1)$時間內計算出小于等于某個數的元素個數。

合并截至目前的分析結果，得到時間復雜度為$O(q?logx?\frac{n}{x})$。這個復雜度十分依賴測試數據給定的$x$，出題人肯定沒那么友好，最簡單的$10^5$個$x=1$就卡死了，況且還有Hack階段。測試一下，果然超時了，后面也給出代碼供參考。

上面測試數據全是$1$的猜想給出了一個優化方向，考慮到有大量重復的計算，某一個$x$算過了，再給定同樣的$x$又重新算了一遍。那么我們何不一次性計算出所有答案，即預處理所有可能的$x$，對于每個查詢直接$O(1)$輸出答案。因為$1\le x\le n$，每個$x$計算的時間復雜度為$O(logx?\frac{n}{x})$，故總的計算量為$\sum _{i=1}^n(logi?\frac{n}{i})$。公式有點眼熟，哦！原來是調和級數！依據如下。
$$\sum _{i=1}^{\infty }\frac{1}{i}=1+\frac{1}{2}+\frac{1}{3}+?$$
調和級數的第$n$項部分和為：
$$\sum _{i=1}^n\frac{1}{i}=1+\frac{1}{2}+\frac{1}{3}+?+\frac{1}{n}$$
也叫作第$n$個調和數。第$n$個調和數與$n$的自然對數的差值（即$\sum _{i=1}^n\frac{1}{i}?\ln n$）收斂于常數（歐拉-馬歇羅尼常數）。

綜上所述，整體時間復雜度為$O(q+n?\ln n?logn)$，$1s$可過。

參考代碼（C++）

超時代碼

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100'005;
const int mod = 1'000'000'007;
int cnt[maxn];
int n, q;int qpow(int a, int b) {int ans = 1;while (b) {if (b & 1)ans = 1LL * ans * a % mod;a = 1LL * a * a % mod;b >>= 1;}return ans;
}int calc(int lim, int step) {if (lim < 0)return 0;int ans = 0, lastc = 0;for (int i = 0; i <= n; i += step) {int j = min(i + lim, n);ans += cnt[j] - lastc;lastc = cnt[min(i + step - 1, n)];}return ans;
}void solve() {cin >> n >> q;for (int i = 1; i <= n; ++i)cnt[i] = 0;int x, id = n >> 1;for (int i = 0; i < n; ++i) {cin >> x;++cnt[x];}for (int i = 1; i <= n; ++i)cnt[i] += cnt[i - 1];for (int i = 0; i < q; ++i) {cin >> x;int l = 0, r = x - 1, ans = -1;while (l <= r) {int mid = (l + r) >> 1;int cl = calc(mid - 1, x), ce = calc(mid, x);if (cl <= id && ce > id) {ans = mid;r = mid - 1;} else if (cl > id)r = mid - 1;elsel = mid + 1;}cout << ans << (" \n"[i == q - 1]);}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t = 1;cin >> t;while (t--)solve();return 0;
}

通過代碼

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100'005;
const int mod = 1'000'000'007;
int cnt[maxn], ans[maxn];
int n, q;int qpow(int a, int b) {int ans = 1;while (b) {if (b & 1)ans = 1LL * ans * a % mod;a = 1LL * a * a % mod;b >>= 1;}return ans;
}int calc(int lim, int step) {if (lim < 0)return 0;int ans = 0, lastc = 0;for (int i = 0; i <= n; i += step) {int j = min(i + lim, n);ans += cnt[j] - lastc;lastc = cnt[min(i + step - 1, n)];}return ans;
}void solve() {cin >> n >> q;for (int i = 1; i <= n; ++i)cnt[i] = 0;int x, id = n >> 1;for (int i = 0; i < n; ++i) {cin >> x;++cnt[x];}for (int i = 1; i <= n; ++i)cnt[i] += cnt[i - 1];for (int i = 1; i <= n; ++i) {int l = 0, r = i - 1, res = -1;while (l <= r) {int mid = (l + r) >> 1;int cl = calc(mid - 1, i), ce = calc(mid, i);if (cl <= id && ce > id) {res = mid;r = mid - 1;} else if (cl > id)r = mid - 1;elsel = mid + 1;}ans[i] = res;}for (int i = 0; i < q; ++i) {cin >> x;cout << ans[x] << (" \n"[i == q - 1]);}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t = 1;cin >> t;while (t--)solve();return 0;
}