侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

Codeforces Round 617 (Div. 3)

GabrielxD
2023-10-23 / 0 评论 / 0 点赞 / 328 阅读 / 2,207 字
温馨提示:
本文最后更新于 2023-11-09,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

Codeforces Round 617 (Div. 3) - Codeforces

Problem - A

方法一:数学

思路

数组在以下两种情况下是合法的:

  1. 数组和为奇数:不用替换任何元素就已经符合题意;
  2. 数组和为偶数但数组内元素有奇有偶:把偶数元素替换为奇数元素数组和就会变为奇数。

代码

#include <cstdio>

using namespace std;

int t, n;

void solve() {
    int sum = 0;
    bool has_odd = false, has_even = false;
    scanf("%d", &n);
    while (n--) {
        int x; scanf("%d", &x);
        sum += x;
        if (x & 1) has_odd = true;
        else has_even = true;
    }
    puts((sum & 1) || has_odd && has_even ? "YES" : "NO");
}

int main() {
    scanf("%d", &t);
    while (t--) solve();

    return 0;
}

Problem - B

方法一:模拟

思路

按照题意模拟即可。

代码

#include <cstdio>

using namespace std;

int t, n;

void solve() {
    scanf("%d", &n);
    int ans = 0;
    while (n / 10) {
        ans += n / 10 * 10;
        n = n / 10 + n % 10;
    }
    ans += n;
    printf("%d\n", ans);
}

int main() {
    scanf("%d", &t);
    while (t--) solve();

    return 0;
}

Problem - C

方法一:暴力 枚举 模拟

思路

如果存在一段移动满足:完成这段移动后回到了这段移动前所在的点。那么这段移动就是可以删掉的。

模拟所有移动找到最短的一段即可(如果有多段长度一样的,输出最前面的)。

代码1

把坐标处理成一个长整数。

#include <cstdio>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int N = 2e5 + 10, MASK = 1e6;
int DIRS[128][2];
int t, n;
char s[N];
unordered_map<LL, int> mp;

void solve() {
    scanf("%d%s", &n, s + 1);
    mp.clear();
    int mn = n + 1, l = 0;
    int x = 0, y = 0;
    for (int i = 1; i <= n; ++i) {
        mp[1LL * x * MASK + y] = i;
        const auto& DIR = DIRS[s[i]];
        x += DIR[0], y += DIR[1];
        int j = mp[1LL * x * MASK + y];
        if (j) {
            int len = i - j + 1;
            if (len < mn) {
                mn = len;
                l = j;
            }
        }
    }
    if (mn <= n) printf("%d %d\n", l, l + mn - 1);
    else puts("-1");
}

int main() {
    scanf("%d", &t);
    DIRS['L'][0] = -1, DIRS['L'][1] = 0;
    DIRS['R'][0] = 1, DIRS['R'][1] = 0;
    DIRS['U'][0] = 0, DIRS['U'][1] = 1;
    DIRS['D'][0] = 0, DIRS['D'][1] = -1;
    while (t--) solve();

    return 0;
}

代码2

自定义结构哈希。

#include <cstdio>
#include <utility>
#include <functional>
#include <unordered_map>

using namespace std;

struct Info {
    int x, y;

    bool operator==(const Info& o) const {
        return x == o.x && y == o.y;
    }
};

struct InfoHash {
    size_t operator()(const Info& info) const {
        return hash<int>()(info.x) ^ hash<int>()(info.y);
    }
};

const int N = 2e5 + 10;
unordered_map<char, Info> DIRS;
int t, n;
char s[N];
unordered_map<Info, int, InfoHash> mp;

void solve() {
    scanf("%d%s", &n, s + 1);
    mp.clear();
    int x = 0, y = 0;
    int mn = n + 1, l = -1;
    for (int i = 1; i <= n; ++i) {
        mp[{x, y}] = i;
        const Info& DIR = DIRS[s[i]];
        x += DIR.x, y += DIR.y;
        int j = mp[{x, y}];
        if (j) {
            int len = i - j + 1;
            if (len < mn) {
                mn = len;
                l = j;
            }
        }
    }
    if (mn <= n) printf("%d %d\n", l, l + mn - 1);
    else puts("-1");
}

int main() {
    scanf("%d", &t);
    DIRS['L'] = {-1, 0};
    DIRS['R'] = {1, 0};
    DIRS['U'] = {0, 1};
    DIRS['D'] = {0, -1};
    while (t--) solve();

    return 0;
}

Problem - D

方法一:贪心

思路

先让所有怪物把能挨的 a+ba+b hp 全部挨完(也就是保证怪物血量:0<hia+b0 < h_i \le a + b)再进行讨论。

此时,hiah_i \le a 的怪物不需要使用秘籍就能让 aa 抢到人头。

由于每只怪物对答案的贡献都固定为 11,所以对于剩下的怪物:优先找血量少的怪物去使用秘籍处理(血量越少,使用秘籍的次数一定会越少),所以直接从小到大排个序依次处理,直到秘籍不够用了为止即可。

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;
int n, a, b, k;
int h[N];

