題目地址

https://codeforces.com/contest/2093

銳評

在所有題意都理解正確的情況下，整體難度不算太難。但是偏偏存在F這么惡心的題意，樣例都不帶解釋一下的，根本看不懂題。D題也惡心，在于遞歸過程的拆分，需要點數學，跟打印遞歸定義的圖形一樣，寫麻了，好在過了。E題居然卡雙 $log$ 做法常數，也是惡心。反而是G題很典，太裸了，可惜被D防住了，根本沒看到G題。再次陷入“看完所有題不會寫，不看完所有題卻會寫”的魔咒。主要還是自己太菜了，打破不了這個魔咒，大佬們就沒這個煩惱。

題解

Problem A. Ideal Generator

題目大意

由 $k$ 個正整數組成的數組 $a$ 在 $[a_1,a_2,\dots ,a_k]=[a_k,a_{k?1},\dots ,a_1]$ 的情況下稱為回文數組（其實就是正著讀反著讀是一樣的）。例如，數組 $[1,2,1]$ 和 $[5,1,1,5]$ 是回文數組，而數組 $[1,2,3]$ 和 $[21,12]$ 不是回文數組。

如果任何整數 $n$ ( $n\ge k$ ) 都可以表示為一個長度正好為 $k$ 的回文數組的元素之和，我們就稱這個數 $k$ 為理想生成數。數組中的每個元素都必須大于 $0$ 。

例如，數字 $1$ 是一個理想生成數，因為任何自然數 $n$ 都可以用數組 $[n]$ 生成。然而，數字 $2$ 并不是一個理想生成數，因為不存在長度為 $2$ 的和為 $3$ 的回文數組。

請判斷給定的數字 $k$ 是否是理想生成數。

題解思路：思維

先通過樣例觀察，發現奇數可以，偶數不行。開始驗證，假如和為 $k$ ，那么全部數組元素為 $1$ 即可，假如和為 $k+1$ ，那么全部數組元素為 $1$ 的基礎上，有一個數要加上 $1$ 還要是回文數組，那么只能放在最中間的位置上了，不然所放位置對稱的那一個位置就不相等了。又因為 $n$ 是連續的，所以差值為 $1$ 只有數組長度是奇數才能滿足，每次都在最中間位置加上 $1$ 。時間復雜度為 $O(1)$ 。

參考代碼（C++）

