题目整体难度

难度	题目编号
Easy	A
Easy Medium	D,K
Medium	F,G,I,J
Hard	B,E
Very Hard	C,H

以下将从简单到难解析这些题目

A. 线段

对于一个向量为 $(x,y)$ 的线段来说，它的一个垂线段向量为 $(y,-x)$ ，所以输出 $0,0,y_2-y_1,-(x_2-x_1)$ 即可，时间复杂度 $O(t)$ ，空间复杂度 $O(1)$ 。

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

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int x = x2 - x1, y = y2 - y1;
        cout << 0 << ' ' << 0 << ' ' << y << ' ' << -x << '\n';
    }
}

D. 防御

这题是一个树上dp 题目，但是做这题之前，你需要先了解 https://codeforces.com/blog/entry/100910 这个链接中的第七个 trick。

观察代价的值范围比较大，所以根据当且保护的值设置状态，令 $dp[u][v]$ 代表在节点 $u$ 为根的子树中保护 $v$ 的价值的东西花费最小的代价是多少。

此时需要分两种情况讨论，令 $sz[u]$ 为以 $u$ 为根的子树的价值和，那么此时有两种转移：

dp[u][sz[u]]=min(dp[u][sz[u]],w[u])\ 相当于选取了节点\ u\\ dp[u][j]=min(dp[u][j],dp[u][i]+dp[v][j-i])\ 相当于不选节点\ u\ 的同时对于当且节点做背包

初始的观察发现这个转移时 $O(n(\sum v)^2)$ 级别的，但是根据链接中提到的 trick 可以把这个 dp 的转移优化到 $O((\sum v)^2)$ 数量级的，最终时间复杂度 $O(n\sum v+(\sum v)^2)$ 。

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

const int int_inf = 1e9 + 100;

void solve() {
    int n, c;
    cin >> n >> c;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++) cin >> v[i];
    vector<int> w(n + 1);
    for (int i = 1; i <= n; i++) cin >> w[i];
    vector<vector<int>> e(n + 1);
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y), e[y].push_back(x);
    }
    vector<int> szv(n + 1);
    vector<vector<int>> dp(n + 1);
    // https://codeforces.com/blog/entry/100910 总时间复杂度是平方看第7条
    auto dfs = [&](auto&& self, int u, int x) -> void {
        for (auto s : e[u]) {
            if (s == x)
                continue;
            self(self, s, u);
            szv[u] += szv[s];
        }
        szv[u] += v[u];
        dp[u].resize(szv[u] + 1, int_inf);
        dp[u][0] = 0, dp[u][szv[u]] = w[u];
        int sz = 0;
        for (auto s : e[u]) {
            if (s == x)
                continue;
            for (int i = sz; i >= 0; i--) {
                for (int j = 0; j <= szv[s]; j++) {
                    dp[u][i + j] = min(dp[u][i + j], dp[u][i] + dp[s][j]);
                }
            }
            sz += szv[s];
        }
    };
    dfs(dfs, 1, 0);
    int ans = 0;
    for (int i = 0; i <= szv[1]; i++)
        if (dp[1][i] <= c)
            ans = i;
    cout << szv[1] - ans << '\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
}

K. GCD of Set

容易证明最优情况下，除了一个较大的集合 $A$ 外，其他集合都只有一个数。

考虑枚举集合 $A$ 的 $\gcd$ 。

集合 $A$ 的 $\gcd=t$ 时，只有在 $U$ 中被 $t$ 整除的数的个数 $\ge n-k+1$ 时才合法，选择其中最小的 $n-k+1$ 个数选入集合A，更新答案。

结论的证明：

假设最优的情况下有两个子集的大小 $\ge 2$ ，记为 $A= \left \{ a_1,a_2,...,a_m \right \} (a_1>a_2>...>a_m)$ ， $B= \left \{ b_1,b_2,...,b_k \right \} (b_1>b_2>..>b_k)$

不妨设 $\gcd(A) \ge \gcd(B)$ 。

设 $A’= \left \{a1 \right \}$ ， $B’= \left \{a_2,...,a_m,b_1,b_2,...,b_k \right \}$ ，因为 $\gcd(A’)=a_1 \ge 2*\gcd(a_1,a_2,...,a_m)=2*\gcd(A)$ , 所以 $\gcd(A’)+\gcd(B’)>\gcd(A’) \ge 2*\gcd(A) \ge \gcd(A)+\gcd(B)$ 。

也就是说，重新调整集合的划分后，答案更优，矛盾。

时间复杂度 $O(n+\max(a)\log(\max(a)))$ 。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve();
int main() {
    ios::sync_with_stdio(false);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}
const int N = 1e6 + 5, A = 1e6 + 5;
int n, k, maxa = 0;
int a[N];
int c[A];
void solve() {
    ll ans = 0, s = 0;
    maxa = 0;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        maxa = max(maxa, a[i]);
        s += a[i];
    }
    for (int i = 1; i <= maxa; i++) c[i] = 0;
    for (int i = 1; i <= n; i++) c[a[i]]++;
    for (int g = 1; g <= maxa; g++) {
        ll sum = 0, cnt = 0;
        for (int i = g; i <= maxa; i += g) {
            if (c[i])
                sum += i, cnt++;
            if (cnt >= n - k + 1)
                break;
        }
        if (cnt == n - k + 1) {
            ans = max(ans, s - sum + g);
        }
    }
    cout << ans << endl;
}

从以下的题目开始，我都会给出关于题目的一些提示，来给大家提供一些如何思考题目的提示。

