完成情况说明:

  • \color{red} \Delta 表示没做完。
  • \color{orange}1 表示并非独自做出所有题。
  • \color{cyan} 2 表示独自做出所有题。
  • \color{green} 3 表示现场 AK 了。
场次 完成情况 备注
abc150 \color{cyan} 2 F 写的多个 \log,正解还没写。
abc151 \color{orange} 1 F 是最小圆覆盖模板题,但我不会
abc152 \color{cyan} 2 Trival
abc153
abc154
abc155
abc156
abc157
abc158
abc159
abc160
abc161
abc162
abc163
abc164
abc165
abc166
abc167
abc168
abc169
abc170
abc171 \color{orange} 1 赛后会的 F
abc172 \color{orange}1 E, F 都是很有意思的题
abc173 \color{orange}1 不会 D 的结论,F 倒是自己做的
abc174 \color{cyan} 2 F 是小 Z 的袜子
abc175 \color{orange}1 F 问了 SJX,D 的 O(n) 还没写
abc176
abc177
abc178 \color{orange} 1 赛时竟然不会 C,不会构造 F
abc179 \color{cyan} 2 较为简单
abc180
abc181
abc182 \color{orange}1 F 问了 SJX
abc183 \color{cyan}2 赛时没做出来 F,赛后就会了
abc184 \color{orange}1 赛时 F TLE 了,赛后看了眼题解才会的
abc185
abc186
abc187
abc188
abc189
abc190

abc150

E Change A Little Bit

abc150E

给出长度为 N 的序列 C

定义两个不同的,长度均为 n01 序列 A, B 的权值 f(A, B) 为进行以下操作的最小代价和,使得 A = B

  • 对于 i \in [1, n],若 A_i \neq B_i,则可花 D \times C_i 的代价 flip A_i。其中 D 表示在操作前有多少个 j 满足 A_j \neq B_j

易知共有 2^N \times (2^{N} - 1) 个不同的有序对 A, B。计算所有对的权值和。

N \leq 2\times 10^5


考虑一对 A, B,操作使得相同的最小代价显然是贪心地操作。具体而言:

把所有不同位按 C 升序排序。优先翻转更小的 C 更优。

把每位的贡献拆出来,令 S_i 表示 C 中有多少个数比 C_i 大。特别的,对于相等的数我们按照某种方式调整使得 \nexists i, j 满足 S_i = S_j

那么第 x 位的贡献就是:

C_x \times 4^{n - S_x - 1}\times 2^{S_x + 1} \times \sum_{i = 0}^{S_x} \binom{S_x}{i} \times (i + 1)

意义:比 C_x 小的数不会影响结果,所以先拿到外面。然后枚举有多少个比 S_x 里的位有多少个不同。拿组合数选一下然后乘一下方案。

后面的 i + 1 有点烦,把 1 拿掉,变成:

C_x \times 4^{n - S_x - 1}\times 2^{S_x + 1} \times [ (\sum_{i = 0}^{S_x} \binom{S_x}{i} \times i) + 2^{S_x}]

考虑咋算 \displaystyle \sum_{i = 0}^{S_x} \binom{S_x}{i} \times i

打开

\begin{aligned} \sum_{i = 0}^{S_x} \binom{S_x}{i} \times i &= \sum_{i = 0}^{S_x} \dfrac{S_x!}{i!(S_x - i)!} \times i \\ &= \sum_{i = 0}^{S_x} \dfrac{S_x!}{(i - 1)!(S_x - i)!} \\ &= S_x \sum_{i = 0}^{S_x} \dfrac{(S_x - 1)!}{(i - 1)!(S_x - i)!} \\ &= S_x \sum_{i = 0}^{S_x} \binom{S_x - 1}{i - 1} \\ &= S_x\times 2^{S_x - 1} \end{aligned}

所以最后的答案是

\sum_{x = 1}^n C_x \times 4^{n - S_x - 1}\times 2^{S_x + 1} \times 2^{S_x - 1} \times (S_x + 2) \\ =

特别的,当 S_x = 0 时,括号里应该是 1

时间复杂度 O(n)

然而继续化简下去,会得到

\sum_{x = 1}^n C_x \times 4^{n - 1}\times(S_x + 2)

别问我最后的式子的组合意义是啥

const int MAXN = 2e5 + 10;
const int P = 1e9 + 7;

int n, c[MAXN], s[MAXN], pow4[MAXN];
pair<int, int> tmp[MAXN];

int qpower(int a, int x) {
    int ret = 1;
    for (; x; x >>= 1, a = 1ll * a * a % P) x & 1 ? ret = 1ll * ret * a % P : 0;
    return ret;
}

int main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
    #endif
    IO::read(n); rep(i, 1, n) IO::read(c[i]), tmp[i] = make_pair(c[i], i);
    sort(tmp + 1, tmp + n + 1), reverse(tmp + 1, tmp + n + 1); int cnt = 0;
    rep(i, 1, n) s[tmp[i].second] = cnt++;
    int pow4 = qpower(4, n - 1), ans = 0;
    rep(i, 1, n) (ans += 1ll * c[i] * pow4 % P * (s[i] + 2) % P) %= P;
    IO::write(ans, '\n');
    return 0;
}

F Xor Shift

给出序列 a, b,求有多少对 k, x,满足将 a 循环左移 k 位得到 a' 后,a'_i \oplus x = b_i

|a| , |b| \leq 2 \times 10^5, a_i < 2^{31}


这是个非正解。

容易知道对于一个 k,最多只有一个 x。而 a_{1 + k} \oplus x = b_1。所以可以 O(1) 得到 x,接下来考虑该如何检验这个 x

即,快速判断序列异或上某个值是否等于另一个序列。

