题目

题目评级

A = B < C < E < F = D

F虽说是折半搜索板子可以但是卡常卡了 $70$ min $5$ 发才过的我因为我们忘记把map换成unorderedmap

A.ABC -> AC

题目描述

给你一个由大写英文字母组成的字符串 $S$ 。这里， $S$ 的长度是奇数。

打印删除 $S$ 中间字符后得到的字符串。 $S$ 的中间字符是 $S$ 的 $\frac{L+1}{2}$ -th 字符，其中 $L$ 是 $S$ 的长度。

思路

语法题所以就做完了

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
	string s;
	cin >> s;
	s.erase((s.length()) / 2, 1);
	cout << s;
	return 0;
}

B.Sum of Digits Sequence

题目描述

对于正整数 $N$ ，把 $f(x)$ 定义为 $x$ 的十进制表示中的数位之和。例如， $f(123) = 1 + 2 + 3 = 6$ 。

用下面的公式定义一个无穷序列 $A = (A_0, A_1, A_2, \ldots)$ ：

$A_0 = 1$
对于 $i \geq 1$ , $A_i = \displaystyle\sum_{j = 0}^{i - 1} f(A_j)$

给你一个正整数 $N$ 。求 $A_N$ 的值。

思路

语法题所以就做完了

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int calc(int n)
{
    int res = 0;
    while (n) {
        res += n % 10;
        n /= 10;
    }
    return res;
}
signed main()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), f(n + 1);
    a[0] = 1;
    f[0] = calc(a[0]);
    for (int i = 1; i <= n; i++) {
        a[i] = 0;
        for (int j = 0; j < i; j++) {
            a[i] += f[j];
        }
        if (i < n + 1) {
            f[i] = calc(a[i]);
        }
    }
    
    cout << a[n];
    return 0;
}

C.Bipartize

题目描述

问题陈述

有一个简单的无向图，该图有 $N$ 个顶点和 $M$ 条边。该图由顶点 $1,$ 顶点 $2,\ldots,$ 顶点 $N$ 和连接顶点 $u _ i$ 和 $v _ i$ 的 $i$ -th 边 $(1\le i\le M)$ 组成。

您将执行以下操作零次或多次：

选择一条尚未删除的边并删除它。

以最少的操作让原图变成二分图

思路

状压其实很显然因为 $n \leq 10$ 。

那我们直接大力状压枚举状态，然后每次发现一条边两边的点在同一集合里，你就更新答案，就做完了。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].first >> edges[i].second;
		edges[i].first--;
		edges[i].second--;
    }
    int ans = m; 
    for (int i = 0; i < (1 << n); i++) {
        int cnt = 0;
		for (int j = 0; j < m; j++) {
            if (((i >> edges[j].first) & 1) == ((i >> edges[j].second) & 1)) {
                cnt++;
            }
        }
        ans = min(ans, cnt);
    }
    cout << ans;
    return 0;
}

D.The Simple Game

题目描述

有一个有向图，图中有 $N$ 个顶点和 $M$ 条边。顶点的编号从 $1$ 到 $N$ ， $i$ 条边是从顶点 $U_i$ 到顶点 $V_i$ 的有向边。在这里，每个顶点的出度至少为 $1$ 。

此外，每个顶点上都有一个字符，顶点 $i$ 上的字符是 $S_i$ 。这里， $S_i$ 指的是 $S$ 的 $i$ 个字符。

爱丽丝和鲍勃用一个棋子在这个图上玩下面的游戏：

一开始，棋子被放在顶点 $1$ ，然后他们交替执行以下操作 $K$ 次，Alice 先执行，Bob 后执行。
- 假设 $u$ 是当前放置棋子的顶点。选择一个顶点 $v$ ，使得顶点 $u$ 到顶点 $v$ 之间有一条边，然后将棋子移动到顶点 $v$ 。
让 $v$ 成为棋子最终放置的顶点。如果 $S_v = $ “A”，爱丽丝获胜；如果是 $S_v = $ “B”，鲍勃获胜。

求双方都以最优方式下棋时的胜者。

在每个输入中，你都会得到 $T$ 个测试用例。求解每个案例。

思路

不知道为什么但是数据范围告诉你也许能记忆化

我们直接倒着推，然后到倒着推的同时大力DFS然后它就过了，我们对每个状态，看一下与它相连的边，如果往那条边搜发现自己能赢，那这个人的策略就是往这条边移动

