Codeforces Round #625 Div. 2 总结

· · 题解

前言：

这场比赛水平发挥较稳定，最后太紧张了，没调出来程序。

希望以后可以放平心态

CF1321A Contest for Robots

SB题

现判是否可行，

再直接算出 b_{i} > r_{i} 有多少个，平均分给 b_{i} < r_{i} 的比赛场次即可。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define mp make_pair
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

int read()
{
    char c = getchar(); int flag = 1, ans = 0;
    while (c < '0' || c > '9') {if (c == '-') flag = -flag; c = getchar();}
    while (c >= '0' && c <= '9') {ans = ans * 10 + c - '0'; c = getchar();}
    return ans * flag;
}

const ll INF = 1e16;
const int MAXN = 100010;
const int MOD = 998244353;
int a[MAXN], b[MAXN];
int n, sum1, sum2;

int main()
{
    scanf ("%d", &n);
    for (int i = 1; i <= n; ++ i)
        scanf ("%d", &a[i]);
    for (int i = 1; i <= n; ++ i)
    {
        scanf ("%d", &b[i]);
        if (b[i] > a[i])
            ++ sum2;
        else if (a[i] > b[i])
            ++ sum1;
    }
    int i;
    for (i = 1; i <= n; ++ i)
        if (a[i] > b[i])
            break;
    if (i == n + 1)
        printf ("-1\n");
    else
        printf ("%d\n", sum2 / sum1 + 1);
    return 0;
}

CF1321B Journey Planning

SB模拟

对于 a_{i} = b，映射为坐标系里的一个点 (i, b)，那么题目要求我们求的就是：

找一条形如 l : y = x + B 的直线（ B 任取），使经过直线 l 的点的横坐标与纵坐标之和最大。

所以令 b_{i} = a_{i} - i，排序，对 b_{i} 相同的一部分求和即可，细节见代码。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define mp make_pair
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

int read()
{
    char c = getchar(); int flag = 1, ans = 0;
    while (c < '0' || c > '9') {if (c == '-') flag = -flag; c = getchar();}
    while (c >= '0' && c <= '9') {ans = ans * 10 + c - '0'; c = getchar();}
    return ans * flag;
}

const ll INF = 1e16;
const int MAXN = 200020;
const int MOD = 998244353;
ll b[MAXN];
int n;
ll ans;

struct Node
{
    int id;
    ll val;
}a[MAXN];

bool cmp (Node x, Node y)
{
    return x.val < y.val;
}

int main()
{
    scanf ("%d", &n);
    for (int i = 1; i <= n; ++ i)
        cin >> b[i];
    for (int i = 1; i <= n; ++ i)
    {
        a[i].val = b[i] - (ll)i;
        a[i].id = i;
    }
    sort (a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; ++ i)
    {
        ll cur = a[i].val + a[i].id;
        while (a[i + 1].val == a[i].val)
        {
            cur += a[i + 1].val;
            cur += a[i + 1].id;
            ++ i;
        }
        ans = max (ans, cur);
    }
    cout << ans << endl;
    return 0;
}

CF1321C Remove Adjacent

SB贪心

从后往前，由字符 z 遍历到字符 b。可以删就删，不能删就pass。

注意（我第一次掉进去的坑）：需要遍历 n 次，因为每一次可能只能删掉一个字符。

否则，hack数据如下：

9
bbbbbbbba
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define mp make_pair
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

int read()
{
    char c = getchar(); int flag = 1, ans = 0;
    while (c < '0' || c > '9') {if (c == '-') flag = -flag; c = getchar();}
    while (c >= '0' && c <= '9') {ans = ans * 10 + c - '0'; c = getchar();}
    return ans * flag;
}

const ll INF = 1e16;
const int MAXN = 100010;
const int MOD = 998244353;
char c[MAXN];
int n, ans, aaa;

vector<int> v[30];

