ATCoder Beginnner Contest 341 A~G

A.Print 341（模拟）

题意：

给定一个正整数 $N$ ，输出由 $N$ 个0和 $(N + 1)$ 个1交替组成的字符串。

分析：

按题意模拟即可

代码：

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    cout << 1;
    for (int i = 0; i < n; i++) {
        cout << "01";
    }
    cout << endl;
    return 0;
}

B.Foreign Exchange（贪心）

题意：

有 $N$ 个国家，编号为 $1$ 到 $N$ 。对于每个 $i = 1, 2, \dots, N$ ，高桥拥有 $A_i$ 个第 $i$ 个国家的货币。高桥可以重复执行以下操作任意次数（可能为零）：

首先，在 $1$ 和 $N - 1$ （含两端）之间选择一个整数 $i$ 。然后，如果他拥有至少 $S_i$ 个第 $i$ 个国家的货币，则他会执行以下操作一次：用 $S_i$ 个第 $i$ 国家的货币交换 $T_i$ 个下一个国家 $(i + 1)$ 的货币。

计算高桥最终可能拥有的第 $N$ 个国家货币数量的最大值。

分析：

按照题意，按照题目所给规则一国一国模拟兑换即可。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const LL N = 2e5 + 10;
LL a[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n - 1; i++) {
        int s, t;
        cin >> s >> t;
        a[i + 1] += a[i] / s * t;
    }
    cout << a[n - 1] << endl;
    return 0;
}

C.Takahashi Gets Lost（模拟）

题意：

有一个 $H$ 行 $W$ 列的网格。网格的每个单元格都是陆地或海洋，由长度为 $W$ 的 $H$ 个字符串 $S_1,S2,…,S_H$ 表示。 $(i, j)$ 表示从上往下第 $i$ 行和从左往右第 $j$ 列的单元格，并且如果 $S_i$ 的第 $j$ 个字符是. ，则 $(i, j)$ 是陆地；如果该字符是#，则 $(i, j)$ 是海洋。

题目约束保证网格周边（即满足 $i = 1$ 、 $i = H$ 或 $j = 1$ 、 $j = W$ 中至少一项的单元格 $(i, j)$ ）上所有单元都是海洋。

$T akaha s hi$ 的飞船在网格中某个单元格坠毁了。之后，他按照长度为 $N$ 的字符串 $T$ 中表示的指令移动 $N$ 次，其中包括 $L$ 、 $R$ 、 $U$ 和 $D$ 。对于 $i = 1, 2, \dots, N$ ， $T$ 的第 $i$ 个字符描述如下：

$L$ 表示向左移动一个单元格。也就是说，在进行此次移动之前若他在 $(i, j)$ ，那么此次移动后他将到达 $(i, j - 1)$ 处；
$R$ 表示向右移动一个单元格。也就是说，在进行此次移动之前若他在 $(i, j)$ ，那么此次移动后他将到达 $(i, j + 1)$ 处；
$U$ 表示向上移动一个单元格。也就是说，在进行此次移动之前若他在 $(i, j)$ ，那么此次移动后他将到达 $(i - 1, j)$ 处；
$D$ 表示向下移动一个单元格。也就是说，在进行此次移动之前若他在 $(i, j)$ ，那么此次移动后他将到达 $(i + 1, j)$ 处。

已知沿着路径的所有单元格（包括坠毁并且当前所在位置）都不会被淹没，输出可能成为其当前位置的单元格数目。

分析：

题目要求按指令移动时不会经过海洋，即不会经过#。枚举位置，模拟操作序列，判断是否会经过#即可。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const LL mod = 998244353;
const LL N = 505;

char c[N][N];

