好久没写题解了，这就来水一篇。
题目大意
给定一个长为 $N$ 的字符串 $S$，由 o、-、x 组成。
判断 $S$ 是否符合下列条件：
$1\le N\le 100$
分析
签到题。直接按题意模拟即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#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 水题大法 速通大法
1
2
3
|
input()
s = input()
print('Yes' if 'o' in s and 'x' not in s else 'No')
|
成功省掉$208$个字符（逃
题目大意
给定两个 $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$次并逐个判断即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#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;
}
|
题目大意
有 $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)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#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;
}
|
题目大意
我们有一个字符串 $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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#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;
}
|
题目大意
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)$，有兴趣的可以自己尝试，这里不详细解释了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#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;
}
|
题目大意
有一个 $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。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#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;
}
|
题目大意
==注意本题时间限制为 $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$ 片时最小可能的每片上草莓数的最大值。
详见代码。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
#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;
}
|