int main()
{
    scanf ("%d", &n);
    aaa = n;
    scanf ("%s", c + 1);
    for (int i = 26; i >= 2; -- i)
        for (int tim = 1; tim <= aaa; ++ tim)
        {
            for (int j = 1; j <= n; ++ j)
                if (c[j] - 'a' + 1 == i)
                {
                    if (c[j] - c[j - 1] == 1)
                    {
                        for (int k = j + 1; k <= n; ++ k)
                            c[k - 1] = c[k];
                        -- n, ++ ans, -- j;
                        //for (int i = 1; i <= n; ++ i)
                            //printf ("%c", c[i]);
                    }
                    else if (c[j] - c[j + 1] == 1)
                    {
                        for (int k = j + 1; k <= n; ++ k)
                            c[k - 1] = c[k];
                        -- n, ++ ans, -- j;
                    }
                }
        }
    printf ("%d\n", ans);
    return 0;
}

CF1321D Navigation System

毒瘤题干：题干过长，引起不适（逃

简单BFS

从终点往BFS一遍，记录每个点的 dis 和 num 值。

分情况讨论，

1. 如果 dis_{p_{i}} \ne dis_{p_{i + 1}} + 1

下一步肯定要更新，因为 p_{k} 到 p_{i} 的最短路肯定 不会经过 p_{i + 1} 这个点（读者可自行画图理解）

这样更新即可：

++ mn, ++ mx;

2. 如果 dis_{p_{i}} = dis_{p_{i + 1}} + 1

I. 如果 num_{p_{i}} = 1

不可能导航到另一条路上，直接过就好

II. 如果 num_{p_{i}} > 1

可能导航到另一条路上，也可能导航准确

这样更新即可：

++ mx;

注意：我代码里的 num 数组全部减了一

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define mp make_pair
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

int read()
{
    char c = getchar(); int flag = 1, ans = 0;
    while (c < '0' || c > '9') {if (c == '-') flag = -flag; c = getchar();}
    while (c >= '0' && c <= '9') {ans = ans * 10 + c - '0'; c = getchar();}
    return ans * flag;
}

const ll INF = 1e16;
const int MAXN = 200020;
int head1[MAXN], head[MAXN], d[MAXN], a[MAXN], num[MAXN];
bool vis[MAXN];
int n, m, cnt, cnt1, k, mx, mn;

struct Edge
{
    int to;
    int nxt;
}e[MAXN], e1[MAXN];

void AddEdge (int from, int to)
{
    e1[++ cnt1].to = to;
    e1[cnt1].nxt = head1[from];
    head1[from] = cnt1;

    e[++ cnt].to = from;
    e[cnt].nxt = head[to];
    head[to] = cnt;
}

void bfs()
{
    for (int i = 1; i <= n; ++ i)
        d[i] = 0x3f3f3f3f;
    queue<int> q;
    q.push(a[k]);
    d[a[k]] = 0;
    while (!q.empty())
    {
        int tmp = q.front();
        q.pop();
        vis[tmp] = true;
        for (int i = head[tmp]; i; i = e[i].nxt)
        {
            int v = e[i].to;
            if (vis[v] == true)
                continue;
            if (d[v] > d[tmp] + 1)
            {
                d[v] = d[tmp] + 1;
                q.push(v);
            }
            else if (d[v] == d[tmp] + 1)
                ++ num[v];
        }
    }
}

int main()
{
    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= m; ++ i)
    {
        int u, v;
        scanf ("%d%d", &u, &v);
        AddEdge (u, v);
    }
    scanf ("%d", &k);
    for (int i = 1; i <= k; ++ i)
        scanf ("%d", &a[i]);
    bfs();
    for (int i = 1; i < k; ++ i)
    {
        if (d[a[i + 1]] + 1 == d[a[i]])
            mx += min (num[a[i]], 1);
        else
            ++ mn, ++ mx;
    }
    //for (int i = 1; i <= n; ++ i)
    //  printf ("%d %d %d\n", i, d[i], num[i]);
    printf ("%d %d\n", mn, mx);
    return 0;
}

CF1321E World of Darkraft: Battle for Azathoth

毒瘤题，也可能是我代码能力太差，这题我调了一年

首先，对于武器和防具，去重；对于怪兽，按防御力排序

