Codeforces Round #625 (1A

题意: 有一列共 n 个城市, 每个城市有美丽值 b[i], 要访问一个子序列的城市, 这个子序列相邻项的原项数之差等于美丽值之差, 求最大的美丽值总和.

思路: 对于一个合法的子序列, b[i] - i 结果是一个定值, 统计该值取最大.

view code

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define inc(i, l, r) for (int i = l; i <= r; i++)

const int maxn = 1e6 + 5;

int n, b[maxn];

int main() {

    cin >> n;

    map<int, ll> a;

    inc(i, 0, n - 1) {

        cin >> b[i];

        a[b[i] - i] += b[i];

    }

    ll res = 0;

    for (auto ite : a) res = max(res, ite.second);

    cout << res << "\n";

}

B - Navigation System

题意: 给出一个有向图和一个人的行动路径, 这个人每次移动前导航仪会给出从当前点到终点的一条最短路线, 如果这个人移动的路线与之不符, 导航仪会重新生成从下一个点出发到终点的最短路线. 问导航仪生成新路线的最小和最大次数.

思路: bfs求出所有点到终点的最短距离. 如果这个人移动时距离终点不是-1, 那他这次移动一定不在最短路线上; 否则, 检查是否有其他使距离-1的路线, 如果有, 那么就知道导航仪可能会重新生成路线.

view code

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define inc(i, l, r) for (int i = l; i <= r; i++)

const int maxn = 1e6 + 5;

const int inf = 0x3f3f3f3f;

vector<int> g[maxn];

vector<int> rg[maxn];

int a[maxn], d[maxn], vis[maxn];

int n, m, u, v, k;

int main() {

    memset(d, 63, sizeof(d));

    cin >> n >> m;

    inc(i, 1, m) {

        cin >> u >> v;

        rg[u].push_back(v);

        g[v].push_back(u);

    }

    cin >> k;

    inc(i, 1, k) cin >> a[i];

    queue<int> que;

    que.push(a[k]);

    d[a[k]] = 0;

    vis[a[k]] = 1;

    while (que.size()) {

        int p = que.front();

        que.pop();

        inc(i, 0, (int)g[p].size() - 1) {

            if (!vis[g[p][i]]) {

                d[g[p][i]] = d[p] + 1;

                que.push(g[p][i]);

                vis[g[p][i]] = 1;

            }

        }

    }

    int res1 = 0, res2 = 0;

    for (int i = 1; i < k; i++) {

        int now = a[i], nxt = a[i + 1];

        if (d[now] != d[nxt] + 1)

            res1++, res2++;

        else

            inc(j, 0, (int)rg[now].size() - 1) {

                if (d[rg[now][j]] + 1 == d[now] && rg[now][j] != nxt) {

                    res2++;

                    break;

                }

            }

    }

    cout << res1 << " " << res2;

}

C - World of Darkraft: Battle for Azathoth

题意: 给出 n 个武器, m 个防具, 分别有攻击力 ai 和防御力 bi, 购买该装备需要的金币ci, 还有 p 个怪兽, 分别具有防御力 xi, 攻击力 yi, 打败它获得的金币 ci. 现要求从中武器和防具中各选出恰好一个, 然后就可以打败所有满足 ai > xj 且 bi > yj 的怪兽并获得 cj. 求最大获利.

思路: 预处理攻击力和防御力达到 x 最少需要支付的金币数 atk[x], def[x]. 对所有怪兽排序(不妨以 xi 为第一关键字), 扫描一遍, 维护这样的线段树: 防御力为 x 时的最大获利, 每个节点初始值为 -def[x], 表示为了该防具需要支付的金币数. 每扫过一只怪兽, 防御力足以打败该怪兽的范围就增加 ci, 而武器攻击力为当前怪兽的 xi + 1, 这样可以确保前面扫描过的怪兽都满足 ai > xj.

view code

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define inc(i, l, r) for (int i = l; i <= r; i++)

#define dec(i, l, r) for (int i = l; i >= r; i--)

#define pii pair<int, int>

#define fi first

#define se second

#define pb push_back

const int maxn = 1e6 + 5;

const int inf = 0x3f3f3f3f;

int n, m, p;

int atk[maxn], def[maxn];

struct node {

    int a, b, c;

    bool operator<(const node &o) const {

        if (a == o.a) return b < o.b;

        return a < o.a;

    }

} mos[maxn];

int x, y, c, matk, mdef;

ll f[4 * maxn], mv[4 * maxn];

void up(int k) { mv[k] = max(mv[k << 1], mv[k << 1 | 1]); }

void down(int k) {

    f[k << 1] += f[k], f[k << 1 | 1] += f[k];

    mv[k << 1] += f[k], mv[k << 1 | 1] += f[k];

    f[k] = 0;

}

void build(int k, int l, int r) {

    if (l == r) {

        mv[k] = -def[l];

        return;

    }

    int mid = l + r >> 1;

    build(k << 1, l, mid);

    build(k << 1 | 1, mid + 1, r);

    up(k);

}