int main() {
    int h, w, n;
    cin >> h >> w >> n;
    string t;
    cin >> t;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> c[i][j];
        }
    }
    int ans = 0;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            if (c[i][j] == '#')
                continue;
            int a = i, b = j;
            bool check = true;
            for (int k = 0; k < n; k++) {
                if (t[k] == 'L') {
                    if (b == 1) {
                        check = false;
                        break;
                    }
                    b -= 1;
                    if (c[a][b] == '#') {
                        check = false;
                        break;
                    }
                } else if (t[k] == 'U') {
                    if (a == 1) {
                        check = false;
                        break;
                    }
                    a -= 1;
                    if (c[a][b] == '#') {
                        check = false;
                        break;
                    }
                } else if (t[k] == 'R') {
                    if (b == w) {
                        check = false;
                        break;
                    }
                    b += 1;
                    if (c[a][b] == '#') {
                        check = false;
                        break;
                    }
                } else {
                    if (a == h) {
                        check = false;
                        break;
                    }
                    a += 1;
                    if (c[a][b] == '#') {
                        check = false;
                        break;
                    }
                }
            }
            if (check) {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

D.Only one of two（二分）

题意：

给定三个正整数 $N$ 、 $M$ 和 $K$ 。其中， $N$ 和 $M$ 不同。

输出第 $K$ 小的正整数，该正整数恰好可被 $N$ 或 $M$ 中的一个数整除。

分析：

先找到 $n, m$ 的最小公倍数 $l$ ，那么对于一个数 $x$ ，能被 $n$ 整除且小于等于 $x$ 的数的个数就是 $[x / n]$ ，所以可以推出（因为可能同时能被 $n, m$ 整除，要删掉能被 $l$ 整除的数字个数）

$[x / n] + [x / m] - 2 * [x / l] >= k$

使用二分来进行查找即可。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;

LL gcd(LL a, LL b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    LL n, m, x, k;
    cin >> n >> m >> k;
    x = (n * m) / gcd(n, m);
    LL l = 0, r = (LL) 2e+20;
    LL mid, cnt;
    while ((l + 1) < r) {
        mid = (l + r) / 2;
        cnt = (mid / n) + (mid / m) - 2 * (mid / x);
        if (cnt < k)
            l = mid;
        else
            r = mid;
    }
    cout << r << endl;
    return 0;
}

E.Alternating String（线段树）

题意：

定义好字符串是由0和1组成的字符串，其中两个连续字符总是不同的。

给你一个长度为 $N$ 的字符串 $S$ ，由0和1组成。

给出 $Q$ 个查询，必须按顺序处理。
查询有两种类型：

1 L R：翻转 $S$ 中第 $L$ 到第 $R$ 的每个字符。也就是说，对于每个满足 $L\leq i\leq R$ 的整数 $i$ ，如果 $S$ 中的第 $i$ 个字符是"1"，则将其改为0，反之亦然。
2 L R：假设 $S^{'}$ 是通过提取 $S$ 的第 $L$ 到第 $R$ 个字符（不改变顺序）得到的长度为 $(R - L + 1)$ 的字符串。如果 $S^{'}$ 是一个好字符串，则输出Yes，否则输出No。

分析：

题目要求的好字符串必须是01交替出现。设数组 $x_i=(s_i \oplus s_{i+1})$ ，如果 $\sum\limits_{i=l}^{r-1}x_i==r-l$ ，那说明 $S$ 的 $[l, r]$ 是01交替的。对区间 $[l, r]$ 进行翻转操作，不难发现所有的 $x_i$ 都不会发生变化。发生变化的只有两个边界，即 $x_{l-1}$ 和 $x_r$ ，显然这两个值会变成它们相反的数。我们注意到操作一对该数组的影响是两个单点修改，操作二是一个区间查询，用线段树维护数组即可。

代码：

#include<bits/stdc++.h>

using namespace std;

template<typename T>
class settree {
public:
    vector<T> cnt;
    int n;

    settree(int _n) : n(_n) { cnt.resize(n); }

    void modify(int x, T v) {
        while (x < n) {
            cnt[x] += v;
            x |= (x + 1);
        }
    }

    T get(int x) {
        T v{};
        while (x >= 0) {
            v += cnt[x];
            x = (x & (x + 1)) - 1;
        }
        return v;
    }

    T sum(int l, int r) {
        T tot = get(r);
        if (l != 0) {
            tot -= get(l - 1);
        }
        return tot;
    }
};

int main() {
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    settree<int> sum(n - 1);
    for (int i = 0; i < n - 1; i++) {
        sum.modify(i, s[i] != s[i + 1]);
    }
    while (q--) {
        int qu, l, r;
        cin >> qu >> l >> r;
        if (qu == 1) {
            --l, --r;
            if (l != 0) {
                sum.modify(l - 1, sum.sum(l - 1, l - 1) == 1 ? -1 : 1);
            }
            if (r != (n - 1)) {
                sum.modify(r, sum.sum(r, r) == 1 ? -1 : 1);
            }
        } else {
            --l, --r;
            if (sum.sum(l, r - 1) == (r - l))
                cout << "Yes" << endl;
            else
                cout << "No" << endl;
        }
    }
    return 0;
}

F.Breakdown（01背包）

题意：

给你一个由 $N$ 个顶点和 $M$ 条边组成的简单无向图。对于 $i=1,2,\ldots,M$ 来说，第 $i$ 条边连接顶点 $u_i$ 和 $v_i$ 。另外，对于 $i=1,2,\ldots,N$ 来说，顶点 $i$ 被赋值为正整数 $W_i$ ，并且有 $A_i$ 个碎片放在上面。

只要图上还有碎片，就重复下面的操作：

首先，从图形中选择一个点 $x$ 并移除上面的一个碎片。
选择与 $x$ 相邻的顶点集合 $S$ （可能为空），即 $\sum\limits_{y\in S}W_y\lt W_x$ ，并在 $S$ 中的每个顶点上放置一个碎片。

输出此操作的最大次数。

题目保证无论如何操作，在有限次迭代后，图形上将没有棋子。

分析：

注意到操作里存在方向性即碎片总是往点权小的点跑。可以先求权值小的点，考虑权值大的点时，考虑放置碎片的点的答案都已经求出，因此可以求出该点的答案。

按点权小到大的顺序求解，假设 $dp_i$ 表示点 $i$ 上有一个碎片带来的最大操作次数，考虑求解当前点 $dp_i$ 时，就是考虑其 $w_y \le w_i$ 的所有 $y$ 。选哪些 $y$ ，其 $\sum dp_y$ 最大。

可以发现这样考虑本题即为01背包问题，因此就按照点权小到大的顺序求解 $n$ 个01背包问题即可。

最后答案就是 $\sum (dp_i \times a_i)$ 。

代码：

 #include<bits/stdc++.h>

typedef long long LL;
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> edge(n);
    int u, v;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        u--, v--;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    vector<int> w(n);
    for (auto &x: w)
        cin >> x;
    vector<int> a(n);
    for (auto &x: a)
        cin >> x;
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int x, int y) { return w[x] < w[y]; });
    vector<int> cost(n);
    LL ans = 0;
    for (auto i: id) {
        vector<array<int, 2>> goods;
        for (auto j: edge[i]) {
            if (w[j] < w[i])
                goods.push_back({w[j], cost[j]});
        }
        if (goods.empty()) {
            cost[i] = 1;
        } else {
            vector<int> dp(w[i], 0);
            for (auto &[x, y]: goods) {
                for (int j = w[i] - 1; j >= x; j--) {
                    dp[j] = max(dp[j], dp[j - x] + y);
                }
            }
            cost[i] = 1 + *max_element(dp.begin(), dp.end());
        }
        ans += 1LL * a[i] * cost[i];
    }
    cout << ans << endl;
    return 0;
}

