AtCoder Beginner Contest 353 A-G 题解

A - Buildings

Solution

纯模拟

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n + 1);
    int pos = -1;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 2; i <= n; i++) 
        if (a[i] > a[1]) {
            pos = i;
            break;
        }
    cout << pos << endl;
    return 0;
}

B - AtCoder Amusement Park

Solution

使用两个指针模拟

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int ans = 0;
    int n, k; cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n;) {
        int sum = 0;
        int j = i;
        while (j <= n && sum + a[j] <= k) sum += a[j++];
        ans += 1; 
        i = j;
    }
    cout << ans << endl;
    return 0;
}

C - Sigma Problem

Question

C - Sigma Problem

对于正整数 $x$ 和 $y$ ，定义 $f (x, y)$ 为 $(x + y) % 10^{9}$

给定一个长度为 $N$ 的序列 $A = (A_{1}, A_{2}, \dots, A_{N})$ 计算：

\sum_{i = 1}^{N - 1} \sum_{j = i + 1}^{N} f (A_{i}, A_{j})

Solution

$A_{i} + A_{j}$ 的最大值是 $2\times 10 {#9}$ 所以如果 $(A_{i} + A_{j}) / 10^{9}$ 最大为 $1$

所以对于 $(A_{i} + A_{j}) % 10^{9} = (A_{i} + A_{j}) - 10^{9}$

我们对于每个 $A_{i}$ 只需要求出有多少 $A_{i} + A_{j} > 10^{9}$ 对于 $A_{i}$ 排序后， $i$ 从小到大枚举，分界点从大变小，可以用双指针来实现

D - Another Sigma Problem

Question

定义 $f (x, y)$ 表示把两个十进制接起来

例如 $f (2, 14) = 214$

给定数组 $A$ ，求：

\sum_{i = 1}^{N - 1} \sum_{j = i + 1}^{N} f (A_{i}, A_{j})

Solution

化简 $f (A_{i}, A_{j}) = A_{i} \times 10^{| A_{j} |} + A_{j}$

\begin{aligned} \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^{N} f (A_{i}, A_{j}) & = \sum_{j = 2}^{N} \sum_{i = 1}^{j - 1} f (A_{i}, A_{j}) \\ = \sum_{j = 2}^{N} \sum_{i = 1}^{j - 1} A_{i} \times 10^{| A_{j} |} + A_{j} \\ = \sum_{j = 2}^{N} (A_{j} + 10^{| A_{j} |} \times \sum_{i = 1}^{j - 1} A_{i}) \end{aligned}

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int ans = 0;
    int n, k; cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n;) {
        int sum = 0;
        int j = i;
        while (j <= n && sum + a[j] <= k) sum += a[j++];
        ans += 1; 
        i = j;
    }
    cout << ans << endl;
    return 0;
}

E - Yet Another Sigma Problem

Question

对于字符串 $x$ 和 $y$ ，定义 $f (x, y)$ 如下：

$f (x, y)$ 是 $x$ 和 $y$ 的最长公共前缀的长度。

给你一个由小写英文字母组成的 $N$ 字符串 $(S_{1}, \dots, S_{N})$ 求：

\sum_{i = 1}^{N - 1} \sum_{j = i + 1}^{N} f (S_{i}, S_{j})

Solution

字典树板子题

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int maxn = 3e5 + 10;

int cnt;

struct Node {
    int val;
    int son[26];
    Node() {
        val = 0;
        memset (son, 0, sizeof (son));
    }
}tr[maxn];

void insert (string s) {
    int p = 0;
    for (int i = 0; i < s.size(); i++) {
        int u = s[i] - 'a';
        if (!tr[p].son[u]) tr[p].son[u] = ++cnt;
        p = tr[p].son[u];
        tr[p].val += 1;
    }
}

int find_same (string s) {
    int p = 0;
    int res = 0;
    for (int i = 0; i < s.size(); i++) {
        int u = s[i] - 'a';
        if (!tr[p].son[u]) break;
        p = tr[p].son[u];
        res += tr[p].val;
    }
    return res;
}

signed main() {
    // freopen ("E.in", "r", stdin);
    int n; cin >> n;
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        ans += find_same (s);
        insert (s);
    }
    cout << ans << endl;
    return 0;
}

F - Tile Distance

Question

F - Tile Distance

坐标平面上有两种类型的瓷砖，大小为 $1 \times 1$ 和大小为 $K \times K$

交替铺设，穿过一个瓷砖的代价为 $1$

问高桥从点 $(S_{x} + 0.5, S_{y} + 0.5)$ 移动到点 $(T_{x} + 0.5, T_{y} + 0.5)$ 的最小代价

Solution

显然，能走大格子就走大格子

