Zth's Blog

记录学习路上的点滴

0%

Deltix Round, Summer 2021

发表于 更新于 分类于

Deltix Round, Summer 2021

A. A Variety of Operations

题意

你手里有两个数$a, b$， 初始值都是$0$， 有两种操作

  1. 给$a, b$同时加上一个数$k$($k$可以是负数)
  2. 给$a$加$k$， 同时给$b$减$k$($k$可以是负数)

给你两个数$c, d$， 问你最少通过多少次操作可以将$a, b$变为$c, d$， 不可能的话输出$-1$

数据范围

多组数据， $t \leq 400$

$0 \leq a, b \leq 10^9$

题解

AC代码

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 <iostream>
#include <cstdio>
#include <cmath>

int t;
int c, d;

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

        if(abs(c - d) % 2)
        {
            printf("-1\n");

            continue;
        }
        if(c == 0 && d == 0)
        {
            printf("0\n");

            continue;
        }
        if(c == 0 || d == 0)
        {
            printf("2\n");

            continue;
        }
        if(c == d)
        {
            printf("1\n");

            continue;
        }
        printf("2\n");
    }

    return 0;
}

B. Take Your Places!

题意

给出一个长度为$n$的整数序列$a_1, a_2, … , a_n$, 每次操作可以交换相邻的两个数

问你最少的操作次数使得这个序列变成奇偶相间的， 不可能的话输出$-1$

数据范围

多组数据， $ t \leq 400$

$n \leq 10^5, 1 \leq a_i \leq 10^9$

题解

我原来的想法

由于$a_i$只贡献奇偶， 为了方便操作我们将$a_i$转化为$a_i \% 2$

首先我们可以确定的是如果这个序列中奇数和偶数的数量差大于1， 那么肯定是没有解的， 否则一定有解， 以下分析均建立在有解的基础上

如果$n$是奇数， 那么答案的排列是固定的， 否则有两种可能的答案序列（奇数开头或偶数开头）我们将答案序列用b序列表示

那么我们的每次操作可能产生以下结果

  1. 交换的两个数都是错的， 那么交换完之后两个数都变成对的
  2. 交换的两个数一个是对的一个是错的， 那么交换完对错位置对调
  3. 交换的两个数都是对的， 没有意义

那么我们就想办法通过操作2使错的数相邻， 然后通过操作1消掉

那么我们的算法如下

i从1到n扫一遍， pre = 0

如果$a_i$是对的， 跳过

否则如果pre为0， pre= i， 跳过

否则对答案产生i - pre的贡献， pre变为0

代码

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>

int t;
int n;
int a[100005], b[100005];

int main()
{
    scanf("%d", &t);
    while(t --)
    {
        int cnt = 0;
        int ans = 1e9;
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));

        scanf("%d", &n);
        for(int i = 1; i <= n; i ++)
        {
            scanf("%d", &a[i]);

            a[i] = a[i] % 2;
            cnt += a[i];
        }

        int sj = cnt, so = n - cnt;
        if(abs(so - sj) > 1)
        {
            printf("-1\n");

            continue;
        }

        if(n % 2)
        {
            ans = 0;

            if(sj > so)
                for(int i = 1; i <= n; i ++)
                    b[i] = i % 2;
            else
                for(int i = 1; i <= n; i ++)
                    b[i] = (i + 1) % 2;

            int pre = 0;
            for(int i = 1; i <= n; i ++)
            {
                if(a[i] != b[i])
                {
                    if(pre)
                        ans += i - pre, pre = 0;
                    else
                        pre = i;
                }
            }
        }
        else
        {
            for(int i = 1; i <= n; i ++) b[i] = i % 2;

            int pre = 0, pans = 0;
            for(int i = 1; i <= n; i ++)
            {
                if(a[i] != b[i])
                {
                    if(pre)
                        pans += i - pre - 1, pre = 0, pans ++;
                    else
                        pre = i;
                }
            }
            ans = std:: min(ans, pans);

            for(int i = 1; i <= n; i ++) b[i] = (i + 1) % 2;

            pre = 0, pans = 0;
            for(int i = 1; i <= n; i ++)
            {
                if(a[i] != b[i])
                {
                    if(pre)
                        pans += i - pre - 1, pre = 0, pans ++;
                    else
                        pre = i;
                }
            }
            ans = std:: min(ans, pans);
        }

        printf("%d\n", ans);
    }

    return 0;
}

不过这么做是错的

虽然看不到输入， 但是正确答案是6， 我的答案是4

很奇怪， 我的做法肯定是可以得到答案的， 就算不是正解， 但是绝对可以经过这么多次操作找到答案， 只不过不一定最优， 现在我得到的结果居然比正解的要小? 不应该啊

错就错在把对的和错的交换， 才是相当于没有交换， 两个对的交换产生两个错的， 当时可能是脑子过载了， 想当然了， 没有仔细考虑

正解

