CF#732 div2

Posted on Edited on In Views:
Symbols count in article: 5k
题目 A B C D E F
通过情况 O O O O X X
难度 800 1200 1500 1900 2800 3000

A. AquaMoon and Two Arrays

题面

略

题解

略

代码

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
/*
 * @题目: A. AquaMoon and Two Arrays
 * @算法: 
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-07-11 22:54:19
 * @LastEditors: Blore
 * @LastEditTime: 2021-07-15 15:14:27
 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 100010
#define maxm 100010
#define ll long long
using namespace std;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int a[200], b[200];
int tmp[200];
int main()
{
    int t = read();
    while (t--)
    {
        int n = read();
        int sum1 = 0, sum2 = 0;
        for (int i = 1; i <= n; i++)
            a[i] = read(), sum1 += a[i];
        for (int i = 1; i <= n; i++)
            b[i] = read(), sum2 += b[i];
        if (sum1 != sum2)
        {
            puts("-1");
            continue;
        }
        int cnt = 0;
        for (int i = 1; i <= n; i++)
            tmp[i] = a[i] - b[i], cnt += abs(tmp[i]);
        int p1 = 1, p2 = 1;
        printf("%d\n", cnt / 2);
        while (p1 <= n && p2 <= n)
        {
            while (tmp[p1] >= 0 && p1 <= n)
                p1++;
            while (tmp[p2] <= 0 && p2 <= n)
                p2++;
            if (p1 > n || p2 > n)
                break;
            printf("%d %d\n", p2, p1);
            tmp[p1]++, tmp[p2]--;
        }
    }
    return 0;
}

B. AquaMoon and Stolen String

题面

略

题解

基本上读懂了题就没啥问题了，有点像消消乐233

代码

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
/*
 * @题目: B. AquaMoon and Stolen String
 * @算法: 
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-07-18 14:37:39
 * @LastEditors: Blore
 * @LastEditTime: 2021-07-18 14:43:12
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int tab[100010][26];
char s[100010];
int main()
{
    int t = read();
    while (t--)
    {
        int n = read(), m = read();
        memset(tab, 0, sizeof(tab));
        rep(i, 1, 2 * n - 1)
        {
            scanf("%s", s + 1);
            rep(j, 1, m)
                tab[j][s[j] - 'a']++;
        }
        rep(i, 1, m)
        {
            rep(j, 0, 26)
            {
                if (tab[i][j] % 2 == 1)
                {
                    putchar('a' + j);
                    break;
                }
            }
        }
        putchar('\n');
    }
    return 0;
}

C. AquaMoon and Strange Sort

题面

略

题解

不错的思维题，首先必须要发现要满足条件，必须保证原来在第奇数/偶数位置上的必须在第奇数/偶数位置上，对奇数和偶数位置上的数分别排序再检验一下即可。

代码

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
/*
 * @题目: C. AquaMoon and Strange Sort
 * @算法: 排序
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-07-18 14:51:06
 * @LastEditors: Blore
 * @LastEditTime: 2021-07-18 15:02:19
 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 100010
#define maxm 100010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int odd[maxn], even[maxn];
int main()
{
    int t = read();
    while (t--)
    {
        int n = read();
        rep(i, 1, n)
        {
            if (i % 2 == 1)
                odd[(i + 1) / 2] = read();
            else
                even[i / 2] = read();
        }
        sort(odd + 1, odd + (n + 1) / 2 + 1);
        sort(even + 1, even + n / 2 + 1);
        int f = 1;
        rep(i, 1, n - 1)
        {
            if (i % 2 == 1 && odd[(i + 1) / 2] > even[(i + 1) / 2])
            {
                f = 0;
                break;
            }
            else if (i % 2 == 0 && odd[i / 2 + 1] < even[i / 2])
            {
                f = 0;
                break;
            }
        }
        if (f)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

D. AquaMoon and Chess

题面

略

题解

不错的思维题（有点像孔明跳棋，不过不是消除）。首先分析每次移动相当于把‘11‘和左边或右边的’0‘或’1‘或’11‘交换位置，于是把所有能相连的‘11’组找出来，之后对只有’0‘组做插入（单独的’1‘可以不考虑因为左边和右边等效）

此外还需要一些组合数学和乘法逆元的知识。

代码

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
/*
 * @题目: D. AquaMoon and Chess
 * @算法: 组合数学
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-07-18 15:18:23
 * @LastEditors: Blore
 * @LastEditTime: 2021-07-18 15:46:21
 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 100010
#define mod 998244353
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
ll F[maxn], rF[maxn];
char s[maxn];
ll inv(ll a, ll m)
{
    if (a == 1)
        return 1;
    return inv(m % a, m) * (m - m / a) % m;
}
int main()
{
    int t = read();
    F[0] = rF[0] = 1;
    rep(i, 1, maxn - 1)
    {
        F[i] = F[i - 1] * i % mod;
        rF[i] = rF[i - 1] * inv(i, mod) % mod;
    }
    while (t--)
    {
        int n = read();
        scanf("%s", s + 1);
        int cg = 0, c1 = 0, c0 = 0;
        rep(i, 1, n)
        {
            if (s[i] == '0')
                c0++;
            else if (i + 1 <= n && s[i + 1] == '1')
                cg++, i++;
            else
                c1++;
        }
        int ans = F[cg + c0] * rF[c0] % mod * rF[cg] % mod;
        printf("%d\n", ans);
    }
    return 0;
}