首页 程序设计 AtCoder

# D

题目和 CC 类似，在主数组内，找最长的 11221122 数组，思路其实都是双指针，但一开始的代码想抽象了

# 错误代码

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
int n, a[N], maxLen = 0;

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    vector<int> v;
    map<int, int> cnt;

    for (int i = 1; i < n; i++) {
        if (a[i] == a[i + 1])
            v.push_back(a[i]), i++;
        else
            v.push_back(0);
    }


    for (int i = 0; i < v.size(); i++)
        if (v[i] != 0) {
            cnt.clear();
            int l = i, r = i;

            while (r < v.size() && v[r] != 0) {
                cnt[v[r]]++;

                while (l < r && cnt[v[r]] == 2)
                    cnt[v[l]]--, l++;

                maxLen = max(maxLen, (r - l + 1) * 2);

                r++;
            }
            i = r - 1;
        }

    cout << maxLen << endl;
}

# 正确双指针代码

注意：题目所要的子串的长度必然是偶数，所以我们找的答案应该是 max(getMax(1), getMax(2)) ，同时从 11 和 22 两个位置找答案

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
int getMax(int idx) {
    memset(cnt, 0, sizeof cnt);
    int l = idx, r = idx, res = 0;
    while (r <= n - 1) {
        if (a[r] != a[r + 1]) {
            while (l < r)
                cnt[a[l]]--, l++;
            r += 2, l += 2;
        }
        else {
            cnt[a[r]] += 2;

            while (cnt[a[r]] > 2)
                cnt[a[l]] -= 2, l += 2;

            r += 2;
        }

        res = max(res, r - 1);
    }

    return res;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cout << max(getMax(1), getMax(2)) << endl;
}

# DP 思路

  • fif_i 存到 ii 为止的最长子序列长度
  • tit_i 存 ii 最后一次出现的位置

动态规划时，两个分别表示：

  1. f[i - 1] + 2 表示从 i−1i-1 这个点到 i+1i + 1 这个点的最长序列长度
  2. i + 1 - t[a[i]] 表示从 i−1i - 1 这个点到 tait_{a_i} 这个点的长度

为了保证序列合法，应该在两者之间取 minmin

1
2
3
4
5
6
7
8
9
10
11
12
void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++) {
        if (a[i] == a[i + 1])
            f[i + 1] = min(f[i - 1] + 2, i + 1 - t[a[i]]);
        t[a[i]] = i;
        ans = max(ans, f[i + 1]);
    }
    cout << ans << endl;
}

# E

题目传送门

# 错误写法

思路和答案类似，都是用的 二分 + 前缀和 来优化处理，但是喜提 AC−8,WA−17,TLE−2\color{green}{AC-8},~\color{red}{WA-17},~\color{brown}{TLE-2} 错误

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
// 在 place 中，找第一个大于等于x的下标
int check(int x) {
    int l = 0, r = place.size() - 1;

    while (l < r) {
        int mid = l + r >> 1;

        if (place[mid] < x)
            l = mid + 1;
        else
            r = mid;
    }

    return l;
}

void solve() {
    cin >> n >> q;
    cin >> s, s = " " + s;

    for (int i = 1; i <= n; i++) {
        int add1 = (s[i] == '1'), add2 = (s[i] == '2');
        pre1[i] = pre1[i - 1] + add1, pre2[i] = pre2[i - 1] + add2;

        if (s[i] == '/')
            place.push_back(i);
    }

    while (q--) {
        int l, r;
        cin >> l >> r;

        int beginIdx = check(l), ans = 1;

        if (place.size() == 0 || place[beginIdx] < l ) {
            cout << 0 << endl;
            continue;
        }

        for (int i = beginIdx; i < place.size() && place[i] <= r; i++) {
            int t = place[i];
            if (t >= 2) {
                int left1 = pre1[t] - pre1[l - 1], right2 = pre2[r] - pre2[t];
                ans = max(ans, max((int)0, min(left1, right2)) * 2 + 1);
            }
        }

        cout << ans << endl;
    }
}

# 正解

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
void solve() {
    cin >> n >> Q >> s;
    s = ' ' + s;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '/')
            a[++m] = i;
        s1[i] = s1[i - 1] + (s[i] == '1');
        s2[i] = s2[i - 1] + (s[i] == '2');
    }
    while (Q--) {
        cin >> L >> R;
        int l = 1, r = m, ans = 0;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (a[mid] < L)
                l = mid + 1;
            else if (a[mid] > R)
                r = mid - 1;
            else {
                int c1 = s1[a[mid]] - s1[L - 1], c2 = s2[R] - s2[a[mid] - 1];
                ans = max(ans, min(c1, c2) * 2 + 1);
                if (c1 <= c2)
                    l = mid + 1;
                else
                    r = mid - 1;
            }
        }
        cout << ans << "\n";
    }
}

更新于 阅读次数 次

请我喝[茶]~(￣▽￣)~*

duoxichangan 微信支付

微信支付

duoxichangan 支付宝

支付宝