考虑对于二进制下每一位都 hash 出。相当于现有 31 个长度为 n01 序列。

因为是循环位移,直接把 a 倍长一份,然后预处理出每一位的 hash 值和把这为上所有值取反后的 hash 值。

对于得到的 x 就看 x 这一位是 1 还是啥,然后逐位检查。

时间复杂度 O(n \log n),有 2\times 4 的常数,分别来自倍长和 4 模数 hash。得卡卡常。

const int MAXN = 2e5 + 10;
const int P[4] = { 19260817, 19491001, 1000000000 + 7, 1000000000 + 9 }, inv2[4] = { 9630409, 9745501, 500000004, 500000005 };

int n, a[MAXN << 1], b[MAXN << 1], inv2pow[4][MAXN << 1], pow2[4][MAXN << 1];

struct HashVal {
    int val[4];
    int& operator [](const int& x) { return val[x]; }
    HashVal() { val[0] = val[1] = val[2] = val[3] = 0; }
    void add(int x, HashVal& pre, int& id) {
        #define work(__) val[__] = (pre[__] + pow2[__][id - 1] * x) % P[__]
        work(0), work(1), work(2), work(3);
        #undef work
    }
    inline bool operator ==(HashVal& _) const { return (val[0] == _[0] && val[1] == _[1] && val[2] == _[2] & val[3] == _[3]); }
};

struct HashValArray {
    HashVal val[MAXN << 1];
    void add(int x, int& id) {
        val[id].add(x, val[id - 1], id);
    }
    HashVal get(int l, int r) {
        HashVal ret;
        HashVal L = val[l - 1], R = val[r];
        #define work(__) ret[__] = 1ll * ((R[__] - L[__]) % P[__] + P[__]) % P[__] * inv2pow[__][l - 1] % P[__]
        work(0), work(1), work(2), work(3);
        #undef work
        return ret;
    }
} hashA[2][31], hashB[31];

#define BIT(S, _) (((S) >> (_)) & 1)

int main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
    #endif
    IO::read(n);
    rep(_, 0, 3) {
        inv2pow[_][0] = 1, pow2[_][0] = 1;
        rep(i, 1, n + n) inv2pow[_][i] = 1ll * inv2pow[_][i - 1] * inv2[_] % P[_], pow2[_][i] = 1ll * pow2[_][i - 1] * 2 % P[_];
    }
    rep(i, 1, n) IO::read(a[i]); rep(i, 1, n) IO::read(b[i]);
    rep(i, 1, n) a[i + n] = a[i], b[i + n] = b[i];
    rep(bit, 0, 30) {
        rep(i, 1, n + n) {
            hashA[0][bit].add(BIT(a[i], bit), i);
            hashA[1][bit].add(BIT(a[i], bit) ^ 1, i);
            hashB[bit].add(BIT(b[i], bit), i);
        }
    }
    rep(k, 0, n - 1) {
        int val = b[1] ^ a[k + 1];
        bool flg = true;
        rep(bit, 0, 30) {
            HashVal tmp1 = hashA[BIT(val, bit)][bit].get(k + 1, k + n), tmp2 = hashB[bit].get(1, n);
            flg &= tmp1 == tmp2;
            if (!flg) break;
        }
        if (flg) IO::write(k, ' '), IO::write(val, '\n');
    }
    return 0;
}

正解感觉非常 untrival。

由于 a' = b,那么 a'_{i + 1} \oplus a'_i = b_{i + 1} \oplus b_i,即 a_{i + 1} \oplus a_i = b_{i + 1} \oplus b_i。那么只需要处理出序列 A_i = a_{i + 1} \oplus a_iB_i = b_{i + 1} \oplus b_i。然后用 KMP 在倍长后的 B 序列求 A 的出现次数就好。关于 x 值,可以 O(1) 求出。

abc175

D Moving Piece Editorial

给出常数 k,有 n 个点,每个点有一条唯一的出边 nxt_i,保证 nxt 为一个 1 \cdots n 的排列。每个点有一个权值 v_i

你可以任意选一个点作为出发点,并进行以下步骤不超过 k 次(不能不进行):

  • 从当前点走到当前点的出点。并且你将得到当前点的权值的分数。

求最多能得到多少分数。


容易看出问题等价与,给出一个环,你能走不超过 k 步,求最大的和。

破环为链,一个显然的 dp,令 f_i 表示以 i 为终点最大的和。

有:

f_i = \max_{j \in [i - len, i)} sum_i - sum_j + \big\lfloor \dfrac{k - (i - j)}{L}\big\rfloor \times \max(0, S)

其中,sum 代表前缀和,S 是整个环的和,L 是环长。

直接暴力搞是 O(n^2) 的,这题数据范围比较小,能过。

typedef long long ll;

const int MAXN = 1e6 + 10;

int n, k, nxt[MAXN], len[MAXN];
ll val[MAXN], sum[MAXN << 1], f[MAXN << 1], arr[MAXN << 1], fans = -LONG_LONG_MAX;

bool vis[MAXN];

int m;

void work(int st) {
    m = 0;
    int cur = nxt[st];
    while (1) {
        arr[++m] = val[cur], vis[cur] = true;
        if (cur == st) break;
        cur = nxt[cur];
    }
    rep(i, 1, m) arr[++m] = arr[i];
    rep(i, 1, m) sum[i] = sum[i - 1] + arr[i];
    int mxlen = min(m >> 1, k);
    ll mxval = -LONG_LONG_MAX; int mxval_len = 0;
    rep(i, 1, m) {
        f[i] = -LONG_LONG_MAX;
        rep(j, max(i - mxlen, 0), i - 1) {
            f[i] = max(sum[i] - sum[j] + 1ll * max(sum[m >> 1], 0ll) * ((k - i + j) / (m >> 1)), f[i]);
        }
        mxval = max(f[i], mxval);
    }
    fans = max(fans, mxval);
}

