A - Treasure Chest
题意
给定由 \(\texttt{.}\)、\(\texttt{|}\)、\(\texttt{*}\) 三种字符组成的长度为 \(n\) 的字符串 \(s\)，保证 \(\texttt{|}\) 的个数为 \(2\)，\(\texttt{*}\) 的个数为 \(1\)。
判断 \(\texttt{*}\) 是否在两个 \(\texttt{|}\) 之间。
代码
#include <cstring>
#include <iostream>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
using namespace std;
int constexpr N = 1e2 + 10;
int n;
char s[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> s + 1;
bool flag = false;
f(i, 1, n) {
if (s[i] == '*') {
if (flag) return cout << "in\n", 0;
else return cout << "out\n", 0;
} else if (s[i] == '|') flag = !flag;
}
return 0;
}
B - Trick Taking
题意
\(n\) 个人，每个人手握一张牌，第 \(i\) 个人的牌的颜色为 \(c_i\)，数字为 \(r_i\)。
给定 \(t\)，如果有人的牌的颜色为 \(t\)，输出数字最大的那个人的编号；如果没有人的牌的颜色为 \(t\)，输出颜色为 \(c_1\) 的牌中数字最大的那个人的编号。
代码
#include <iostream>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
using namespace std;
int const N = 2e5 + 10;
int n, t, x[N], m1, m2, a1, a2;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> t;
f(i, 1, n) cin >> x[i];
f(i, 1, n) {
int y; cin >> y;
if (x[i] == t) if (y > m1) m1 = y, a1 = i;
if (x[i] == x[1]) if (y > m2) m2 = y, a2 = i;;
}
if (m1 == 0) cout << a2 << '\n';
else cout << a1 << '\n';
return 0;
}
C - Dango
题意
给定只含有字符 \(\texttt-\) 和 \(\texttt o\) 长度为 \(n\) 的字符串 \(s\)，求最长的子串 \(t\)，长度为 \(l+1\)，满足 \(t_1=t_2=\dots=t_l=\texttt o,t_{l+1}=\texttt-\) 或 \(t_1=\texttt-,t_2=t_3=\dots=t_{l+1}=\texttt o\)。
输出最大的 \(l\)。无解输出 \(\texttt{-1}\)。
思路
无解情况只有全是 \(\texttt-\) 的情况和全是 \(\texttt o\) 的情况。
其他情况求出最长的一串 \(\texttt o\) 的长度即可。
代码
#include <iostream>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
using namespace std;
int constexpr N = 2e5 + 10;
int n, ans;
char s[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> s + 1;
if (s[1] == '-') {
int fl = false;
f(i, 1, n) if (s[i] == 'o') { fl = true; break; }
if (!fl) return cout << "-1\n", 0;
} else {
int fl = false;
f(i, 1, n) if (s[i] == '-') { fl = true; break; }
if (!fl) return cout << "-1\n", 0;
}
int l = 0;
f(i, 1, n) {
if (s[i] == '-') {
ans = max(ans, l);
l = 0;
} else ++l;
}
ans = max(ans, l);
cout << ans << '\n';
return 0;
}
D - Find by Query
题意
交互题。给定一个 \(0/1\) 串 \(s\) 的长度 \(n\)，你有 \(20\) 次向评测程序询问 \(s_i\) 的机会，求出一个位置 \(p\) 使得 \(s_p=0,s_{p+1}=1\)。保证 \(s_1=0,s_n=1\)，可以证明一定有解。
通过输出一行 \(\texttt{? }i\) 向评测程序询问 \(s_i\)，输出一行 \(\texttt{! }p\) 提交答案。
\(2\le n\le10^5\)。
思路
一个重要的性质是：如果 \(s_l=0\)，\(s_r=1\)，那么一定存在 \(p\in[l,r)\) 使得 \(s_p=0\)，\(s_{p+1}=1\)。
因此采用二分法。
代码
#include <iostream>
using namespace std;
int n;
bool query(int x) {
cout << "? " << x << endl;
int a; cin >> a;
return a;
}
signed main() {
cin >> n;
int l = 1, r = n;
while (l + 1 < r) {
int mid = l + r >> 1;
if (query(mid)) r = mid;
else l = mid;
}
cout << "! " << l << endl;
return 0;
}
E - Nearest Black Vertex
题意
给定 \(n\) 个点 \(m\) 条边的简单无向连通图，边权为 \(1\)，请你将所有节点染成黑或白两种颜色，满足：
- 至少有一个黑点；
- 给定 \(k\) 组 \(p_i,d_i\)，对于每个 \(i\in[1,k]\)，有：距离节点 \(p_i\) 最近的黑点与 \(p_i\) 的距离恰好为 \(d_i\)。
第一行输出 \(\texttt{Yes}\) 或 \(\texttt{No}\) 表示有解或无解。如果有解，第二行输出节点的染色方案（\(0/1\) 串）。
\(1\le n\le2000\)，\(n−1\le\min\left\{\dfrac{n(n-1)}2,2000\right\}\)，\(0\le k\le n\)。
思路
在每个 \(p_i\) 的方圆 \(d_i\) 以内一定全是白点，这是 必要条件。
于是我们从每个 \(p_i\) 开始 BFS，把必须要染白的节点标记上。
此时，把所有剩下的节点染黑一定不劣。然后验证，从还剩下的所有黑点开始第二轮 BFS，更新每个关键点与最近黑点的距离。如果距离都恰好为 \(d_i\) 那么这就是一个解，否则无解。
代码
#include <queue>
#include <bitset>
#include <cstring>
#include <iostream>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
using namespace std;
typedef pair<int, int> pii;
int constexpr N = 2e3 + 10;
int n, m, k, p[N], d[N], idx[N];
int head[N], cnt;
struct Edge {
int to, nxt;
} e[N << 1];
inline void add(int from, int to) {
e[++cnt].to = to, e[cnt].nxt = head[from], head[from] = cnt;
return;
}
bitset<N> c, vis;
queue<pii> q;
void BFS(int x) {
vis.reset();
q.emplace(p[x], 0);
vis[p[x]] = 1;
while (!q.empty()) {
int u = q.front().first, dis = q.front().second;
q.pop();
if (dis == d[x]) continue;
c[u] = 0;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (vis[v]) continue;
vis[v] = 1;
q.emplace(v, dis + 1);
}
}
return;
}
int md[N];
inline void gmn(int &a, int b) { a = a < b ? a : b; }
void check(int x) {
vis.reset();
q.emplace(x, 0);
vis[x] = 1;
while (!q.empty()) {
int u = q.front().first, dis = q.front().second;
q.pop();
gmn(md[idx[u]], dis);
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (vis[v]) continue;
vis[v] = true;
q.emplace(v, dis + 1);
}
}
return;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
int u, v;
f(i, 1, m) {
cin >> u >> v;
add(u, v), add(v, u);
}
c.set();
cin >> k;
f(i, 1, k) {
cin >> p[i] >> d[i];
idx[p[i]] = i;
BFS(i);
}
memset(md, 0x3f, sizeof md);
f(i, 1, n) if (c[i]) check(i);
f(i, 1, k) if (md[i] ^ d[i]) return cout << "No\n", 0; //循环里i写成k了调了好久。。。。。。。
cout << "Yes\n";
f(i, 1, n) cout << c[i];
cout << '\n';
return 0;
}
*F - Square Subsequence
题意
给定一个由小写英文字母组成的字符串 \(s\)，求不同的非空字符串 \(t\) 的个数，满足 \(tt\)（将 \(t\) 复制一遍拼接到后面）是 \(s\) 的子序列（不一定连续），结果对 \(998244353\) 取模。
\(1\le|s|\le100\)。
思路
设 \(|s|=n\)。题目中要求 \(t\) 不能重复，为了去重，我们在提取字符串时 尽量靠左 提取字符。
于是设 \(\sigma(i,c)\) 表示 \(s_{i+1}s_{i+2}\dots s_n\) 中字符 \(c\) 出现的最左位置（若没有 \(c\) 则设为 \(+\infty\)）。
那么提取的过程是这样的：（设 \(m\) 为 \(t\) 的长度）
- 取 \(s_{p_1}\)，其中 \(p_1=\sigma(0,t_1)\)；
- 取 \(s_{p_2}\)，其中 \(p_2=\sigma(p_1,t_2)\)；
- ……
- 取 \(s_{p_m}\)，其中 \(p_m=\sigma(p_{m-1},t_m)\)；
- 取 \(s_{q_1}\)，其中 \(q_1=\sigma(p_m,t_1)\)；
- 取 \(s_{q_2}\)，其中 \(q_2=\sigma(q_1,t_2)\)；
- ……
- 取 \(s_{q_m}\)，其中 \(q_m=\sigma(q_{m-1},t_m)\)。
考虑对于一个确定的 \(t\)，如何把它从 \(s\) 中提取出来。
枚举 第二个 \(t\) 的起始位置 \(x=q_1\)。那么就确定了 \(t_1=s_{q_1}=s_x\)，并且 \(p_1=\sigma(0,t_1)=\sigma(0,s_x)\)。
接着，我们枚举 \(t_2,t_3,\dots\) 是哪些字符：
- 钦定一个小写英文字母为 \(t_2\)，令 \(p_2=\sigma(p_1,t_2),q_2=\sigma(q_1,t_2)\)；
- 钦定一个小写英文字母为 \(t_3\)，令 \(p_3=\sigma(p_2,t_3),q_3=\sigma(q_2,t_3)\)；
- ……
- 钦定一个小写英文字母为 \(t_m\)，令 \(p_m=\sigma(p_{m-1},t_m),q_m=\sigma(q_{m-1},t_m)\)。
还有一个问题：如何把两段 \(t\) 衔接上，并且做到不重不漏？这就需要计入答案的 \(x\) 满足 \(x=\sigma(p_m,s_x)\)。
上面的过程可以在处理出 \(\sigma\) 后枚举 \(x\)，对于每个 \(x\) 用 DP 来计算。
设 \(dp(i,j)\) 表示使得 \(p_m=i\) 且 \(q_m=j\) 的不同的 \(t\) 的个数。
那么状态转移为：令 \(dp(\sigma(i,c),\sigma(j,c))\gets dp(\sigma(i,c),\sigma(j,c))+dp(i,j)\)。这个转移过程相当于扩展 \(t\) 的下一位的过程。
答案为 \(\sum_{x=\sigma(i,s_x)}\sum_jdp(i,j)\)。
时间复杂度 \(O(n^3w)\)，其中 \(w=26\)。
代码
#include <cstring>
#include <iostream>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
#define g(x, y, z) for (int x = (y); x >= (z); --x)
using namespace std;
int constexpr N = 110, W = 26;
int constexpr INF = 0x3f3f3f3f;
int constexpr MOD = 998244353;
int n, nxt[N][W], tmp[W], dp[N][N], ans;
char s[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> s + 1;
n = strlen(s + 1);
memset(tmp, 0x3f, sizeof tmp);
g(i, n, 1) {
memcpy(nxt[i], tmp, sizeof tmp);
tmp[s[i] - 'a'] = i;
}
f(x, 2, n) {
memset(dp, 0, sizeof dp);
f(i, 1, x - 1) if (s[i] == s[x]) { ++dp[i][x]; break; } //初值, 找最左边的i
f(i, 1, n) f(j, i + 1, n) f(c, 0, 25)
if ((nxt[i][c] ^ INF) && (nxt[j][c] ^ INF))
(dp[nxt[i][c]][nxt[j][c]] += dp[i][j]) %= MOD;
f(i, 1, n) if (x == nxt[i][s[x] - 'a'])
f(j, i + 1, n) (ans += dp[i][j]) %= MOD;
}
cout << ans << '\n';
return 0;
}
*G - Minimum Permutation
题意
给定一个长度为 \(n\) 的序列 \(a\)，其中只含有 \(1\) 到 \(m\) 的数字，并且 \(1\) 到 \(m\) 内的每个数字都至少出现一次。
求 \(a\) 的字典序最小的子序列 \(b\)，满足 \(b\) 是 \(1\) 到 \(m\) 的一个排列。
\(1\le m\le n\le2\times10^5\)。
思路
我们依次考虑每一位。如果当前正要选第 \(i\) 个数，那么位置 \(j\) 可选当且仅当还没选的 \(m-i\) 个数在区间 \([j+1,n]\) 内均至少出现一次。
由于要求字典序最小，所以在所有可选的位置中，我们选择数字最小的。如果最小的数字有多个，我们选择位置靠前的。
可以用反证法证明这样一定更优。
于是，为了保证合法，我们维护当前还没选的数中 最后出现的位置最靠前 的那个数。这样，如果这个位置在 \(j\) 之后，说明当前还没选的所有数都在 \(j\) 之后。可以用平衡树（STL set）维护，方便把不合法的情况删除，同时维护最小值。
为了保证最优，我们维护所有可选位置，以数字小为第一关键字、位置靠前为第二关键字排列。用堆（优先队列）维护。
代码
#include <set>
#include <queue>
#include <bitset>
#include <vector>
#include <iostream>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
using namespace std;
typedef pair<int, int> pii;
int constexpr N = 2e5 + 10;
int n, m, A[N], lst[N];
set<pii> s;
priority_queue<pii, vector<pii>, greater<pii> > b;
bitset<N> used;
vector<int> ans;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
f(i, 1, n) {
cin >> A[i];
lst[A[i]] = i;
}
f(i, 1, m) s.insert(make_pair(lst[i], i));
int l = 0;
f(k, 1, n) {
while (!s.empty() && k <= (*s.begin()).first) {
if (!used[A[k]]) b.push(make_pair(A[k], k));
++k;
}
--k;
while (!b.empty() && (used[b.top().first] || b.top().second < l)) b.pop();
if (!b.empty()) {
int x = b.top().first, y = b.top().second;
b.pop();
used[x] = true;
ans.push_back(x);
s.erase(make_pair(lst[x], x));
l = y;
}
if (ans.size() == m) break;
}
for (int i: ans) cout << i << ' ';
cout << '\n';
return 0;
}
Ex - Dice Sum Infinity
题意
高桥有一个小于 \(10^9\) 的正整数 \(R\) 和一个质地均匀的正方体骰子，每次掷出骰子都会等概率掷出 \(1,2,3,4,5,6\) 中的一个数，且每次掷骰子互不影响。
设 \(X\) 为当前掷出的数的总和。高桥将会不断地掷骰子，直到当前 \(X-R\) 为 \(10^9\) 的倍数时停止。
求掷骰子次数 \(C\) 的期望，对 \(998244353\) 取余。
具体地，设结果可以表示为既约分数 \(\dfrac pq\) 的形式，则输出满足 \(xq\equiv p\pmod{998244353}\) 的 \(x\)（\(0\le x<998244353\)）。
思路
代码
不会