G.Highest Ratio（计算几何）

题意：

给你一个长度为 $N$ 的序列 $A=(A_1,A_2,\ldots,A_N)$ 。
求每个 $k=1,2,\ldots,N$ 的解：

当选择一个整数 $r$ 使得 $k\leq r\leq N$ 时，求序列 $A$ 中第 $k$ 到第 $r$ 项的最大平均值。

序列 $A$ 的第 $k$ 到第 $r$ 项的平均值定义为 $\frac{1}{r-k+1}\displaystyle\sum\limits_{i=k}^r A_i$ 。

分析：

考虑二维平面上编号为 $0,1,2,\ldots,N$ 的 $(N + 1)$ 个点。

点 $0$ 的坐标为 $x_0,y_0)=(0,0)$ ，点 $i$ 的坐标为 $(x_i,y_i)=(i,A_1+A_2+\cdots +A_i)$ 。
那么 $A_L,A_{L+1},\ldots,A_R$ 的平均值就表示为点 ${L-1}$ 和点 $R$ 的斜率。

对于固定的 $k$ $(1\leq k\leq N)$ ，考虑如何求出序列 $A$ 中第 $k$ 到第 $r$ 项的最大平均值。
取点 ${k-1},k,k+1,\ldots,N$ 中的凸包。如果点 ${k-1},k,k+1,\ldots,N$ 是共线的，那么是 $A_k=A_{k+1}=\cdots~A_N$ ，所以平均值是 $A_k$ 。凸包是一个面积为正的区域。点 ${k-1}$ 是唯一一个坐标最小为 $x$ 的点，位于凸包的边界上。从点 $(k - 1)$ 顺时针绕边界一周后，如果下一个点是 $p$ ，那么答案就是 $\frac{y_p-y_{k-1}}{x_p-x_{k-1}}$ 。这是因为，从点 $(k - 1)$ 逆时针时，如果下一个点是 $q$ ，那么对于构成凸包的点 $i$ $(k\leq i\leq N )$ ，答案是 $\frac{y_p-y_{k-1}}{x_p-x_{k-1}}$ 。根据凸包的定义，经过点 $i$ 和 $(k - 1)$ 的直线的斜率至少是点 $q$ 和点 $(k - 1)$ 的斜率，最多是点 $p$ 和 $(k - 1)$ 的斜率。我们所求的值相当于连接点 $i$ $(k\leq i\leq N)$ 和点 $(k - 1)$ 的直线的最大斜率。所以答案是 $\frac{y_p-y_{k-1}}{x_p-x_{k-1}}$ ，也就是连接点 $p$ 和 $(k - 1)$ 的直线 $(k - 1)$ 的斜率。

