A. Detective Book
模拟题，有一些细节需要注意。
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
const int N = 10010;
int n, a[N], ans = 0;
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", a + i);
int tot = 1;
while(tot <= n){
ans++;
int i = tot;
tot = max(tot, a[tot]);
while(++i <= tot){
tot = max(tot, a[i]);
}
tot++;
}
printf("%d\n", ans);
return 0;
}B. Good String
贪心。
- 找到从前往后第一个\(>\)，把后面全部删掉（如果不删掉，结果不会更优，前面的字符也无法处理）
- 找从后往前第一个\(<\)，把前面全部删掉，理由同上
找到这两个操作中最优的即可。
#include <cstdio>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 110;
int n;
char s[N];
int main(){
int T; scanf("%d", &T);
while(T--){
scanf("%d%s", &n, s + 1);
int l = 1, r = n;
while(s[l] != '>') l++;
while(s[r] != '<') r--;
printf("%d\n", min(l - 1, n - r));
}
return 0;
}C. Playlist
贪心。
我们现在题解前设定\(cnt\)为选的歌曲总长度，\(min\)为选的歌曲里最小的美好程度，即\(ans = min * cnt\)
将每首歌曲按\(b[i]\)（美好程度）从大到小排序。即保证\(b[i] >= b[i + 1] (1 <= i < n)\)
我们首先考虑没有歌曲限制，可以选择无限个歌曲。
每次选的美好程度一定是连续的一段\([1, r]\)，也就是\([1, r]\)区间内的歌曲必须全部选择。
证明：反证法
如果没有放满，则一定存在一个歌曲\(i\)满足\(b[i] >= min\)。如果选择了这个歌曲，那么\(minn\)不会产生变化，又题目规定\(t[i] >= 1\)，即加入后\(cnt\)一定会变大，所 以答案一定会更优。
所以，假设没有限制，我们只需要从从大到小考虑每一个歌曲，把它放入，找到最优答案，由于顺次考虑，设当前考虑歌曲为\(i\)，\(minn = b[i]\)（因为从大到小排序），\(cnt\)也是增加了\(t[i]\)，可以顺利求解。
如果有限制呢？
我们可以从已选的歌曲中删，因为已选的歌曲满足\(b[i] >= minn\)，即使删除\(minn\)值不会发生变化。所以我们只要从已选中选一个\(t[i]\)（长度）最小的即可，这个过程可以用小根堆维护。
PS：由于写的时候以为要动态维护最小值，所以写了两个小根堆，实际只用一个，另外一个排序即可，但是其实复杂度没有变化，因为快排也是\(O(nlogn)\)...
#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 300010;
int n, k, t[N], b[N];
priority_queue<PII> q;
priority_queue<int, vector<int>, greater<int> > minn;
int main(){
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++){
scanf("%d%d", t + i, b + i);
q.push(make_pair(b[i], t[i]));
}
LL cnt = 0, ans = -1;
int tot = 0;
while(!q.empty()){
PII u = q.top(); q.pop(); tot++;
minn.push(u.second);
cnt += u.second;
ans = max(ans, cnt * u.first);
if(tot == k) cnt -= minn.top(), minn.pop(), tot --;
}
printf("%lld\n", ans);
return 0;
}D. Minimum Triangulation
考虑到只能用边上的点做三角形的边。要分割成\(n - 2\)个三角形。
可以做两种选择可以达成要求：
- 找一个重心\(i\)，然后连接另外每一个点即可。答案是\(i * x * y + i * y + z + ...\)
- 换根，每次转移中心，答案是\(x * y * z + y * z * a + ...\)
要求权值最小，选择方案\((1)\)且选重心为\(1\)即可，因为换根下所有根都是$ >= 1$，所以值必然会不优。因为本人太弱，做完题看题解才知道还有通项公式，作为蒟蒻的我根本不懂...
#include <cstdio>
#include <iostream>
using namespace std;
int n, res = 0;
int main(){
scanf("%d", &n);
for(int i = 2; i < n; i++)
res += i * (i + 1);
printf("%d\n", res);
return 0;
}E. Palindrome-less Arrays
自闭，我给看懵了。
考虑到如果存在奇回文，必定存在长度为\(3\)的回文子串，那么我们只要保证\(a[i] != a[i + 2]\)即可。这时候我们把奇偶拆分，通过\(dp\)预处理一段\(-1\)连续字串的处理方案，（用\(dp\)处理）再相乘即可。
（以上全部理解至题解，萌新根本想不到...）
设\(f[i][0/1]\) 为中间连续\(i\)个\(-1\)，两端数字相同\(/\)不同的方案数
边界：\(f[0][0] = 1, f[0][1] = 0\)
\(f[i][0] = (k - 2) * f[i - 1][0] + f[i - 1][1]\)
也就是说，可以从\(i - 1\)个连续\(-1\)，再加上一个数字，只需满足这个字符\(!=\)开头和结尾即可，而开头和结尾不一样，所以是\(k - 2\)。也可以从\(i - 1\)个，两端相同的过来，方案是唯一的
\(f[i][1] = (k - 1) * f[i - 1][0]\)
同理。
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 200010, MOD = 998244353;
int n, k, a[N], b[N], l1 = 0, l2 = 0, f[N][2];
int inline mul(int x, int y){
return ((LL)x * y) % MOD;
}
int inline add(int x, int y){
return ((LL)x + y) % MOD;
}
int power(int q, int m){
int res = 1;
while(m){
if(m & 1) res = (LL)res * q % MOD;
q = (LL)q * q % MOD;
m >>= 1;
}
return res;
}
int work(int w[], int len){
if(n == 0) return 1;
int l = 1, r = len;
while(l <= len && w[l] == -1) l++;
if(l == len + 1) return mul(k, power(k - 1, len - 1));
while(r && w[r] == -1) r--;
int res = mul(power(k - 1, l - 1), power(k - 1, len - r));
int first = l;
for(l = first + 1; l <= r; l++){
if(w[l] == -1) continue;
res = mul(res, f[l - first - 1][w[first] == w[l]]);
first = l;
}
return res;
}
int main(){
scanf("%d%d", &n, &k);
f[0][0] = 1;
for(int i = 1; i <= n; i++){
f[i][0] = add(mul(k - 2, f[i - 1][0]), f[i - 1][1]);
f[i][1] = mul(k - 1, f[i - 1][0]);
}
for(int i = 1; i <= n; i++) {
if(i & 1) scanf("%d", &a[++l1]);
else scanf("%d", &b[++l2]);
}
printf("%d\n", mul(work(a, l1), work(b, l2)));
return 0;
}