Codeforces Round #1089(Div.2)

上了点分，这场感觉评价不高，好多电波题。

B

题目大意：给定 $n$ 个元素的数组 $a$ ，它是 $1 \sim n$ 的一个排列，现在挨个遍历它，对于当前的 $a_i(1 \leq i \leq n)$ ，如果 $a_i$ 已经被标记了，那么就结束游戏。否则可以选择坐下或者跳过，如果坐下，则会标记 $a_{a_i}$ ，现在问你，最多可以坐下多少次？

数据范围: $1 \leq n \leq 2 \cdot 10^5$

思路：贪心题，按照常理来说应该枚举每个会炸掉的位置，这可以用一个堆来维护，不过这里有个 $O(n)$ 的解法，就是争取将游戏进行到最后，也就是不坐所有会炸掉的椅子，电波题。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


void solve() {
    int n;
    cin >> n;
    vi a(n + 1);
    rep(i, 1, n) cin >> a[i];
    vi b(n + 1);
    rep(i, 1, n) b[a[i]] = i;
    int ans = 0, tem = 0;
    rep(i, 1, n) {
        if (b[i] < i) tem++;
        ans = max(ans, i - tem);
    }
    cout << ans << endl;
    return;
}

C1

题目大意：给定长度为 $n$ 的数组 $a$ 和长度为 $n$ 的数组 $b$，现在可以对 $a$ 的每个下标进行最多一次操作：选取 $1 \leq m \leq b_i$ 且 $m \not ={a_i}$ ，将 $a_i$ 变为 $m$ 。

现在要求变化后的任意子数组的最大公因数都跟原数组相同，问最多能变化多少次？

注意：在简单版本中， $b_i=a_i$

数据范围： $1 \leq a_i \leq 10^9,2 \leq n \leq 2 \cdot 10^5$

思路：赛时五分钟开了，算是弥补了一下B开太慢的差距。

首先，不难注意到如果所有相邻的数最大公因数都相同，那么最后的所有最大公因数都相同，于是贪心地，将一个数转化为它与相邻数的最大公约数的最小公倍数，那么如果能转化，就计数，否则不行。

 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


void solve() {
    int n;
    cin >> n;
    vi a(n);
    vi b(n);
    rep(i, 0, n - 1) cin >> a[i];
    rep(i, 0, n - 1) cin >> b[i];
    vi tem(n);
    auto lcm = [&](ll x, ll y) -> ll {
        ll tem = __gcd(x, y);
        return x / tem * y;
    };
    rep(i, 0, n - 1) {
        if (i == 0) {
            tem[i] = __gcd(a[i], a[i + 1]);
        } else if (i == n - 1) {
            tem[i] = __gcd(a[i], a[i - 1]);
        } else {
            tem[i] = lcm(__gcd(a[i], a[i + 1]), __gcd(a[i], a[i - 1]));
        }
    }
    int ans = 0;
    rep(i, 0, n - 1) {
        if (a[i] != tem[i]) ans++;
    }
    cout << ans << endl;
    return;
}

C2

题目大意：跟上题一样，注意本题不再存在 $b_i=a_i$ 的限制。

数据范围： $2 \leq n \leq 5 \cdot 10^4,1 \leq a_i,b_i \leq 10^9$

思路：先想想这道题跟上道题的区别在哪，首先就是，如果能变成最小的，那么还是变成最小的，随后，之前有一些无法变化的，由于 $b_i$ 变大了，因此可以往上变化，但是仍然需要保持公因数条件。

从而不难想到，往上变化，是怎么个往上变化的法子呢？一个显然的思路就是将C1中求出的数（此时刚好是 $a_i$ ）乘上某个质数，而乘上的这个质数，由于需要保证跟旁边的数没有进一步的公因数，因此在前二十个质数中必然存在（可以通过连乘的方法验证），于是看到这里的状态数少，考虑二维DP即可，时间复杂度 $O(400n)$ 。

 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


