Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

ARC136

发表于 分类于
本文字数： 11k 阅读时长 ≈ 10 分钟
标签：            

ARC136

A - A ↔ BB

可以发现，直接将 $BB$ 换成 $A$ 显然更优，将 $A$ 换成 $BB$ 当且仅当 $BA - BBB - AB$ ，一直贪心取即可。

查看代码 
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
#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
int n;
string s;
int main()
{
    cin >> n >> s;
    int t;
    do
    {
        t = s.size();
        for (int i = 0; i + 1 < s.size(); i++)
            if (s[i] == 'B' && s[i + 1] == 'B')
                s.replace(i--, 2, "A");
        for (int i = 0; i + 1 < s.size(); i++)
            if (s[i] == 'B' && s[i + 1] == 'A')
                swap(s[i], s[i + 1]);
    } while (s.size() < t);
    cout << s;
    return 0;
}

B - Triple Shift

一种贪心是对于 $B$ 中的每一个数，在当前位置后 $A$ 中找到该数，并将其按照规则跳到前面来。如果有解，那么一定可以完成至剩下最后两个，此时，如果两个数不一样，说明两个序列不是同一个多重集，显然无解。

接下来手玩发现了一个性质，如果前面有两个数中的一个，一定存在一种方案可以将两个数顺序交换。

  • $AAB - ABA$ ，$AaAB - ABaA - aABA$ ，$AabAB - abAAB - abABA - AabBA$ ，以此类推，前面在 $x$ 位置的 $A$ 可以通过每次 $x = x + 2$ 的的方式移动到最后的 $A$ 前后，然后实现 $AAB - ABA$ ，再将 $A$ 移动到前面，并保证其他数不变；
  • $BAB - BBA$ ，如果是前面有两个数终中的后者，也是同理，相当于前者的逆变换。

如果只这样判断就会发现会 WA 一个点。

考虑下面的 Hack

1
2
3 3 4 1 2
3 3 4 2 1

显然如果将整个序列倒着做一遍，剩下的两个数一定是相同的。很多错误的 AC 代码都会被这个 Hack。

为了保险，将序列倒着做一次。

查看代码 
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
#include <cstdio>
#include <algorithm>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 5e3 + 10;
int n, A[N], B[N], tA[N], tB[N];
bool check()
{
    for (int i = 1; i + 2 <= n; i++)
    {
        int t = 0;
        for (int j = i; j <= n && !t; j++)
            A[j] == B[i] && (t = j);
        if (!t)
            return false;
        while (t >= i + 2)
        {
            int tmp = A[t];
            A[t] = A[t - 1];
            A[t - 1] = A[t - 2];
            A[t - 2] = tmp;
            t -= 2;
        }
        if (A[i] == B[i])
            continue;
        else if (A[i + 1] == B[i])
        {
            int tmp = A[i];
            A[i] = A[i + 1];
            A[i + 1] = A[i + 2];
            A[i + 2] = tmp;
        }
    }
    if (A[n - 1] == B[n - 1] && A[n] == B[n])
        return true;
    if (A[n] != B[n - 1] || A[n - 1] != B[n])
        return false;
    for (int i = 1; i < n - 1; i++)
        if (A[i] == B[n - 1] || A[i] == B[n])
            return true;
    return false;
}
int main()
{
    read(n);
    for (int i = 1; i <= n; i++)
        read(A[i]), tA[i] = A[i];
    for (int i = 1; i <= n; i++)
        read(B[i]), tB[i] = B[i];
    bool flag = check();
    for (int i = 1; i <= n; i++)
    {
        A[i] = tA[i];
        B[i] = tB[i];
    }
    reverse(A + 1, A + n + 1);
    reverse(B + 1, B + n + 1);
    flag |= check();
    puts(flag ? "Yes" : "No");
    return 0;
}

正解的思路是这样的：

首先如果两个序列不是同一个多重集一定无解。

假设现在所有的数不一样，对于任意的一次交换：$ABC - BCA$ 将第一个数移动到最后一个，如果 $A$ 是最小的，那么移动后逆序对数增加两个；如果 $A$ 是最大的，那么逆序对数减少 $2$ 个；否则，那么逆序对数不变。显然，一次操作不会影响到 $A$ 的逆序对数的奇偶性。我们将前 $n - 2$ 个数转到正确的位置上后，如果当前两个数不同，那么一定是逆序对数不同；否则，逆序对数一定相同。现在考虑如果存在相同的数，现在强行规定相同的数的顺序，那么对整个序列的逆序对数的影响一定是在这些相同的数的内部，我们可以任意调整两个数的顺序来改变整个序列的逆序对数的奇偶性。

综上，答案为 YES 当且仅当两个序列构成同一个多重集，且逆序对数的奇偶性相同或存在若干个相同的数。

这样可以将数据加强为 $O(n \log n)$​ 。