int main() {
    scanf("%d%d%d%d", &n, &a, &b, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &h[i]);
        h[i] %= a + b;
        if (h[i] == 0) h[i] += a + b;
    }
    sort(h, h + n);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        h[i] -= a;
        int cnt = (h[i] + a - 1) / a;
        if (cnt <= k) {
            ++ans;
            k -= cnt;
        } else break;
    }
    printf("%d\n", ans);

    return 0;
}

Problem - E1

方法一:二分图

冒泡排序把所有逆序对连边建图,然后染色法判二分图即可。合法方案即为染色数组。

(这种方法只有 easy version 能用)

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210;
int n;
char s[N];
int pos[N];
int h[N], e[N * N], ne[N * N], idx;
int color[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool dye(int u, int c) {
    color[u] = c;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (color[v] == -1 && !dye(v, !c) || color[v] == c) return false;
    }
    return true;
}

int main() {
    scanf("%d%s", &n, s + 1);
    memset(h, -1, sizeof(h));
    for (int i = 1; i <= n; ++i) pos[i] = i;
    for (int i = 1; i <= n - 1; ++i) {
        for (int j = 1; j <= n - i; ++j) {
            if (s[j] > s[j + 1]) {
                swap(s[j], s[j + 1]), swap(pos[j], pos[j + 1]);
                add(pos[j], pos[j + 1]), add(pos[j + 1], pos[j]);
            }
        }
    }
    memset(color, -1, sizeof(color));
    for (int u = 1; u <= n; ++u) {
        if (color[u] == -1 && !dye(u, 0)) {
            puts("NO");
            return 0;
        }
    }
    puts("YES");
    for (int i = 1; i <= n; ++i) putchar('0' + color[i]);

    return 0;
}

方法二:动态规划 最长严格降序子序列

字符串里的严格降序子序列都是一串需要交换的集合。

所以直接对字符串做动态规划找到最长严格降序子序列,如果其长度不大于 2 就说明可以进行合法染色,否则不能。

合法方案即为 动规数组1\text{动规数组}-1

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 210;
int n;
int chr_color[128], pos_color[N];

int main() {
    scanf("%d", &n);
    getchar();
    for (int i = 0; i < n; ++i) {
        char c = getchar();
        for (char j = 'a'; j <= 'z'; ++j) {
            if (c < j) pos_color[i] = max(pos_color[i], chr_color[j]);
        }
        if (pos_color[i] > 1) {
            puts("NO");
            return 0;
        }
        chr_color[c] = ++pos_color[i];
    }
    puts("YES");
    for (int i = 0; i < n; ++i) putchar('0' + pos_color[i] - 1);

    return 0;
}

Problem - E2

方法一:动态规划 最长严格降序子序列

同上。

数组长度最长有 2×1052\times10^5,用一般的 LIS 问题的 DP 做法肯定行不通(O(n2)O(n^2) 的时间复杂度)。但是发现字符串中之可能出现 26 个小写英文字母,所以内层循环不再枚举下标,直接枚举字母即可(代价是要多维护一个字符的贡献数组)。

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;
int n;
char s[N];
int f[N], g[128];

int main() {
    scanf("%d%s", &n, &s);
    getchar();
    int mx = 0;
    for (int i = 0; i < n; ++i) {
        f[i] = 1;
        for (int j = 'a'; j <= 'z'; ++j) {
            if (j > s[i]) f[i] = max(f[i], g[j] + 1);
        }
        g[s[i]] = f[i];
        mx = max(mx, f[i]);
    }
    printf("%d\n", mx);
    for (int i = 0; i < n; ++i) printf("%d ", f[i]);

    return 0;
}

Problem - F

方法一:建图 构造 DFS

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5010, INF = 2e9;
int n, m;
int h[N], w[N * 2], e[N * 2], ne[N * 2], idx;
struct Edge {
    int u, v, w;

    bool operator<(const Edge& o) const {
        return w < o.w;
    }
} edges[N], qs[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool dfs(int u, int p, int dest, int d) {
    if (u == dest) return true;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == p) continue;
        if (dfs(v, u, dest, d)) {
            int j = h[v];
            while (~j && e[j] != u) j = ne[j];
            w[i] = w[j] = d;
            return true;
        }
    }
    return false;
}

int get_mn(int u, int p, int dest) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == dest) return w[i];
        if (v == p) continue;
        int d = get_mn(v, u, dest);
        if (d != -1) return min(w[i], d);
    }
    return -1;
}

int main() {
    scanf("%d", &n);
    memset(h, -1, sizeof(h));
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y), add(y, x);
        edges[i] = {x, y, -1};
    }
    scanf("%d", &m);
    for (int i = 0; i < m; ++i) scanf("%d%d%d", &qs[i].u, &qs[i].v, &qs[i].w);
    sort(qs, qs + m);
    for (int i = 0; i < m; ++i) dfs(qs[i].u, -1, qs[i].v, qs[i].w);
    for (int i = 0; i < m; ++i) {
        int res = get_mn(qs[i].u, -1, qs[i].v);
        if (res != qs[i].w) {
            puts("-1");
            return 0;
        }
    }
    for (int i = 0; i < n - 1; ++i) {
        const int& u = edges[i].u, & v = edges[i].v;
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (j == v) {
                printf("%d ", w[i] ? w[i] : 0721);
                break;
            }
        }
    }

    return 0;
}
0

评论区