F. 机惨

提示 $1$ ：复制次数最大是多少。

复制的次数最多为 $\lceil \log(k)\rceil$ 次，因为复制之后如果不粘贴，这次复制就是没有意义的，所以文本的长度每次至少会翻倍。

提示 $2$ ：当固定复制次数后，采取什么样的粘贴策略可以使得粘贴操作花费的代价最小。

在一次复制之后如果要粘贴 $n$ 次相当于使得文本的长度变成当且文本长度的 $(n+1)$ 倍，所以假如有 $x$ 次复制操作，设每次复制之间粘贴 $p$ 次，那么就是求在 $p_1\times p_2 \dots \times p_x \ge k$ 的情况下使得 $p_1+p_2\dots +p_x$ 的值最小，根据不等式知识，显然是这些 $p_i$ 的值接近或相同时总和最小。

所以这题只需要枚举复制操作的次数，求出在每种复制次数的情况下粘贴代价的最小值相加即可，时间复杂度 $O(t\log(k)\log(k))$ 。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll ll_inf = 1e18 + 100;
const long double eps = 1e-8;
ll t, seed, mod, w, k;

ll rnd() {
    seed = (1ll * seed * 7 + 13) % mod;
    return seed;
}

void solve() {
    cin >> seed >> mod >> w >> k;
    ll sm = 0, ans = ll_inf;
    for (int i = 1; i <= 32; i++) {
        sm += rnd();
        ll cur = powl(k, 1.0 / i) + 1 - eps;
        ll nowk = 1, cost = sm + (cur - 1) * i * w;
        for (int j = 1; j <= i; j++) nowk *= cur;
        for (int j = 1; j <= i; j++) {
            nowk /= cur, nowk *= cur - 1;
            if (nowk < k)
                break;
            cost -= w;
        }
        ans = min(ans, cost);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> t;
    while (t--) solve();
}

G. 宝石碰撞

提示 $1$ ：考虑 $n\ge 4$ 的情况。

$n≥4$ 的时候，一定存在操作方法使得数组中所有数都变为任意非空集合的异或。

证明如下：

假设集合中包含的数是 $a_1\dots a_k$ ，i按升序排列，那么一个显然的观察是操作 $(1,2),(1,3),\dots,(1,k)$ 就可以使得 $1$ 到 $k$ 之间的所有数全变为 $a_1\oplus a_2\dots \oplus a_k$ 。考虑需要获得的集合包含 $a_1$ 和 $a_n$ 的情况。如果集合同时包含a1和an则直接按上述操作做即可，如果缺少任意一个都需要想办法把不需要的那个通过一些操作消掉下面通过具体的构造方式证明可行。

无端点且有至少两个中间点：用 $1$ $3$ 分别表示两个端点的数，中间两个 $2$ 表示先提前把集合中除端点外的数先合并后的区间的左右端点。

1\ 2\ 2\ 3\\ 12\ 12\ 2\ 3\\ 12\ 1\ 1\ 3\\ 12\ 1\ 13\ 13\\ 12\ 3\ 3\ 13\\ 12\ 1\ 1\ 1\\ 2\ 2\ 2\ 2\\

无端点且只有一个中间点：假设这个中间点是 $2$

1\ 2\ 3\ 4\\ 1\ 2\ 34\ 34\\ 1\ 2\ 0\ 0\\ 1\ 2\ 2\ 0\\

转化为至少两个中间点的情况

只有一个端点：中间两个 $2$ 表示先操作 $(2,n-1)$ 后的位置 $2$ 和位置 $n-1$ 。

1\ 2\ 2\ 3\\ 12\ 12\ 2\ 3\\ 12\ 123\ 123\ 123\\ 3\ 3\ 3\ 3\\

一个端点加一个或多个中间：中间一个 $2$ 表示将集合中除端点外的所有点事先合并后形成的区间中的任意位置。

1\ 2\ 3\\ 12\ 12\ 3\\ 12\ 123\ 123\\ 3\ 3\ 123\\ 12\ 12\ 12\\

注意到构造中一些步骤会将两个 $2$ 分开，因此 $n＜4$ 不能做到构造任意集合。

可以通过打表所有情况或爆搜解决 $n≤3$ 的情况，而对于 $n\ge 4$ 的情况，答案就是所以数字的异或最大值，这个可以通过线性基求得。

时间复杂度 $O(t+n\times\log(a))$ 。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct LIB {
    ll p[100]{ 0 }, d[100]{ 0 }, cnt, top, zero = 1;
    void ins(ll x) {
        if (x)
            zero = 0;
        for (int i = 62; i >= 0; i--)
            if (x & (1LL << i)) {
                if (!p[i]) {
                    p[i] = x, cnt++;
                    break;
                } else
                    x ^= p[i];
            }
    }
    bool ask(ll x) {
        for (int i = 62; i >= 0; i--)
            if (x & (1ll << i))
                x ^= p[i];
        return x == 0;
    }
    ll getmax() {
        ll ans = 0;
        for (int i = 62; i >= 0; i--)
            if ((ans ^ p[i]) > ans)
                ans ^= p[i];
        return ans;
    }
    ll askmin() {
        if (zero)
            return 0;
        for (int i = 0; i <= 62; i++)
            if (p[i])
                return p[i];
    }
    void rebuild() {
        cnt = 0;
        top = 0;
        for (int i = 62; i >= 0; i--)
            for (int j = i - 1; j >= 0; j--)
                if (p[i] & (1ll << j))
                    p[i] ^= p[j];
        for (int i = 0; i <= 62; i++)
            if (p[i])
                d[cnt++] = p[i];
    }
    ll kth(int k) {
        if (k >= (1ll << cnt))
            return -1;
        ll ans = 0;
        for (int i = 62; i >= 0; i--)
            if (k & (1ll << i))
                ans ^= d[i];
        return ans;
    }
    int rank(ll x) {
        int ans = 0;
        for (int i = cnt - 1; i >= 0; i--)
            if (x >= d[i])
                ans += (1 << i), x ^= d[i];
        return ans + zero;
    }
};
/*
  - ins(ll x)：插入一个元素到线性基中，本质上是进行高斯消元，得到每一位的线性基。
  - ask(ll x)：查询某数字x是否可以通过线性基中的数通过异或操作组合得到。
  - getmax()：返回线性基中能够组合出的最大的数。
  - askmin()：返回线性基中能够组合出的最小的数。
  - rebuild()：重建线性基，主要是排序，并计算实际的线性基数的个数。
  - kth(int k)：返回线性基中第k小的数，如果不存在则返回-1。它通过二进制表示的方式寻找第k个数。
  - rank(ll x)：计算一个数在线性基中的排名，即在线性基中小于等于这个数的数的数量。
  -
  结构体内部的数组p存放的是线性基，数组d存放的是重建后的线性基，zero表示是否存在0。每一个函数都是高斯消元在编程中应用的具体体现。
 */
set<array<int, 3>> has;
void solve() {
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n == 1) {
        cout << a[1] << '\n';
    } else if (n == 2) {
        cout << max(a[1] + a[2], (a[1] ^ a[2]) * 2) << '\n';
    } else if (n >= 4) {
        LIB lib;
        for (int i = 1; i <= n; i++) lib.ins(a[i]);
        cout << lib.getmax() * n << '\n';
    } else {
        ll ans = 0;
        for (auto st : has) {
            ll sm = 0;
            for (int i = 1; i <= 3; i++) {
                int cur = 0;
                for (int j = 0; j < 3; j++)
                    if (st[i - 1] >> j & 1)
                        cur ^= a[j + 1];
                sm += cur;
            }
            ans = max(ans, sm);
        }
        cout << ans << '\n';
    }
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    auto dfs = [&](auto&& self, int a, int b, int c) -> void {
        {
            int aa = a ^ b, bb = a ^ b, cc = c;
            if (!has.count({ aa, bb, cc })) {
                has.insert({ aa, bb, cc });
                self(self, aa, bb, cc);
            }
        }
        {
            int aa = a, bb = b ^ c, cc = b ^ c;
            if (!has.count({ aa, bb, cc })) {
                has.insert({ aa, bb, cc });
                self(self, aa, bb, cc);
            }
        }
        {
            int aa = a ^ c, bb = a ^ c, cc = a ^ c;
            if (!has.count({ aa, bb, cc })) {
                has.insert({ aa, bb, cc });
                self(self, aa, bb, cc);
            }
        }
    };
    has.insert({ 1, 2, 4 });
    dfs(dfs, 1, 2, 4);
    int t;
    cin >> t;
    while (t--) solve();
}