毕竟，对于每个点 $k$ ，只需考虑点 ${k-1},k+1,\ldots,N$ 的凸包，并找出从点 $(k - 1)$ 顺时针方向遍历凸包边界时遇到的下一个点即可；换句话说，就是构成上边界的点序列中点 $(k - 1)$ 的下一个点。

如果直接为每个 $k$ 寻找凸包，会超时。但是，在按此顺序添加点 $N,N-1,\ldots,0$ 的同时求凸包上边界时，可以求出经过点 ${k-1}$ 的直线的斜率，以及构成上边界的点序列中点 ${k-1}$ 旁边的点。这样，就可以找到所有所需的值，其时间复杂度与只找到一次由点 $0,1,\ldots,N$ 组成的点集的凸包的时间复杂度相同。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const LL mod = 998244353;
const LL N = 2e5 + 5;

LL pre[N], arr[N], q[N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    reverse(arr + 1, arr + n + 1);
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + arr[i];
    }
    vector<double> ans;
    int l = 0, r = -1;
    q[++r] = 0;
    for (int i = 1; i <= n; i++) {
        while (l < r && (pre[i] - pre[q[r]]) * (q[r] - q[r - 1]) <= (pre[q[r]] - pre[q[r - 1]]) * (i - q[r]))
            r--;
        ans.push_back(1.0 * (pre[i] - pre[q[r]]) / (i - q[r]));
        q[++r] = i;
    }
    for (auto it = ans.rbegin(); it != ans.rend(); ++it) {
        cout << fixed << setprecision(10) << *it << endl;
    }
    return 0;
}