然后操作次数是 $2*k$ ，别搞错了（

代码

#include<bits/stdc++.h>
using namespace std;
int n, m, k;
string s;
vector<int> edges[200005];
vector<vector<vector<int>>> ans;
bool dfs(int x, int y, bool flag)
{
    if (y == 0) {
        return s[x - 1] == 'A';
    }
    if (ans[x][y][flag] != -1) {
        return ans[x][y][flag];
    }
    if (flag) {
        bool anss = 0;
        for (int nex : edges[x]) {
            if (dfs(nex, y - 1, 0)) {
                anss = 1;
                break;
            }
        }
        return ans[x][y][flag] = anss;
    } else {
        bool anss = 1;
        for (int nex : edges[x]) {
            if (!dfs(nex, y - 1, 1)) {
                anss = 0;
                break;
            }
        }
        return ans[x][y][flag] = anss;
    }
}
void solve()
{
    cin >> n >> m >> k;
    cin >> s;
    for (int i = 1; i <= n; i++) {
        edges[i].clear();
    }
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
    }
    ans.assign(n + 1, vector<vector<int>>(2 * k + 1, vector<int>(2, -1)));
	cout << (dfs(1, 2 * k, 1) ? "Alice" : "Bob") << '\n';
}
signed main()
{
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

E.Wind Cleaning

题目描述

有一个网格，网格中有 $H$ 行和 $W$ 列。让 $(i, j)$ 表示从上往下第 $i$ 行和从左往上第 $j$ 列的单元格。

高桥就在这个网格中的一个单元格上，而网格中的一些单元格上有垃圾。

单元格的状态由长度为 $W$ 的 $H$ 字符串 $S_1, S_2, \ldots, S_H$ 给出，其中 $S_{i, j}$ 表示 $S_i$ 的 $j$ -th 字符，代表以下状态：

如果 $S_{i, j} =$ T，则 $(i, j)$ 单元格就是高桥所在的单元格。
如果是 $S_{i, j} =$ #，则 $(i, j)$ 单元格是高桥所在的单元格。#`， $(i, j)$ 单元格就是有垃圾的单元格。
如果是 $S_{i, j} =$ .，则 $(i, j)$ 单元格是没有垃圾的空格。

高桥所在的单元格没有垃圾。

他可以重复执行以下操作：

从四个方向（上、下、左、右）中选择一个，同时将所有垃圾向该方向移动一格。在这里，如果垃圾移动到格子外，垃圾就会消失；如果垃圾移动到他所在的格子，他就会变脏。

请判断他是否有可能在不弄脏的情况下让所有垃圾消失，如果可能，请找出尽可能少的操作次数。

思路

结论：暴力全对直接BFS就做完了

对啊你直接那个set记一下哪些地方有垃圾，然后直接暴力转移 1发就过了所以不知道为什么你们不做（

我们知道每个垃圾每次挪就 $1$ 格，不难发现横向纵向的移动根本不会超过二倍边长，然后能得到的状态其实很少，然后这题BFS最多 $4 * H * W$ 轮然后时间复杂度就完全正确了（

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    int tx, ty;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 'T') {
                tx = i;
                ty = j;
            }
        }
    }
    set<pair<int, int>> init;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == '#') {
                init.insert({i, j});
            }
        }
    }
    queue<set<pair<int, int>>> q;
    set<set<pair<int, int>>> st;
    q.push(init);
    st.insert(init);
    int ans = 0;
    vector<pair<int, int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            set<pair<int, int>> tp = q.front();
            q.pop();
            if (tp.empty()) {
                cout << ans;
                return 0;
            }
            for (auto &d : dir) {
                set<pair<int, int>> tpst;
                bool flag = 0;
                for (auto &j : tp) {
                    int dx = j.first + d.first;
                    int dy = j.second + d.second;
                    if (dx >= 0 && dx < n && dy >= 0 && dy < m) {
                        if (dx == tx && dy == ty) {
                            flag = 1;
                            break;
                        }
                        tpst.insert({dx, dy});
                    }
                }
                if (!flag && st.find(tpst) == st.end()) {
                    st.insert(tpst);
                    q.push(tpst);
                }
            }
        }
        ans++;
    }
    cout << -1;
    return 0;
}

