# B

# 题目大意

现在，在一条无限长的数周上， ... -2 -1 0 1 2 ... 上有房子，初始时，$0$ 房子感染病毒，病毒每次会传播一个房子，现在告诉你，$n$ 时刻感染的范围是 [l, r] ，问你，$m$ 时刻可能的感染区间是？

# 数据范围

• $1 \le m \le n \le 2000$

# 题解

只考虑先向一边传播，传播到 $l$ 后若还不够 $m$ 天，则从 $0$ 向 $r$ 传播

1
2
3
4
5
6
7
8

void solve() {
    cin >> n >> m >> l >> r;
    
    if (m <= abs(l))
        cout << -m << " 0\n";
    else
        cout << l << " " << m - abs(l) << endl;
}

# D

# 题目大意

现在奇妙的世界里有两个鼓，敲左边会发出 L 或 LL 的声音，敲右边会发出 R 或者 RR 的声音，现在给你敲鼓的顺序字符串 $p$ 和一串声音 $s$，问 $s$ 是否可能是字符串 $p$ 敲击的结果？

# 数据范围

• $1 \le |p| \le |s| \le 2 \times 10^5$

# 题解

我们只需要对于每个字符串，计算出一个这样的 vector<pair<char, int>> v 即可

• v[i].first 用来记录连续的符号
• v[i].second 用来记录连续的长度

首先，要满足题目要求得两个 vp.size() == vs.size() ，满足后，对于第 $i$ 个，需满足

• 符号相等
• $p$ 锤的次数不超过 $s$ 响的次数；$s$ 响的次数不超过两倍的 $p$ 锤的次数

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

void fill(string&s, vector<pair<char, int>>& v) {
    for (int i = 0; i < s.size(); i++) {
        int j = i;
        while (j < s.size() && s[i] == s[j])
            j++;
        v.push_back({s[i], j - i});
        i = j - 1;
    }
}

void solve () {
    string p, s;
    cin >> p >> s;
    vector<pair<char, int>> vp, vs;
    fill(p, vp), fill(s, vs);

    if (vp.size() != vs.size()) {
        cout << "NO" << endl;
        return;
    }

    for (int i = 0; i < vp.size(); i++) {
        if (vp[i].first != vs[i].first
            || vp[i].second > vs[i].second || vp[i].second * 2 < vs[i].second) {
            cout << "NO" << endl;
            return;
        }
    }

    cout << "YES" << endl;
}

# E

# 题目大意

给你一个 $n$ 个整数的序列 $A=(a_1, ..., a_n)$
请输出 $\max{(\sum\limits_{i=1}^{n}(a_k}$ ^ $a_i))$

# 数据范围

• $1 \le n \le 2 \times 10^5,0 \le {a_i} {<} {2^{30}}$

# 题解

对与异或而言，只有不同的会有贡献

那么我们可以用一个 $cnt$ 数组预处理好每一位的 $1$ 的个数，再扫一遍 $a_1 \to a_n$
对于每一个扫到的 $a_i$，令其为 $a_k$，然后计算结果即可

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

void solve () {
    cin >> n;
    vector<int> a(n), cnt(33);
    for (auto& k : a) {
        cin >> k;
        int t = k;

        for (int i = 0 ; i < 32; i++) {
            cnt[i] += (t & 1);
            t >>= 1;
        }
    }

    int res = 0;
    
    for (int j = 0; j < a.size(); j++) {
        int t = a[j], tmp = 0;
        for (int i = 0; i < 32; i++) {
            if (t & 1)
                tmp += (n - cnt[i]) * (1 << i);
            else
                tmp += cnt[i] * (1 << i);

            t >>= 1;
        }

        res = max(res, tmp);
    }

    cout << res << endl;
}

# F

# 题目大意

给你整数 $n,m,k$，其中 $k \ge 2, n\cdot m\equiv 0 \pmod{k}$
你要构造一个 $n \times m$ 的矩阵，要求满足

• 每个数都是 $[1,k]$
• $[1,k]$ 每个数出现次数相同
• 任意两个相邻的数，不相等