I. 棋盘

提示 $1$ ：假如对于棋盘进行黑白染色，一个拼图占据的格子有什么性质。

一个拼图只会占据相同颜色的三个单元格。

假设棋盘中黑色单元格数量为 $b$ ，白色单元格数量为 $w$ ，那么答案就是 $\lfloor \frac{b}{3} \rfloor + \lfloor \frac{w}{3} \rfloor$ 。

如何证明一定存在一种构造方案使得棋盘尽可能能够放满呢，考虑一个更加弱化的问题，在一个 $n$ 的节点的树上切断一些边，得到一些 $3$ 个节点的子树，这种子树的数量就是 $\lfloor \frac{n}{3}\rfloor$ ，这个结论比较显然，在此就不做证明了。

那么我们可以对于棋盘的某一种颜色的格子，假如两个格子之间有一个公共的顶点那么就相当于树上有一条边，那么这些格子组成了一个连通图，显然这是比树更强的（更容易划分的），所以一定满足树的结论。

#include <bits/stdc++.h>
using namespace std;
long long n, m, T;
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld", &n, &m);
        if (min(n, m) == 1)
            printf("0\n");
        else
            printf("%lld\n", (n * m) / 2 / 3 + (n * m + 1) / 2 / 3);
    }
    return 0;
}

J. Swap, Splice and Modulus

提示 $1$ ：先考虑一个简单的问题，有一个正整数 $n$ 和一个质数 $p$ ，把整数 $n$ 连续写 $m$ 次得到的数字模 $p$ 的值是多少。

假如数字 $n$ 的位数是 $w$ ，那么答案是 $n+n\times 10^w+n\times 10^{2w}+\dots +n\times 10^{(m-1)w}=n\times (1+10^w +\dots + 10^{(m-1)w})$ ，显然这个值可以通过等比数列求和公式得到。

提示 $2$ ：使用数据结构维护数字的某一个前缀拼接起来对于 $p$ 取模的结果。

使用线段树，假如左子树的结果为 $w_{left}$ ，右子树的结果为 $w_{right}$ ，右子树中所以数字的位数和为 $len$ ，那么当且节点的答案就为 $w_{left}\times 10^{len} + w_{right}$ ，所以线段树只需要维护取模后的结果和当且节点包含的区间所有数字的位数和即可。