void add(int k, int l, int r, int val, int a, int b) {

    if (a <= l && r <= b) {

        mv[k] += val, f[k] += val;

        return;

    }

    down(k);

    int mid = l + r >> 1;

    if (a <= mid) add(k << 1, l, mid, val, a, b);

    if (b > mid) add(k << 1 | 1, mid + 1, r, val, a, b);

    up(k);

}

int main() {

    memset(atk, 127, sizeof(atk));

    memset(def, 127, sizeof(def));

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cin >> n >> m >> p;

    inc(i, 1, n) {

        cin >> x >> c;

        atk[x] = min(atk[x], c);

        matk = max(x, matk);

    }

    dec(i, matk - 1, 1) atk[i] = min(atk[i], atk[i + 1]);

    inc(i, 1, m) {

        cin >> x >> c;

        def[x] = min(def[x], c);

        mdef = max(x, mdef);

    }

    dec(i, mdef - 1, 1) def[i] = min(def[i], def[i + 1]);

    build(1, 1, mdef);

    inc(i, 0, p - 1) {

        cin >> x >> y >> c;

        mos[i] = {x, y, c};

    }

    sort(mos, mos + p);

    ll res = -atk[1] - def[1];

    inc(i, 0, p - 1) {

        if (mos[i].b < mdef) add(1, 1, mdef, mos[i].c, mos[i].b + 1, mdef);

        if (mos[i].a < matk) res = max(res, mv[1] - atk[mos[i].a + 1]);

    }

    cout << res;

}

D - Reachable Strings

题意: 给出一个串 s, 和 q 组查询, 询问 s 的两个子串是否是 Reachable. 所谓 Reachable 是指将一个串的子串 "011" 变为 "110" 或者把 "110" 变为 "011", 可以变换多次. |s| ≤ 2e5, q ≤ 2e5.

思路: 这个变换操作的本质就是将 "0" 移动并穿过若干个 "11". 将串 s 中成对相邻的 "1" 都去掉得到串 t, 此时 Reachable 就等价于在 t 中的对应子串一样. 这个可以用 Hash 判断. 注意子串在变换到 t 时左右两边省略掉的 "1" 奇偶性也得一致.

view code

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define inc(i, l, r) for (int i = l; i <= r; i++)

#define dec(i, l, r) for (int i = l; i >= r; i--)

const int maxn = 2e5 + 5;

const int mod0 = 1e9 + 7;

const int mod1 = 1e9 + 9;

const int BASE = 2;

int n, l1, l2, len, q;

char s[maxn];

int num[maxn];

ll hash0[maxn], hash1[maxn];

ll pow0[maxn], pow1[maxn];

int l[maxn], r[maxn], pos[maxn];

string t = "#";

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cin >> n >> s + 1 >> q;

    dec(i, n, 1) r[i] = s[i] == '1' ? r[i + 1] + 1 : 0;

    inc(i, 1, n) l[i] = s[i] == '1' ? l[i - 1] + 1 : 0;

    inc(i, 1, n) {

        if (s[i] == '0') {

            pos[i] = t.size();

            t += '0';

        } else if (t.back() == '1') {

            t.pop_back();

        } else {

            t += '1';

        }

    }

    int len = t.size() - 1;

    pow0[0] = pow1[0] = 1;

    inc(i, 1, len) {

        pow0[i] = pow0[i - 1] * BASE % mod0;

        pow1[i] = pow1[i - 1] * BASE % mod1;

        hash0[i] = (hash0[i - 1] * BASE + t[i] - '0') % mod0;

        hash1[i] = (hash1[i - 1] * BASE + t[i] - '0') % mod1;

    }

    inc(ca, 1, q) {

        cin >> l1 >> l2 >> len;

        int z1 = l1 + r[l1], y1 = l1 + len - 1 - l[l1 + len - 1];

        int z2 = l2 + r[l2], y2 = l2 + len - 1 - l[l2 + len - 1];

        if (z1 > y1 && z2 > y2) {

            cout << "Yes\n";

            continue;

        }

        if (z1 > y1 || z2 > y2) {

            cout << "No\n";

            continue;

        }

        if (r[l1] % 2 != r[l2] % 2 ||

            l[l1 + len - 1] % 2 != l[l2 + len - 1] % 2) {

            cout << "No\n";

            continue;

        }

        z1 = pos[z1] - 1, y1 = pos[y1], z2 = pos[z2] - 1, y2 = pos[y2];

        if (y1 - z1 == y2 - z2 &&

            (hash0[y1] + (mod0 - pow0[y1 - z1]) * hash0[z1]) % mod0 ==

                (hash0[y2] + (mod0 - pow0[y2 - z2]) * hash0[z2]) % mod0 &&

            (hash1[y1] + (mod1 - pow1[y1 - z1]) * hash1[z1]) % mod1 ==

                (hash1[y2] + (mod1 - pow1[y2 - z2]) * hash1[z2]) % mod1) {

            cout << "Yes\n";

        } else {

            cout << "No\n";

        }

    }

}

巴特西

Codeforces Round #625 (1A - 1D)

最新文章

热门文章