F.Not Adjacent

题目描述

给你一个长度为 $N$ 的整数序列 $A=(A _ 1,A _ 2,\ldots,A _ N)$ 。

有 $2 ^ N$ 个（不一定连续）的子序列 $A$ 。求有多少个子序列 $(A _ {i _ 1},A _ {i _ 2},\ldots,A _ {i _ k})\ (1\le i _ 1\lt i _ 2\lt\cdots\lt i _ k\le N)$ 同时满足以下两个条件：

所选元素在 $A$ 中不相邻。也就是说， $1+i _ j\ne i _ {j+1}$ 对所有 $1\le j\lt k$ 都成立。
和是 $M$ 的倍数。即 $\displaystyle\sum _ {j=1} ^ kA _ {i _ j}\equiv0\pmod M$ 。

即使两个子序列作为整数序列是相等的，但如果它们所处的位置不同，也要分别计算。

思路

直接大力折半搜索 $O(2^{\frac{n}{2}})$ 然后像我一样卡常卡1个多小时就过了：

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int m;
void dfs(int x, int cnt, int ls, int f, const vector<int> &v, int st, bool flag, vector<pair<int, int>> &res)
{
    if (x == v.size()) {
        if (flag && f != 0) {
            res.push_back({f, cnt});
        } else if (!flag && ls != 0) {
            res.push_back({ls, cnt});
        }
        return;
    }
    dfs(x + 1, cnt, ls, f, v, st, flag, res);
    int pos = x + st;
    if (ls == 0 || pos >= ls + 2) {
        int tpsum = (cnt + v[x]) % m;
        int tpls = pos;
        int tpf = flag && (f == 0) ? pos : f;
        dfs(x + 1, tpsum, tpls, tpf, v, st, flag, res);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int mid = n / 2;
    vector<int> v1(a.begin(), a.begin() + mid);
    vector<int> v2(a.begin() + mid, a.end());
    vector<pair<int, int>> s1;
    s1.reserve(1 << 22);
    vector<pair<int, int>> s2;
    s2.reserve(1 << 22);
    if (!v1.empty()) {
        dfs(0, 0, 0, 0, v1, 1, false, s1);
    }
    if (!v2.empty()) {
        dfs(0, 0, 0, 0, v2, mid + 1, true, s2);
    }
    sort(s1.begin(), s1.end());
    vector<pair<pair<int, int>, int>> mp1;
    for (int i = 0; i < s1.size(); i++) {
        if (i == 0 || s1[i] != s1[i - 1]) {
            mp1.push_back({s1[i], 1});
        } else {
            mp1.back().second++;
        }
    }
    sort(s2.begin(), s2.end());
    vector<pair<pair<int, int>, int>> mp2;
    for (int i = 0; i < s2.size(); i++) {
        if (i == 0 || s2[i] != s2[i - 1]) {
            mp2.push_back({s2[i], 1});
        } else {
            mp2.back().second++;
        }
    }
    int ans = 0;
    for (auto &[k, cnt] : mp1) {
        if (k.second == 0) {
            ans += cnt;
        }
    }
    for (auto &[k, cnt] : mp2) {
        if (k.second == 0) {
            ans += cnt;
        }
    }
    map<int, vector<pair<int, int>>> mp3;
    for (auto &[k, cnt] : mp2) {
        mp3[k.second].push_back({k.first, cnt});
    }
    map<int, vector<pair<int, int>>> mp4;
    for (auto &[x, v] : mp3) {
        sort(v.begin(), v.end());
        vector<pair<int, int>> tp;
        int cnt = 0;
        for (int i = (int)v.size() - 1; i >= 0; i--) {
            cnt += v[i].second;
            tp.push_back({v[i].first, cnt});
        }
        reverse(tp.begin(), tp.end());
        mp4[x] = tp;
    }
    for (auto &[k, cnt] : mp1) {
        int ls = k.first;
        int s1 = k.second;
        int tp = (m - s1) % m;
        if (mp4.find(tp) == mp4.end()) continue;
        auto &v = mp4[tp];
        auto it = lower_bound(v.begin(), v.end(), make_pair(ls + 2, 0LL));
        if (it != v.end()) {
            ans += cnt * it->second;
        }
    }
    cout << ans + 1;
    return 0;
}

复盘

打atcoder的原因：