2023/12/16 晚 (OTC+8)22:35
T1 Constructive Problems
题意描述：
问如图方式填充一个 n\times m 的矩阵要预先填充多少个格子。
分析：
观察发现，每一列至少填充一个，才能构成条件，答案为 max(n,m)。
T2 Begginer’s Zelda
题意描述：
你可以把树的任意一条路径合并成一个点（如图），问多少次能将整棵树合并成一个点。
分析：
观察每次合并，最好的情况是包含两个叶子节点的合并。每次合并不会增加叶子节点，所以只要统计叶子节点总数。答案为 \lfloor (sum+1)/2\rfloor。
T3 Largest Subsequence
题意描述：
每次进行操作：找出字符串中字典序最大的子序列，并将其循环右移一位。问几次操作后序列为有序，或无法有序。
分析：
手模几次观察规律，如果可以使序列变为有序，所有的位移仅存在于最初始的最大字典序子序列上。
一个字符串中最大字典序的子序列一定是不递增的，所以倒着枚举出不递减子序列即可。根据这个性质，我们发现每次右移必须松弛一个字符，也就是初始子序列中最后一位，即最小一位，若不能松弛（也就是转过来之后发现前面一位比它大），当前新增的字符的大小一定会更大，也就构不成有序。
观察松弛操作，发现是reverse，那么将子序列翻转，判断是否有序，若有序，答案为\texttt{子序列长度}-\texttt{第一个字符的数量}。
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
const double eps = 1e-8;
const double pi = acos(-1.0);
int T;
const int MAXN = 2e5 + 10;
char s[MAXN], t[MAXN];
int n;
inline void init(){for(int i = 0; i <= n; i++) {s[i] = t[i] = 0;}}
/*
czddeneeeemigec
znmigec
ccddezeeeenmige
ccddeeeeeeznmig
*/
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// freopen("C.in", "r", stdin);
cin >> T;
while(T--) {
cin >> n;
init();
cin >> s;
vector<int> indx;
char tmp = s[0];
int tot = 0;
char mox = 'a';
for(int i = n - 1; i >= 0; i--) {
if(s[i] >= mox) {
mox = s[i];
t[tot++] = s[i];
indx.emplace_back(i);
}
}
tot--;
int sz = tot;
while(tot >= 1 and t[tot] == t[tot - 1]) tot--;
int flag = 1;
for(int i = 0; i < indx.size(); i++) {
s[indx[i]] = t[sz - i];
}
for(int i = 1; i < n; i++) {
if(s[i] < s[i - 1]) flag = 0;
}
if(flag == 1) cout << tot << endl;
else cout << -1 << endl;
}
return 0;
}
T4 Cyclic MEX
题意描述：
给定集合 \lbrace 0, 1, 2, \ldots , n-1\rbrace 的一种排列，求该排列循环右移任意次数后 \sum^{n}_{i=1}mex[a_1,a_2,\ldots,a_i] 的最大值。
分析：
观察发现几个性质：
- 所有序列的MEX是不递减的。
- 每次循环也就是弹出第一个数字 x ，MEX小于 x 的序列不变，大于 x 的序列变为 x。
- 每次弹出第一个数字减少第一位的MEX值，后加上 n。
由于不递减，每次减少的第一位值都很好维护，而 n 是最大的，直接添加在最后。很容易想到使用 deque 维护这个状态，分别记录MEX的数值和个数。而每个数字只会被弹出一次，所以删除和添加的次数是 \mathcal{O}(n) 的。
Code：
#include<bits/stdc++.h>
using namespace std;
#define int long long//不开 long long 见祖宗
const int N = 1e6 + 10;
int T, n, a[N];
signed main()
{
ios::sync_with_stdio(false);//关流同步，或者scanf
cin.tie(nullptr);
cout.tie(nullptr);
cin >> T;
while(T--){
deque<pair<int, int>> q;//结构体也行，全局记得清空
cin >> n;
vector<int> stat(n + 1);//注意初始化，以及空间，开大了会T
int pos = 0;
int cnt = 0, ans = 0;
for(int i = 1; i <= n; i++) {
cin >> a[i];
stat[a[i]] = 1;
while(stat[pos]) pos++;
q.push_back({pos, 1});
cnt += pos;
}
ans = cnt;
// cout << ans << endl;
for(int i = 1; i < n; i++) {
cnt -= q.front().first;
pair<int, int> now = {a[i], 0};
q.front().second--;
if(q.front().second == 0) {
q.pop_front();
}
while(!q.empty() && q.back().first > a[i]) {
cnt -= q.back().first * q.back().second;
now.second += q.back().second; q.pop_back();
}
q.push_back(now);
cnt += now.first * now.second;
q.push_back({n, 1});
cnt += n;
ans = max(ans, cnt);
}
cout << ans << endl;
}
return 0;
}