vl primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
void solve() {
    int n;
    cin >> n;
    vi a(n);
    vi b(n);
    rep(i, 0, n - 1) cin >> a[i];
    rep(i, 0, n - 1) cin >> b[i];
    vi tem(n);
    auto lcm = [&](ll x, ll y) -> ll {
        ll tem = __gcd(x, y);
        return x / tem * y;
    };
    rep(i, 0, n - 1) {
        if (i == 0) {
            tem[i] = __gcd(a[i], a[i + 1]);
        } else if (i == n - 1) {
            tem[i] = __gcd(a[i], a[i - 1]);
        } else {
            tem[i] = lcm(__gcd(a[i], a[i + 1]), __gcd(a[i], a[i - 1]));
        }
    }
    vvl tem2(n);
    rep(i, 0, n - 1) {
        tem2[i].push_back(a[i]);
        if (tem[i] <= b[i] && tem[i] != a[i]) {
            tem2[i].push_back(tem[i]);
        }
        if (tem[i] == a[i]) {
            for (auto& p : primes) {
                if (1LL * p * tem[i] <= b[i]) {
                    tem2[i].push_back(1LL * p * tem[i]);
                } else
                    break;
            }
        }
        sort(all(tem2[i]));
        tem2[i].erase(unique(all(tem2[i])), tem2[i].end());
    }
    vvi dp(n, vi(26, INT_MIN));
    rep(i, 0, sz(tem2[0]) - 1) dp[0][i] = (tem2[0][i] == a[0] ? 0 : 1);
    rep(i, 1, n - 1) {
        rep(j, 0, sz(tem2[i]) - 1) {
            int tem3 = (tem2[i][j] == a[i] ? 0 : 1);
            rep(k, 0, sz(tem2[i - 1]) - 1) {
                if (__gcd(tem2[i][j], tem2[i - 1][k]) == __gcd(a[i], a[i - 1])) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][k] + tem3);
                }
            }
        }
    }
    int ans = 0;
    rep(i, 0, sz(tem2[n - 1]) - 1) ans = max(ans, dp[n - 1][i]);
    cout << ans << endl;
    return;
}

D

题目大意：给定一个RBS（合法括号序列） $s$ 和一个合法括号序列 $t$ ，每次可以选取 $s$ 的两个不相交RBS并交换位置，问任意次是否能把 $s$ 转化为 $t$ ？

数据范围： $4 \leq n \leq 5 \cdot 10^5$

思路：赛后补的，首先说明，对于这类任意的题目，首先就是需要一个观察，比如找不变量或者一次就行。

这里给了一个新的思路，就是将RBS看做一个树形结构。

考虑(()()())，则外层的()作为父节点，里面并列的三个()都作为它的孩子。对于任意的RBS也是这样，外层父节点，内层兄弟节点。

然后观察样例，将 s 和 t 画出来，不难发现：它们有多个叉的最高节点深度相同，同时叶子数相同。

再考虑题目给出的定义，就是交换 u 跟 v 的连续不相交一段子树，或者交换 u 的两段连续不相交子树。

这里给出一个证明：如果多个叉最高节点的深度不同，那么对于它们上面的节点，由于只有一个叉，因此无法交换，所以始终不能相同；而对于叶子树，由于交换不改变叶子数，显然这是相同的。

然后，最高多叉节点的深度，就是从两侧开始双指针遍历，如果检测两侧没有嵌套的括号树，而叶子就是紧挨的()数。

这种题还是练得比较少，同时这种思路需要注意力，还是要多练。

 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


void solve() {
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    auto cnt_leaves = [&](const string& s) -> int {
        int cnt = 0;
        rep(i, 0, n - 2) {
            if (s[i] == '(' && s[i + 1] == ')') cnt++;
        }
        return cnt;
    };
    auto cnt_matches = [&](const string& s) -> int {
        int cnt = 0;
        vi match(n);
        stack<int> st;
        rep(i, 0, n - 1) {
            if (s[i]=='(') {
                st.push(i);
                continue;
            }
            match[st.top()]=i;
            st.pop();
        }
        int l = 0, r = n - 1;
        while (match[l] == r) {
            l++;
            r--;
            cnt++;
        }
        return cnt;
    };
    if (cnt_leaves(s) == cnt_leaves(t) && cnt_matches(s) == cnt_matches(t))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return;
}