查看代码 
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
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 1e6 + 10;
bool vis[N], tr[N];
int n, A[N], B[N];
void modify(int x)
{
    for (; x <= n; x += x & -x)
        tr[x] ^= 1;
}
bool query(int x)
{
    bool res = 0;
    for (; x; x -= x & -x)
        res ^= tr[x];
    return res;
}
bool inversion(int *w)
{
    for (int i = 1; i <= n; i++)
        tr[i] = 0;
    bool res = 0;
    for (int i = n; i; i--)
    {
        res ^= query(w[i]);
        modify(w[i]);
    }
    return res;
}
int main()
{
    int T;
    read(T);
    while (T--)
    {
        read(n);
        for (int i = 1; i <= n; i++)
            read(A[i]);
        for (int i = 1; i <= n; i++)
            read(B[i]);
        if (multiset<int>(A + 1, A + n + 1) != multiset<int>(B + 1, B + n + 1))
        {
            puts("No");
            continue;
        }
        vector<int> ws;
        for (int i = 1; i <= n; i++)
            ws.push_back(A[i]);
        sort(ws.begin(), ws.end());
        ws.erase(unique(ws.begin(), ws.end()), ws.end());
        for (int i = 1; i <= n; i++)
        {
            A[i] = lower_bound(ws.begin(), ws.end(), A[i]) - ws.begin() + 1;
            B[i] = lower_bound(ws.begin(), ws.end(), B[i]) - ws.begin() + 1;
        }
        for (int i = 1; i <= n; i++)
            vis[i] = false;
        bool flag = false;
        for (int i = 1; i <= n; i++)
            if (vis[A[i]])
            {
                puts("Yes");
                flag = true;
                break;
            }
            else
                vis[A[i]] = true;
        if (!flag)
            puts(inversion(A) ^ inversion(B) ? "No" : "Yes");
    }
    return 0;
}

C - Circular Addition

按照套路，需要差分，环上做差分，此时所有数的和为 $0$ ，序列操作可以被转化为一个数 $+1$ ，一个数 $-1$ ，最后将所有的数变为 $0$ ，感觉没有问题。

一个 Hack

1
2
3
1 5 2

事实上，序列上可以这样做，但是环上就有问题了。因为没有第一个个数的信息，可能确实差分数组为 $0$ 了，但是对应的原数组并不为 $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
#include <cstdio>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
typedef long long LL;
const int N = 2e5 + 10;
int n, w[N];
int abs(int x)
{
    return x > 0 ? x : -x;
}
int main()
{
    read(n);
    for (int i = 0; i < n; i++)
        read(w[i]);
    LL res = 0;
    for (int i = 0; i < n; i++)
        res += abs(w[i] - w[(i + 1) % n]);
    res >>= 1;
    for (int i = 0; i < n; i++)
        w[i] > res && (res = w[i]);
    write(res);
    return 0;
}

D - Without Carry

题意即有多少个数对，使得两两加法不进位。可以将问题转化为偏序问题，将所有的 $x$ 放入集合，对于所有的 $999999 - x$ ，求有多少个数小于它。可以用树状数组做。

查看代码 
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
#include <cstdio>
#include <vector>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 1e6 + 10, M = 11;
int n, A[N], tr[M][M][M][M][M][M];
void add(int a, int b, int c, int d, int e, int f)
{
    a++, b++, c++, d++, e++, f++;
    int tmpa = a, tmpb = b, tmpc = c, tmpd = d, tmpe = e, tmpf = f;
    for (a = tmpa; a <= 10; a += (a & -a))
        for (b = tmpb; b <= 10; b += (b & -b))
            for (c = tmpc; c <= 10; c += (c & -c))
                for (d = tmpd; d <= 10; d += (d & -d))
                    for (e = tmpe; e <= 10; e += (e & -e))
                        for (f = tmpf; f <= 10; f += (f & -f))
                            tr[a][b][c][d][e][f]++;
}
int query(int a, int b, int c, int d, int e, int f)
{
    a++, b++, c++, d++, e++, f++;
    int tmpa = a, tmpb = b, tmpc = c, tmpd = d, tmpe = e, tmpf = f;
    int res = 0;
    for (a = tmpa; a; a ^= (a & -a))
        for (b = tmpb; b; b ^= (b & -b))
            for (c = tmpc; c; c ^= (c & -c))
                for (d = tmpd; d; d ^= (d & -d))
                    for (e = tmpe; e; e ^= (e & -e))
                        for (f = tmpf; f; f ^= (f & -f))
                            res += tr[a][b][c][d][e][f];
    return res;
}
vector<int> get(int x)
{
    vector<int> v;
    v.resize(6);
    for (int j = 0; j < 6; j++)
    {
        v[j] = x % 10;
        x /= 10;
    }
    return v;
}
int main()
{
    read(n);
    for (int i = 1; i <= n; i++)
    {
        read(A[i]);
        vector<int> v = get(A[i]);
        add(v[0], v[1], v[2], v[3], v[4], v[5]);
    }
    long long res = 0;
    for (int i = 1; i <= n; i++)
    {
        A[i] = 999999 - A[i];
        vector<int> v = get(A[i]);
        res += query(v[0], v[1], v[2], v[3], v[4], v[5]);
        bool flag = 1;
        for (int x : v)
        {
            flag &= (x >= 5);
        }
        res -= flag;
    }
    write(res >> 1);
    return 0;
}
相关文章