int main() {
    IO::read(n), IO::read(k);
    rep(i, 1, n) IO::read(nxt[i]);
    rep(i, 1, n) IO::read(val[i]);
    rep(i, 1, n) if (!vis[i]) {
        work(i);
    }
    printf("%lld\n", fans);
    return 0;
}

考虑优化,最后一项的 \big\lfloor \dfrac{k - (i - j)}{L}\big\rfloor,取值只有可能有两种:\big\lfloor \dfrac{k}{L} \big\rfloor 以及 \big\lfloor \dfrac{k}{L} \big \rfloor - 1

取得 \big\lfloor \dfrac{k}{L} \big\rfloor 的一对 (i, j),必有 i - j \leq k \bmod L。因此,这一段可以把后面一项去掉,前面一项就可以直接单调队列。

取得后面一项的则没有任何限制,因此,也可以单调队列。

代码待补。

E Picking Goods

给出一个 R \times C 的网格,网格上有 k 个格子上有分数。

你从 (1, 1) 出发,每次向下或右走,最终走到 (R, C)。每次走到一个有分数的点可以选择是否拿走分数。每一行至多拿走三个格子的分数。

求最多一共能拿走多少分数。


直接 dp,f(i, j, 0/1/2/3) 表示走到 (i, j) 拿了 0/1/2/3 个格子最大分数。

时间复杂度 O(n^2)

int main() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= k; ++i) {
        int x, y, _val; scanf("%d %d %d", &x, &y, &_val);
        val[x][y] = _val;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            for (int pre = 0; pre <= 3; ++pre) f[0][i][j] = max(f[0][i][j], f[pre][i - 1][j]), f[1][i][j] = max(f[1][i][j], f[pre][i - 1][j] + val[i][j]);
            f[0][i][j] = max(f[0][i][j], f[0][i][j - 1]);
            for (int cnt = 1; cnt <= 3; ++cnt) {
                f[cnt][i][j] = max(f[cnt][i][j], max(f[cnt][i][j - 1], f[cnt - 1][i][j - 1] + val[i][j]));
            }
        }
    }
    ll ans = 0;
    for (int cnt = 0; cnt <= 3; ++cnt) ans = max(ans, f[cnt][n][m]);
    printf("%lld\n", ans);
    return 0;
}

F Making Palindrome

N 个字符串 S_i,你需要选择若干个字符串,满足将其按照某种顺序拼接后,是一个回文串。一个字符串可以选择多次。每个字符串都有一个代价。

求最小代价和。

|S_i| \leq 20N \leq 50


考虑在左右依次交替放一个串。如果一个字符在右侧有匹配的字符,则将这个字符删去。这样每次都只会在一边剩下一些字符。状态可以由 (0/1, S) 描述,表示现在在 左/右 剩下字符串 S

因为我们是在左右交替放,所以剩下的字符一定是 N 个字符串中某个字符串的 前/后 缀。因此,至多只有 2000 种剩下的后缀。共 4000 个节点。

考虑直接 dij,每次枚举出边,分类讨论一下即可。

时间复杂度 O(M \log M)M \leq 2000

typedef long long ll;

const int MAXN = 2000 + 10;

template <typename T>
bool chkmin(T& a, T b) { if (a > b) return a = b, true; return false; }
template <typename T>
bool chkmax(T& a, T b) { if (a < b) return a = b, true; return false; }

int n;
string str[MAXN], id_to_str[MAXN];
bool is_palindrome[MAXN];
unordered_map<string, int> str_to_id;
ll val[MAXN], ans = LONG_LONG_MAX, dis[2][MAXN], vis[2][MAXN];

typedef pair<int, int> Node;
typedef pair<ll, Node> plii;

priority_queue<plii, vector<plii>, greater<plii> > que;

bool starts_with(string& a, string& b) {
    if (a.size() < b.size()) return false;
    rep(i, 0, b.size() - 1) if (a[i] != b[i]) return false;
    return true;
}

Node trans(int flg, string u, string v) {
    Node ret; ret.first = 0, ret.second = 0;
    string res;
    if (flg == 0) reverse(v.begin(), v.end());
    else reverse(u.begin(), u.end());
    if (flg == 0 && starts_with(u, v) || flg == 1 && starts_with(v, u)) {
        ret.first = 0;
        if (flg == 1) res = v.substr(u.size(), v.size() - u.size() + 1);
        else res = u.substr(v.size(), u.size() - v.size() + 1);
    } else if (flg == 0 && starts_with(v, u) || flg == 1 && starts_with(u, v)) {
        ret.first = 1;
        if (flg == 0) res = v.substr(u.size(), v.size() - u.size() + 1);
        else res = u.substr(v.size(), u.size() - v.size() + 1);
        reverse(res.begin(), res.end());
    } else {
        ret.first = -1;
        return ret;
    }
    ret.second = str_to_id[res];
    return ret;
}