对于每一个查询，答案基于是提示 $1$ 和 $2$ 结合起来的结果，相当于很多个所有数字拼接到一起加上某一个前缀，按照两个方法结合起来计算即可，时间复杂度 $O(n\log(n)+q\log(n)\log(n))$ 。

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

const int maxn = 3e5 + 5;
int a[maxn], n, q, mod, pw[maxn * 10], op, i, j, x;
struct node {
    int val, len;
} f[maxn << 2];

int add(int x, int y, int mod) {
    x += y;
    if (x >= mod)
        x -= mod;
    return x;
}
int mul(int x, int y, int mod) {
    ll z = 1ll * x * y;
    z %= mod;
    x = z;
    return x;
}
int mins(int x, int y, int mod) {
    x -= y;
    if (x < 0)
        x += mod;
    return x;
}
int qpow(int x, int y, int mod) {
    int ans = 1 % mod;
    while (y) {
        if (y & 1)
            ans = mul(ans, x, mod);
        x = mul(x, x, mod);
        y >>= 1;
    }
    return ans;
}
int glen(int x) {
    int len = 0;
    while (x) ++len, x /= 10;
    return len;
}

#define ls (k << 1)
#define rs (k << 1 | 1)
#define mid ((l + r) >> 1)
node operator+(const node& lsh, const node& rsh) {
    node ans;
    ans.len = lsh.len + rsh.len;
    int temp = mul(lsh.val, pw[rsh.len], mod);
    ans.val = add(temp, rsh.val, mod);
    return ans;
}
void build(int k, int l, int r) {
    if (l == r) {
        f[k].len = glen(a[l]);
        f[k].val = a[l];
        return;
    }
    build(ls, l, mid), build(rs, mid + 1, r);
    f[k] = f[ls] + f[rs];
}
void modify(int k, int l, int r, int pos, int x) {
    if (l == r) {
        f[k].len = glen(x);
        f[k].val = x;
        return;
    }
    if (pos <= mid)
        modify(ls, l, mid, pos, x);
    else
        modify(rs, mid + 1, r, pos, x);
    f[k] = f[ls] + f[rs];
}
node query(int k, int l, int r, int x, int y) {
    if (l == x && r == y)
        return f[k];
    if (y <= mid)
        return query(ls, l, mid, x, y);
    else if (x > mid)
        return query(rs, mid + 1, r, x, y);
    else
        return query(ls, l, mid, x, mid) + query(rs, mid + 1, r, mid + 1, y);
}
#undef ls
#undef rs
#undef mid