在枚举到第 i 个防具的时候，我们枚举所有恰能被第 i 个防具击败的怪兽（也就是第 i - 1 个防具击败不了，但是第 i 个防具可以击败的）

然后我们对每个武器维护一个权值。当我们枚举到一个怪兽的时候，就先二分出最弱的一个能击败这个怪兽 A 值的武器，然后给所有不弱于这个武器的武器的权值加上这个怪兽的收益。

每次枚举完怪兽，我们就找一下（贡献值 - 价格）最大的武器，更新答案

这里，由于对每个武器维护的权值需要区间加，区间求 \max ，所以可以选用线段树来维护

这题不太好讲，可能讲的不太清楚，细节见代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define mp make_pair
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pil;
typedef pair<ll, ll> pli;
typedef pair<ll, ll> pll;

ll read()
{
    char c = getchar(); ll flag = 1, ans = 0;
    while (c < '0' || c > '9') {if (c == '-') flag = -flag; c = getchar();}
    while (c >= '0' && c <= '9') {ans = ans * 10 + c - '0'; c = getchar();}
    return ans * flag;
}

const ll INF = 1e16;
const ll MAXN = 500020;
ll tree[MAXN << 2], lazy[MAXN << 2], x[MAXN];
ll n, m, p, ans = -INF;

struct Attack
{
    ll a, ca;
}atk1[MAXN], atk[MAXN];

struct Defense
{
    ll b, cb;
}def1[MAXN], def[MAXN]; 

struct Monster
{
    ll a, d, c;
}mon[MAXN];

bool cmp1 (Attack x, Attack y)
{
    return x.a < y.a || (x.a == y.a && x.ca < y.ca);
}

bool cmp2 (Defense x, Defense y)
{
    return x.b < y.b || (x.b == y.b && x.cb < y.cb);
}

bool cmp3 (Monster x, Monster y)
{
    return x.d < y.d;
}

void push_back (ll now, ll l, ll r)
{
    if (lazy[now] == 0)
        return;
    ll mid = (l + r) >> 1;
    lazy[now << 1] += lazy[now];
    lazy[now << 1 | 1] += lazy[now];
    tree[now << 1] += lazy[now];
    tree[now << 1 | 1] += lazy[now];
    lazy[now] = 0;
}

void build_tree (ll now, ll l, ll r)
{ 
    if (l == r)
    {
        tree[now] = -atk[l].ca;
        return;
    }
    ll mid = (l + r) >> 1;
    build_tree (now << 1, l, mid);
    build_tree (now << 1 | 1, mid + 1, r);
    tree[now] = max (tree[now << 1], tree[now << 1 | 1]);
}

void modify (ll now, ll l, ll r, ll L, ll R, ll x)
{
    if (L <= l && r <= R)
    {
        lazy[now] += x;
        tree[now] += x;
        return;
    }
    push_back (now, l, r);
    ll mid = (l + r) >> 1;
    if (L <= mid)
        modify (now << 1, l, mid, L, R, x);
    if (R > mid)
        modify (now << 1 | 1, mid + 1, r, L, R, x);
    tree[now] = max (tree[now << 1], tree[now << 1 | 1]);
}