int main() {
    IO::read(n);
    str_to_id[""] = 0;
    rep(i, 1, n) {
        cin >> str[i]; IO::read(val[i]);
        string cur; cur.clear();
        rep(j, 0, str[i].size() - 1) {
            cur.push_back(str[i][j]);
            if (!str_to_id.count(cur)) {
                int _sz = str_to_id.size();
                str_to_id[cur] = _sz;
            }
        }
        cur.clear();
        per(j, str[i].size() - 1, 0) {
            cur = str[i][j] + cur;
            if (!str_to_id.count(cur)) {
                int _sz = str_to_id.size();
                str_to_id[cur] = _sz;
            }
        }
    }
    for (auto _cur : str_to_id) {
        string cur = _cur.first;
        string ruc = cur;
        id_to_str[_cur.second] = cur;
        reverse(ruc.begin(), ruc.end());
        is_palindrome[_cur.second] = (cur == ruc);
    }
    rep(i, 0, str_to_id.size()) dis[0][i] = dis[1][i] = LONG_LONG_MAX;
    rep(i, 1, n) {
        if (is_palindrome[str_to_id[str[i]]]) ans = min(ans, val[i]);
        chkmin(dis[0][str_to_id[str[i]]], val[i]);
        chkmin(dis[1][str_to_id[str[i]]], val[i]);
        que.push(m_p(val[i], m_p(0, str_to_id[str[i]])));
        que.push(m_p(val[i], m_p(1, str_to_id[str[i]])));
    }
    while (!que.empty()) {
        plii u = que.top(); que.pop();
        if (vis[u.second.first][u.second.second]) continue;
        vis[u.second.first][u.second.second] = true;
        rep(i, 1, n) {
            Node v = trans(u.second.first, id_to_str[u.second.second], str[i]);
            if (v.first == -1) continue;
            if (chkmin(dis[v.first][v.second], dis[u.second.first][u.second.second] + val[i])) {
                que.push(m_p(dis[v.first][v.second], v));
            }
        }
    }
    rep(i, 0, str_to_id.size()) {
        if (is_palindrome[i]) chkmin(ans, min(dis[0][i], dis[1][i]));
    }
    if (ans >= (LONG_LONG_MAX >> 1)) { puts("-1"); return 0; }
    printf("%lld\n", ans);
    return 0;
}

abc174

grade

D Alter Altar

给出一个长度为 n 的由 RW 构成的字符串 Sn \leq 200000)。每次可以任选以下操作进行一次:

  • 将某两个字符 swap
  • 将某个字符取反(由 R 变成 W,反之亦然)

最少进行多少次操作,使得最后的序列不存在 i \in [1, n),满足 S[i] == 'W' && S[i + 1] == 'R'


最终的字符串一定是形如:

\text{RRR}\cdots \text{RWWW}\cdots \text{W}

猜了个结论,一定存在一个次数最小的操作,满足没有用到第二种操作。

所以最终的串是固定的,O(n) 扫一遍就好了。

不知道为啥这是对的,下午去问问 Juanzhang。

const int MAXN = 200000 + 10;

int n, arr[MAXN], cnt1, ans;
char str[MAXN];

int main() {
    IO::read(n);
    scanf("%s", str + 1);
    rep(i, 1, n) arr[i] = (str[i] == 'R');
    rep(i, 1, n) cnt1 += arr[i];
    rep(i, 1, cnt1) ans += !arr[i];
    printf("%d\n", ans);
    return 0;
}

E Logs

你有长为 n 的序列 A。可以进行以下操作不超过 k 次:

  • 选择序列中的元素 A_i,规定一个 t \in (0, A_i),删除 A_i 并加入 tA_i - t

求操作后,最大元素最小值。


直接二分答案 x,可以发现把一个长度为 L 的元素操作成合法的若干个元素至少需要 \big\lfloor \dfrac{L - 1}{x} \big\rfloor 次操作。

typedef long long ll;

const int MAXN = 2e5 + 10;

int n, k, arr[MAXN];

bool check(int x) {
    ll cnt = 0;
    rep(i, 1, n) cnt += (arr[i] - 1) / x;
    return cnt <= k;
}

int main() {
    IO::read(n), IO::read(k);
    rep(i, 1, n) IO::read(arr[i]);
    int l = 1, r = *max_element(arr + 1, arr + n + 1), ans;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    printf("%d\n", ans);
    return 0;
}

F Range Set Query

静态数区间颜色个数。

n \leq 5 \times 10^5


经典问题。

考虑一段区间内的某个颜色的所有元素构成的集合,只会有一个元素有贡献。

所以我们就钦定最靠右的那个元素有贡献。打上标记。

发现每加入一个元素,只会至多有两个位置被修改。所以可以维护一个可持久化数组,求个区间和就行。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5 + 10;
const int MAX_NODE_CNT = MAXN << 6;

int n, m, lst[MAXN];

struct Persistent_Segment_Tree {
    #define mid ((l + r) >> 1)
    #define ls(_) t[_].ls
    #define rs(_) t[_].rs
    #define lq(_) t[_].ls, l, mid
    #define rq(_) t[_].rs, mid + 1, r
    int node_cnt, rt[MAXN];
    int& operator [](const int& x) { return rt[x]; }
    struct node { int ls, rs, data; } t[MAX_NODE_CNT]; 
    int build(int l, int r) {
        int cur = ++node_cnt;
        if (l == r) return cur;
        ls(cur) = build(l, mid), rs(cur) = build(mid + 1, r);
        return cur;
    }
    int modify(int pre, int l, int r, int pos, int val) {
        int cur = ++node_cnt; t[cur] = t[pre], t[cur].data += val;
        if (l == r) { return cur; }
        if (pos <= mid) ls(cur) = modify(ls(pre), l, mid, pos, val);
        else rs(cur) = modify(rs(pre), mid + 1, r, pos, val);
        return cur;
    }
    int query(int cur, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return t[cur].data;
        int ret = 0;
        if (ql <= mid) ret += query(lq(cur), ql, qr);
        if (qr > mid) ret += query(rq(cur), ql, qr);
        return ret; 
    } 
} t;

int main() {
    scanf("%d %d", &n, &m);
    t[0] = t.build(1, n);
    for (int i = 1, x; i <= n; ++i) {
        scanf("%d", &x); t[i] = t.modify(t[i - 1], 1, n, i, 1);
        if (lst[x]) t[i] = t.modify(t[i], 1, n, lst[x], -1);
        lst[x] = i;
    }
    int pre_ans = 0;
    for (int i = 1, u, v; i <= m; ++i) {
        scanf("%d %d", &u, &v);
        printf("%d\n", (t.query(t[v], 1, n, u, v)));
    }
    return 0;
}