void solve() {
    cin >> n >> q >> mod;
    for (int i = 1; i <= n; i++) cin >> a[i];
    pw[0] = 1;
    for (int i = 1; i <= n * 10; i++) pw[i] = mul(pw[i - 1], 10, mod);
    build(1, 1, n);
    for (int _ = 1; _ <= q; _++) {
        cin >> op;
        if (op == 1) {
            cin >> i >> j;
            modify(1, 1, n, i, a[j]), modify(1, 1, n, j, a[i]);
            swap(a[i], a[j]);
        } else {
            int x;
            cin >> x;
            int y = x / n, z = x % n;
            if (z) {
                node left = query(1, 1, n, 1, z);
                int val = mul(f[1].val, pw[left.len], mod), len = f[1].len;
                int ans = mul(mul(val, mins(1, qpow(pw[len], y, mod), mod), mod),
                              qpow(mins(1, pw[len], mod), mod - 2, mod), mod);
                ans = add(ans, left.val, mod);
                cout << ans << '\n';
            } else {
                int val = f[1].val, len = f[1].len;
                int ans = mul(mul(val, mins(1, qpow(pw[len], y, mod), mod), mod),
                              qpow(mins(1, pw[len], mod), mod - 2, mod), mod);
                cout << ans << '\n';
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
}

B. Good Array

提示 $1$ ：先考虑一个简化版的问题，给定一个数组 $a$ ，求这个数组是否是一个好的数组。

我们假设最后的所有数字的 $lcm$ 的质因数分解形式是 $p_1^{x_1}p_2^{x_2}\dots p_i^{x_i}$ ，可以使用优先队列从小到大搜索最多 $n+1$ 个不同的数字，得到 $lcm$ 的因数，看是否被数字 $a$ 的所有数字包含，时间复杂度 $O(n\log(n))$ 。

提示 $2$ ：把提示 $1$ 中的搜索过程变成增量的。

在每次一个新的数字加入后，我们搜索在这个数字加入后的 $lcm$ 新出现的因数，并且检查当且前缀的所有数字是否可以包含所有因数，最多搜索 $n+1$ 个数字，所以时间复杂度为 $O(n\log(n))$ 。具体实现细节见代码。

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

#define notall(x) x.begin() + 1, x.end()
#define all(x) x.begin(), x.end()
#define mul_t  \
    int _t;    \
    cin >> _t; \
    while (_t--)
#define seed chrono::steady_clock::now().time_since_epoch().count()
#define r_engine default_random_engine(seed)

const int int_inf = 1000000100;
const ll ll_inf = 4000000000000000400;

template <class T>
void writeln(const T &t) {
    cout << t << '\n';
}
template <class T, class... args>
void writeln(const T &t, const args &... rest) {
    cout << t << ' ';
    writeln(rest...);
}
template <class T1>
void writeln(const vector<T1> &v) {
    for (auto c : v) cout << c << ' ';
    cout << '\n';
}
template <class T1, class T2>
void writeln(const vector<T1> &v, T2 n) {
    for (T2 i = 1; i <= n; i++) cout << v[i] << ' ';
    cout << '\n';
}
template <class T1, class T2>
void writeln(const pair<T1, T2> &p) {
    cout << p.first << ' ' << p.second << '\n';
}
void writeln() { cout << endl; }
vector<bool> isnotprime;
vector<int> primes, mindiv;
void getprime(int n) {
    isnotprime.resize(n + 1, 0), mindiv.resize(n + 1, 1);
    isnotprime[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (isnotprime[i] == 0) {
            primes.push_back(i);
            mindiv[i] = i;
        }

        for (size_t j = 0; j < primes.size() && i * primes[j] <= n; j++) {
            isnotprime[i * primes[j]] = 1, mindiv[i * primes[j]] = primes[j];
            if (i % primes[j] == 0)
                break;
        }
    }
}
map<int, int> getdiv(int n) {
    map<int, int> res;
    while (n > 1) {
        res[mindiv[n]]++;
        n /= mindiv[n];
    }
    return res;
}
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    map<int, int> lcmmp;
    int num = n;
    set<int> need{ 1 };
    auto get_new = [&](map<int, int> &base, int newp) {
        int up = m / newp;
        priority_queue<int, vector<int>, greater<>> pq;
        pq.push(1);
        for (auto [x, y] : base) {
            if (x > up)
                break;
            vector<int> newnum;
            for (ll i = x, j = 1; i <= up && j <= y; i *= x, j++) {
                vector<int> poped;
                while (!pq.empty()) {
                    auto c = pq.top();
                    if (i * c <= up) {
                        newnum.push_back(i * c);
                        if (pq.size() + newnum.size() + poped.size() > num) {
                            num = -1;
                            return;
                        }
                    } else
                        break;
                    pq.pop();
                    poped.push_back(c);
                }
                for (auto c : poped) pq.push(c);
            }
            for (auto c : newnum) pq.push(c);
        }
        num -= pq.size();
        while (!pq.empty()) {
            auto c = pq.top();
            need.insert(c * newp);
            pq.pop();
        }
    };
    string ans = string(n + 1, '0');
    for (int i = 1; i <= n; i++) {
        if (num < 0)
            break;
        auto curdiv = std::move(getdiv(a[i]));
        for (auto [x, y] : curdiv) {
            if (y > lcmmp[x]) {
                int dec = y - lcmmp[x];
                ll cur = 1;
                for (int i = 1; i <= lcmmp[x]; i++) {
                    cur *= x;
                    if (cur > m)
                        break;
                }
                lcmmp.erase(x);
                if (cur < m) {
                    for (int i = 1; i <= dec; i++) {
                        cur *= x;
                        if (cur > m)
                            break;
                        get_new(lcmmp, cur);
                    }
                }
                lcmmp[x] = y;
            }
        }
        need.erase(a[i]);
        if (need.empty() && num >= 0)
            ans[i] = '1';
    }
    writeln(ans.substr(1));
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(15);
    getprime(1e7);
    mul_t solve();
}

E. Time Traveler

提示 $1$ ：这不是一个最短路问题，注意到 $u<v$ 具有偏序关系，这是一个图上dp 问题。

提示 $2$ ：考虑如何设置 $dp$ 状态。

令 $dp[u][i]$ 代表为了从节点 $u$ 的第 $i$ 条出边出发的时刻 $time[i]$ 出发所为了花费的最小代价总和，那么假设有一个时刻集合 $tv$ 代表 $u$ 的所有入边的到达时刻且，那么对于 $tv$ 中的，每一个时刻 $t$ ，它们到达 $u$ 的最小代价为 $w$ ，那么存在转移：

dp[u][i]=min(dp[u][i],w+time[i]-t+c_u)[t\le time[i]]\\ dp[u][i]=min(dp[u][i],w+t-time[i])[t\ge time[i]]\\

每个节点的答案就是它的所有入边的代价 $w$ 的最小值。

直接转移最坏时间复杂度是 $O(m^2)$ 的，此时可以在对于时间排序后使用前缀/后缀和双指针最小值优化这个 dp，时间复杂度为 $O(n+m\log(m))$ 。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll ll_inf = 1e18 + 100;
void solve() {
    int n, m;
    cin >> n >> m;
    vector<ll> c(n + 1);
    for (int i = 1; i <= n; i++) cin >> c[i];
    vector<vector<array<ll, 3>>> e(n + 1);
    vector<int> outdeg(n + 1), indeg(n + 1);
    for (int i = 1; i <= m; i++) {
        ll u, v, w, t;
        cin >> u >> v >> w >> t;
        e[u].push_back({ v, w, t });
        ++indeg[u], ++outdeg[v];
    }
    for (int i = 1; i <= n; i++)
        sort(e[i].begin(), e[i].end(), [&](const auto &lsh, const auto &rsh) { return lsh[2] < rsh[2]; });
    vector<vector<ll>> dp(n + 1);
    vector<map<ll, vector<ll>>> mp(n + 1);
    vector<ll> ans(n + 1, ll_inf);
    for (int i = 1; i <= n; i++) dp[i].resize(indeg[i], ll_inf);
    for (int i = 0; i < e[1].size(); i++) {
        auto [v, w, t] = e[1][i];
        dp[1][i] = t;
    }
    ans[1] = 0;
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (outdeg[i] == 0)
            q.push(i);
    while (!q.empty()) {
        auto u = q.front();
        q.pop();
        // dp when enter in
        if (u != 1) {
            ll premn = ll_inf;
            auto bgp = mp[u].begin();
            for (int i = 0; i < e[u].size(); i++) {
                while (bgp != mp[u].end() && bgp->first <= e[u][i][2]) {
                    ll curtim = bgp->first;
                    for (auto dps : bgp->second) premn = min(premn, dps - curtim);
                    bgp = next(bgp);
                }
                dp[u][i] = min(dp[u][i], premn + e[u][i][2]);
            }
            ll sufmn = ll_inf;
            auto edp = mp[u].end();
            for (int i = e[u].size() - 1; i >= 0; i--) {
                while (edp != mp[u].begin() && prev(edp)->first >= e[u][i][2]) {
                    edp = prev(edp);
                    ll curtim = edp->first;
                    for (auto dps : edp->second) sufmn = min(sufmn, dps);
                }
                dp[u][i] = min(dp[u][i], sufmn + c[u]);
            }
        }
        for (int i = 0; i < e[u].size(); i++) {
            ll cur = dp[u][i];
            auto [v, w, t] = e[u][i];
            ans[v] = min(ans[v], cur + w);
            ll tim = t + w;
            mp[v][tim].push_back(cur + w);
            if (--outdeg[v] == 0)
                q.push(v);
        }
    }
    for (int i = 1; i <= n; i++) cout << (ans[i] >= ll_inf / 2 ? -1 : ans[i]) << " \n"[i == n];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(15);
    int t;
    cin >> t;
    while (t--) solve();
}

考虑本题的一个加强版：把题目中的条件 $u<v$ 改为 $u\neq v$ ，即所有点不再具有偏向关系怎么解决。

C. 山

提示 $1$ ：尝试在题目要求下解决 $q=1,l=1,r=n$ 的询问。

对于两个相邻的数字 $a_i,a_{i+1}$ 来说，对于某个 $k$ 来说，使得数组单调不减少的条件为 $a_{i+1}\times k^x\ge a_i$ ， $x$ 为操作的次数，那么此时这个操作会对后面的所有数对造成什么影响呢。

提示 $2$ ：尝试在题目要求下解决 $q=5\times 10^5,l=1,r=n$ 的询问。

对于所有不同的 $k$ 来说，不同的答案会有多少种呢。其实最多只有 $O(n\times \log(b))$ 种，这是因为对于任意的两个相邻的数字来说，根据分块的思想，使得满足这两个数字单调不减的操作次数的大小只有 $n\times \log(b)$ 种。

那么此时结合提示 $1$ ，去离线的解决提示 $2$ 中的问题，先对于所有询问按照 $k$ 从小到大排序，然后计算对于两个相邻的数字来说，在某一刻 $k$ 从 $x$ 变化为 $x+1$ 时，那么使得这两个数字单调不减的操作次数从 $a$ 变为 $b$ 。思考提示 $1$ 的问题，假如某一个位置操作次数为 $a$ 次，因为数组初始时单调不减，那么此时后面的所有位置的操作数字也需要增加 $a$ ，所以此时只需要一个区间加，整体求和的线段树就可以解决问题（其实也可以不使用任何数据结构）。

提示 $3$ ：尝试解决 $1\le l<r\le n$ 的询问。

对于某一个区间 $[l,r]$ 来说，根据提示 $1$ ，发现其实有两个部分贡献了这个区间的答案，一个是 $[1,l-1]$ ，另一个是 $[l,r]$ ，考虑如何只凑出区间 $[l,r]$ 的答案，其实答案就是区间 $[l,r]$ 的部分在区间 $[l,r]$ 内的贡献加上区间 $[1,l-1]$ 在区间 $[l,r]$ 内的贡献减去区间 $[1,l-1]$ 在区间 $[1,l-1]$ 内的贡献，如何求出每部分的值代码中有给出。

提示 $4$ ：上述方法的时间复杂度已经满足要求，但是浮点数的运算很慢，如何减少浮点数运算次数。

在计算不同的 $k$ 对于两个相邻的数字所需的操作次数时，使用根号分治算法。

最终时间复杂度 $O(q\log(n)\log(n)+\sqrt n \times B+\frac{n\log(n)}{\log(B)}$ ， $B$ 取 $1000$ 左右时较优。

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

const long double eps = 1e-14;

struct segmenttree {
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mid ((l + r) >> 1)
    vector<ll> f, g;
    segmenttree(int n) { f.assign((n << 2) + 1, 0), g.assign((n << 2) + 1, 0); }
    void down(int k, int l, int r) {
        if (g[k]) {
            g[ls] += g[k], g[rs] += g[k];
            f[ls] += g[k] * (mid - l + 1), f[rs] += g[k] * (r - mid);
            g[k] = 0;
        }
    }
    void up(int k) { f[k] = f[ls] + f[rs]; }
    void modify(int k, int l, int r, int x, int y, ll z) {
        if (l == x && r == y) {
            g[k] += z;
            f[k] += z * (y - x + 1);
            return;
        }
        down(k, l, r);
        if (y <= mid)
            modify(ls, l, mid, x, y, z);
        else if (x > mid)
            modify(rs, mid + 1, r, x, y, z);
        else
            modify(ls, l, mid, x, mid, z), modify(rs, mid + 1, r, mid + 1, y, z);
        up(k);
    }
    ll caclsum(int k, int l, int r, int x, int y) {
        if (l == x && r == y)
            return f[k];
        down(k, l, r);
        ll sum;
        if (y <= mid)
            sum = caclsum(ls, l, mid, x, y);
        else if (x > mid)
            sum = caclsum(rs, mid + 1, r, x, y);
        else
            sum = caclsum(ls, l, mid, x, mid) + caclsum(rs, mid + 1, r, mid + 1, y);
        up(k);
        return sum;
    }
#undef ls
#undef rs
#undef mid
};

template <typename T>
struct Fenwick {
    int n;
    vector<T> tr;

    Fenwick(int n) : n(n), tr(n + 1) {}

    int lowbit(int x) { return x & -x; }

    void modify(int x, T c) {
        for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    }

    void modify(int l, int r, T c) {
        modify(l, c);
        if (r + 1 <= n)
            modify(r + 1, -c);
    }

    T query(int x) {
        T res = T();
        for (int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }

    T query(int l, int r) {
        if (l > r)
            return T();
        return query(r) - query(l - 1);
    }

    int find_first(T sum) {
        int ans = 0;
        T val = 0;
        for (int i = __lg(n); i >= 0; i--) {
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] < sum) {
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans + 1;
    }

    int find_last(T sum) {
        int ans = 0;
        T val = 0;
        for (int i = __lg(n); i >= 0; i--) {
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] <= sum) {
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans;
    }
};

void solve() {
    int n, q, bs;
    cin >> n >> q >> bs;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<array<int, 4>> qurs(q + 1);
    for (int i = 1; i <= q; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        qurs[i] = { k, l, r, i };
    }
    vector<vector<array<int, 2>>> b(n);
    vector<int> lstz(n + 1);
    auto get = [&](int pos) {
        int z = a[pos] - a[pos + 1];
        if (z == 0 || bs == 1)
            return;
        if (lstz[z]) {
            b[pos] = b[lstz[z]];
            return;
        }
        lstz[z] = pos;
        long double up = z * log10l(bs) - eps;
        // xln2⋅(log_2{x})^2=z*20
        //暴力算1100个数
        for (int i = 2; i <= 1100; i++) {
            int res = ceill(up / log10l(i));
            if (b[pos].empty() || res != b[pos].back()[1])
                b[pos].push_back({ i, res });
        }
        int cur = b[pos].back()[1];
        for (int i = cur - 1; i >= 1; i--) {
            if (i * 9 < up)
                break;
            int res = ceill(powl(10, up / i));
            if (b[pos].empty() || res != b[pos].back()[0])
                b[pos].push_back({ res, i });
            else
                b[pos].back()[1] = i;
        }
    };
    map<int, vector<array<ll, 2>>> change;
    for (int i = 1; i < n; i++) {
        get(i);
        int lst = 0;
        for (auto &[x, y] : b[i]) {
            if (x == 0)
                continue;
            change[x].push_back({ y - lst, i });
            lst = y;
        }
    }
    segmenttree tr(n);
    Fenwick<ll> treesum(n), treecontri(n);
    sort(qurs.begin() + 1, qurs.end());
    vector<ll> ans(q + 1);
    int p = 1;
    change[int(1e9) + 1] = {};
    for (auto &[x, v] : change) {
        while (p <= q && qurs[p][0] < x) {
            auto &[k, l, r, idx] = qurs[p];
            ans[idx] = tr.caclsum(1, 1, n - 1, 1, r - 1) - treecontri.query(1, l - 1) +
                       treesum.query(1, l - 1) * (n - r);
            ++p;
        }
        for (auto &[cg, idx] : v) {
            tr.modify(1, 1, n - 1, idx, n - 1, cg);
            treecontri.modify(idx, cg * (n - idx));
            treesum.modify(idx, cg);
        }
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(15);
    int t;
    cin >> t;
    while (t--) solve();
}

H. AGAIN! Permutation with MAX Score

提示1：得分的上限是多少？

得分的上限为 $\lceil \frac{n}{2}\rceil$ ，证明如下：

假如有 $\lceil \frac{n}{2}\rceil +1$ 个满足条件的位置，那么必然有三个连续的位置，设他们的值为 $x,y,z$ ，那么 $k/(k-1) = y/x = z/y$ ，即 $k=y/(y-x)=z/(z-y)(k\in N^+)$ ，此时发现， $k\ge 2$ ，那么最多只有 $\lfloor log(n)\rfloor$ 个位置是满足条件的，与假设矛盾，所以不可能有 $\lceil \frac{n}{2}\rceil +1$ 个满足条件的位置。

提示2： $k$ 取多少较为合适？

$\frac{n}{2}\le k \le 2n$ ，当 $k$ 不是这个范围时答案最大为 $\lfloor log(n)\rfloor$ 。

提示3: $n$ 是奇数和偶数时哪个更容易解决？

偶数更容易，因为有对称性。

根据提示，先解决 $n$ 为偶数的问题，当 $n$ 为偶数时，观察可知，共有 $\frac{n}{2}$ 对数字的和为 $n+1$ ，所以取 $k=n+1$ ，类似 $n,1,n-1,2...$ 这样构造即可，此时答案为 $\frac{n}{2}$ 。

下面对于 $n$ 为奇数的情况进行讨论：

当 $n\%4=1$ 时，也能发现一定的对称性，当取 $k=\frac{n+1}{2}$ 时，按照 $n-1,2,n-3,4,\dots,\frac{n+1}{2},3,n-2,1,n$ 的方法构造即可，此时答案为 $\frac{n+1}{2}$ 。

接下来靠注意力已经不行了，可以根据提示二进行打表操作。

使用暴力的方式打表，大概可以从 $n=1$ 打表到 $n=12$ ，此时可以发现，除了 $n=3$ 和 $n=11$ 外，答案均为 $\lceil \frac{n}{2}\rceil$ ，而这两个数答案为 $\lceil \frac{n}{2}\rceil -1$ 。除此之外，你可能还有个发现，那就是当 $n$ 为奇数且 $k=\frac{n+1}{2}$ 的时候，奇数可以取到最优解。

接下来，你可以确定 $k$ ，使用状压dp 的方式进行打表，对于 $n\%4=3$ ，你会得到如下结果：
$n=15$ ： $[14,2,12,4,3,5,9,7,8,6,10,11,13,1,15]$ $n=19$ ： $[18,2,7,3,15,5,4,6,12,8,1,9,10,17,13,14,16,11,19]$

当 $n=15$ 即 $n\%8=7$ 的时候，观察每一对 $i$ 和 $i+1$ 的和（除了中心的数字），可以发现他们的和对于 $k$ 的倍数分别为 $2,2,1,2,2,1,2,3,2$ ，以 $k=8$ 划分为两部分可以得到 $2,2,1,2,2$ ， $2,3,2$ ，可以发现，当 $n$ 增加 $8$ 的时候，只需要在前后两个序列的首尾都增加一个 $2$ 即可。

当 $n=19$ 即 $n\%8=3$ 的时候，观察每一对 $i$ 和 $i+1$ 的和（除了中心的数字），可以发现他们的和对于 $k$ 的倍数分别为 $2,1,2,1,2,1,1,2,3,2$ ，以 $k=10$ 划分为两部分可以得到 $2,1,2,1,2$ ， $3,3,3$ ，可以发现，当 $n$ 增加 $8$ 的时候，只需要在前后两个序列的首尾都增加一个 $2$ 即可。

对于上述两个例子都给出 $n+8$ 的构造方法： $n=23$ ：22 2 20 4 18 6 5 7 15 9 13 11 12 10 14 8 16 17 19 3 21 1 23
$n=27$ ：26 2 24 4 9 5 21 7 6 8 18 10 3 11 15 13 14 12 16 23 19 20 22 17 25 1 27

本题是一道十分需要打表基本功，观察能力和耐心的题，出题人在写这道题时，大概花了8小时左右的时间。

时间复杂度 $O(n)$ 。

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

void solve() {
    int n;
    cin >> n;
    if (n % 2 == 0) {
        cout << n + 1 << '\n';
        int l = 1, r = n;
        while (l < r) cout << r-- << ' ' << l++ << ' ';
        cout << '\n';
    } else if (n % 4 == 1) {
        cout << (n + 1) / 2 << '\n';
        vector<int> ans(n + 1);
        for (int i = 2; i <= n / 2; i += 2) ans[i] = i, ans[i - 1] = (n + 1) - ans[i];
        for (int i = n; i > n / 2 + 1; i -= 2) ans[i] = i, ans[i - 1] = (n + 1) - ans[i];
        ans[n / 2 + 1] = n / 2 + 1;
        for (int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];
    } else {
        // special case 3 11
        if (n == 3 || n == 11) {
            cout << n << '\n';
            int l = 1, r = n - 1;
            while (l < r) cout << r-- << ' ' << l++ << ' ';
            cout << n << '\n';
        } else if (n % 8 == 7) {
            // 2 2 1 2 2
            // 2 2 3 2 2
            // 23
            vector<int> ans(n + 1);
            ans[n] = n;
            ans[2] = 2, ans[1] = n - 1;
            for (int i = n - 2, j = 1; j <= n / 4; i -= 2, j++) {
                if (j * 2 - 1 == n / 4)
                    ans[i] = ans[i + 2] - 3;
                else
                    ans[i] = ans[i + 2] - 2;
                ans[i + 1] = (n + 1) / 2 * (ans[i + 2] - ans[i]) - ans[i + 2];
            }
            for (int i = 4, j = 1; j <= n / 4; i += 2, j++) {
                if (j * 2 - 1 == n / 4)
                    ans[i] = ans[i - 2] + 1;
                else
                    ans[i] = ans[i - 2] + 2;
                ans[i - 1] = (n + 1) / 2 * (ans[i] - ans[i - 2]) - ans[i];
            }
            cout << (n + 1) / 2 << '\n';
            for (int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];
        } else {
            // more specail cases
            // 3个1   3个3
            int a = n / 4 + 1, b = n / 4 - 1;
            vector<int> ans(n + 1);
            ans[n] = n;
            ans[2] = 2, ans[1] = n - 1;
            int mida = (a + 1) / 2, midb = (b + 1) / 2;
            for (int i = 4, j = 1; j <= a; i += 2, j++) {
                if (abs(j - mida) > 2)
                    ans[i] = ans[i - 2] + 2;
                else {
                    if ((j - mida) & 1)
                        ans[i] = ans[i - 2] + 2;
                    else
                        ans[i] = ans[i - 2] + 1;
                }
                ans[i - 1] = (n + 1) / 2 * (ans[i] - ans[i - 2]) - ans[i];
            }
            for (int i = n - 2, j = 1; j <= b; i -= 2, j++) {
                if (abs(j - midb) <= 1)
                    ans[i] = ans[i + 2] - 3;
                else
                    ans[i] = ans[i + 2] - 2;
                ans[i + 1] = (n + 1) / 2 * (ans[i + 2] - ans[i]) - ans[i + 2];
            }
            cout << (n + 1) / 2 << '\n';
            for (int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];
        }
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
}

第六届「帆软杯」东南大学大学生程序设计竞赛（冬季）专业组 题解