如果起点和终点在小格子中，先走到附近的大格子里面，然后查询大格子之间的最短路径，一共有 $16$ 条

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll K; cin >> K;
    ll Sx, Sy, Tx, Ty; cin >> Sx >> Sy >> Tx >> Ty; Sx += K, Sy += K, Tx += K, Ty += K;
    ll dist = abs(Tx - Sx) + abs(Ty - Sy);
    if (1 < K) {
        vector<tuple<ll, ll, ll> > st;
        if (((Sx / K) ^ (Sy / K)) & 1) {
            st.emplace_back(Sx / K, Sy / K, 0);
        }
        else {
            st.emplace_back(Sx / K - 1, Sy / K, 1 + Sx % K);
            st.emplace_back(Sx / K + 1, Sy / K, K - Sx % K);
            st.emplace_back(Sx / K, Sy / K - 1, 1 + Sy % K);
            st.emplace_back(Sx / K, Sy / K + 1, K - Sy % K);
        }

        vector<tuple<ll, ll, ll> > ed;
        if (((Tx / K) ^ (Ty / K)) & 1) {
            ed.emplace_back(Tx / K, Ty / K, 0);
        }
        else {
            ed.emplace_back(Tx / K - 1, Ty / K, 1 + Tx % K);
            ed.emplace_back(Tx / K + 1, Ty / K, K - Tx % K);
            ed.emplace_back(Tx / K, Ty / K - 1, 1 + Ty % K);
            ed.emplace_back(Tx / K, Ty / K + 1, K - Ty % K);
        }

        if (K == 2) {
            for (auto [sx, sy, d1] : st)
                for (auto [tx, ty, d2] : ed)
                    dist = min(dist, abs(sx - tx) + abs(sy - ty)  + abs (abs(sx - tx) - abs(sy - ty)) / 2 + d1 + d2);
        }
        else {
            for (auto [sx, sy, d1] : st)
                for (auto [tx, ty, d2] : ed)
                    dist = min(dist, abs(sx - tx) + abs(sy - ty) + abs(abs(sx - tx) - abs(sy - ty)) + d1 + d2);
        }
    }
    cout << dist << endl;
    return 0;
}

G - Merchant Takahashi

Question

AtCoder 王国有 $N$ 个城镇：城镇 $1$ 、 $2$ 、 $\dots$ 、 $N$ 。从 $i$ 镇到 $j$ 镇，必须支付 $C \times | i - j |$ 日元的过路费。

商人高桥正在考虑参加 $M$ 个或更多即将到来的市场。

第 $i$ 个市场 $(1 \leq i \leq M)$ 由一对整数 $(T_{i}, P_{i})$ 描述，其中市场在城镇 $T_{i}$ 举行，如果他参加，将赚取 $P_{i}$ 日元。

对于所有的 $1 \leq i \leq M$ ， $i$ 次市场在 $(i + 1)$ 次市场开始之前结束。他移动的时间可以忽略不计。

他从 $10^{10^{100}}$ 日元开始，最初在 $1$ 镇。通过优化选择参与哪些市场以及如何移动，确定他可以获得的最大利润。

从形式上看，如果他在 $M$ 个市场后获得最大资金额，那么 $10^{10^{100}} + X$ 就是他的最终资金额。求 $X$ 。

Solution

显然 DP

定义 $f [i]$ 表示第 $i$ 个活动结束后，且第 $i$ 个活动必须参加所能达到的最大钱数

那么 $f [i] = {max}_{j = 1}^{i} {f [j] - C | T [i] - T [j] | + P [i]}$

我们可以根据 $T [i]$ 和 $T [j]$ 的大小分类讨论

$T [i] > T [j]$ 时

f [i] = {max}_{j = 1}^{i} {f [j] + C T [j]} - C T [i] + P [i]

$T [i] \leq T [j]$ 时

f [i] = {max}_{j = 1}^{i} {f [j] - C T [j]} + C T [i] + P [i]

用两棵线段树维护就好了

Code

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

const ll inf = 1e18;
const ll INF = inf * inf;
ll read() {
    ll x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
void print(ll x) {
    if (x < 0) {putchar('-'); x = -x;}
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');

}
struct Segment_Tree {
    vector<ll> val;
    int n;
    Segment_Tree(int n) : n(n) {val.assign(4 * n, -INF);}
    void push_up(int x) {val[x] = max(val[x << 1], val[x << 1 | 1]);}
    ll query(int x, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return val[x];
        if (ql > qr) return -INF;
        ll res = -INF;
        int mid = (l + r) / 2;
        if (ql <= mid) res = max(res, query(x << 1, l, mid, ql, qr));
        if (qr > mid) res = max(res, query(x << 1 | 1, mid + 1, r, ql, qr));
        return res;
    }
    void update(int x, int l, int r, int pos, ll v) {
        if (l == r) {val[x] = v; return;}
        int mid = (l + r) / 2;
        if (pos <= mid) update(x << 1, l, mid, pos, v);
        else update(x << 1 | 1, mid + 1, r, pos, v);
        push_up(x);
    }
};

int main() {
    ll ret = 0;
    int n; cin >> n;
    ll C = read(); 
    int m; cin >> m;
    vector<ll> T(m + 1, 0ll), P(m + 1, 0ll);
    for (int i = 1; i <= m; i++)
        T[i] = read(), P[i] = read();
    Segment_Tree up(n + 1), dn(n + 1);
    up.update(1, 1, n, 1, C);
    dn.update(1, 1, n, 1, -C);
    vector<ll> dp(n + 1, -INF); dp[1] = 0;
    for (int i = 1; i <= m; i++) {
        ll ans_l = up.query(1, 1, n, 1, T[i] - 1) - C * T[i] + P[i];
        ll ans_r = dn.query(1, 1, n, T[i] + 1, n) + C * T[i] + P[i];
        ll ans = max(ans_l, ans_r);
        ans = max(ans , dp[T[i]] + P[i]);
        dp[T[i]] = max(dp[T[i]], ans);
        ret = max(ret, ans);
        up.update(1, 1, n, T[i], ans + C * T[i]);
        dn.update(1, 1, n, T[i], ans - C * T[i]);
    }
    print(ret); puts("");
    return 0;
}