2020-03-02发表2020-11-21更新OI / 题解

Codeforces Round #625

¶ 翻译

¶ A. Contest for Robots

给出长度为 $1\le n\le 100$ 的两个序列 $r,b$ ，且满足 $r_i, b_i\in\{0, 1\}$ ，你需要确定 $p_i$ （ $p_i\ge 1$ ）。

满足 $\sum_{i=1}^n r_ip_i > \sum_{i=1}^n b_ip_i$ ，并且最小化 $\max_{i=1}^n{p_i}$ 。

如果不可能，输出 $-1$ 。

¶ B. Journey Planning

给出长度为 $1\le n\le 2\cdot 10^5$ 的序列 $b$ ， $1\le b_i\le 4\cdot 10^5$

称合法序列为， $c_1,\cdots,c_k$ ，满足 $c_i<c_{i+1}$ 和 $c_{i+1}-c_i = b_{c_{i+1}}-b_{c_i}$ （ $k=1$ 时也是合法的），定义其美丽值为 $\sum_{i=1}^k b_{c_i}$ 。

求最大美丽值。

¶ C. Remove Adjacent

给出字符串 $s$ ， $1\le|s|\le100$ 。

定义一次变换为，选中第 $i$ 个字符移除，字符串长度减少 $1$ ，选中字符需要满足 $s_{i-1},s_{i+1}$ 中至少有一个是 $s_i$ 的前驱。

求最多可进行几次操作。

给出 $2\le n\le2\cdot 10^5$ 个节点， $2\le m\le2\cdot 10^5$ 条边的有向图，路径 $p_1,\cdots,p_k$ ，路径中没有重复元素，边 $(p_i,p_{i+1})$ 总是存在。

定义 $s=p_1,t=p_k$ 。

有一个导航系统，若当前在节点 $u$ ，会构造一条从 $u$ 到 $t$ 的最短路径（这种路径可能不止一条，但导航系统只会选其中一条），设导航系统规划的下一个节点为 $w$ ，实际行走的下一个节点为 $v$ 。

$w=v$ 不会触发重构。
$w\neq v$ 会触发重构。

实际行走路线为 $p$ ，求可能的最少重构次数和最多重构次数。

¶ E. World of Darkraft: Battle for Azathoth

有 $n$ 种武器，攻击力和价格分别为 $a_i,ca_i$ 。

有 $m$ 种盔甲，防御力和价格分别为 $b_i,cb_i$ 。

是

ca_i

而不是

c\cdot a_i

有 $p$ 个敌人，防御力、攻击力和掉落金币数为 $x_i,y_i,z_i$ 。

求

\max_{i,j}\left\{\left(\sum_{x_k<a_i,y_k<b_j} z_k\right) - ca_i - cb_j\right\}

¶ F. Reachable Strings

有零一串 $t$ ，从 $1$ 编号， $t[l\dots r]$ 代表 $l$ 到 $r$ 的字串（字串是连续的）。

有两种变换，011->110 和 110->011 。若字符串 $s_1$ 可经过若干次（可为 $0$ ）变换变成 $s_2$ 则称 $s_1$ 可到达 $s_2$ 。

有 $q$ 个询问，给出 $l_1,l_2,len$ ，问 $t[l_1\dots l_1+len-1]$ 是否可到达 $t[l_2\cdots l_2+len-1]$ 。

¶ 题解

¶ A. Contest for Robots

对于 $r_i=b_i$ 或 $r_i=0,b_i=1$ 肯定填 $1$

若没有 $r_i=1,b_i=0$ 则无解，

否则就是让这些 $r_i=1,b_i=0$ 凑出来。

\sum_{r_i=1,b_i=0} p_i > \sum_{r_i=0,b_i=1} 1

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr; using std::cin; using std::cout; using std::endl; using std::make_pair; using std::pair;
typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull; typedef pair<int, int> pii; 

const int N = 200;

int r[N], b[N], p[N];

int main() {
    std::ios::sync_with_stdio(false);
    cout.tie(0);
    int n; cin >> n;
    rep(i, 1, n) cin >> r[i]; rep(i, 1, n) cin >> b[i];
    int ge; bool flag = 0;
    int x = 0, y = 0, z;
    rep(i, 1, n){
        if (r[i] == b[i]) { z++; continue; }
        if (r[i] == 1) x++;
        if (b[i] == 1) y++;
    }
    if (x == 0){ cout << -1; }
    else {
        if ((y+1)%x == 0) cout << (y+1)/x;
        else cout << (y+1)/x + 1;
    }
    return 0;
}

¶ B. Journey Planning

移项可得 $c_{i+1}-b_{c_{i+1}} = c_i-b_{c_i}$

即对于 $i$ ，定义 $d_i=i-b_i$

合法序列即为满足 $d_{c_i}=\cdots=d_{c_k}$

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr; using std::cin; using std::cout; using std::endl; using std::make_pair; using std::pair;
typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull; typedef pair<int, int> pii; 

const int N = 600010;

int b[N], a[N];
ll sum[N*2];