abc178

grade

C Ubiquity

统计长度为 n 的数列的个数,满足:

  • a_i \in [0, 9]
  • \exist i, \ a_i = 0
  • \exist i, \ a_i = 9

容斥,全部的减去没有 9 的减去没有 0 的加上没有 0, 9 的。

ll qpower(int a, int x) {
    ll ret = 1;
    for (; x; x >>= 1, a = 1ll * a * a % P) x & 1 ? ret = 1ll * ret * a % P : 0;
    return ret;
}

int main() {
    IO::read(n);
    printf("%lld\n", ((qpower(10, n) - 2 * qpower(9, n) % P + qpower(8, n)) % P + P) % P);
    return 0;
}

感觉自己对这种容斥还不太熟悉(

E Dist Max

给出 n 个点,求任意点对曼哈顿距离最大值。

n \leq 2 \times 10^5


x 递增加入,这样保证第一维可以拆开。

第二维相当于是求一个前后缀最大值。

BIT 维护即可。

int main() {
    IO::read(n);
    rep(i, 1, n) IO::read(arr[i].first), IO::read(arr[i].second), tmp[i] = arr[i].second;
    sort(arr + 1, arr + n + 1), sort(tmp + 1, tmp + n + 1);
    int _n = unique(tmp + 1, tmp + n + 1) - tmp - 1;
    rep(i, 1, n) num[i] = lower_bound(tmp + 1, tmp + _n + 1, arr[i].second) - tmp;
    rep(i, 1, n) {
        if (i > 1) ans = max(ans, arr[i].first + max(arr[i].second + bit1.query(num[i]), bit2.rquery(num[i]) - arr[i].second));
        bit1.add(num[i], -(arr[i].first + arr[i].second)), bit2.radd(num[i], -arr[i].first + arr[i].second);
    }
    bit1.clear(), bit2.clear();
    per(i, n, 1) {
        if (i < n) ans = max(ans, -arr[i].first + max(arr[i].second + bit1.query(num[i]), bit2.rquery(num[i]) - arr[i].second));
        bit1.add(num[i], -(-arr[i].first + arr[i].second)), bit2.radd(num[i], arr[i].first + arr[i].second);
    }
    printf("%lld\n", ans);
    return 0;
}

然而可以 O(n)

void solve() {
  int n = read();
  int mx1 = -1e18, mx2 = -1e18, mn1 = 1e18, mn2 = 1e18;
  rep(i, 1, n) {
    int x = read(), y = read();
    chkmax(mx1, x + y), chkmin(mn1, x + y);
    chkmax(mx2, x - y), chkmin(mn2, x - y);
  }
  int ans = max(mx1 - mn1, mx2 - mn2);
  cout << ans << endl;
}

(source:Juanzhang)

F Contrast

给出两个不降的序列 A, B,重排 B,使得 \nexists i, A_i = B_i

n \leq 2\times 10^5


构造 1:

考虑 reverse(B)。这样之后至多会有一个区间的 BA 相同,并且这个区间的值都一样。然后从左右找能够替换的就行。

int main() {
    IO::read(n);
    rep(_, 0, 1) rep(i, 1, n) IO::read(arr[_][i]), cnt[_][arr[_][i]]++;
    reverse(arr[1] + 1, arr[1] + n + 1);
    rep(i, 1, n) if (arr[0][i] == arr[1][i]) val = arr[0][i], pos.push_back(i);
    int l = 1, r = n; bool flg = false;
    for (auto cur_pos : pos) {
        if (flg == false) {
            if (arr[0][l] != val && arr[1][l] != val) {
                swap(arr[1][l], arr[1][cur_pos]);
                ++l;
            } else flg = true;
        }
        if (flg == true) {
            if (arr[0][r] != val && arr[1][r] != val) {
                swap(arr[1][r], arr[1][cur_pos]);
                --r;
            } else return puts("No"), 0;
        }
    }
    puts("Yes");
    rep(i, 1, n) printf("%d ", arr[1][i]);
    return 0;
}

构造 2:

B shift 一段距离可以合法。(不太清楚为什么这是必要的)。

对于每个值,shift 的合法距离是一段区间,把这些区间并起来就好。

int main() {
    IO::read(n);
    ansr = INT_MAX;
    rep(_, 0, 1) rep(i, 1, n) IO::read(arr[_][i]);
    rep(_, 0, 1) rep(i, 1, n) {
        if (arr[_][i] != arr[_][i - 1]) l[_][arr[_][i]] = i;
        if (arr[_][i] != arr[_][i + 1]) r[_][arr[_][i]] = i;
    }
    rep(i, 1, n) {
        if (l[0][i] && l[1][i]) {
            ansl = max(ansl, r[0][i] - l[1][i] + 1);
            // ansr = min(ansr, abs(l[0][i] - r[1][i]));
            ansr = min(ansr, l[0][i] - r[1][i] + n - 1);
        }
    }
    // printf("l = %d, r = %d\n", ansl, ansr);
    if (ansl > ansr) return puts("No"), 0;
    puts("Yes");
    rep(i, 1, n) {
        ans[(i + ansl - 1) % n + 1] = arr[1][i];
    }
    rep(i, 1, n) printf("%d ", ans[i]);
    return 0;
}

abc173

D Chat in a Circle \color{red}\times

n 个人,每个人有一个权值,现在按某种顺序插入到一个环上。对于插入的第 i 个人(i > 1),随意安排他插入的位置,并且将获得与他相邻的两个位置的人的权值的最小值的分数。求最多分数。

n \leq 2\times 10^5


看起来应该是按权值降序地插入,然后每次贪心。

证明如下:

假设有 x, y, a, b,满足 x > y > a > b

如果是按照权值降序插入,则是:

(x, y) \rightarrow (x, a, y) \rightarrow (x, b, a, y)\ \text{or}\ (x, a, b, y)

贡献是 \min(x, y) + a

如果先插入了 b,则是:

(x, y) \rightarrow (x, b, y) \rightarrow (x, b, a, y)\ \text{or}\ (x, a, b, y)

贡献是 \min(x, y) + b

显然第一种更优。

确定插入顺序之后考虑插入位置。如果每次都贪心插入到分数最大的地方,可以获得最大分数。因为不存在一个比他更大的方案,因为每个数都最多贡献两次。

时间复杂度 O(n)

int main() {
    IO::read(n);
    rep(i, 1, n) IO::read(arr[i]);
    sort(arr + 1, arr + n + 1), reverse(arr + 1, arr + n + 1);
    ans += arr[1];
    int cnt = 1, i = 2;
    while (cnt <= n - 1) {
        if (cnt == n - 1) break;
        ans += 1ll * min(2, n - 1 - cnt) * arr[i];
        i++, cnt += min(2, n - 1 - cnt);
    }
    printf("%lld\n", ans);
    return 0;
}

E Multiplication 4 \color{red}\times

给出 n 个数(可能为负数),取 k 个数,使得乘积最大。

n \leq 2 \times 10^5


每次要么取最小的两个数,要么取最大的。

贪心就行。

int main() {
    IO::read(n), IO::read(k);
    rep(i, 1, n) IO::read(arr[i]);
    sort(arr + 1, arr + n + 1);
    if (k & 1 && arr[n] < 0) {
        per(i, n, n - k + 1) ans = 1ll * ans * arr[i] % P;
        printf("%lld\n", (ans + P) % P);
        return 0;
    }
    int l = 1, r = n, tot = 0;
    if (k & 1) ans = arr[n] % P, r--, tot++;
    while (l <= r && tot <= k) {
        if (tot == k) break;
        ll numl = arr[l] * arr[l + 1];
        ll numr = arr[r] * arr[r - 1];
        if (numl > numr) ans = 1ll * numl % P * ans % P, l += 2, tot += 2;
        else ans = 1ll * numr % P * ans % P, r -= 2, tot += 2;
    }
    printf("%lld\n", (ans % P + P) % P);
    return 0;
}

F Intervals on Tree \color{green} \sqrt{}

给出一棵树,函数 f(i, j) 代表,下标在 [i, j] 之间的点的生成子图的连通块个数。

\sum_{l = 1}^n \sum_{r = l}^n f(l, r)

n \leq 2 \times 10^5


树上 V 个点 E 条边的子图的连通块个数为 V - E

就能直接算了。

int main() {
    IO::read(n);
    rep(i, 1, n) ans += 1ll * (n - i + 2) * (n - i + 1) / 2;
    rep(i, 1, n - 1) {
        int a, b;
        IO::read(a), IO::read(b);
        if (a > b) swap(a, b);
        ans -= 1ll * a * (n - b + 1);
    }
    printf("%lld\n", ans);
    return 0;
}

abc171

F Strivore

给出一个小写拉丁字符串 S。一次操作被定义为:

  • 在当前串的某个位置(可以为开头或结尾)插入一个小写字符。

问一共有多少个可以以 S 为初始串,经过 K 次操作得到。

998244353 取模。


问题等价与问有多少个串,满足长度为 |S| + K,且 S 为其子序列。

考虑一个显然的 DP。状态由 (i, j) 描述,表示现在填了 i 位,并且匹配 S 到了 j。则:

f(i, j) = \sum_{c = a}^\text{z} f(i - 1, j - [S(j) = c])

即:

f(i, j) = 25 \times f(i - 1, j) + f(i - 1, j - 1)

因此我们发现,答案是与 S 无关的

上式可以联想到杨辉三角。

事实上考虑当 S 全部由 \text{a} 组成时,答案即为求大小为 |S| + K 的包含至少 |S|a 的字符串个数。

枚举恰有多少个 a 即可。

const int MAXN = 1e7 + 10;
const int P = 1e9 + 7;

int prod[MAXN], inv[MAXN], k, s;
char str[MAXN];

int Combine(int n, int m) { return 1ll * prod[n] * inv[n - m] % P * inv[m] % P; }

int qpower(int a, int x) {
    int res = 1;
    for (; x; x >>= 1, a = 1ll * a * a % P) x & 1 ? res = 1ll * res * a % P : 0;
    return res;
}

void add(int& a, int b) { a = a + b > P ? a + b - P : a + b; }

int main() {
    prod[0] = 1;
    rep(i, 1, MAXN) prod[i] = 1ll * prod[i - 1] * i % P;
    inv[0] = inv[1] = 1;
    rep(i, 2, MAXN) inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
    rep(i, 2, MAXN) inv[i] = 1ll * inv[i] * inv[i - 1] % P;
    IO::read(k);
    scanf("%s", str + 1);
    s = strlen(str + 1);
    int ans = 0;
    rep(i, s, k + s) {
        // printf("%d\n", Combine(k + s, i));
        add(ans, 1ll * Combine(k + s, i) * qpower(25, k + s - i) % P);
    }
    printf("%d\n", ans);
    return 0;
}

实际上也可以从数学的角度由

f(i, j) = 25 \times f(i - 1, j) + f(i - 1, j - 1)

推导出

f(i, j) = \binom{i}{j} \times 25^{i - j}

数学归纳一下可以证明。

不过也能由打表看出其规律,大概和 25 的次幂有关。并且指数从左到右递减。

abl

E Replace Digits

维护一个十进制数。操作设计将某一位到某一位上的所有数字改为 x,并输出其 \bmod\ 998244353 的值。

位数 \leq 2 \times 10^5


可以直接对位建线段树。


const int MAXN = 2e5 + 10;
const int P = 998244353;

int n, q, _pow10[MAXN], inv[MAXN];

int getsum(int k) {
    return 1ll * ((_pow10[k] - 1) % P + P) % P * inv[9] % P;
}

struct Segment_Tree {
    #define mid ((l + r) >> 1)
    #define ls k << 1, l, mid
    #define rs k << 1 | 1, mid + 1, r
    struct Node { int val, tag; } t[MAXN << 2];
    void pushup(int k) { t[k].val = (t[k << 1].val + t[k << 1 | 1].val) % P; }
    void pushdown(int k, int l, int r) {
        if (t[k].tag != -1) {
            t[k << 1].tag = t[k].tag, t[k << 1 | 1].tag = t[k].tag;
            t[k << 1].val = 1ll * t[k].tag * getsum(mid - l + 1) % P * _pow10[n - mid] % P;
            t[k << 1 | 1].val = 1ll * t[k].tag * getsum(r - mid) % P * _pow10[n - r] % P;
            t[k].tag = -1;
        }
    }
    void build(int k, int l, int r) {
        t[k].tag = -1;
        if (l == r) return t[k].val = _pow10[n - r], void();
        build(ls), build(rs);
        pushup(k);
    }
    void modify(int k, int l, int r, int ql, int qr, int val) {
        if (ql <= l && r <= qr) {
            t[k].tag = val;
            t[k].val = 1ll * val * getsum(r - l + 1) % P * _pow10[n - r] % P;
            return ;
        }
        pushdown(k, l, r);
        if (ql <= mid) modify(ls, ql, qr, val);
        if (qr > mid) modify(rs, ql, qr, val);
        pushup(k);
    }
} sgt;

int main() {
    _pow10[0] = 1;
    inv[0] = inv[1] = 1;
    rep(i, 2, MAXN - 1) inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
    rep(i, 1, MAXN - 1) _pow10[i] = 1ll * _pow10[i - 1] * 10 % P;
    IO::read(n), IO::read(q);
    sgt.build(1, 1, n);
    rep(i, 1, q) {
        int l, r, val;
        IO::read(l), IO::read(r), IO::read(val);
        sgt.modify(1, 1, n, l, r, val);
        printf("%d\n", sgt.t[1].val);
    }
    return 0;
}

F Heights and Pairs

给出 2n 个数,求将这 2n 个数分成 n 对,使得 \forall (a, b),满足 a \neq b 的方案数。

n \leq 5\times10^4, a_i \leq 10^5


SJX 大爷给我讲了讲。尽管我不会 NTT,但还是记录一下咋做吧(

\text{cnt}(i) 代表 i 这个数出现的次数。

考虑 f(i, j) 代表值域为 [1, i],钦定有 j 个数对相等。

那么

f(i, j) = \sum_{k = 0}^{\lfloor\frac{\text{cnt}(i)}{2}\rfloor} \binom{\text{cnt}(i)}{2k} \times \binom{2k}{k} \times k! \times f(i - 1, j - k)

g(i, k) 记为前面的系数,则

f(i, j) = \sum_{k = 0}^{\lfloor\frac{\text{cnt}(i)}{2}\rfloor} g(i, k)\times f(i - 1, j - k)

记答案多项式

F = \sum_{i = 1}^n f(10^5, i) \times x^i

G_n = \sum_{i = 1}^n g(n, i) \times x^i

F = \prod_{i = 1}^{10^5} G_n

利用分治 NTT 解决即可。

abc182

F Valid Payments

n 种硬币,第 i 个的面值为 c_i,保证 \forall i \in[1, n), c_i | c_{i + 1}

给出 X,问有多少个 y \geq X,满足在用最少硬币个数表示 y - X 的方案与用少硬币个数表示 y 的方案中,不存在一种硬币都被用到了。

n \leq 50, c_i \leq 10^{15}


因为整除的性质,最少硬币表示的方案一定是贪心地选。那么我们就可以转换为一个变进制下的问题,考虑计算有多少个 a = y - Xa + X 在变进制下没有一位同时和 a 大于 0

那么 f(i, 0/1) 表示从最低位填到了 i 位,并且 a + Xi 位是否发生了进位。

转移仅有两种:a 这一位填 0,或依靠进位 a + X 这一位填 0

int main() {
    IO::read(n); IO::read(x);
    a[0] = 1;
    rep(i, 1, n) IO::read(a[i]), A[i - 1] = (a[i] / a[i - 1]) - 1;
    A[n] = LONG_LONG_MAX;
    ll x_copy = x;
    per(i, n, 1) {
        if (!x_copy) break;
        if (x_copy >= a[i]) X[i] = x_copy / a[i], x_copy %= a[i];
    }
    f[0][0] = 1;
    rep(i, 0, n - 1) {
        rep(carry, 0, 1) {
            ll& slf = f[i][carry];
            ll nxt = X[i + 1] + carry; bool carry_tag = false;
            if (nxt > A[i + 1]) carry_tag = true;
            f[i + 1][carry_tag] += slf;
            nxt = A[i + 1] + 1 - carry - X[i + 1];
            if (nxt > 0 && nxt <= A[i + 1]) f[i + 1][true] += slf;
        }
    }
    IO::write(f[n][false], '\n');
    return 0;
}

abc183

F Confluence

维护一个并查集,每个元素有个特征值 c_i。操作设计合并,求某个集合里有多少个特征值为 k 的元素。

n, q, c_i \leq 2\times 10^5


感觉场上有点亏,没有仔细想。

考完之后就感觉可以分块,将集合分为大小大于 \geq \sqrt{n}< \sqrt{n} 的集合。

对于大集合,考虑直接用一个数组直接维护答案,对于小集合,暴力 dfs 求答案。

容易知道回答询问是 O(n \sqrt{n}) 的。

对于合并,启发式的分为三类:

  • 小集合小集合合并:
    • 若合并后 sz 大于 \sqrt{n}。花 O(n) 的时间处理一下答案。这样的合并次数最多 2\sqrt{n} 次。
    • 否则直接连边。记得路径压缩。这样是 O(1) 的。
  • 小集合合并到大集合:花 O(\text{size}) 的时间遍历小集合(bfs 或 dfs 一下)并处理答案。此类合总的复杂度不会超过 O(n)(考虑每个点的贡献即可证明)。
  • 大集合大集合合并:花 O(n) 的时间遍历一遍。合并次数最多 \sqrt{n} - 1 次。

所以总的复杂度是 O(n \sqrt n) 的。不知道为啥跑得飞快,目前进了首页。

细节很多,例如第二类合并的单次复杂度不能和 n 有关,只能和 \text{size} 有关,不然会 T 飞...

const int MAXN = 2e5 + 10, T = 350;

int n, q, c[MAXN], ans[MAXN / T + 10][MAXN], bcnt, max_c;

struct Node {
    int fa, sz, idx, col; vector<int> son;
    Node () { sz = 1; }
} dsu[MAXN];

int gf(int x) { return dsu[x].fa == x ? x : dsu[x].fa = gf(dsu[x].fa); }

int sans;
int que[MAXN], lpos, rpos;
void bfs(int u, const int& cc) {
    lpos = rpos = 0;
    que[rpos++] = u;
    while (lpos < rpos) {
        if (dsu[que[lpos]].col == cc) sans++;
        for (int v : dsu[que[lpos]].son) que[rpos++] = v;
        ++lpos;
    }
}
inline void query_s(const int& u, const int& c) {
    sans = 0;
    bfs(u, c);
    IO::write(sans, '\n');
}
inline void query_b(const int& x, const int& y) {
    IO::write(ans[dsu[x].idx][y], '\n');
}
inline void query(int x, int y) {
    if (dsu[x].idx == 0) query_s(x, y);
    else query_b(x, y);
}

int tmp[MAXN];
int trash_queue[MAXN], tl;

void bfs(int u) {
    lpos = rpos = 0;
    que[rpos++] = u;
    while (lpos < rpos) {
        tmp[ dsu[que[lpos]].col ]++, trash_queue[++tl] = dsu[que[lpos]].col;
        for (int v : dsu[que[lpos]].son) que[rpos++] = v;
        ++lpos;
    }
}

inline void merge_ss(const int& x, const int& y) {
    if (dsu[x].sz + dsu[y].sz >= T) {
        dsu[x].idx = ++bcnt;
        tl = 0, bfs(x);
        rep(i, 1, max_c) ans[bcnt][i] = tmp[i];
        rep(i, 1, tl) tmp[trash_queue[i]] = 0;
        tl = 0, bfs(y);
        rep(i, 1, max_c) ans[bcnt][i] += tmp[i];
        rep(i, 1, tl) tmp[trash_queue[i]] = 0;
    }
    dsu[x].sz += dsu[y].sz, dsu[y].fa = x, dsu[x].son.push_back(y);
}
inline void merge_bs(const int& x, const int& y) {
    tl = 0, bfs(y); register int bnum = dsu[x].idx;
    rep(i, 1, tl) ans[bnum][trash_queue[i]]++;
    rep(i, 1, tl) tmp[trash_queue[i]] = 0;
    dsu[x].sz += dsu[y].sz, dsu[y].fa = x, dsu[x].son.push_back(y);
}
inline void merge_bb(const int& x, const int& y) {
    register int bnumx = dsu[x].idx, bnumy = dsu[y].idx;
    rep(i, 1, max_c) ans[bnumx][i] += ans[bnumy][i];
    dsu[x].sz += dsu[y].sz, dsu[y].fa = x, dsu[x].son.push_back(y);
}
inline void merge(int x, int y) { // please ensure that x and y is the root
    if (x == y) return ;
    if (dsu[x].sz < dsu[y].sz) swap(x, y);
    if (dsu[x].idx == 0 && dsu[y].idx == 0) merge_ss(x, y);
    else if (dsu[x].idx && dsu[y].idx == 0) merge_bs(x, y);
    else if (dsu[x].idx && dsu[y].idx) merge_bb(x, y);
}

int main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
    #endif
    IO::read(n), IO::read(q);
    rep(i, 1, n) IO::read(c[i]), dsu[i].fa = i, dsu[i].col = c[i];
    max_c = *max_element(c + 1, c + n + 1);
    rep(i, 1, q) {
        int opt, x, y, fx, fy; IO::read(opt), IO::read(x), IO::read(y);
        if (opt == 1)
            fx = gf(x), fy = gf(y), merge(fx, fy);
        else query(gf(x), y);
    }
    return 0;
}

写完之后看了一下别人的代码,发现自己弱智了,维护答案可以对所有集合(不论大小)开一个 map 存答案,空间是 O(n \log n) 的。不需要分类。

但是这样跑得没我快

一件趣事:翻代码的时候看到一位老哥也没写 map,但是跑得比我还快(可惜我实在没看懂他在写啥),他的代码里有如下注释:

www

翻译一下大概就是:没想到用 map,我可以退役了。

巧了我也是。

国庆 Day1 模拟赛赛后题解与总结
上一篇 «
莫比乌斯函数的应用与莫比乌斯反演
» 下一篇