AtCoder Beginner Contest 299
A - Treasure Chest (abc299 a)
题目大意
给定一个包含 |*.的字符串，其中|两个，*一个，问*是否在两个|之间。
解题思路
找到两个|的下标\(l, r\)以及 *的下标\(mid\)，看看是否满足 \(l < mid < r\)即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
string s;
cin >> n >> s;
int l = s.find('|'), r = s.find('|', l + 1), m = s.find('*');
if (m > l && m < r)
cout << "in" << '\n';
else
cout << "out" << '\n';
return 0;
}
B - Trick Taking (abc299 b)
题目大意
给定\(n\)个人的卡片，颜色为 \(c_i\)，数字为 \(r_i\)。
如果其中有颜色为 \(T\)的牌，则该颜色中数字最大的卡片对应的人赢。如果没有，则颜色为第一个人的卡牌颜色（即\(c_0\)）中数字最大的卡片对应的人赢。
问谁赢。
解题思路
按照题意的两种情况，分别判断即可。
神奇的代码
#include <bits/stdc++.h>
#include <vector>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, t;
cin >> n >> t;
int maxx = 0;
int win = 0;
bool ok = false;
vector<int> c(n);
for(int i = 0; i < n; ++ i){
cin >> c[i];
ok |= (c[i] == t);
}
if (!ok)
t = c[0];
for(int i = 0; i < n; ++ i){
int r;
cin >> r;
if (c[i] == t){
if (maxx < r){
maxx = r;
win = i;
}
}
}
cout << win + 1 << '\n';
return 0;
}
C - Dango (abc299 c)
题目大意
定义一种字符串\(s\)的等级\(X\)（是一个正整数）， 满足仅包含 -o，且头或尾仅一处为-，其余都为o。其等级\(X\)为 o的数量。
给定一个字符串\(T\)，问其子串的最大等级。
解题思路
依次遍历字符串\(T\)，遇到两个 -时期间就有一个等级。
然后再考虑从头到第一个-的子串，从最后一个-到尾的子串的等级。
注意单纯的一个-并不是合法的（\(0\)不是正整数）
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
string s;
cin >> n >> s;
int la = 0;
int ans = 0;
for(int i = 0; i < n; ++ i){
if (s[i] == '-'){
ans = max(ans, i - la);
la = i;
}
}
if (int pos = s.find('-'); pos != string::npos){
ans = max(ans, n - la);
ans = max(ans, pos + 1);
}
if (ans == 1)
ans = 0;
cout << ans - 1 << '\n';
return 0;
}
D - Find by Query (abc299 d)
题目大意
交互题。
这里有个长度为\(n\)的\(01\)字符串 \(s\) ，其中\(s_1 = 0, s_n = 1\) 。
你可以询问\(s_i\)的值。
输出一个位置 \(p\)满足 \(s_p \neq s_{p + 1}\)。
给定字符串长度\(n\)，你最多问20次。 \(n \leq 2 \times 10^5\)。
解题思路
感觉好像和某次 \(cf\)的交互题很像。
注意题意保证了\(s_1 = 0, s_n = 1\)。
首先询问中间位置\(mid = \frac{n}{2}\)，如果\(s_{mid} = 1\)，由于\(s_n = 1\)，最坏情况很有可能这后半部份都是 \(1\)，显然我们不该去问。但因为 \(s_1 = 0, s_{mid} = 1\)，所以前半部份必定有一处\(s_p = 0, s_{p + 1} = 1\)。 反之\(s_{mid} = 0\)的情况同理。
这样，通过一次询问，我们可以把答案保证存在的区间砍半了。那最多砍 \(\log n\)次就找到结果了。由于 \(n \leq 2 \times 10^5\)，所以不会超过\(20\)次。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
int l = 1, r = n;
while(l + 1 < r){
int mid = (l + r) >> 1;
cout << "? " << mid << endl;
int ok;
cin >> ok;
if (ok)
r = mid;
else
l = mid;
}
cout << "! " << l << endl;
return 0;
}
E - Nearest Black Vertex (abc299 e)
题目大意
给定一张图，要求给点涂黑白色，要求至少有一个黑点，且满足\(k\)个要求。
每个 要求 \((p_i, d_i)\)表示点 \(p_i\)距离黑点的最近距离恰好为 \(d_i\)。
点数、边数 \(\leq 2000\)
解题思路
注意边数只有\(2000\)。
我们可以对每个要求的 \(p_i\)进行 \(BFS\)，把距离其小于 \(d\)的点都标记为白色。
然后再对每个要求的 \(p_i\)进行 \(BFS\)，把距离其为\(d\)的且未被标记为白色的点标记为黑色。
如果有个要求没有找到可以被涂黑色的点，就无解了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> edge(n);
for(int i = 0; i < m; ++ i){
int u, v;
cin >> u >> v;
-- u, -- v;
edge[u].push_back(v);
edge[v].push_back(u);
}
int k;
cin >> k;
vector<int> forbid(n);
vector<int> col(n);
vector<array<int, 2>> rule(k);
auto BFS = [&](int s, int d){
if (d == 0)
return;
vector<int> dis(n, -1);
queue<int> team;
dis[s] = 0;
team.push(s);
while(!team.empty()){
int u = team.front();
forbid[u] = 1;
team.pop();
for(auto &v : edge[u]){
if (dis[v] != -1)
continue;
dis[v] = dis[u] + 1;
if (dis[v] < d)
team.push(v);
}
}
};
for(auto &[p, d] : rule){
cin >> p >> d;
-- p;
BFS(p, d);
}
bool ok = true;
auto paint = [&](int s, int d){
vector<int> dis(n, -1);
queue<int> team;
dis[s] = 0;
team.push(s);
while(!team.empty()){
int u = team.front();
team.pop();
if (!forbid[u] && dis[u] == d){
col[u] = 1;
return true;
}
for(auto &v : edge[u]){
if (dis[v] != -1)
continue;
dis[v] = dis[u] + 1;
if (dis[v] <= d)
team.push(v);
}
}
return false;
};
for(auto &[p, d] : rule){
ok &= paint(p, d);
}
if (!ok)
cout << "No" << '\n';
else{
cout << "Yes" << '\n';
if (k == 0)
col[0] = 1;
for(auto &i : col)
cout << i;
cout << '\n';
}
return 0;
}
F - Square Subsequence (abc299 f)
题目大意
给定一个字符串\(s\)，问有多少个串 \(t\)，满足 \(tt\)是 \(s\)的一个子序列。
解题思路
首先不考虑拼接，即问字符串\(s\)中本质不同的子序列数量。这个难点在于如何不算重。一个方法就是规定一种子序列映射到字符串的方式。
容易想到的就是最近匹配，就是判断字符串\(t\)是不是字符串 \(s\)的子序列时，对依次对每个 \(t_i\)进行最近的匹配，能匹配\(s_j\)就匹配上 。我们就按照这个方式去计算，每个本质不同的子序列就只算到一次。
即设 \(dp[i]\)表示以 \(i\)结尾的本质不同的子序列数量，设 \(pos\)表示最大的 \(j\)满足 \(j < i\)且 \(s_{pos} == s_i\)，那么 \(dp[i] = \sum_{j = pos}^{i} dp[j]\)
同样，我们可以按照此方式解决算重问题。从上述问题转到这个问题，一个自然的想法是设\(dp[i][j]\)表示串 \(tt\)中，前一个 \(t\)的末尾在 \(i\)，后一个 \(t\)的末尾在 \(j\)（显然有 \(s_i == s_j\)）的子串数量。
为方便叙述，设 \(tt\)为 \(t_1 t_2\) ，即\(T_{10}T_{11}..T_{1n}T_{20}T_{21}...T_{2n}\)，\(nxt(i, j)\)表示 \(s_i\)后第一个 字符是 \(j\)的位置。
考虑初始状态，如果我们枚举第一个字母是\(k\)的话，那么 \(i = nxt(0, k)\)，而 \(j\)的话感觉难以确定，它可以在任意的 \(a_j = k\)处，区别可能是串 \(t\)的长度不同。因此我们得枚举\(j\)的位置。
确定了初始状态 \(dp[i][j] = 1\)后，然后就枚举下一个字母 \(k\)，由于采取的是最近匹配的原则，那么下一个匹配位置就分别是 \(nxt(i, k)\)和 \(nxt(j, k)\)，即 \(dp[nxt(i, k)][nxt(j,k)] += dp[i][j]\)，转移式子即为此。
最后累计答案时，因为采取最近匹配的原则，我们只对满足 \(nxt(x, s_{i}) = j\)的 \(dp[x][y]\)（ \(y \geq j\)即可）进行累加。
总的来说，就是设\(dp[i][j][k]\)表示 \(t_2\)开头在 \(s_i\)， \(t_1\)末尾在\(s_j\)， \(t_2\) 末尾在\(s_k\)的方案数。
转移式子 \(dp[i][nxt(j, c)][nxt(k, c)] += dp[i][j][k]\)，
答案\(ans = \sum_{i = 1}^{n} \sum_{nxt(j, s_i) == i} \sum_{k = i}^{n} dp[i][j][k]\)
总的时间复杂度是 \(O(n^3)\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mo = 998244353;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
string s;
cin >> s;
int n = s.size();
vector<array<int, 26>> nxt(n);
array<int, 26> pos;
pos.fill(-1);
for(int i = n - 1; i >= 0; -- i){
nxt[i] = pos;
pos[s[i] - 'a'] = i;
}
int ans = 0;
for(int st = 1; st < n; ++ st){
vector<vector<int>> dp(n, vector<int>(n, 0));
int first = s[st] - 'a';
int l = pos[first], r = st;
dp[l][r] = 1;
for(int i = l; i < r; ++ i)
for(int j = r; j < n; ++ j){
for(int k = 0; k < 26; ++ k){
int nl = nxt[i][k], nr = nxt[j][k];
if (nl == -1 || nr == -1 || nl >= r)
continue;
dp[nl][nr] += dp[i][j];
if (dp[nl][nr] >= mo)
dp[nl][nr] -= mo;
}
}
for(int i = l; i < r; ++ i)
for(int j = r; j < n; ++ j){
if (nxt[i][first] == r){
ans += dp[i][j];
if (ans >= mo)
ans -= mo;
}
}
}
cout << ans << '\n';
return 0;
}
G - Minimum Permutation (abc299 g)
题目大意
给定一个长度为\(n\)，仅包含数字 \(1 \sim m\)的数组\(a\)，问其字典序最小的一个子序列，是一个排序。
解题思路
从左到右依次考虑数组\(a\)，对于当前的数字\(a_i\)，一个朴素的想法是，选不选它，如果不选它，剩下的序列还能不能组成一个排列，如果不能，则一定要选它，那问题就剩下如何判断能不能组成，以及如果不一定选择，该怎么办。
能不能组成一个排列，就是看剩下序列的数字包不包含还没选择的数，设还没选择的数为\(left\)。
然后对于不是一定要选的数，我们可以先存起来，这样就有一个由满足要求的\(a_i\)组成的候选集合。
继续往右遍历，会遇到第一个不满足要求的位置\(a_r\)，此时可以从候选集合里选数字最小的数，放到答案里，此时\(left\)就少了一个数。
因为\(left\)是判断某个数是不是一定要选的条件，当\(left\)少一时，说明这个条件变得更容易满足，因此\(a_r\)可能会满足，因此可以继续往右边遍历，往候选集合里添加新的数。而之前满足要求的还是满足。
由此就循环就可以得到最终答案了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> a(n);
vector<int> cnt(m + 1);
int ok = 0;
auto add = [&](int x, int val){
if (cnt[x] == 0)
ok ++;
cnt[x] += val;
};
auto sub = [&](int x, int val){
cnt[x] -= val;
if (cnt[x] == 0)
ok --;
};
for(auto &i : a){
cin >> i;
add(i, 1);
}
vector<int> ans;
vector<int> used(m + 1, 0);
priority_queue<array<int, 2>> candidate;
int target = m;
int l = -1;
for(int i = 0; i < n; ++ i){
if (used[a[i]])
continue;
if (ok != target){
while(-candidate.top()[1] < l || used[-candidate.top()[0]])
candidate.pop();
int val = -candidate.top()[0];
int pos = -candidate.top()[1];
ans.push_back(val);
used[val] = 1;
l = pos;
if (cnt[val])
sub(val, cnt[val]);
candidate.pop();
-- i;
-- target;
continue;
}
sub(a[i], 1);
candidate.push({-a[i], -i});
}
while(ans.size() < m){
int val = -candidate.top()[0];
int pos = -candidate.top()[1];
candidate.pop();
if (pos < l || used[val])
continue;
ans.push_back(val);
used[val] = 1;
l = pos;
}
for(int i = 0; i < m; ++ i){
cout << ans[i] << ' ';
}
cout << '\n';
return 0;
}
赛后发现是道原题，去年的时候做过。
当时的思路更朴素，首先把第一个数\(a_0\)放入答案末尾，然后依次考虑之后的每个数\(a_i\)和答案的末尾的数 \(ans_{back}\)比较，如果 \(a_i < ans_{back}\)，且之后还有一个 \(a_j(j > i) == ans_{back}\)的话，那么当前的 \(ans_{back}\)可以扔掉（仍能保证后续能构造出一个排列），一直扔掉直到\(a_i > ans_{back}\)或者不存在 \(a_j(j > i) == ans_{back}\)，此时把 \(a_i\)放到答案末尾。
然后依次考虑就可以了。时间复杂度是\(O(n)\)的。
简短的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 8;
int a[N], cnt[N];
bool used[N];
int ans[N], cur;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> m >> n;
for(int i = 1; i <= m; ++ i){
cin >> a[i];
cnt[a[i]] ++;
}
cur = 0;
for(int i = 1; i <= m; ++ i){
cnt[a[i]] --;
if (used[a[i]])
continue;
while (cur > 0 && cnt[ans[cur]] && ans[cur] >= a[i]){
used[ans[cur]] = false;
-- cur;
}
++ cur;
ans[cur] = a[i];
used[a[i]] = true;
}
for(int i = 1; i <= n; ++ i)
cout << ans[i] << " \n"[i == n];
return 0;
}
Ex - Dice Sum Infinity (abc299 h)
题目大意
<++>
解题思路
<++>
神奇的代码