int main() {
    std::ios::sync_with_stdio(false);
    cout.tie(0);
    int n; cin >> n;
    ll ans = 0;
    rep(i, 1, n){
        cin >> b[i];
        a[i] = N+i - b[i];
        sum[a[i]] += b[i];
        ans = std::max(ans, sum[a[i]]);
    }
    cout << ans;
    return 0;
}

¶ C. Remove Adjacent

举例来说，对于 c，只有 b 对 c 有影响，删除 d, e, f,… 要么不会影响，要么使 b 更加靠近 c，让 c 能被删除。

总的来说，就是进行多次扫描，每一次扫描，删除可删除的最大字符。

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr; using std::cin; using std::cout; using std::endl; using std::make_pair; using std::pair;
typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull; typedef pair<int, int> pii; 

const int N = 1000;

char s[N], prev[N], next[N];

bool tag[N];

int main() {
    std::ios::sync_with_stdio(false);
    cout.tie(0);
    int n; cin >> n;
    cin >> s+1;
    rep(i, 1, n){
        cin >> s[i];
    }
    rep(i, 0, n+1) prev[i] = i-1, next[i] = i+1;
    int ans = 0;
    while(1){
        int add = 0, targ = 0;
        rep(i, 1, n){
            if (tag[i]) continue;
            if (s[prev[i]] - s[i] == -1 || s[next[i]] - s[i] == -1){
                targ = std::max(targ, int(s[i]));
            }
        }
        rep(i, 1, n){
            if (tag[i]) continue;
            if (s[i] == targ && (s[prev[i]] - s[i] == -1 || s[next[i]] - s[i] == -1)){
                prev[next[i]] = prev[i];
                next[prev[i]] = next[i];
                add++;
                tag[i] = 1;
            }
        }
        if (add == 0) break;
        ans += add;
    }
    cout << ans;
    return 0;
}

若当前在节点 $u$ ，设导航系统可能规划的下一个节点为 $w_1,\cdots,w_x$ ，实际行走的下一个节点为 $v$ 。

设 $d(u)$ 为 $u$ 到 $t$ 距离。

若 $d(w)<d(v)$ 那么一定会重构。
若 $d(w)=d(v)$ 那么可能会重构。

$d(u)$ 构建反图求即可。

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr; using std::cin; using std::cout; using std::endl; using std::make_pair; using std::pair;
typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull; typedef pair<int, int> pii; 

namespace graph {
const int INF = 2147483647;
template <int N, int M>
struct graph {
    struct edge {
        int v, w;
        edge *nxt;
        edge() : v(0), w(0), nxt(NULL) {}
        edge(int _v, int _w, edge *_nxt) : v(_v), w(_w), nxt(_nxt) {}
    };
    edge e[M];
    edge *head[N];
    int cnt, n;
    inline void addedge(const int &u, const int &v, const int w) {
        e[cnt] = edge(v, w, head[u]);
        head[u] = &e[cnt];
        ++cnt;
    }
    graph() {
        std::memset(head, 0, sizeof(head));
        cnt = 0;
    }
    void dijkstra(int s, int dis[]) {
        for (int i = 0; i <= n; ++i) {
            dis[i] = INF;
        }
        std::priority_queue<pii, std::vector<pii>, std::greater<pii>> q;
        dis[s] = 0;
        q.push(std::make_pair(0, s));
        while (!q.empty()) {
            pii cur = q.top();
            q.pop();
            if (cur.first > dis[cur.second]) continue;
            for (edge *i = head[cur.second]; i != NULL; i = i->nxt) {
                if (dis[i->v] > cur.first + i->w) {
                    dis[i->v] = cur.first + i->w;
                    q.push(std::make_pair(dis[i->v], i->v));
                }
            }
        }
    }
};
}  // namespace graph

const int N = 2e5+100, M = 2e5+100;

graph::graph<N, M> f, g;

int p[N], dis[N];

int main() {
    std::ios::sync_with_stdio(false);
    cout.tie(0);
    int n, m; cin >> n >> m;
    f.n = g.n = n;
    rep(i, 1, m){
        int u, v;
        cin >> u >> v;
        f.addedge(u, v, 1);
        g.addedge(v, u, 1);
    }

    int k; cin >> k;
    rep(i, 1, k) cin >> p[i];

    g.dijkstra(p[k], dis);
    int min = 0, max = 0;
    rep(qaq, 1, k-1){
        int less = 0, eq = 0;
        int u = p[qaq];
        int s = dis[p[qaq+1]];
        for(auto i = f.head[u]; i ; i = i->nxt){
            if (i->v == p[qaq+1]) continue;
            if (dis[i->v] < s) less++;
            if (dis[i->v] == s) eq++;
        }
        if (less) min++;
        if (less || eq) max++;
    }
    cout << min << ' ' << max;
    return 0;
}

¶ E. World of Darkraft: Battle for Azathoth

是一个简单扫描线。

构造线段树，支持区间加，总体最大。

按武器的攻击力（或者说敌人的防御力）扫描，线段树维护盔甲的防御力（或者说敌人的攻击力），线段树中不是盔甲防御力的值的地方赋成 $-\infin$ ，其余地方赋成 $-cb$ 。

