Atcoder ABC415游记（A~E）

A.Unsupported Type

题目描述

给你一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\dots,A_N)$ 和一个整数 $X$ 。
请判断 $X$ 是否包含在 $A$ 中。

思路

水

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    set<int> s;
    while (n--) {
        int x;
        cin >> x;
        s.insert(x);
    }
    int x;
    cin >> x;
    cout << (s.count(x) ? "Yes" : "No");
    return 0;
}

B.Pick Two

题目描述

有一个线性仓库，储存的包裹数量均等。
仓库的布局用字符串 $S$ 表示。
仓库有 $|S|$ 个分区，编号为 $1,2,\dots,|S|$ ，字符串 $S$ 对其描述如下：

当 $S$ 的 $i$ 个字符为 "#"时，一个包裹被放置在 $i$ 区段。
当 $S$ 的 $i$ -th字符为". "时， $i$ 节中不会放置任何软件包。

仓库里有一个机器人，它会重复以下操作，直到仓库里没有包裹为止：

从装有包裹的区域中区域编号最小的区域收集两个包裹。收集到的包裹被运出仓库。

每次迭代时，确定被运出的两个包裹最初位于仓库的哪个区段。

（这个题目描述来自deepl 一句人话都没有）

思路

水

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin >> s;
    int l = -1, flag = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '#') {
            if (flag) {
                cout << l << ',' << i + 1 << '\n';
                flag = 0;
            } else {
                l = i + 1;
                flag = 1;
            }
        }
    }
}

C.Mixture

题目描述

有 $N$ 种化学物质 $1,2,\dots,N$ 。你的目标是创造一种所有化学品都混合的状态。
给你一个长度为 $2^N-1$ 的字符串 $S$ ，由 0 和 1 组成，表示以下信息：

首先，定义一种或多种化学品混合的状态 $i$ $i$ ( $1 \le i \le 2^N-1$ $1 \leq i \leq 2^{N} - 1$ )如下：
- 当 $i$ 的二进制表示中从下往上的 $k$ （ $1 \le k \le N$ ）位数为 $1$ 时，且只有在此时，化学品 $k$ 才会被包含在内。
- 例如，二进制中的 $13$ 是 $1101_{(2)}$ ，所以状态 $13$ 代表化学物质 $1,3,4$ 混合的状态。
当 $S$ 的 $i$ -th 字符为 "0 "时，状态 $i$ 是安全的。
当 $S$ 的 $i$ --th 字符为 "1 "时，状态 $i$ 为危险。

您使用以下操作混合化学品：

首先，准备一个空瓶。
接下来，重复以下步骤：
- 选择一种尚未倒入瓶中的化学品，将其倒入瓶中。
- 此时，瓶中混合的化学品不得处于危险状态。

判断此操作是否能产生所有化学品都混合的状态。

给你 $T$ 个测试用例，请逐一求解。

思路

赛时先交了一发TLE的DFS+状压

然后瞪了一会眼糊了个BFS上去过了

代码

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int n;
    string s;
    cin >> n >> s;
    int m = 1 << n;
    vector<bool> flag(m, 0);
    for (int i = 0; i < m - 1; i++) {
        if (s[i] == '0') {
            flag[i + 1] = 1;
        }
    }
    queue<int> q;
    vector<bool> vis(m, 0);
    q.push(0);
    vis[0] = 1;
    while (!q.empty()) {
        int tp = q.front();
        q.pop();
        for (int i = 0; i < n; i++) {
            int nex = tp | (1 << i);
            if (nex >= m) {
                continue;
            }
            if (flag[nex] && !vis[nex]) {
                vis[nex] = 1;
                q.push(nex);
            }
        }
    }
    cout << (vis[m - 1] ? "Yes" : "No") << '\n';
}
int main()
{
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

D.Get Many Stickers

题目描述

有一家奇怪的可乐商店。这家商店并不直接出售可乐，而是提供空可乐瓶和新可乐瓶的交换服务。

起初，高桥有 $N$ 瓶可乐，他可以重复任意次数（或 $0$ 次）采取以下任何行动。

喝掉你拥有的 $1$ 瓶可乐。你拥有的瓶装可乐数量减少 $1$ ，空瓶数量增加 $1$ 。（如果在行动前你没有 $1$ 瓶可乐，则无法进行此行动）。
选择一个大于 $1$ 且小于 $M$ 的整数 $i$ 。将 $A_i$ 个空瓶交给可乐商店，换取 $B_i$ 瓶可乐和 $1$ 张纪念贴纸。（不能选择 $i$ 使行动前的空瓶数少于 $A_i$ 。如果没有 $i$ 可选，则无法进行此行动）。

高桥喜欢密封件。如果操作成功，你最多可以得到多少个印章？

假设高桥一开始没有 $1$ 个空瓶和 $1$ 张贴纸。

思路

首先问问自己：空可乐瓶和没喝的可乐瓶区别何在？

我们的目标是最大化贴纸数，所以我们要让 $N$ 每次减少速度尽量慢。

数据范围里给了 $B_i < A_i$ ，所以每一次兑换 $N$ 都必然减小，说了这么多，显然可以贪心（那为什么我想了半天对 $M$ DP）

$N$ 每次操作会减小 $A_i - B_i$ ，我们把数组按照这俩差值从小到大排序即可；要是相同就按照 $A_i$ 排序即可。

然后代码实现还涉及了 $N$ 怎么减少的细节，可以看代码

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node {
    int a, b, c;
};
bool cmp(const node &x, const node &y) {
    return x.c < y.c;
}
signed main()
{
    int n, m;
    cin >> n >> m;
    vector<node> a(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i].a >> a[i].b;
        a[i].c = a[i].a - a[i].b;
    }
    sort(a.begin(), a.end(), cmp);
    int ans = 0;
    int x = n;
    for (int i = 0; i < a.size(); i++) {
        if (x <= 0) {
            break;
        }
        if (x >= a[i].a) {
            int k = (x - a[i].a) / a[i].c + 1;
            ans += k;
            x -= k * a[i].c;
        } 
    }
    cout << ans;
    return 0;
}

