Codeforces Round 550 (Div.3) 题解

Contest
1277 Words

Codeforces Round #550 (Div.3) 题解

A. Diverse Strings & B. Parity Alternated Deletions

太水了，略

C. Two Shuffled Sequences

Description

你有一个长为$n$的数列，你要把它分成两个数列，满足一个数列单调递增，另一个数列单调递减

求任意一种方案

Solution

根据抽屉原理，如果有$\geq3​$个相同的数字那么肯定不行

否则对于出现两次的数，把它分别放在两个数列里

出现一次的数随便放在哪个数列里都行

然后就做完了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>

#define R register
#define ll long long
#define cmax(a, b) ((a < b) ? b : a)
#define cmin(a, b) ((a < b) ? a : b)
#define sum(a, b, mod) ((a + b) % mod)
#define openfile(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
const int MaxN = 500010;
int n, in, de;
int a[MaxN], vis[MaxN], cnt[MaxN], inc[MaxN], dec[MaxN];
int cmp(int a, int b)
{
    return a > b;
}
inline int read()
{
    int x = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0')
        ch = getchar();
    while (ch <= '9' && ch >= '0')
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}
int main()
{
    n = read();
    for (int i = 1; i <= n; ++i)
    {
        a[i] = read(), ++cnt[a[i]];
        if (cnt[a[i]] >= 3)
            return 0 * printf("NO");
    }
    for (int i = 1; i <= n; i++)
    {
        if (cnt[a[i]] == 1)
            inc[++in] = a[i];
        else if (cnt[a[i]] == 2 && vis[a[i]] == 1)
            dec[++de] = a[i];
        else
            inc[++in] = a[i], ++vis[a[i]];
    }
    std::sort(inc + 1, inc + in + 1);
    std::sort(dec + 1, dec + de + 1, cmp);
    printf("YES\n");
    printf("%d\n", in);
    for (int i = 1; i <= in; i++)
        printf("%d ", inc[i]);
    puts("");
    printf("%d\n", de);
    for (int i = 1; i <= de; i++)
        printf("%d ", dec[i]);
    puts("");
    return 0;
}

D. Equalize Them All

Description

给定一个数列$a_i$,你有两种操作

  • 操作$1​$,把$a_i​$赋值为$a_i+|a_i−a_j|​$

  • 操作$2$,把$a_i$赋值为$a_i-|a_i−a_j|$

操作均需满足$|i-j|=1$

求最小次数及方案

Solution

贪心一下，你就知道

首先肯定是把所有数字全部变成出现次数最大的那个数时最优

所以你记录一下出现次数最大的那个数每次出现的位置，然后模拟一下

Finished

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>

#define R register
#define ll long long
#define cmax(a, b) ((a < b) ? b : a)
#define cmin(a, b) ((a < b) ? a : b)
#define sum(a, b, mod) ((a + b) % mod)
#define openfile(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
const int MaxN = 2e5 + 10;
int n;
int a[MaxN], cnt[MaxN];
std::vector<int> vec;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), ++cnt[a[i]];
    int max = 0, num = 0;
    for (int i = 1; i <= n; i++)
    {
        if (max < cnt[a[i]])
            max = cnt[a[i]], num = a[i];
    }
    printf("%d\n", n - max);
    if (max == n)
        return 0;
    vec.push_back(0);
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == num)
            vec.push_back(i);
    }
    for (int i = 1; i < vec.size(); i++)
    {
        for (int j = vec[i] - 1; j > vec[i - 1]; j--)
        {
            if (a[j] > num)
                printf("%d %d %d\n", 2, j, j + 1);
            else
                printf("%d %d %d\n", 1, j, j + 1);
        }
    }
    if (vec[vec.size() - 1] < n)
    {
        for (int i = vec[vec.size() - 1] + 1; i <= n; i++)
        {
            if (a[i] > num)
                printf("%d %d %d\n", 2, i, i - 1);
            else
                printf("%d %d %d\n", 1, i, i - 1);
        }
    }
    return 0;
}

