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)

题目大意

<++>

解题思路

<++>

神奇的代码



热门相关:帝少的专属:小甜心,太缠人   仗剑高歌   刺客之王   寂静王冠   豪门闪婚:帝少的神秘冷妻