既然答案序列已知了， 那我们就把所有的1移到他们在答案序列中的位置就好了（当然， 移动0也可以， 这里以1为例）

那么问题就转化为把所有的1放到正确的位置所需要的最少的步数

答案是给出的序列a中的1和答案序列中的1的顺序对应， 也就a中第i个1移到答案序列的第i个1的位置， 可以保证最小

为什么这样是对的？

使用微扰法证明

假设我们交换两个i的移动方案

没有交换之前， 答案一定是小于$rmax - lmax$的， 因为没有重叠部分， 交换后有了重叠部分， 一定是比原来的大的， 所以原来的解就是最优解

AC代码

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>

int t;
int n;
int a[100005], b[100005];

int main()
{
    scanf("%d", &t);
    while(t --)
    {
        int cnt = 0;
        long long ans = 1e18;
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));

        scanf("%d", &n);
        for(int i = 1; i <= n; i ++)
        {
            scanf("%d", &a[i]);

            a[i] = a[i] % 2;
            cnt += a[i];
        }

        int sj = cnt, so = n - cnt;
        if(abs(so - sj) > 1)
        {
            printf("-1\n");

            continue;
        }

        if(n % 2)
        {
            ans = 0;

            if(sj > so)
                for(int i = 1; i <= n; i ++)
                    b[i] = i % 2;
            else
                for(int i = 1; i <= n; i ++)
                    b[i] = (i + 1) % 2;

            int i = 0, j = 0;
            while(i <= n)
            {
                if(a[i] == 1)
                {
                    while(b[j] != 1) j ++;

                    ans += abs(i - j);
                    j ++;
                }

                i ++;
            }
        }
        else
        {
            for(int i = 1; i <= n; i ++) b[i] = i % 2;

            long long pans = 0;
            int i = 0, j = 0;
            while(i <= n)
            {
                if(a[i] == 1)
                {
                    while(b[j] != 1) j ++;

                    pans += abs(i - j);
                    j ++;
                }

                i ++;
            }
            ans = std:: min(ans, pans);

            for(int i = 1; i <= n; i ++) b[i] = (i + 1) % 2;

            pans = 0;
            i = 0, j = 0;
            while(i <= n)
            {
                if(a[i] == 1)
                {
                    while(b[j] != 1) j ++;

                    pans += abs(i - j);
                    j ++;
                }

                i ++;
            }
            ans = std:: min(ans, pans);
        }

        printf("%d\n", ans);
    }

    return 0;
}

居然还要开long long。。。

D. Take a Guess

题意（交互题）

有一个长度为$n$的整数序列， 这个序列固定但不会给出， 每次你有两个操作

  1. 选择$i \neq j$, 得到$a_i \& a_j$的结果
  2. 选择$i \neq j$, 得到$a_i | a_j$的结果

让你在2 * n次操作之内给出这个序列中第k小的数的值（不是下标）

数据范围

$3 \leq n \leq 10^4$

题解

首先我们可以得到一个很明显的结论

如果$a_i$已知， 那么$a_j = a_i | a_j - a_i + a_i \& a_j$

也就是说我们只要确定出这个序列中的某一个数， 我们就可以通过$2 \times (n - 1)$次操作得到其他的数， 那么我们就想办法得到第一个数就好了

那么我画了个文氏图容斥了一下， 得到

$a_1 = a_1 | a_2 | a_3 - a_2 | a_3 + a_1 \& a_2 + a_1 \& a_3 - a_1 \& a_2 \& a_3$

除了上述的$2 \times (n - 1)$次操作外我们只多了一个$a_2 | a_3$, 就可以解决本题了

AC代码

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
#include <iostream>
#include <cstdio>
#include <algorithm>

int n, k;
int num[10004], cnt;

int main()
{
    std:: cin >> n >> k;

    int a12, a13, o12, o13, o23;
    std:: cout << "and 1 2" << std:: endl;
    std:: cin >> a12;
    std:: cout << "and 1 3" << std:: endl;
    std:: cin >> a13;
    std:: cout << "or 1 2" << std:: endl;
    std:: cin >> o12;
    std:: cout << "or 1 3" << std:: endl;
    std:: cin >> o13;
    std:: cout << "or 2 3" << std:: endl;
    std:: cin >> o23;

    int f, a, o;

    f = (o12 | o13) - o23 + a12 + a13 - (a12 & a13);
    num[++ cnt] = f;
    num[++ cnt] = o12 - f + a12;
    num[++ cnt] = o13 - f + a13;

    for(int i = 4; i <= n; i ++)
    {
        std:: cout << "and 1 " << i << std:: endl;
        std:: cin >> a;
        std:: cout << "or 1 " << i << std:: endl;
        std:: cin >> o;

        num[++ cnt] = o - f + a;
    }

    std:: sort(num + 1, num + n + 1);
    std:: cout << "finish " << num[k] << std:: endl;

    return 0;
}