E.Hungry Takahashi

题目描述

有一个行数为 $H$ 列数为 $W$ 的网格。从上往下数 $i$ 行，从左往上数 $j$ 列的方格记为 $(i,j)$ 。每个方格上都有一些硬币，方格 $(i,j)$ 上的硬币是 $A_{i,j}$ 。

高桥最初位于 $(1,1)$ 方格，有 $x$ 枚硬币。在接下来的 $H+W-1$ 天里，会发生几件事。在第 $k\ (1\leq k\leq H+W-1)$ 天，以下事情依次发生：

高桥收集了他所在方格中的所有硬币。
饥饿的高桥花掉 $P_k$ 个硬币去买食物。但是，如果他的硬币少于 $P_k$ ，他就买不到大米，会饿晕过去。
如果 $k < H + W - 1 $ ，高桥选择他所在方格的右边 $1$ 或下面 $1$ 的一个方格并移动到那里。但是，他不能离开网格，

如果有办法让高桥在接下来的 $H+W-1$ 天里不挨饿，求一最小的非负整数，即开始时高桥拥有的硬币数 $x$ 。

思路

（原来DP就行，炸了）

首先看到这题题面和数据范围一眼发现可以二分答案，我是寄了每一天要硬币数的前缀和。

判断的部分然后就全是细节，具体看代码了。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>> a;
bool check(int x, int n, int m, vector<int> tppre) {
    if (a[0][0] < tppre[1] - x) {
        return 0;
    }
    vector<int> pre(m, -1e18);
    pre[0] = a[0][0];
    for (int j = 1; j < m; j++) {
        if (pre[j - 1] != -1e18) {
            pre[j] = pre[j - 1] + a[0][j];
        }
        int k = j + 1; 
        if (pre[j] < tppre[k] - x) {
            pre[j] = -1e18;
        }
    }
    for (int i = 1; i < n; i++) {
        vector<int> now(m, -1e18);
        if (pre[0] != -1e18) {
            now[0] = pre[0] + a[i][0];
        }
        int pos = i + 1; 
        if (now[0] != -1e18 && now[0] < tppre[pos] - x) {
            now[0] = -1e18;
        }
        for (int j = 1; j < m; j++) {
            int tp = -1e18;
            if (pre[j] != -1e18) {
                tp = pre[j] + a[i][j];
            }
            if (now[j - 1] != -1e18) {
                int ttp = now[j - 1] + a[i][j];
                if (tp == -1e18 || ttp > tp) {
                    tp = ttp;
                }
            }
            int k = i + j + 1; 
            if (tp != -1e18 && tp >= tppre[k] - x) {
                now[j] = tp;
            } else {
                now[j] = -1e18;
            }
        }
        pre = now;
    }
    return (pre[m - 1] != -1e18);
}
signed main() {
    int n, m;
    cin >> n >> m;
    a.resize(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    int d = n + m - 1;
    vector<int> b(d);
    for (int i = 0; i < d; i++) {
        cin >> b[i];
    }
    vector<int> pre(d + 1, 0);
    for (int i = 1; i <= d; i++) {
        pre[i] = pre[i - 1] + b[i - 1];
    }
    int l = -1e15; 
    int r = 1e15;  
    int ans = r;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid, n, m, pre)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << max(0LL, ans);
    return 0;
}