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)
题目大意
<++>
解题思路
<++>
神奇的代码
- Beginner AtCoder Contest 299beginner atcoder contest 299 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310