C.Doors Breaking and Repairing
题意：有n个门以及他们的血量，A的能力值x和B的能力值y，和无限个回合，每回合先由A选择一个门进行攻击，选择的门血量减少x，然后由B选择一个门进行加固,血量增加y（一个门的血量(leq 0)以后他就不能被加固了，但即使一扇门没有被攻击过，也可以加固）
问最后A最多能打破多少扇门
如果 (x > y)，所有门的总血量每回合都会减少，经过无限个回合，所有的门一定都会被打破。
否则就是 (x leq y) 的情况，发现那些血量 (> x) 的门A永远打不破，因为A打一下，B就可以加固那扇门，血量 (leq x) 的门，A打破一扇，B就加固一扇门，A只能打破一半（A先手，要上取整）
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, x, y;
cin >> n >> x >> y;
if (x > y) return cout << n, 0;
int cnt = 0;
for (int i = 1; i <= n; ++i) cin >> y, cnt += y <= x;
cout << (cnt + 1) / 2 << endl;
return 0;
}
D.Balanced Ternary String
题意：给一个字符集是012的字符串（长度是3的倍数），可以修改某个位置上的字符，要求修改最少使得012个数相等，在此条件下输出字典序最小的串。
比较关键的想法
-
只能把多的改成少的，否则次数不是最少
-
0要靠前放，2要靠后放，只考虑这两个就可以（因为剩下的就是1）
#include <bits/stdc++.h>
using namespace std;
#define lop1(i, n) for (int i = 1; i <= n; ++i)
#define dlop1(i, n) for (int i = n; i >= 1; --i)
int n, cnt[3], per;
char s[300005], ans[300005];
int main() {
cin >> n >> (s + 1);
per = n / 3;
lop1(i, n)
if (s[i] == '0' && cnt[0] < per) if (cnt[0] < per) ++cnt[0], ans[i] = '0';
dlop1(i, n)
if (s[i] == '2' && cnt[2] < per) if (cnt[2] < per) ++cnt[2], ans[i] = '2';
//留下 $leq$ per 个0和2
lop1(i, n)
if (!ans[i] && s[i] != '1' && cnt[0] < per) if (cnt[0] < per) ++cnt[0], ans[i] = '0';
dlop1(i, n)
if (!ans[i] && s[i] != '1' && cnt[2] < per) if (cnt[2] < per) ++cnt[2], ans[i] = '2';
//0和2哪个多就改成另外一个
lop1(i, n)
if (!ans[i] && cnt[0] < per) ++cnt[0], ans[i] = '0';
dlop1(i, n)
if (!ans[i] && cnt[2] < per) ++cnt[2], ans[i] = '2';
//1改成0和2
lop1(i, n) if (!ans[i]) ans[i] = '1';
//剩下的是1
lop1(i, n) putchar(ans[i]);
return 0;
}
E.Monotonic Renumeration
题意：定义一个数组a的b数组为满足下列条件的数组
- (b[1]=0)
- 如果 (a_i=a_j)，那么(b_i=b_j)
- (b[i]=b[i-1]+1) 或者 (b[i]=b[i-1])
给出a，求合法的b的数量 膜998244353
计数+取模=毒瘤？好像不是这样耶...
设 (l[x]) 为最左边的 (x) 的位置， (r[x]) 为最右边的 (x) 的位置，由第二个条件可以发现 b数组 ([;l[x],;r[x];]) 内的数都是相等的，([;l[x],;r[x];]) 如果两个区间相交，那么它们并的区间内都是相等的
现在只剩下不相交的区间了，发现交界处有两种选择，一种是前面一段的b值+1，一种是不变（第三个条件），假设有m个不相交区间，就有m-1个交界处，答案就是 (2^{m-1})
我的代码不好看，放Tutorial里的代码
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int main()
{
int n;
scanf("%d", &n);
vector<int> a(n);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
map<int, int> lst;
vector<int> last_pos(n);
for(int i = n - 1; i >= 0; i--)
{
if(!lst.count(a[i]))
lst[a[i]] = i;
last_pos[i] = lst[a[i]];
}
int ans = 1;
int cur_max = -1;
for(int i = 0; i < n - 1; i++)
{
cur_max = max(cur_max, last_pos[i]);
if(cur_max == i)
ans = (2 * ans) % MOD;
}
printf("%d
", ans);
return 0;
}
F.Elongated Matrix
可以把每个行看成一个整体（比如看成一个点），一个点走到另一个点的代价就是 (min{a[i][k]-a[j][k]})，然后状压DP (dp[i][S]) 表示状态为S，当前走到第i个点的最大的k值，就行了。。。
发现不对，事实上还有个东西没处理，就是两列的交界处，事实上是选定的第一行跟最后一行 (min{a[i][k]-a[j][k-1]})，假设叫做 (dis1[i][j])
状压DP的过程是：先枚举起点s，算出所有状态，再枚举终点t，把答案跟 (min{dp[t][(111...)_2],dis1[s][t]}) 取max
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int dis[17][19], dis1[17][19], a[17][10001], dp[17][(1 << 16) + 1], n, m, ans;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; a[i++][m] = 2 * inf)
for (int j = 0; j < m; ++j) cin >> a[i][j];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
int *p = a[i], *p1 = a[j];
dis1[i][j] = dis[i][j] = inf;
for (int k = 0; k < m; ++k) dis[i][j] = min(dis[i][j], abs(*p++ - *p1)), dis1[i][j] = min(dis1[i][j], abs(*p1++ - *p));
}
for (int s = 0; s < n; ++s) {// 起点
memset(dp, 0, sizeof dp);
dp[s][1 << s] = inf;
for (int S = 0; S < (1 << n); ++S)
for (int i = 0; i < n; ++i) if (S & (1 << i))
for (int j = 0; j < n; ++j) if (!(S & (1 << j)))
dp[j][S | (1 << j)] = max(dp[j][S | (1 << j)], min(dp[i][S], dis[i][j]));
for (int t = 0; t < n; ++t) ans = max(ans, min(dis1[s][t], dp[t][(1 << n) - 1]));
}
cout << ans;
return 0;
}