Contestant~. Rank 881. Rating +7.
A. Prime Deletion
题意
给定 \(\{0, 1, \ldots, 9\}\) 的一种排列，定义一次操作为在排列剩余元素个数 大于2 的条件下，任意删去一个数字。
任意次操作后，输出排列拼接而成的数字，并满足该数字是质数。
思路
因为 \(13, 31\) 都是质数，并且 \(1\) 一定在 \(3\) 的左边或者右边，因而判一下 \(1\) 的位置即可。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt "bits/stdc++.h"
#include chatgpt
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
string s;
cin >> s;
int i1 = -1, i3 = -1;
for(int i=0;i<9;i++){
if(s[i] == '1') i1 = i;
if(s[i] == '3') i3 = i;
}
if(i1 < i3) cout << "13\n";
else cout << "31\n";
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}太奇妙了
B. Two Binary Strings
题意
给定两个长度均为 \(n\) 的二进制字符串 \(a, b\)，满足两个字符串都以 \(0\) 开头，\(1\) 结尾。
定义一次操作为选定任意一个字符串 \(s\)，并选定 \(1 \leq l < r \leq n\)，满足 \(s_l = s_r\)，并将 \(s_{[l, r]}\) 内所有字符赋值为 \(s_l\)。
任意次操作后，输出两个字符串是否可能相同。
思路
既然都以 \(0\) 开头，\(1\) 结尾，那么如果存在某个位置 \(i\)，满足 \(a_i = b_i = 0\)，那么我们就可以将 \(a_{[1, i]}, b_{[1, i]}\) 内所有字符改为 \(0\)。
同理，如果存在某个位置 \(j\)，满足 \(a_j = b_j = 1\)，那么我们就可以将 \(a_{[j, n]}, b_{[j, n]}\) 内所有字符改为 \(1\)。
显然，若 \(j = i + 1\)，那么最后的字符串一定相等。
那么问题等价于：判断是否存在 \(i \in [1, n - 1]\)，使 \(a_i = b_i = 0, a_{i + 1} = b_{i + 1} = 1\)。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt "bits/stdc++.h"
#include chatgpt
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
string s1, s2;
cin >> s1 >> s2;
int n = s1.size();
s1 = " " + s1, s2 = " " + s2;
for(int i=1;i<=n-1;i++){
if(s1[i] == s2[i] && s1[i + 1] == s2[i + 1]){
if(s1[i] == '0' && s1[i + 1] == '1'){
cout << "YES\n";
return;
}
}
}
cout << "NO\n";
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}如果没那个条件就成大模拟了（
C. Queries for the Array
题意
定义 已排序 为该序列不降序，若序列元素个数 \(< 2\)，也判定为已排序。
对于一个未知的序列，一开始序列为空，给定操作序列对应的字符串，判断是否合法，其中操作如下：
"0"：当前序列未排序；
"1"：当前序列已排序；
"+"：加入任意一个数字；
"-"：删去 最后 一个数字
思路
首先，既然元素个数 \(<2\) 一定已排序，那么我们只需记录当前序列的长度 \(cnt\)，如果出现 \(cnt < 2\)，且当前字符为 \(0\)，那么直接判 \(NO\)。
其次，我们记最小的 未排序 序列的长度为 \(mn\)，最长的 已排序 序列的长度 \(mx\)，
那么，另一个不合法的条件是：\(mn \leq mx, mn > 0\)。
我们可以考虑下面的构造：
遇到 \(+\)，将 \(1\) 加入序列；
遇到 \(0\)，将最后一个数改为 \(0\)。
可以证明上面的构造是最优的，且恰好满足上述的合法判定条件。
那么我们考虑下面的维护：
遇到 \(+\)，增加序列长度；
遇到 \(-\)，减小序列长度。此时，如果 \(mx\) 和减小前的长度相等，那么我们就得去掉一个数，也就是减掉 \(1\)。同样的，如果 \(mn\) 和减小前的长度相等，那么可能会出现删除该数后整个序列有序，因而将 \(mn\) 修改为 \(0\)；
遇到 \(1\)，\(mx = cnt\)；
遇到 \(0\)，如果 \(cnt < 2\)，那么直接判 \(NO\)。此时一并更新 \(mn\)；
在处理完每个字符之后，判断 \(mn \leq mx, mn > 0\) 是否满足，满足直接判 \(NO\)。
当然，也可以直接用线段树维护，不过去掉板子之后码量差不多。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt "bits/stdc++.h"
#include chatgpt
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
string s;
cin >> s;
int mx = 0, mn = 0; //最大已排序前缀，最小未排序后缀
int cnt = 0;
for(auto &e : s){
if(e == '+') cnt ++;
else if(e == '-'){
cnt --;
if(mx == cnt + 1) mx = cnt;
if(cnt < mn) mn = 0;
}else if(e == '1'){
mx = cnt;
}else{
if(cnt <= 1){
cout << "NO\n";
return;
}
if(mn == 0 || mn > cnt) mn = cnt;
}
if(mn <= mx && mn > 0){
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}线段树用在 \(C\) 还是太抽象了
D. Sorting By Multiplication
题意
给定一个序列 \(a\)，定义一次操作为选定 一个区间 以及 任意一个数字 \(x\)，并将区间内的所有数都乘上 \(x\)。
在 \(x\) 可以为负的条件下，输出最小操作总数，使整个序列升序。
思路
显然，上一个数的状态可以转移到下一个数，且对应的变化是是否多一次操作，因而我们考虑动态规划。
具体来说，我们令 \(dp[i][j]\) 为前 \(i\) 个数让其升序的最小操作数，\(j\) 代表当前位置是否为负数。
那么，我们按照 \(a_{i - 1}, a_i\) 的大小进行分类讨论：
\(a_{i - 1} < a_i\)，此时如果该位为正数，我们就无需操作；否则我们得单独对该数进行一次操作，来让这个数比前一个 负数 大，显然这个时候，前面的数不可以是正数。
\(a_{i - 1} > a_i\)，此时如果该位是正数，我们就得单独对该数进行一次操作，来让这个数比前一个数大；否则，我们就无需操作，但需要满足上一个数是负数。
\(a_{i - 1} = a_i\)，此时无论如何，当前位置都得单独进行一次操作，来让这个数比前一个数大。
当然，初始化的时候 \(dp[1][1] = 1\)。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt "bits/stdc++.h"
#include chatgpt
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
vector<vector<int>> dp(n + 1, vector<int>(2)); //当前位置是不是负数
dp[1][1] = 1;
for (int i = 2; i <= n; i++) {
dp[i][0] = dp[i - 1][1];
dp[i][1] = dp[i - 1][1];
if (a[i - 1] < a[i]) {
dp[i][1] ++;
dp[i][0] = min(dp[i][0], dp[i - 1][0]);
} else if (a[i - 1] > a[i]) {
dp[i][0] = min(dp[i][0], dp[i - 1][0] + 1);
} else {
dp[i][1] ++;
dp[i][0] = min(dp[i][0], dp[i - 1][0] + 1);
}
}
cout << min(dp[n][0], dp[n][1]) << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}主要难在设计状态（