E. Median String

Description

有两个长度为$k$的字符串

你要求它们的”中间字符串”(即两个字符串的平均值)

数据保证有解

Solution

首先把两个字符串化成两个数字数组$a_i$,$b_i$$a<b$

然后按类似高精度的方式将两个串相减,再$÷2$，得到另一个串$c_i$

然后让$a_i$加上$c_i$,Finish

(注意进位！

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>

#define R register
#define ll long long
#define cmax(a, b) ((a < b) ? b : a)
#define cmin(a, b) ((a < b) ? a : b)
#define sum(a, b, mod) ((a + b) % mod)
#define openfile(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
const int MaxN = 500010;
std::string s, t;
int k, nums[MaxN], numt[MaxN], ans[MaxN], add[MaxN];
int main()
{
    scanf("%d", &k);
    std::cin >> s >> t;
    if (s == t)
    {
        std::cout << s;
        return 0;
    }
    for (int i = 1; i <= k; i++)
        nums[i] = s[i - 1] - 'a' + 1;
    for (int i = 1; i <= k; i++)
        numt[i] = t[i - 1] - 'a' + 1;
    for (int i = k; i >= 1; i--)
    {
        while (nums[i] > numt[i])
            numt[i] += 26, numt[i - 1]--;
        if ((numt[i] - nums[i]) % 2)
            add[i + 1] += 13;
        add[i] = (numt[i] - nums[i]) / 2;
    }
    for (int i = k; i >= 1; i--)
    {
        ans[i] += nums[i] + add[i];
        while (ans[i] > 26)
            ans[i - 1]++, ans[i] -= 26;
        while (ans[i] == 0)
            ans[i - 1]++, ans[i] += 26;
    }
    for (int i = 1; i <= k; i++)
        printf("%c", ans[i] + 'a' - 1);
    return 0;
}

F. Graph Without Long Directed Paths

Description

你有一个无向图,没有重边和自环

你的任务是把这个无向图转成有向图，满足这个有向图里找不到长度$\geq2$的边

Solution

将这个图黑白染色

可以发现如果一条边连接的两个点如果都是同一个颜色，那么就不行

否则就从白向黑连边(黑向白也行)

Finished.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
#define R register
#define ll long long
#define cmax(a, b) ((a < b) ? b : a)
#define cmin(a, b) ((a < b) ? a : b)
#define sum(a, b, mod) ((a + b) % mod)
#define openfile(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
const int MaxN = 500010;
struct edge
{
    int to, next;
};
edge e[MaxN];
int n, m, cnt;
int head[MaxN], col[MaxN], u[MaxN], v[MaxN];
inline void add_edge(int u, int v)
{
    ++cnt;
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}
inline int read()
{
    int x = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0')
        ch = getchar();
    while (ch <= '9' && ch >= '0')
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}
inline void dfs(int u, int c)
{
    col[u] = c;
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (col[v])
            continue;
        dfs(v, (c == 1) ? 2 : 1);
    }
}
int main()
{
    n = read(), m = read();
    for (int i = 1; i <= m; i++)
    {
        u[i] = read(), v[i] = read();
        add_edge(u[i], v[i]);
        add_edge(v[i], u[i]);
    }
    for (int i = 1; i <= n; i++)
        if (!col[i])
            dfs(i, 1);
    for (int i = 1; i <= m; i++)
    {
        if (col[u[i]] == col[v[i]])
            return 0 * printf("NO");
    }
    printf("YES\n");
    for (int i = 1; i <= m; i++)
    {
        if (col[u[i]] == 1)
            printf("1");
        else
            printf("0");
    }
    return 0;
}

后记

这是zcy第一次在cf的比赛中切$6$题耶(＾－＾)V

一定要庆祝一下

<模板> 树套树
洛谷2210 Haywire
关注我

分类

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×