# 数据范围

• $2 \le n \times m \le 2 \times 10^5$
• $2 \le k \le n \times m$

# 题解

• 如果 m % k != 0 ，那么可以按一排一排顺序，$1 \to k$ 不断往下排
• 如果 n % k != 0 ，那么可以按一列一列顺序，$1 \to k$ 不断往下排
• 如果 n % k == 0 && m % k == 0 ，那么可以按每行分别是重复 $1, 2, ..., k \to 2, 3, ..., k, 1 \to 3, 4, ..., k, 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

  void solve(){ int n, m, k, cnt = 1; cin >> n >> m >> k; vector<vector<int>> ans(n, vector<int>(m)); if (m % k != 0) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cout << cnt++ << " "; if (cnt > k) cnt = 1; } cout << endl; } } else if (n % k != 0) { for (int i = 0; i < n * m; i++) { ans[i % n][i / n] = cnt++; if (cnt > k) cnt = 1; } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) cout << ans[i][j] << " "; cout << endl; } } else { for (int i = 1; i <= n; i++) { int cnt = i % k == 0 ? k : i % k; for (int j = 1; j <= m; j++) { cout << cnt++ << " "; if (cnt > k) cnt = 1; } cout << endl; } } }

# G

# 题目大意

对于一个长为 $m$ 的数组 $b$，定义酷炫值为 $\sum\limits_{i=1}^{m}{b_i \times i}$
你现在有一个空数组，你可以进行以下三种操作

1. 对数组进行循环移位：$[a_1, ..., a_n] \to [a_n,a_1 ..., a_{n-1}]$
2. 反转整个数组：$[a_1, a_2,...,a_{n-1}, a_n] \to [a_n, a_{n-1}, ..., a_2, a_1]$
3. 在数组末尾添加一个元素

你需要执行 $Q$ 次操作，每次操作后，需要输出当前数组的炫酷值

# 数据范围

• $1 \le Q \le 2 \times 10^5$

# 题解

维护这几个变量

• $sum=\sum\limits_{i=1}^{n}a_i$
• $cool$ - 代表酷炫值

三个操作对应的值的变化如下

1. 循环移位，$cool$ 从 $1 * a_1 + 2 * a_2 + ... + (n-1)*a_{n-1} + n * a_n$ 变化为 1*a_n+2*a_1+3*a_2+...+n*a_
   • 可以发现 $cool = cool + sum - a_n + (n-1)a_n$
2. 逆转整个数组，$cool$ 从 $1 * a_1 + 2 * a_2 + .. + n * a_n$ 变化为 $1 * a_n + 2 * a_{n-1} + ... + n * a_1 = \sum\limits_{i=1}^{n}$
   • 可以发现 $cool = (n+1) * \sum\limits_{i=1}^n{a_i} - cool$
3. 添加一个数
   • 这个操作比较容易，$cool = cool + n * a_n$

题目本身其实还挺容易的，但重点是时间复杂度的考量
一开始我用的双端队列，实现操作 2. 用的 $reverse$，但它的复杂度是 $O(n)$，故不应该用 $reverse$
应该考虑采用一个 $flag$ 标记，分别标记当前是哪一头为正方向

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

void solve() {
    int q;
    cin >> q;
    
    deque<int> dq;
    int sum = 0, cool = 0;
    bool flag = false;
    
    while (q--) {
        int op;
        cin >> op;
        
        if (op == 3) {
            int k;
            cin >> k, sum += k;

            if (!flag)
                dq.push_back(k), cool += k * dq.size();
            else
                dq.push_front(k), cool += k * dq.size();
        }
        else if (op == 1) {
            int t = 0;
            if (!flag)
                t = dq.back(), dq.pop_back(), dq.push_front(t);    
            else
                t = dq.front(), dq.pop_front(), dq.push_back(t);
            cool += (sum - t) - (dq.size() - 1) * t;
        }
        else if (op == 2) {
            flag = !flag;
            cool = (dq.size() + 1) * sum - cool;
        }
        
        cout << cool << endl;
    }
}