AtCoder Beginner Contest 215 （个人题解 A~F）

比赛链接：Here

AB水题，

C - One More aab aba baa

题意：

• 给出字符串 和整数 ，请输出字典序第 大的原字符串 的排序

思路：

• 先说简单写法：
  利用 C++ 内置函数 next_permutation 直接排序即可（代码一）

• 复杂写法：
  枚举情况，设字符串长度为 ，那么也就会有 种组合（先不管存在一样的），所以可以DFS来进行枚举爆搜（代码二）

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    string s; int k;
    cin >> s >> k;
    sort(s.begin(), s.end());
    while (k > 1) {
        next_permutation(s.begin(), s.end());
        k -= 1;
    }
    cout << s;
}

vector<string>vs;
string s, t;
int k, n;
void dfs(int x) {
    if (x == 0) {
        vs.push_back(t);
        return ;
    }
    for (int i = 0; i < n; ++i) {
        if (x & (1 << i)) { // 枚举第 i 位的情况
            t.push_back(s[i]);
            dfs(x ^ (1 << i));
            t.pop_back();
        }
    }
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> s >> k;
    n = int(s.size());
    dfs((1 << n) - 1);
    sort(vs.begin(), vs.end());
    unique(vs.begin(), vs.end());
    cout << vs[k - 1];
}

D - Coprime 2

赛时很可惜这个没做出来QAQ

题意：

• 给定 个数字，请问在 中有多少个数字与给出的 个数字互质

思路：

• 首先像埃拉托色尼筛法一样先把 的每个素数筛选出来，
• 然后把 的因子也统计出来（把其中的素数标记）
• 然后针对被标记的素因子从中删去即可

时间复杂度：#card=math&code=%5Cmathcal%7BO%7D%28N%5Csqrt%7B%5Cmax%7BA%7D%7D%29)

const int N = 1e5 + 10;
vector<int> pfact(int x) {
    vector<int>ans;
    for (int i = 2; i * i <= x; ++i) {
        while (x % i == 0) {
            x /= i;
            ans.push_back(i);
        }
    }
    if (x != 1) ans.push_back(x);
    return ans;
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m; cin >> n >> m;
    vector<bool>st(N, true);
    for (int i = 0, x; i < n; ++i) {
        cin >> x;
        vector<int> v = pfact(x);
        for (auto &nx : v) {
            if (st[nx]) for (int j = nx; j < N; j += nx) st[j] = false;
        }
    }
    vector<int> ans;
    for (int i = 1; i <= m; ++i) if (st[i]) ans.push_back(i);
    cout << ans.size() << "\n";
    for (int x : ans) cout << x << "\n";
}

E - Chain Contestant

题意：

我们有 种比赛类型： ，现在有 场比赛每场比赛以 表示，

RioTian 想要在 场比赛中选择并参加至少一项，并且满足以下条件

• 参加的比赛顺序中，同类型的比赛是连续的
  形式上，参加的 场比赛并且其中的第 个比赛是 类型时，对于整数每个三元组 #card=math&code=%28i%2Cj%2Ck%29) 使得

求出 参加比赛的方式数 ，取模于 。

考虑状压DP，

设 表示为对于前 场比赛，迄今为止参加的比赛集以及最后参加比赛的种类为 时的方案数。

为第 场比赛的种类

• 对于每组 和每一种比赛 ，在 （对应RioTian没有参加第 场比赛时），如果 $ j =x$ 也要加上 (对应 RioTian 参加第 场比赛时与上一场参加的比赛类型相同)
• 对于每个不包含 的集合 和每种竞赛 ，将 添加到 ，其中 是添加了 的 ，对应RioTian参加第 次比赛时和他上次参加的比赛不同
• ，其中 代表仅包含 的集合（对应参加的第一场比赛是第 场比赛的情况）

最后输出 （U为比赛集合，j 为比赛种类）

时间复杂度：#card=math&code=%5Cmathcal%7BO%7D%282%5EKNK%29)

const int mod = 998244353;
ll f[1024][1024][10];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; string s;
    cin >> n >> s;
    for (int i = 1; i <= n; ++i) {
        int x = s[i - 1] - 'A';
        for (int u = 0; u < 1024; ++u)
            for (int j = 0; j < 10; ++j) {
                f[i][u][j] = f[i - 1][u][j];
                if (j == x) {
                    f[i][u][j] += f[i - 1][u][j];
                    f[i][u][j] %= mod;
                }
            }
        for (int v = 0; v < 1024; v++) {
            if (v & (1 << x)) continue;
            for (int j = 0; j < 10; j++) {
                f[i][v | (1 << x)][x] += f[i - 1][v][j];
                f[i][v | (1 << x)][x] %= mod;
            }
        }
        f[i][(1 << x)][x]++;
        f[i][(1 << x)][x] %= mod;
    }
    ll ans = 0;
    for (int u = 0; u < 1024; ++u) for (int j = 0; j < 10; ++j)
            (ans += f[n][u][j]) %= mod;
    cout << ans;
}

F - Dist Max 2

F是一道思维题，

先贴一下代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    vector<pair<int, int>> v(n);
    for (int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end());
    int ok = 0, ng = 1000000001;
    while (ng - ok > 1) {
        int md = (ok + ng) / 2;
        queue<pair<int, int>> que;
        bool able = false;
        int mi = 1000000001, ma = 0;
        for (auto p : v) {
            while (!que.empty()) {
                if (que.front().first > p.first - md)break;
                mi = min(mi, que.front().second); ma = max(ma, que.front().second);
                que.pop();
            }
            if (mi <= p.second - md || ma >= p.second + md) able = true;
            que.push(p);
        }
        if (able) ok = md;
        else ng = md;
    }
    cout << ok << endl;
}