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)

题目大意

<++>

解题思路

<++>

神奇的代码

---

原文链接：https://www.cnblogs.com/Lanly/p/17344724.html