int main()
{
    scanf ("%lld%lld%lld", &n, &m, &p);
    for (ll i = 1; i <= n; ++ i)
        scanf ("%lld%lld", &atk1[i].a, &atk1[i].ca);
    for (ll i = 1; i <= m; ++ i)
        scanf ("%lld%lld", &def1[i].b, &def1[i].cb);
    sort (atk1 + 1, atk1 + n + 1, cmp1);
    sort (def1 + 1, def1 + m + 1, cmp2);
    ll tp = 0; //开始去重 
    for (ll i = 1; i <= n; ++ i)
        if (atk1[i].a != atk[tp].a)
            atk[++ tp] = atk1[i];
    n = tp, tp = 0;
    for (ll i = 1; i <= m; ++ i)
        if (def1[i].b != def[tp].b)
            def[++ tp] = def1[i];
    m = tp;

    for (ll i = 1; i <= p; ++ i)
        scanf ("%lld%lld%lld", &mon[i].a, &mon[i].d, &mon[i].c);
    sort (mon + 1, mon + p + 1, cmp3);

    memset (tree, -0x3f, sizeof (tree));
    build_tree (1, 1, n);
    ll pos = 1;
    for (ll i = 1; i <= n; ++ i)
        x[i] = atk[i].a;
    for (ll i = 1; i <= m; ++ i)
    {
        for (; pos <= p && mon[pos].d < def[i].b; ++ pos)
        {
            ll now = upper_bound (x + 1, x + n + 1, mon[pos].a) - x;
            if (x[now] > mon[pos].a)
                modify (1, 1, n, now, n, mon[pos].c);
        }
        //if (ans < query (1, 1, n, 1, n) - def[i].cb)
        //  prllf ("%lld %lld\n", i, query (1, 1, n, 1, n) - def[i].cb);
        ans = max (ans, tree[1] - def[i].cb);
    }
    printf ("%lld\n", ans);
    return 0;
}

CF1321F Reachable Strings

挺好的思维题，码量也不大

首先，需要看出一件事情————一次变换相当于让一个 0 向前跳两位或向后跳两位，但 00 这种子串两个 0 都互相跳不过去

虽然很显然，但不容易向这方面思考（可能是我太菜了）

假设 t 是原字符串， t_{l_{1}, l_{1} + 1, ... , l_{1} + len - 1} 中 0 的奇偶性依次是 k1_{1}, k1_{2}, ..., k1_{cnt_{1}}，t_{l_{2}, l_{2} + 1, ... , l_{2} + len - 1} 中 0 的奇偶性依次是 k2_{1}, k2_{2}, ..., k2_{cnt_{2}}

那么可以由 t_{l_{1}, l_{1} + 1, ... , l_{1} + len - 1} 变成 t_{l_{2}, l_{2} + 1, ..., l_{2} + len - 1} 的充分必要条件是：

\begin{cases}cnt_1 = cnt_2 \\ k1_{i} = k2_{i} (1 \le i \le cnt_1) \end{cases}

接下来就简单了————
对字符串简单哈希一下就可以了

详情见我代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define mp make_pair
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

ll read()
{
    char c = getchar(); ll flag = 1, ans = 0;
    while (c < '0' || c > '9') {if (c == '-') flag = -flag; c = getchar();}
    while (c >= '0' && c <= '9') {ans = ans * 10 + c - '0'; c = getchar();}
    return ans * flag;
}

const ll INF = 1e16;
const int MAXN = 200020;
const ll MOD = 1e9 + 9, bas = 23;
ll has[2][MAXN], pw[MAXN], cnt[MAXN];
char c[MAXN];
int n, q;

ll query (int l, int r, int op)
{
    return ((has[op][r] - has[op][l - 1] * pw[cnt[r] - cnt[l - 1]]) % MOD + MOD) % MOD;
}

int main()
{
    scanf ("%d", &n);
    scanf ("%s", c + 1);
    for (int i = 1; i <= n; ++ i)
    {
        has[0][i] = has[0][i - 1], has[1][i] = has[1][i - 1], cnt[i] = cnt[i - 1];
        if (c[i] == '0')
        {
            has[0][i] = (has[0][i - 1] * bas + 1 + (i & 1)) % MOD;
            has[1][i] = (has[1][i - 1] * bas + 1 + ((i & 1) ^ 1)) % MOD;
            ++ cnt[i];
        }
    }
    pw[0] = 1;
    for (ll i = 1; i <= n; ++ i)
        pw[i] = pw[i - 1] * bas % MOD;
    scanf ("%d", &q);
    for (int i = 1; i <= q; ++ i)
    {
        ll l1, l2, len;
        scanf ("%lld%lld%lld", &l1, &l2, &len);
        if (query (l1, l1 + len - 1, l1 & 1) == query (l2, l2 + len - 1, l2 & 1))
            printf ("Yes\n");
        else
            printf ("No\n");
    }
    return 0;
}