Educational Codeforces Round 96

十一月 02, 2020 6960

做题记录

4 分钟 A，9 分钟 B，29 分钟写完 C 但是多测没清空浪费了 5 分钟还白给了两发罚时，D 有思路但是后面一个细节想错了，凭感觉写了一份结果 WA 了两发就放弃了，E 只有初步思路

A. Number of Apartments

解题思路

读了一遍题，发现是数学构造，差点放弃
看到了 1\leq n \leq 1000
好 我直接枚举

代码实现

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
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

int n;

int main() {
    int T = read();
    while (T --> 0) {
        n = read();
        for (int a = 0; a <= n; a += 3) {
            for (int b = 0; a + b <= n; b += 5) {
                int c = n - a - b;
                if (c % 7 == 0) {
                    printf("%d %d %d\n", a / 3, b / 5, c / 7);
                    goto suc;
                }
            }
        }
        puts("-1");
        suc: continue;
    }
    return 0;
}

B. Barrels

解题思路

最大化极差。
那就试试能不能最大化最大值且最小化最小值。

发现一次倒水肯定倒干净最优，因为瓶子容量无限大而且这样最小值可以到达 0。
发现如果倒干净的话，一定是把最多的水聚集到一块最优。

所以答案为前 k 大之和减 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
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 200000 + 10;

int n, k, aa[MAXN];

int main() {
    int T = read();
    while (T --> 0) {
        n = read(); k = read();
        for (int i = 1; i <= n; ++i) {
            aa[i] = read();
        }
        std::sort(aa + 1, aa + 1 + n, std::greater<int>());
        long long int ans = 0;
        for (int i = 1; i <= k + 1; ++i) ans += 1ll * aa[i];
        printf("%lld\n", ans);
    }
    return 0;
}

C. Numbers on Whiteboard

解题思路

经过一阵艰难的手玩（盲猜规律），发现可以每次选最大的两个值消掉，而且这样答案永远为 2

交上去发现 A 了就不管了

代码实现

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
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

int n;
std::priority_queue<int> st;
std::vector<std::pair<int, int> > op;

int main() {
    int T = read();
    while (T --> 0) {
        n = read();
        for (int i = 1; i <= n; ++i) {
            st.push(i);
        }
        for (int i = 1; i <= n - 1; ++i) {
            auto mxn = st.top(); st.pop();
            auto tmxn = st.top(); st.pop();
            st.push((mxn + tmxn + 1) >> 1);
            op.push_back({mxn, tmxn});
        }
        printf("%d\n", st.top());
        while (!st.empty()) st.pop();
        for (auto v : op) {
            printf("%d %d\n", v.first, v.second);
        } op.clear();
    }
    return 0;
}

D. String Deletion

解题思路

下面称呼「块」为「一段连续、字符均相同的子串」。

通过手玩可以发现，似乎每次删最前面一个字符是最优的，因为反正每次第一个块都会被整段删掉，提前给它删一个字符也无所谓，相当于这次操作是白送的。

但是有一个反例：如果第一个块只有一个字符，那么这样一次操作相当于删了两个块而不是一个块，有点浪费。

如何解决？

一个显然的想法是删最后一个块的字符，但是这样也不对，因为如果最后一个块也仅有一个字符的话，一次删除也是两个块，好像没啥用。

那就往前找找，看看前面有没有块长度大于等于 2，有就删它里面的字符，这样一次操作就可以做到只删一个块。

同时可以发现任意一个长度大于等于 2 的块都可以删，效果是一样的。

所以，我们要维护一个数据结构，支持：

  1. 删除第一个整块
  2. 让第一个长度大于等于 2 的块长度减 1

这个东西可以双指针做。维护一个指针指向当前的前缀删到哪个块，另一个指针指向第一个长度大于等于 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
51
52
53
const int MAXN = 2e5 + 10;

struct Node {
    int ind0, siz;
    Node(int id = 0, int sz = 0) : ind0(id), siz(sz) {}
    bool operator < (const Node &th) const {
        return siz == th.siz ? ind0 < th.ind0 : siz < th.siz;
    }
};

int n;
char ss[MAXN];
int siz[MAXN], blk;

int main() {
    int T; scanf("%d", &T);
    while (T --> 0) {
        scanf("%d", &n);
        scanf("%s", ss + 1);
        for (int i = 1; i <= n; ++i) {
            ++blk;
            while (true) {
                ++siz[blk];
                if (ss[i] != ss[i + 1]) break;
                ++i;
            }
        }
        int ans = 0, q = 1; // q 为块指针
        bool only = false; // 仅剩下大小为 1 的块
        for (int i = 1; i <= blk; ++i) {
            // 枚举当前删到了哪个前缀
            if (only) {
                // 只剩大小为 1 的块了，一次操作删两个
                ++ans; ++i; continue;
            }
            if (siz[i] >= 2) {
                // 这个块可以删，直接删了
                ++ans;
            } else {
                while (q < i || (q <= blk && siz[q] < 2)) ++q;
                if (q > blk) {
                    // 只剩下大小为 1 的块了
                    only = true; ++ans; ++i; continue;
                } else {
                    ++ans; --siz[q];
                }
            }
        }
        printf("%d\n", ans);
        memset(siz, 0, sizeof siz); blk = 0;
    }
    return 0;
}

E. String Reversal

解题思路

先给一个经典结论：

将一个序列冒泡排序成升序的调换次数为这个序列的逆序对个数。

挺显然的，具体自己百度

看到调换顺序，一个想法就是给字符串重新定义「升序」，然后按照新的「升序」进行冒泡排序，并按照上面的结论计算答案。

所以我们对这个字符串的每一个字符，找出它在反转后的下标，形成一个新的序列，并对它进行计算答案。

但是有一个问题：有重复的字符怎么办？

通过手玩我们可以知道，最优的情况是，对于第一个重复字符，将它对应到最后一个相同的字符最优，往后以此类推。因为反转过来时，最后一个字符就变成了新的第一个字符，所以最靠后的相同的字符就是反转后的最靠前的相同字符，符合最小化次数的目标。

所以在实现的时候，我们可以分三步走：

  1. 找到每个字符对应字符的位置
  2. 将所有位置反转
  3. 求逆序对数

就做完了。

代码实现

如果代码理解不能的话建议对照手玩。

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
const int MAXN = 200000 + 10;

int n;
char ss[MAXN];
std::vector<int> inds[27];
int reorder[MAXN];

struct BIT {
    int ss[MAXN];
    BIT() { memset(ss, 0, sizeof ss); }
    #define lb(x) ((x) & (-(x)))
    void insert(int s) {
        while (s >= 1) {
            ++ss[s]; s -= lb(s);
        }
    }
    int query(int s) {
        int ret = 0; while (s <= n) {
            ret += ss[s]; s += lb(s);
        } return ret;
    }
} bit;

long long int getInvPairs() {
    long long int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += bit.query(reorder[i]);
        bit.insert(reorder[i]);
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    scanf("%s", ss + 1);
    for (int i = 1; i <= n; ++i) {
        inds[ss[i] - 'a'].push_back(i);
    }
    for (int i = 'a'; i <= 'z'; ++i) {
        for (int j = 0, siz = (int) inds[i - 'a'].size(); j < siz; ++j) {
            reorder[inds[i - 'a'][j]] = inds[i - 'a'][siz - j - 1];
        }
    }
    for (int i = 1; i <= n; ++i) reorder[i] = n - reorder[i] + 1;
    // for (int i = 1; i <= n; ++i) printf("%d%c", reorder[i], " \n"[i == n]);
    printf("%lld\n", getInvPairs());
    return 0;
}