#include <bits/stdc++.h>
using namespace std;
int n;void solve() {cin >> n;cout << ((n & 1) ? "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. Expensive Number

題目大意

正整數 $n$ 的代價被定義為數字 $n$ 除以其數位之和的結果。

例如，數字 $104$ 的代價是 $\frac{104}{1+0+4}=20.8$ ，數字 $111$ 的代價是 $\frac{111}{1+1+1}=37$ 。

給你一個不包含前導零的正整數 $n$ 。你可以從數字 $n$ 中刪除任意數位(包括不刪除)，這樣剩下的數字至少包含一位數，并且嚴格大于零。剩下的數字不能重新排列。因此，你可能得到一個前導為零的數字。

例如，給你一個數字 $103554$ 。如果去掉 $1$ 、 $4$ 和一個數字 $5$ ，最后得到的數字是 $035$ ，其代價是 $\frac{035}{0+3+5}=4.375$ 。

為了使代價最小，你需要從這個數字中刪除最少多少個數字？

題解思路：貪心

首先，一個數字的數位之和是不可能大于這個數字的，最多和它相等。那么代價最小意味著什么？顯然就是相等。所以只有一位數字時代價達到最小，代價為 $1$ 。因為題目刪除數位后允許有前導 $0$ ，所以選定某個數字前面的 $0$ 可以不刪除。又因為題目要求刪除后組成的這個數必須嚴格大于 $0$ ，所以我們要找一個非 $0$ 數位。因為前導 $0$ 可以保留，后導 $0$ 不能保留（保留就不是個位數了），所以我們倒著枚舉，找到第一個非 $0$ 數位位置，將這個位置前面的非 $0$ 數位刪除以及后面的數位刪除，刪除的數位個數即是答案。時間復雜度為 $O(n)$ 。

參考代碼（C++）

#include <bits/stdc++.h>
using namespace std;
string str;void solve() {cin >> str;int n = str.size();int id = n - 1;for (int i = n - 1; i >= 0; --i)if (str[i] != '0') {id = i;break;}int ans = n - 1 - id;for (int i = id - 1; i >= 0; --i)if (str[i] != '0')++ans;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 C. Simple Repetition

題目大意

帕夏喜歡質數！為了找到生成質數的新方法，他再次對互聯網上的一種算法產生了興趣：

• 要得到一個新數字 $y$ ，重復 $k$ 次數字 $x$ 的十進制表示 $x$ (不含前導零)。

例如， $x=52$ 和 $k=3$ 可以得到 $y=525252$ ， $x=6$ 和 $k=7$ 可以得到 $y=6666666$ 。

帕夏非常希望得到的數字 $y$ 是質數，但他還不知道如何檢驗這種算法生成的數字的質性。請幫助帕夏，告訴他 $y$ 是否是質數！

如果一個整數 x 只有 2 個不同的除數 1 和 x ，那么這個整數 x 就是質數。例如， 13 是質數，因為它只有 2 個除數： 1 和 13 。請注意，數字 1 不是質數，因為它只有一個除數。

題解思路：思維/分類討論

我們來一一分析下。

• $k=1$ ，顯然只需要判定 $x$ 是否質數。
• $k>1$ ，即 $x$ 至少重復了 $2$ 次，設 $x$ 有 $n$ 個數位，那么 $y$ 顯然有一個除數 $x$ ，使得 $\frac{y}{x}=a_1\underset{n?1個}{\underbrace{0?0}}{a}_2\underset{n?1個}{\underbrace{0?0}}\dots a_k$ ，其中 $a_i=1,1\le i\le k$ 。那么只要 $1<x<y$ ， $y$ 必然不是質數，顯然 $x<y$ 必然成立，所以只需要再單獨判斷一下 $x$ 為 $1$ 的情況即可。

根據上面的分析，問題得解。時間復雜度為 $O(1)$ 。

參考代碼（C++）

#include <bits/stdc++.h>
using namespace std;
int n, m;bool check(int x) {if (x < 2)return false;for (int i = 2; i * i <= x; ++i)if (x % i == 0)return false;return true;
}void solve() {cin >> n >> m;if (m == 1)cout << (check(n) ? "YES\n" : "NO\n");else if (n == 1) {int x = 0;for (int i = 0; i < m; ++i)x = x * 10 + 1;cout << (check(x) ? "YES\n" : "NO\n");} elsecout << "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 D. Skibidi Table

題目大意

瓦迪姆喜歡用整數填充方形表格。不過今天他想到了一個好玩的方法！以大小為 $2\times 2$ 的表格為例，表格的行從上到下編號，列從左到右編號。我們將 $1$ 置于左上角單元格， $2$ 置于右下角單元格， $3$ 置于左下角單元格， $4$ 置于右上角單元格。這就是他所需要的全部樂趣！

幸運的是，瓦迪姆有一個大小為 $2^n\times 2^n$ 的表格。他計劃用從 $1$ 到 $2^{2n}$ 的整數按升序填滿它。為了填滿這樣一個大表，瓦迪姆將把它分成 $4$ 個相等的方表，先填滿左上角的表，然后填滿右下角的表，接著填滿左下角的表，最后填滿右上角的表。在填滿每張小方表的過程中，他又會把每張小方表分割成更小的表，直到填滿 $2\times 2$ 大小的方表為止。

現在瓦迪姆迫不及待地想開始填表，但是他有兩類 $q$ 個問題：

• 第 $x$ 行第 $y$ 列的單元格中的數字是多少
• 數字 $d$ 位于哪個單元格坐標

幫助回答瓦迪姆的問題。

題解思路：DFS

題意倒是很直接，思路也很明確，就是不斷DFS縮小區域。但是這個區域怎么設計還真是惡心，會的很會，不會的真的會卡很久，看群友有被卡兩小時的。

首先對于塊的大小，假如當前處于第 $n$ 層，塊的大小為 $2^{n?1}\times 2^{n?1}$ ，即是寬高各減一半。其次是對于坐標步長，根據前面分析（寬高各減一半），可知步長就是 $2^{n?1}$ 。知道這兩個性質就好辦了，只需要知道當前處于第幾層，以及當前層的左上角坐標，即可一步步縮小范圍，直到不能再縮小，即是答案，詳見代碼。時間復雜度為 $O(nq)$ 。

參考代碼（C++）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int n, q;ll dfs1(int cur, int l, int r, int x, int y) {// cout << "dfs1:" << cur << ':' << l << ':' << r << ':' << x << ':' << y << '\n';if (l == x && r == y)return 1;ll dt = 1LL << (cur - 1);ll dd = dt * dt;if (x >= l + dt && y >= r + dt)return dd + dfs1(cur - 1, l + dt, r + dt, x, y);if (x >= l + dt)return (dd << 1) + dfs1(cur - 1, l + dt, r, x, y);if (y >= r + dt)return 3 * dd + dfs1(cur - 1, l, r + dt, x, y);return dfs1(cur - 1, l, r, x, y);
}pii dfs2(int cur, int l, int r, ll d) {// cout << "dfs2:" << cur << ':' << l << ':' << r << ':' << d << '\n';if (d == 1)return {l, r};ll dt = 1LL << (cur - 1);ll dd = dt * dt;if (d > 3 * dd)return dfs2(cur - 1, l, r + dt, d - 3 * dd);if (d > (dd << 1))return dfs2(cur - 1, l + dt, r, d - (dd << 1));if (d > dd)return dfs2(cur - 1, l + dt, r + dt, d - dd);return dfs2(cur - 1, l, r, d);
}void solve() {cin >> n >> q;string op;int x, y;ll d;while (q--) {cin >> op;if (op == "->") {cin >> x >> y;cout << dfs1(n, 1, 1, x, y) << '\n';} else {cin >> d;pii ans = dfs2(n, 1, 1, d);cout << ans.first << ' ' << ans.second << '\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 E. Min Max MEX

題目大意

給你一個長度為 $n$ 的數組 $a$ 和一個數字 $k$ 。

子數組的定義是數組中一個或多個連續元素的序列。你需要將數組 $a$ 分割成 $k$ 個不重疊的子數組 $b_1,b_2,\dots ,b_k$ ，使得這些子數組的合集等于整個數組。此外，你需要最大化 $x$ 的值，即 $x=\min (MEX(b_i)),1\le i\le k$ 。

$MEX(v)$ 表示數組 $v$ 中沒有的最小非負整數。

題解思路：二分

對于 $u=MEX(v)$ ，如果選擇數組 $v$ 的一部分數組成數組 $vt$ ，那么對于所有 $w<u$ ，是否都能找到 $w=MEX(vt)$ ？答案是肯定的。所以我們考慮二分，下限 $l=0$ ，上限 $r=n$ （因為數組頂多是 $[0,1,\dots ,n?1]$ ）。那么我們怎么去check呢？對于 $MEX$ 為 $u$ ，我們只需要維護一個集合，然后遍歷整個數組，對于每個元素，滿足 $a_i<u,0\le i<n$ ，就將其加入集合，當集合元素個數達到了 $u$ ，然后計數加一（表示可以劃分為一個子數組，滿足 $MEX\ge u$），并且清空當前集合。這樣到最后，只要計數大于等于 $k$ ，表示可以合理劃分。時間復雜度為 $O(nlognlogn)$ （check用到了set，換成數組每次標記取反可以降到 $O(nlogn)$ ）。

PS：此題居然卡雙 $log$ 做法常數，真是無語啊！

參考代碼（C++）

雙 $log$ 超時代碼。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int maxn = 200'005;
int a[maxn];
int n, m;bool check(int x) {set<int> st;for (int i = 0; i < x; ++i)st.insert(i);if (st.empty())return true;set<int> stc;int cnt = 0;for (int i = 0; i < n; ++i) {if (a[i] < x)stc.insert(a[i]);if (stc.size() == st.size()) {++cnt;stc.clear();if (cnt >= m)return true;}}return cnt >= m;
}void solve() {cin >> n >> m;for (int i = 0; i < n; ++i)cin >> a[i];int l = 0, r = n + 1, ans = -1;while (l <= r) {int mid = (l + r) >> 1;if (check(mid)) {ans = mid;l = mid + 1;} elser = mid - 1;}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;
}

雙 $log$ 通過代碼。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int maxn = 200'005;
int a[maxn];
int n, m;bool check(int x) {set<int> st;int cnt = 0;for (int i = 0; i < n; ++i) {if (a[i] < x)st.insert(a[i]);if (st.size() == x) {++cnt;st.clear();if (cnt >= m)return true;}}return cnt >= m;
}void solve() {cin >> n >> m;for (int i = 0; i < n; ++i)cin >> a[i];int l = 1, r = n, ans = 0;while (l <= r) {int mid = (l + r) >> 1;if (check(mid)) {ans = mid;l = mid + 1;} elser = mid - 1;}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;
}

單 $log$ 通過代碼。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int maxn = 200'005;
int a[maxn];
bool vis[maxn];
int n, m;bool check(int x) {for (int i = 0; i < x; ++i)vis[i] = false;bool f = true;int cnt = 0, cur = 0;for (int i = 0; i < n; ++i) {if (a[i] < x) {if (vis[a[i]] != f) {++cur;vis[a[i]] = f;}}if (cur == x) {++cnt;cur = 0;f = !f;if (cnt >= m)return true;}}return cnt >= m;
}void solve() {cin >> n >> m;for (int i = 0; i < n; ++i)cin >> a[i];int l = 1, r = n, ans = 0;while (l <= r) {int mid = (l + r) >> 1;if (check(mid)) {ans = mid;l = mid + 1;} elser = mid - 1;}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. Hackers and Neural Networks

題目大意

黑客們再次試圖利用神經網絡的輸出創建娛樂短語。這一次，他們想獲得長度為 $n$ 的字符串數組 $a$ 。

最初，他們有一個長度為 $n$ 的數組 $c$ ，其中充滿了空白，用符號 $?$ 表示。因此，如果 $n=4$ ，則初始值為 $c=[?,?,?,?]$ 。

黑客可以訪問 $m$ 個神經網絡，每個神經網絡都有自己的請求答案版本–長度為 $n$ 的字符串數組 $b_i$ 。

黑客試圖通過以下操作從數組 $c$ 中獲取數組 $a$ ：

• 選擇神經網絡 $i$ ，對數組 $c$ 執行下一步操作：選擇一個隨機的空白，例如在位置 $j$ 處，將 $c_j$ 替換為 $b_{i,j}$ 。

  例如，如果選擇了第一個神經網絡 $b_1=[\text{?I?},\text{?love?},\text{?apples?}]$ ，當前 $c=[?,\text{?like?},?]$ ，那么在對第一個神經網絡進行操作后， $c$ 可能會變成 $[\text{?I?},\text{?like?},?]$ 或 $[?,\text{?like?},\text{?apples?}]$ 。

• 選擇位置 $j$ 并將 $c_j$ 替換為空白。

不幸的是，由于黑客訪問神經網絡的方式，他們只能在所有操作完成后才能看到修改后的數組 $c$ ，因此他們必須事先指定整個操作序列。

然而，神經網絡的隨機行為可能會導致永遠無法獲得所需的數組，或者獲得所需的數組需要過多的操作。

因此，黑客們希望您能幫助他們選擇一個操作序列，以保證在最少的操作次數內獲得數組 $a$ 。

更具體地說，如果存在一個操作序列可以保證從數組 $c$ 中獲得數組 $a$ ，那么在所有這樣的序列中，找出一個操作次數最少的序列，并輸出其中的操作次數。

如果沒有將數組 $c$ 轉換成數組 $a$ 的操作序列，則輸出 $?1$ 。

題解思路：貪心

題意真的很長且很拉，真的看完好像不知道要求什么？讓我們再細細品味一下！反正就是進行兩個操作嘛，只要對應位置的字符串不對就一定要繼續操作。只要操作，那么操作次數必然會增加。

假如某個操作后，某個位置已經是正確的，下一次操作你會不會去改它？顯然不會了，不然你還得再至少進行一次操作二以及至少隨機一次操作一，而且隨機后不一定是對的，何必呢？

如果所有位置都是空的，你會不會進行操作二？顯然也不會，白白浪費一次操作嘛。所以第一次操作肯定是操作一，這是個隨機過程。

通過上面的分析，我們唯一能決定的就是可以選擇跑哪個神經網絡。從概率論角度來說，我們當然希望選擇命中概率更高的，這樣所得的期望就越大，后續所需要的操作就更少。所以第一次操作就至關重要了，我們就選命中概率最大的神經網絡，這樣我們就能保證 $n$ 次操作后，隨機正確位置最大。這樣所有位置都被填滿了，最后對不正確的位置，我們只需要先執行一次操作二，再找到一個神經網絡，其對應位置存在正確字符串，因為只會空白位置隨機，而當前空白位置只有一個，顯然這是一個必然事件。

上面操作一定是最優的嗎？一定的。假設你選擇某個神經網絡的命中率是 $\frac{x}{y}$ ，你把其他所有的神經網絡全部組合起來，命中率形如 $\frac{x+a}{y+b}$ ，其不可能更大。

對于不存在的情況，顯然所有對應位置都沒有目標串，就無法做到。時間復雜度為 $O(mn\max (|b_{i,j}|))$ 。

參考代碼（C++）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int maxn = 505;
string p[maxn], str[maxn][maxn];
int cntr[maxn], cntc[maxn];
int n, m;void solve() {cin >> n >> m;for (int i = 0; i < n; ++i) {cin >> p[i];cntc[i] = 0;}for (int i = 0; i < m; ++i) {cntr[i] = 0;for  (int j = 0; j < n; ++j) {cin >> str[i][j];if (str[i][j] == p[j]) {++cntc[j];++cntr[i];}}}for (int i = 0; i < n; ++i)if (cntc[i] == 0) {cout << "-1\n";return;}int maxc = 0;for (int i = 0; i < m; ++i)maxc = max(maxc, cntr[i]);cout << (n + ((n - maxc) << 1)) << '\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. Shorten the Array

題目大意

長度為 $m$ 的數組 $b$ 的美感定義為所有可能數對 $1\le i\le j\le m$ 中的 $\max (b_i\oplus b_j)$ ，其中 $x\oplus y$ 是數字 $x$ 和 $y$ 的 bitwise XOR。我們將數組 $b$ 的美感表示為 $f(b)$ 。

如果數組 $b$ 中有 $f(b)\ge k$ ，那么這個數組 $b$ 就叫做美麗數組。

最近，科斯佳從商店買了一個長度為 $n$ 的數組 $a$ 。他認為這個數組太長了，所以打算從中剪切出一些美麗的子數組。也就是說，他想選擇數字 $l$ 和 $r$ ( $1\le l\le r\le n$ )，這樣數組 $a_{l\dots r}$ 就很美麗了。這樣一個子數組的長度為 $r?l+1$ 。整個數組 $a$ 也被視為一個子數組(包含 $l=1$ 和 $r=n$ )。

你的任務是找出數組 $a$ 中最短的美麗子數組的長度。如果沒有一個子數組是美麗的，那么你應該輸出數字 $?1$ 。

題解思路：雙指針+字典樹Trie

首先，對于每個 $l$ ，如果找到第一個滿足條件的 $r(r\ge l)$ ，那么顯然 $r+1(r<n)$ 也可以。既然這樣，那么我們維護一個雙指針，對于每個左指針，不斷擴展右指針，直到找到第一個滿足條件的位置，更新答案即可。那么怎么快速計算出當前區間是否可以滿足條件呢？很容易就會想到字典樹求當前區間可以得到的最大異或值。時間復雜度為 $O(n)$ （計算次數實際為 $30n$ ，常數忽略，但實際運行時間還是要考慮的）。

參考代碼（C++）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int maxn = 200'005;
const int maxnode = 6'000'005;
const int sigma_size = 2;
struct trie {int child[maxnode][sigma_size];int value[maxnode];int size;void init() {size = 1;memset(child[0], 0, sizeof(child[0]));}void insert(int x, int y) {int pos = 0;for (int i = 29; i >= 0; --i) {int id = (x >> i) & 1;if (!child[pos][id]) {memset(child[size], 0, sizeof(child[size]));value[size] = 0;child[pos][id] = size++;}pos = child[pos][id];value[pos] += y;}}int query(int x) {// cout << "query: " << x << '\n';int pos = 0, ans = 0;for (int i = 29; i >= 0; --i) {int id = (x >> i) & 1;int idx = id ^ 1;int p = child[pos][idx];if (p && value[p]) {ans |= 1 << i;pos = p;} else {p = child[pos][id];if (p && value[p])pos = p;elsereturn -1;}}// cout << "query: ans = " << ans << '\n';return ans;}
} tr;
int a[maxn];
int n, m;void solve() {cin >> n >> m;for (int i = 0; i < n; ++i)cin >> a[i];if (m == 0) {cout << "1\n";return;}tr.init();int l = 0, r = 0, ans = n + 1;while (r < n) {// cout << l << ", " << r << endl;while (r < n && tr.query(a[r]) < m)tr.insert(a[r++], 1);if (r < n)ans = min(ans, r - l + 1);tr.insert(a[l++], -1);if (l > r)r = l;}cout << (ans == n + 1 ? -1 : 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;
}