好久没写题解了，这就来水一篇。
A - Job Interview
题目大意
给定一个长为 \(N\) 的字符串 \(S\)，由 o、-、x 组成。
判断 \(S\) 是否符合下列条件：
- \(S\) 中至少有一个
o。 - \(S\) 中没有
x。
\(1\le N\le 100\)
分析
签到题。直接按题意模拟即可。
代码
#include <cstdio>
using namespace std;
int main()
{
while(getchar() != '\n');
char c;
bool ok = false;
while((c = getchar()) != '\n')
{
if(c == 'x')
{
puts("No");
return 0;
}
if(c == 'o')
ok = true;
}
puts(ok? "Yes": "No");
return 0;
}
Python
水题大法速通大法input() s = input() print('Yes' if 'o' in s and 'x' not in s else 'No')成功省掉\(208\)个字符（
逃
B - Coloring Matrix
题目大意
给定两个 \(N\times N\) 的矩阵 \(A\) 和 \(B\)，都由 \(0\) 和 \(1\) 组成。
你可以将 \(A\) 顺时针旋转 \(0\degree,90\degree,180\degree\) 或 \(270\degree\)（任选其一）。
判断旋转后的 \(A\) 能否满足：
- 对于每个 \(A_{i,j}=1\) 的 \((i,j)\)，\(B_{i,j}=1\)。
\(1\le N\le 100\)
分析
原题中还贴心的给出了如何将一个矩阵旋转\(90\degree\)，照题意模拟，旋转\(4\)次并逐个判断即可。
代码
#include <cstdio>
#define maxn 105
using namespace std;
int a[maxn][maxn], b[maxn][maxn], c[maxn][maxn];
int main()
{
int n;
scanf("%d", &n);
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
scanf("%d", a[i] + j);
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
scanf("%d", b[i] + j);
for(int x=0; x<4; x++)
{
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
c[i][j] = a[i][j];
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
a[i][j] = c[n - 1 - j][i];
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(a[i][j] && !b[i][j])
goto bad; // goto 不是好习惯（改不掉了），千万不要学
puts("Yes");
return 0;
bad:;
}
puts("No");
return 0;
}
C - Cards Query Problem
题目大意
有 \(N\) 个盒子，编号 \(1\sim N\)，初始均为空。依次处理 \(Q\) 次询问：
1 i j：将数字 \(i\) 写在一张空卡牌上，放入盒子 \(j\)。2 i：按升序输出盒子 \(i\) 中的所有卡牌（允许重复）。3 i：按升序输出包含卡牌 \(i\) 的所有盒子的编号。若一个盒子里有多张卡牌 \(i\)，则这个盒子的编号仅输出一次。
\(1\le N,Q\le 2\times 10^5\)
对于查询中所有卡牌上的数字 \(x\)，均有 \(1\le x\le 2\times 10^5\)。
对于查询中所有的盒子编号 \(y\)，均有 \(1\le y\le N\)。
题目保证输出不超过 \(2\times 10^5\) 个整数。
分析
我们分别考虑两种输出操作的做法。
2 i：很容易想到，既然要按升序输出，并且允许重复，我们可以使用 \(N\) 个multiset来依次存储每个盒子中的卡牌，处理操作 \(1\) 时更新。3 i：首先不能从 \(N\) 个盒子中依次查找，这样明显会 TLE。正确的做法是，使用 \(2\times 10^5\) 个set（注意不能重复，所以不用multiset）分别存储每张卡牌所在的箱子编号，处理操作 \(1\) 时更新。
此外，本题也可以使用 priority_queue、map，甚至直接输出时排序并去重，不过使用 set 的方式是最简单、代码量最少的。几种方法的总时间复杂度都是 \(\mathcal O(Q\log N)\)。
代码
#include <cstdio>
#include <set>
#define maxn 200005
using namespace std;
multiset<int> box[maxn];
set<int> has[maxn];
int main()
{
int n, q;
scanf("%d%d", &n, &q);
while(q--)
{
int op, i;
scanf("%d%d", &op, &i);
if(op == 1)
{
int j;
scanf("%d", &j);
box[j].insert(i);
has[i].insert(j);
}
else if(op == 2)
{
for(int x: box[i])
printf("%d ", x);
putchar('\n');
}
else if(op == 3)
{
for(int x: has[i])
printf("%d ", x);
putchar('\n');
}
}
return 0;
}
D - Writing a Numeral
题目大意
我们有一个字符串 \(S\)。初始时，\(S=\) 1。
处理如下 \(Q\) 次询问：
1 x：将数字 \(x\) 追加至 \(S\) 的最后面。保证 \(x \in \{1,2,3,4,5,6,7,8,9\}\)。2：删除 \(S\) 的第一个字符。保证此时 \(|S|>1\)。3：输出 \(S\) 在十进制中对应的数字，对 \(998244353\) 取模。
\(1\le Q\le 6\times 10^5\)
分析
首先，我们必须使用一个 queue 或 deque 来存储字符串 \(S\)。然后，为了在 \(\mathcal O(1)\) 的时间内处理第三种操作，我们必须维护 \(S \bmod (P=998244353)\) 的值，记为 \(A\)。下面考虑前两种操作对 \(A\) 的影响：
1 x：只需在十进制中腾出一位 \(0\) 再加上 \(x\) 即可，可表示为 \(A \leftarrow (10A+x)\bmod P\)。2：先从队列中取出 \(S\) 的第一位，记为 \(x\)。我们需要从 \(A\) 中减掉最高位乘上其在十进制中的权值，即 \(A \leftarrow (A-10^{|S|}x)\bmod P\)（此时 \(|S|\) 表示队列取出前一位后的长度，等同于取出前的 \(|S|-1\)）
对于 \(10^n\) 的计算，我们可以用一个变量实时维护 \(10^{|S|}\bmod P\) 的值，也可以预处理出所有 \(10^n \bmod P\)，或者直接使用快速幂。
总时间复杂度为 \(\mathcal O(Q\log Q)\)（快速幂）或 \(\mathcal O(Q)\)（预处理）。
代码
实现 \(1\)：使用 AtCoder Library + 快速幂，队列使用 deque
#include <cstdio>
#include <deque>
#include <atcoder/modint>
using namespace std;
using modint = atcoder::modint998244353;
int main()
{
deque<int> s;
s.push_back(1);
int q;
scanf("%d", &q);
modint ans = 1;
while(q--)
{
int op;
scanf("%d", &op);
if(op == 1)
{
int x;
scanf("%d", &x);
s.push_back(x);
ans = ans * 10 + x;
}
else if(op == 2)
{
int x = s.front(); s.pop_front();
ans -= x * modint(10).pow((int)s.size());
}
else printf("%d\n", ans.val());
}
return 0;
}
实现 \(2\)：用变量维护 \(10^{|S|} \bmod P\) 的值，队列使用 queue
#include <cstdio>
#include <queue>
#define MOD 998244353
using namespace std;
int main()
{
int Q;
scanf("%d", &Q);
queue<int> q;
q.push(1);
int ans = 1, p = 1;
while(Q--)
{
int op;
scanf("%d", &op);
if(op == 1)
{
int x;
scanf("%d", &x);
q.push(x);
ans = (ans * 10LL + x) % MOD;
p = p * 10LL % MOD;
}
else if(op == 2)
{
ans -= (long long) q.front() * p % MOD; q.pop();
p = p * 299473306LL % MOD; // 299473306 是 10 对于 MOD 的逆元，这句话相当于把 p 除以 10
if(ans < 0) ans += MOD;
}
else printf("%d\n", ans);
}
return 0;
}
E - Unfair Sugoroku
题目大意
Takahashi 和 Aoki 将玩一个游戏。游戏规则如下：
- 游戏棋盘有 \(N\) 个点（编号 \(1\sim N\)），两玩家轮流投骰子并前进。
- Takahashi 初始在点 \(A\)，Aoki 初始在点 \(B\)。
- Takahashi 的骰子等概率出现 \(1,2,\dots,P\)，Aoki 的骰子等概率出现 \(1,2,\dots,Q\)。
- 当一个玩家当前在点 \(x\) 且骰子出现 \(i\) 时，他移动到点 \(\min(x+i,N)\)。
- 先到达点 \(N\) 的玩家胜利。
假定 Takahashi 先行，求他赢的概率，对 \(998244353\) 取模。
\(2\le N\le 100\)
\(1\le A,B\le N\)
\(1\le P,Q\le 10\)
分析
考虑概率 DP（下面用 Ta 表示 Takahashi，Ao 表示 Aoki）：
- 令 \(f_{i,j}\) 表示 Ta 在点 \(i\)，Ao 在点 \(j\)，下一轮 Ta 移动时 Ta 获胜的概率。
- 令 \(g_{i,j}\) 表示 Ta 在点 \(i\)，Ao 在点 \(j\)，下一轮 Ao 移动时 Ta 获胜的概率。
首先考虑初始状态。根据游戏规则，对于任意 \(1\le i<n\)，\(f_{n,i}=g_{n,i}=1,f_{i,n}=g_{i,n}=0\)。
转移也很显然：
- 对于 Ta 当前走的每种可能的步数 \(k=1,2,\dots,P\)，有 \(f_{i,j}:=f_{i,j}+\frac1Pg_{\min(i+k,N),j}\)。
- 对于 Ao 当前走的每种可能的步数 \(k=1,2,\dots,Q\)，有 \(g_{i,j}:=g_{i,j}+\frac1Qf_{i,\min(j+k,N)}\)。
整理上面的式子，得到：
\[f_{i,j}=\begin{cases} 0 & (j=N)\\ 1 & (i=N)\\ \frac1P\sum\limits_{k=1}^Pg_{\min(i+k,N),j} & (i,j\ne N) \end{cases}\\ ~\\ g_{i,j}=\begin{cases} 0 & (j=N)\\ 1 & (i=N)\\ \frac1Q\sum\limits_{k=1}^Qf_{i,\min(j+k,N)} & (i,j\ne N) \end{cases}\\ \]这里注意，由于 \(i=j=N\) 的情况无意义（不可能达到），所以无需特殊考虑。
最终输出结果即为 \(f_{p,q}\)。总时间复杂度为 \(\mathcal O(N^2(P+Q))\)。使用前缀和可以优化到 \(\mathcal O(N^2)\)，有兴趣的可以自己尝试，这里不详细解释了。
代码
#include <cstdio>
#include <algorithm>
#define MOD 998244353
#define maxn 105
using namespace std;
using LL = long long;
inline LL inv(LL x) // x ^ (MOD - 2) % MOD
{
int y = MOD - 2;
LL res = 1LL;
while(y)
{
if(y & 1) (res *= x) %= MOD;
(x *= x) %= MOD, y >>= 1;
}
return res;
}
inline void add(int& x, int y)
{
if((x += y) >= MOD)
x -= MOD;
}
int f[maxn][maxn], g[maxn][maxn];
int main()
{
int n, a, b, p, q;
scanf("%d%d%d%d%d", &n, &a, &b, &p, &q);
for(int i=0; i<n; i++)
f[n][i] = g[n][i] = 1, f[i][n] = g[i][n] = 0;
LL prob_p = inv(p), prob_q = inv(q);
for(int i=n-1; i>=a; i--)
for(int j=n-1; j>=b; j--)
{
for(int k=1; k<=p; k++)
add(f[i][j], g[min(i + k, n)][j]);
f[i][j] = f[i][j] * prob_p % MOD;
for(int k=1; k<=q; k++)
add(g[i][j], f[i][min(j + k, n)]);
g[i][j] = g[i][j] * prob_q % MOD;
}
printf("%d\n", f[a][b]);
return 0;
}
F - Rook Score
题目大意
有一个 \(10^9\times 10^9\) 的网格。令 \((i,j)\) 表示第 \(i\) 行 \(j\) 列的格子（\(1\le i,j\le 10^9\)）。
对于 \(i=1,2,\dots,N\)，整数 \(x_i\) 被写在 \((r_i,c_i)\) 上。在剩余的 \(10^{18}-N\) 个格子里只有数字 \(0\)。
你可以选择一个格子 \((R,C)\) 并计算与其同行或同列的 \(2\times 10^9-1\) 个整数之和 \(S\)。
求最大可能的 \(S\)。
\(1\le N\le 2\times 10^5\)
\(1\le r_i,c_i,x_i\le 10^9\)
\((r_i,c_i)\ne (r_j,c_j)~~~~~~(i\ne j)\)
分析
我们令 \(f(R,C)\) 表示对于 \((R,C)\) 的 \(S\)，令 \(\mathrm{rs}_R\) 表示第 \(R\) 行的整数之和，\(\mathrm{cs}_C\)表示第 \(C\) 列的整数之和，\(A_{R,C}\) 表示 \((R,C)\) 上的整数。
容易发现，\(f(R,C)=\mathrm{rs}_R+\mathrm{cs}_C-A_{R,C}\)。
然后证明当 \(f(R,C)\) 最大时，\(\mathrm{rs}_R,\mathrm{cs}_C\ne0\)：
- 若 \(\mathrm{rs}_R=\mathrm{cs}_C=0\)，则 \(f(r_0,c_0)=x_0>0=f(R,C)\)，所以 \((R,C)\) 不是最优解；
- 若 \(\mathrm{rs}_R\ne0,\mathrm{cs}_C=0\)，则 \(f(R,c_0)=\mathrm{rs}_R+\mathrm{cs}_{c_0}-A_{R,c_0}\ge f(R,C)=\mathrm{rs}_R\)，所以 \((R,C)\) 不是最优解（或有多个最优解，但其中至少有一个解 \((x,y)\) 使得 \(\mathrm{rs}_x,\mathrm{cs}_y\ne0\)）
- \(\mathrm{rs}_R=0,\mathrm{cs}_C\ne0\) 同理。
所以，我们可以依次考虑每一行 \(R\)（\(\mathrm{rs}_R\ne 0\)），相当于固定了 \(\mathrm{rs}_R\)。这时，我们只需找到一列 \(C\)（\(\mathrm{cs}_C\ne 0\)），使得 \(\mathrm{cs}_C-A_{R,C}\) 最大，就可以解决此问题。
但如果依次考虑所有包含点的列，则最坏情况下时间复杂度为 \(\mathcal O(N^2)\)，无法通过此题。这时，我们可以使用一个 multiset 或 map 来维护当前每列对答案的贡献（\(\mathrm{cs}_C-A_{R,C}\)）。对于每一行 \(R\)，仅需更新这一行上有非 \(0\) 数字的点 \((R,C)\) 的贡献（减去 \(A_{R,C}\)）即可。
这样，由于每个点会被更新正好一次，所以总时间复杂度为 \(\mathcal O(N\log N)\)。
代码
注意更新完成，求得当前答案后需要复原 map 或 multiset。
#include <cstdio>
#include <vector>
#include <set>
#include <unordered_map>
using namespace std;
using LL = long long;
using pii = pair<int, int>;
unordered_map<int, vector<pii>> rows;
unordered_map<int, LL> col_sum;
template <typename T>
class MaxSet {
private:
multiset<T> s;
public:
inline void insert(const T& x) { s.insert(x); }
inline void update(const T& old, const T& New) {
s.erase(s.find(old));
s.insert(New);
}
inline T max() { return *s.rbegin(); }
};
int main()
{
int n;
scanf("%d", &n);
while(n--)
{
int x, y, v;
scanf("%d%d%d", &x, &y, &v);
rows[x].emplace_back(y, v);
col_sum[y] += v;
}
MaxSet<LL> s;
for(auto [_, sum]: col_sum)
s.insert(sum);
LL ans = 0LL;
for(auto& [x, v]: rows)
{
for(auto [y, val]: v)
s.update(col_sum[y], col_sum[y] - val);
LL cur = s.max();
for(auto [y, val]: v)
s.update(col_sum[y] - val, col_sum[y]), cur += val;
if(cur > ans) ans = cur;
}
printf("%lld\n", ans);
return 0;
}
G - Strawberry War
题目大意
注意本题时间限制为 \(6\mathrm s\)。
我们有一块长方形的蛋糕。它可被看作一个 \(H\times W\) 的网格，第 \(i\) 行 \(j\) 列上有 \(s_{i,j}\) 个草莓。
我们对蛋糕进行 \(T\) 次切分，切成 \(T+1\) 块。每次切蛋糕可以选择当前的一块，并将其从中间横切或竖切成两块：
你想把蛋糕切的尽可能均匀。意思是，令 \(M\) 表示切分完成后每一块上的草莓数量的最大值，\(m\) 表示最小值，求出 \(M-m\) 的最小值。
\(1\le H,W\le 6\)
\(1\le T\le HW-1\)
\(0\le s_{i,j}\le 10^{16}\)
分析
本题解参考官方题解。
操作完成后得到的蛋糕一定是蛋糕的子矩形，所以最多只有 \(\binom {H+1}2\times\binom {W+1}2=\frac{H(H+1)W(W+1)}4\le 441\) 种数字在剩下的块中。令这些可能的数分别为 \(a_1,a_2,\dots,a_X\)。可知 \(X\le \frac{H(H+1)W(W+1)}4\le 441\)。
根据上面的 \(a\)，我们只需先确定 \(m\in \{a_1,a_2,\dots,a_X\}\)，再找到与其对应的最小 \(M\)，算出 \(M-m\) 的最小值即可。
定义 \(f_{i,j,k,l,m}\) 表示将 \(x\in[i,j),y\in[k,l)\) 的子矩形切成 \(m\) 片时最小可能的每片上草莓数的最大值。
详见代码。
代码
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1000000000000000000;
int main(){
int H, W, T;
cin >> H >> W >> T;
vector<vector<long long>> s(H, vector<long long>(W));
for (int i = 0; i < H; i++){
for (int j = 0; j < W; j++){
cin >> s[i][j];
}
}
vector<vector<vector<vector<long long>>>> sum(H, vector<vector<vector<long long>>>(H + 1, vector<vector<long long>>(W, vector<long long>(W + 1, 0))));
vector<long long> x;
for (int i = 0; i < H; i++){
for (int j = i + 1; j <= H; j++){
for (int k = 0; k < W; k++){
for (int l = k + 1; l <= W; l++){
for (int m = i; m < j; m++){
for (int n = k; n < l; n++){
sum[i][j][k][l] += s[m][n];
}
}
x.push_back(sum[i][j][k][l]);
}
}
}
}
int cnt = x.size();
long long ans = INF;
for (int i = 0; i < cnt; i++){
vector<vector<vector<vector<vector<long long>>>>> dp(T + 1, vector<vector<vector<vector<long long>>>>(H, vector<vector<vector<long long>>>(H + 1, vector<vector<long long>>(W, vector<long long>(W + 1, INF)))));
for (int j = H - 1; j >= 0; j--){
for (int k = j + 1; k <= H; k++){
for (int l = W - 1; l >= 0; l--){
for (int m = l + 1; m <= W; m++){
if (sum[j][k][l][m] >= x[i]){
dp[0][j][k][l][m] = sum[j][k][l][m];
}
for (int n = j + 1; n < k; n++){
for (int o = 0; o < (n - j) * (m - l); o++){
for (int p = 0; p < (k - n) * (m - l) && o + p < T; p++){
dp[o + p + 1][j][k][l][m] = min(dp[o + p + 1][j][k][l][m], max(dp[o][j][n][l][m], dp[p][n][k][l][m]));
}
}
}
for (int n = l + 1; n < m; n++){
for (int o = 0; o < (k - j) * (n - l); o++){
for (int p = 0; p < (k - j) * (m - n) && o + p < T; p++){
dp[o + p + 1][j][k][l][m] = min(dp[o + p + 1][j][k][l][m], max(dp[o][j][k][l][n], dp[p][j][k][n][m]));
}
}
}
}
}
}
}
ans = min(ans, dp[T][0][H][0][W] - x[i]);
}
cout << ans << endl;
}