A.Verify Password（字符串）

題意：

Monocarp正在開發他的新網站，目前面臨的挑戰是如何讓用戶選擇強密碼。

Monocarp認為，強密碼應滿足以下條件：

• 密碼只能由小寫拉丁字母和數字組成；
• 字母后面不能有數字（因此，每個字母后面要么有另一個字母，要么字符串結束）；
• 所有數字應按非遞減順序排序；
• 所有字母應按非遞減順序排序。

請注意，密碼可以只有字母或數字。

Monocarp成功地實現了第一個條件，但他在其余條件上很吃力。您能幫他驗證密碼嗎？

分析：

按照$ASCII$值進行比較（因為字母的$ASCII$本來就在數字后面）。只要找到前面比后面的數大就輸出$NO$，反之$YES$。

代碼：

#include<bits/stdc++.h>
using namespace std;void solve(){int n;cin>>n;string s;cin>>s;bool flag = true;for (int i = 1; i < n; i++){if (isalpha(s[i - 1]) && isdigit(s[i])){flag = false;break;}if(s[i - 1] > s[i]){flag = false;break;}}if(flag)cout<<"YES"<<endl;elsecout<<"NO"<<endl;
}int main(){int t;cin>>t;while(t--){solve();}return 0;
}

B.Increase/Decrease/Copy（思維）

題意：

給你兩個整數數組：長度為$n$的數組$a$和長度為$n+1$的數組$b$。

你可以按任意順序執行下列操作任意次數：

• 選擇數組$a$中的任意元素，并將其增加$1$；
• 選擇數組$a$中的任意元素，并將其減少$1$；
• 選擇數組$a$中的任意元素，復制并追加到數組$a$的末尾。

你的任務是計算將數組$a$轉換為數組$b$所需的最少上述操作次數（可能為零）。可以證明，在問題的限制條件下，這總是可能的。

分析：

對于$a_i?>b_i,1\le i\le n$，轉變的最小代價就是它們的差值。

對于$b_{n+1}$，得到它的最小代價就是$a_i?>b_i$過程中與它最小的差值$+1$。

代碼：

#include<bits/stdc++.h>typedef long long LL;
using namespace std;
#define INF 0x7fffffffvoid solve() {int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}vector<int> b(n + 1);for (int i = 0; i < n + 1; i++) {cin >> b[i];}int need = INF;LL ans = 0;for (int i = 0; i < n; i++) {ans += abs(b[i] - a[i]);need = min(need, abs(b[n] - b[i]));need = min(need, abs(b[n] - a[i]));if (a[i] < b[n] && b[n] < b[i] || a[i] > b[n] && b[n] > b[i])need = 0;}cout << ans + need + 1 << endl;
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

C.Job Interview（枚舉）

題意：

Monocarp打算開一家自己的IT公司。他想招聘$n$名程序員和$m$名測試員。

有$n+m+1$名候選人，按到達時間順序從$1$到$n+m+1$依次編號。第$i$個候選人的編程技能為$a_i$，測試技能為$b_i$（一個人的編程技能和測試技能是不同的）。團隊的技能是所有被聘為程序員的候選人的編程技能之和，以及所有被聘為測試員的候選人的測試技能之和。

當應聘者前來面試時，Monocarp會嘗試將其分配到最適合的職位（如果應聘者的編程技能較高，則錄用其為程序員，否則錄用其為測試員）。如果該職位的所有名額都已招滿，Monocarp就會將他們分配到其他職位。

你的任務是，針對每個候選人，計算如果除他們之外的所有人都來面試，團隊的技能。請注意，這意味著正好有$n+m$名候選人來參加面試，因此公司的所有$n+m$個職位都將被填滿。

分析：

從前往后遍歷，檢查一下是$a$能力值浪費了還是$b$能力值浪費了，然后從后往前枚舉，開一個數組維護一下最近后綴損失能力值。輸出答案的時候，如果當前的人的站的職位剛好是能力值被浪費的職位，輸出總和減去當前的人的能力值加上最近損失能力值。

代碼：