具体看代码吧。

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr; using std::cin; using std::cout; using std::endl; using std::make_pair; using std::pair;
typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull; typedef pair<int, int> pii; 

const int N = 1e6+10;
ll inf = 0x3f3f3f3f3f3f3f3f;

int n, m; ll c;

struct Seg{
    struct Node{
        int l, r;
        ll sum, tag, max;
    } T[N*4];
#define s T[c]
#define ls (c<<1)
#define rs ((c<<1)|1)
#define ln T[ls]
#define rn T[rs]
    inline void upd(int c){
        s.sum = ln.sum + rn.sum;
        s.max = std::max(ln.max, rn.max);
    }
    inline void pushdown(int c){
        ln.tag += s.tag, rn.tag += s.tag;
        ln.sum += (ln.r-ln.l+1)*s.tag, rn.sum += (rn.r-rn.l+1)*s.tag;
        ln.max += s.tag, rn.max += s.tag;
        s.tag = 0;
    }
    void build(int c, int l, int r){
        s.l = l, s.r = r;
        if (l == r){ s.sum = s.max = -inf; return; }
        int mid = (l+r)/2;
        build(ls, l, mid);
        build(rs, mid+1, r);
        upd(c);
    }
    void init(int n){ build(1, 1, n); }
    int P, L, R; ll X;
    void _add(int c){
        if (L <= s.l && s.r <= R){ s.tag += X; s.max += X; s.sum += (s.r-s.l+1)*X; return; }
        if (s.r < L || R < s.l) return;
        pushdown(c); _add(ls); _add(rs); upd(c);
    }
    void add(int pos, ll x){ L = R = pos, X = x; _add(1); }
    void add(int l, int r, ll x){ L = l, R = r, X = x; _add(1); }
    ll _query(int c){
        if (L <= s.l && s.r <= R) return s.sum;
        if (s.r < L || R < s.l) return 0;
        pushdown(c); return _query(ls) + _query(rs);
    }
    ll _query_max(int c){
        if (L <= s.l && s.r <= R) return s.max;
        if (s.r < L || R < s.l) return -inf;
        pushdown(c);
        return std::max(_query_max(ls), _query_max(rs));
    }
    ll query_max(int l, int r){ L=l, R=r; return _query_max(1); }
    ll query_sum(int l, int r){ L=l, R=r; return _query(1); }
    void print(int c){
        cerr << s.l << ' ' << s.r << ' ' << s.max << endl;
        if (s.l == s.r){  return; }
        pushdown(c);
        print(ls); print(rs);
    }
#undef s
#undef ls
#undef rs
#undef ln
#undef rn
} ds;

struct W{
    int a;
    ll c;
    bool operator== (const W& rhs){
        return a == rhs.a;
    }
} w[N], a[N];
bool cmp(const W&a, const W& b){
    return a.a == b.a ? a.c < b.c : a.a < b.a;
}
struct X
{
    int x, y, z;
} mos[N];
bool cmp_x(const X&a, const X&b){
    return a.x < b.x;
}

int main() {
    std::ios::sync_with_stdio(false);
    cout.tie(0);
    int n, m, p; cin >> n >> m >> p;
    rep(i, 1, n) cin >> w[i].a >> w[i].c;
    rep(i, 1, m) cin >> a[i].a >> a[i].c;
    std::sort(w+1, w+1+n, cmp);
    n = std::unique(w+1, w+1+n) - (w+1);
    std::sort(a+1, a+1+m, cmp);
    m = std::unique(a+1, a+1+m) - (a+1);
    // cerr << n << ' ' << m << endl;
    rep(i, 1, p) cin >> mos[i].x >> mos[i].y >> mos[i].z;
    std::sort(mos+1, mos+1+p, cmp_x);
    int M = 1e6+10;
    ds.init(M);
    rep(i, 1, m){
        ds.add(a[i].a, inf-a[i].c);
    }
    // ds.print(1);

    ll ans = -inf;
    int j = 1;
    rep(i, 1, n){
        for(; j <= p && mos[j].x < w[i].a; ++j) ds.add(mos[j].y+1, M, mos[j].z);
        ans = std::max(ans, ds.query_max(1, M) - w[i].c);
    }
    cout << ans;
    return 0;
}

¶ F. Reachable Strings

Codeforces Round #625

https://gesrua.xyz/archives/题解/Codeforces/CF1321

作者

Gesrua

发布于

2020-03-02

更新于

2020-11-21

许可协议

#Codeforces

Codeforces Round #625

¶ 翻译

¶ A. Contest for Robots

¶ B. Journey Planning

¶ C. Remove Adjacent

¶ D. Navigation System

¶ E. World of Darkraft: Battle for Azathoth

¶ F. Reachable Strings

¶ 题解

¶ A. Contest for Robots

¶ B. Journey Planning

¶ C. Remove Adjacent

¶ D. Navigation System

¶ E. World of Darkraft: Battle for Azathoth

¶ F. Reachable Strings

作者

发布于

更新于

许可协议

目录

分类