#include<bits/stdc++.h>typedef long long LL;
using namespace std;
const LL N = 1e6 + 10;
LL q[N], p[N], a[N], b[N];void solve() {LL n, m;cin >> n >> m;LL sum1, sum2, num1, num2, f;sum1 = sum2 = num1 = num2 = f = 0;for (int i = 0; i <= n + m; i++) {cin >> a[i];q[i] = p[i] = 0;}for (int i = 0; i <= n + m; i++) {cin >> b[i];f += a[i] > b[i];if (a[i] > b[i] && num1 <= n || m == i - num1) {num1++;sum1 += a[i];p[i] = 1;} elsesum1 += b[i];if (a[i] < b[i] && num2 <= m || n == i - num2) {num2++;sum2 += b[i];q[i] = 1;} elsesum2 += a[i];}for (int i = 0; i <= n + m; i++) {cout << " ";cout << (f > n ? (p[i] ? sum1 - a[i] : sum2 - b[i]) : (q[i] ? sum2 - b[i] : sum1 - a[i]));}
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

D.Invertible Bracket Sequences（前綴和、雙指針）

題意：

正則括號序列是指可以通過在序列的原始字符之間插入字符"1"和"+"來轉換成正確算術表達式的括號序列。例如

• 括號序列"()()“和”(())“是正則表達式（得到的表達式是”(1)+(1)“和”((1+1)+1)"）；
• 括號序列")(“、”(“和”)"則不是。

讓我們定義括號序列的逆序如下：用’)‘替換所有括號’(‘，反之亦然（用’(‘替換所有括號’)'）。例如，字符串"()((“和”)())"互為反義詞。

給你一個正則括號序列$s$。計算如果將$s$中從第$l$個字符到第$r$個字符（包括）的子串$s$替換為其逆序數，$s$仍然是正則括號序列的整數對$(l,r)$($1\le l\le r\le |s|$)的個數。

分析：

統計序列前$i$個有多少個左括號是剩余的，然后思考$(l,r)$的選擇有何特征：可以發現，若第$i$位之前所剩余的左括號跟第$j$位之前所剩余的左括號數量一樣，那么$(i+1,j)$這個區間就可能被選擇，否則一定不會被選擇。

因此我們將剩余左括號數量相同的位置放一起，然后考慮其區間能否真的被選中。通過觀察可以發現：若$(i,j)$之間位置的剩余左括號數量小于等于第$i$位之前所剩余的左括號的兩倍，那么這個區間就可以被選中，因此本題轉換成$RMQ$問題。

在枚舉位置時，隨著起始位置的增大，末尾位置也一定是非遞減的，因此用雙指針可以將復雜度從$O(n^{2}logn)$變為$O(nlogn)$。

代碼：

#include <bits/stdc++.h>using namespace std;
typedef long long LL;
const LL N = 5e05 + 10;LL n;
vector<LL> a(N, 0);LL Max[N][21];
LL Min[N][21];struct ST {void init() {for (LL i = 1; i <= n; i++) {Max[i][0] = a[i];Min[i][0] = a[i];}}void work() {for (LL j = 1; j <= 21; j++)for (LL i = 1; i + (1 << j) - 1 <= n; i++) {Max[i][j] = max(Max[i][j - 1], Max[i + (1 << (j - 1))][j - 1]);Min[i][j] = min(Min[i][j - 1], Min[i + (1 << (j - 1))][j - 1]);}}LL QueryMax(LL l, LL r) {LL k = log2(r - l + 1);return max(Max[l][k], Max[r - (1 << k) + 1][k]);}LL QueryMin(LL l, LL r) {LL k = log2(r - l + 1);return min(Min[l][k], Min[r - (1 << k) + 1][k]);}
};void solve() {string s;cin >> s;s = "0" + s;LL len = s.size();n = len + 5;a[0] = 0;vector<LL> st[len];for (LL i = 1; i < len; i++) {if (s[i] == '(') {a[i] = a[i - 1] + 1;} else {a[i] = a[i - 1] - 1;}st[a[i]].push_back(i);}ST st1;st1.init();st1.work();LL cnt = 0;for (LL i = 1; i < len; i++) {if (st[i].size() <= 1)continue;LL len = st[i].size();LL r = 0;for (LL l = 0; l < len; l++) {if (r == len) {cnt += (r - l - 1);continue;}LL left = st[i][l];LL right = st[i][r];while (r < len && st1.QueryMax(left, right) <= i * 2) {r++;if (r == len) {break;}right = st[i][r];}cnt += (r - l - 1);}}cout << cnt << endl;
}int main() {LL t;cin >> t;while (t--) {solve();}return 0;
}

賽后交流

在比賽結束后，會在交流群中給出比賽題解，同學們可以在賽后查看題解進行補題。

群號： 704572101，賽后大家可以一起交流做題思路，分享做題技巧，歡迎大家的加入。