Rank 220/4526. AC 8/13.

迟到了 \(20\) 分钟，赛后 \(8\) 分钟就把 \(A, B\) 切了（

A. Tokitsukaze and Bracelet

题意

给定三种加成的属性值，根据属性值，有下面的加成规则：

1. 对于第一种属性值 \(a\)：\(a=100\) 时 \(+0\)，\(a=150\) 时 \(+1\)，\(a=200\) 时 \(+2\)；

2. 对于后两种属性值 \(b, c\)：值为 \(\{29, 30, 31, 32\}\) 时 \(+0\)，值为 \(\{34, 36, 38, 40\}\) 时 \(+1\)，值为 \(45\) 时 \(+2\)

输出总加成。

思路

如题，模拟即可。

时间复杂度：\(O(1)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int a, b, c;
    cin >> a >> b >> c;
    int ans = 0;
    if(a == 100) ans += 0;
    else if(a == 150) ans += 1;
    else ans += 2;
    if(b == 45) ans += 2;
    else if(b == 34 || b == 36 || b == 38 || b == 40) ans += 1;
    if(c == 45) ans += 2;
    else if(c == 34 || c == 36 || c == 38 || c == 40) ans += 1;
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

主打一个手速

B. Tokitsukaze and Cats

题意

在一个 \(n \times m\) 的网格中，有 \(k\) 个物品放置在 \((x_i, y_i)\) 坐标对应的方格内。现在，需要将每个物品的上下左右 \(4\) 个边框都变成障碍物，输出最后有多少个边框变成了障碍物。

思路

我们可以把横向的边框和纵向的边框单独考虑，从而抽象为一个矩阵中元素是否被选择。

那么很简单，我们只需读入每个坐标，在横向边框的矩阵中，选择 \(i, i - 1\)；纵向也是同理。最后我们统计有多少矩阵中的元素被我们选择了即可。

时间复杂度：\(O(nm)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<bool>> c(n + 2, vector<bool>(m + 2)), r(n + 2, vector<bool>(m + 2));
    while(k --) {
        int x, y;
        cin >> x >> y;
        c[x][y] = c[x - 1][y] = true;
        r[x][y] = r[x][y - 1] = true;
    }
    int ans = 0;
    for(auto &e1 : c) {
        for(auto e2 : e1) {
            if(e2) ans ++;
        }
    }
    for(auto &e1 : r) {
        for(auto e2 : e1) {
            if(e2) ans ++;
        }
    }
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

相对来说应该是最快的写法了吧（

C. Tokitsukaze and Min-Max XOR

题意

给定一个长为 \(n\) 的序列 \(a\) 以及一个整数 \(k\)，构造长度为任意值 \(m\) 的序列 \(b\)，满足：

1. \(1 \leq b_i \leq n\)

2. \(\forall i \in [2, m],\ s.t.\ b_{i - 1} < b_i\)

3. \(\min(a_{b_1}, a_{b_2}, \ldots, a_{b_m}) \oplus \max(a_{b_1}, a_{b_2}, \ldots, a_{b_m}) \leq k\)

输出构造方案数的总和，对 \(10^9 + 7\) 取模。

思路

取最小和最大只是个幌子，因为 \(b\) 一定是严格递增的，且我们不关注具体构造出的方案是什么，从而我们只需将 \(a\) 升序排序，那么选择好左右端点，这个区间内的元素就可以任意取。

具体来说，排序后，我们取 \(a_i\) 和 \(a_j\) 作为最小值和最大值，那么中间总共有 \(j - i - 1\) 个元素，于是对这个选择 \(<i, j>\)，有 \(2^{j - i - 1}\) 种方案。

当然，\(i = j\) 也算一种方案，但是我们先不考虑这个，在答案的最后再计入。

那么，现在问题在如何选取最值，因为我们需要让异或值落在范围内。

如何让异或和比 \(k\) 小呢？和上一场的某题一样，我们只需让 \(k\) 的某个为 \(1\) 的高位变为 \(0\) 即可，并且后续的低位可以任意选。

于是，我们可以考虑从小到大遍历，并在每次遍历完的时候将自己加入某种数据结构中，便于直接查询。

不妨使用 \(01\) 字典树。

我们用 \(s := a[j]\) 遍历字典树，并以 \(k\) 为参考，找出符合条件的 \(t := a[i]\)。如果 \(s\) 某一位对应于 \(k\) 的值为 \(1\)，那么在 \(t\) 的该位上，我们选择和 \(s\) 一致，从而得到异或为 \(0\)，此时后续的低位可以任意选，我们将其子树的代价总和记录到答案中。不过最后我们还得把 \(k\) 本身的代价也计入答案，因为条件是小于等于。

至于选择什么作为叶节点的代价，我们可以发现 \(2^{j - i - 1} = \frac{2^{j-1}}{2^i}\)，\(i, j\) 是无关的。从而我们只需将 \(\frac{1}{2^{i}}\) 作为叶节点的代价，在每一位枚举完的时候将该数字以权值 \(\frac{1}{2^i}\) 加入字典树即可。在枚举每一位时，我们只需按上述遍历字典树的方式，得到代价和 \(1 + 2^{j-1} \cdot \sum \frac{1}{2^i}\)，累加答案即可。

时间复杂度：\(O(n \log k)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

static __int128 qp(__int128 x, __int128 y, const __int128 m = mod) {
    static __int128 ans;
    ans = 1, x %= m;
    for (; y; y >>= 1, x = x * x % m) if (y & 1) ans = ans * x % m;
    return ans;
}

int inv(int n, int m = mod) { return qp(n, m - 2, m); }

struct TRIE01 {
    int nxt[N * 30][2], idx, sum[N * 30], len, root;
    void init(int k) { len = k, memset(nxt, 0, (sizeof nxt[0]) * (idx + 1)), memset(sum, 0, (sizeof sum[0]) * (idx + 1)), idx = 1, root = idx ++; }
    void update(int x, int val){
        int now = root;
        for(int i= len - 1; i >= 0;i--) {
            int p = (x >> i) & 1;
            if(!nxt[now][p]) nxt[now][p] = idx ++;
            now = nxt[now][p];
            sum[now] = (sum[now] + val) % mod;
        }
    }
    int query(int s, int k){ //查找满足 x xor s <= k 的 sum[x]
        int now = root, ans = 0;
        for (int i = len - 1; i >= 0; i--) {
            int x = (s >> i) & 1;
            if((k >> i) & 1) { //k该位反选0，低位就可任意选
                if(nxt[now][x]) ans = (ans + sum[nxt[now][x]]) % mod;
                now = nxt[now][x ^ 1];
            }else now = nxt[now][x];
        }
        ans = (ans + sum[now]) % mod; // ==k
        return ans;
    }
}trie01;

int p2[N], p2_inv[N];

void init() {
    p2[0] = p2[1] = p2_inv[0] = p2_inv[1] = 1;
    p2[1] = 2, p2_inv[1] = inv(2);
    for(int i=2;i<=2e5;i++) {
        p2[i] = p2[i - 1] * p2[1] % mod;
        p2_inv[i] = p2_inv[i - 1] * p2_inv[1] % mod;
    }
}

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    sort(all(a));
    int ans = 1;
    trie01.init(31);
    for(int i=2;i<=n;i++) {
        trie01.update(a[i - 1], p2_inv[i - 1]);
        ans = (ans + 1 + trie01.query(a[i], k) * p2[i - 1] % mod) % mod;
    }
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

赛时想到了 \(01\) 字典树，但不知道咋写（

D. Tokitsukaze and Slash Draw

题意

对于一个由 \(n\) 张卡片从底往上堆叠而成的卡组，从底往上数第 \(k\) 张牌为特殊卡片。

现在，给定 \(m\) 种具有调整牌组顺序的卡片，每种卡片有无限张，且第 \(i\) 种卡片的效果为：将卡组从上往下数共 \(a_i\) 张卡整体搬移到卡组的最下方，并花费 \(b_i\) 代价。

输出使特殊卡片调整到卡组最顶部所需的最小代价。

思路

等价于一个带取模的完全背包问题。

在这里，起点为 \(k \bmod n\)，终点为 \(0\)，我们可以任意选择卡片，且每种卡片有无限张，使最后的代价最小。

朴素的完全背包需要 \(O(n^2m)\) 的复杂度，因为这里的取模会导致值变小，从而我们需要在原来的基础上多遍历 \(n-1\) 次，才能正确转移。

可以发现，背包问题的起点和终点都已知，且每次状态转移的起点和终点也都已知，从而我们将其转化为一个最短路问题。

具体来说，我们将读入的卡片作为移动 \(a_i\) 单位需要的最小代价，这个代价可以作为两点间的边权。

我们也无需建图，因为我们在枚举的时候知道下一个结点是什么。

从而，当我们遇到 \(i \to j\) 时，简单计算可知，需要移动 \((j - i + n) \bmod n\)，此时根据前面记录的最小代价，我们就可以得到我们需要的边权了。

时间复杂度：\(O(m + n^2 \log n^2)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> w(n + 1, inf);
    for(int i=1;i<=m;i++) {
        int a, b;
        cin >> a >> b;
        w[a] = min(w[a], b);
    }
    priority_queue<pii, vector<pii>, greater<>> q;
    vector<int> dist(n + 1, inf);
    dist[k % n] = 0, q.emplace(0, k % n);
    vector<bool> st(n + 1);
    while (!q.empty()) {
        auto [d, v] = q.top(); q.pop();
        if (st[v]) continue;
        st[v] = true;
        for(int i=0;i<n;i++) {
            int p = (i - v + n) % n;
            if (dist[i] > d + w[p]) dist[i] = d + w[p], q.emplace(dist[i], i);
        }
    }
    cout << (dist[0] == inf ? -1 : dist[0]) << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

好像稠密图也没必要堆优化（

E. Tokitsukaze and Eliminate (easy)

题意

给定 \(n\) 个宝石，第 \(i\) 个宝石具有颜色 \(col_i\)，定义一次操作如下：

选定一个颜色 \(x\)，将颜色为 \(x\) 的最右边的宝石，以及该宝石右侧的所有宝石全都消除。

输出让所有宝石都消除的最少操作次数。

本题中，最多只有两种颜色。

思路

既然最多只有两种颜色，我们就只需从右往左枚举，当出现第一个不同的元素，就将其以及后面的所有宝石全都删去。

最后我们会留下几个颜色相同的宝石，此时我们只能一个一个删除。

时间复杂度：\(O(n)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    int ans = 0, pre = -1, now = 0;
    for(int i=n;i>=1;i--) {
        if(pre == -1) pre = a[i], now ++;
        else if(pre != a[i]) {
            ans ++;
            pre = -1, now = 0;
        }else now ++;
    }
    cout << ans + now << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

一开始没看到 \(2\) 种，差点把 \(hard\) 搞出来了（

F. Tokitsukaze and Eliminate (hard)

题意

给定 \(n\) 个宝石，第 \(i\) 个宝石具有颜色 \(col_i\)，定义一次操作如下：

选定一个颜色 \(x\)，将颜色为 \(x\) 的最右边的宝石，以及该宝石右侧的所有宝石全都消除。

输出让所有宝石都消除的最少操作次数。

本题中，最多有 \(n\) 种颜色。

思路

观察可得，后面删的越多，越有利于前面的删除，而如何删的最多呢？

我们直接枚举当前存在的所有颜色的最右边的宝石位置，找出最小值即可，这就是我们当前能删的最多数量。

重复上述操作，不难证明最后的答案一定是最优的。

至于如何实现，我们可以用 \(\mathtt{stl}\) 维护当前存在的颜色的最右端点，复杂度可行。

时间复杂度：\(O(n \log n)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<set<int>> ind(n + 1);
    set<int> st;
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        st.ep(a[i]);
        ind[a[i]].ep(i);
    }
    int ans = 0;
    for(int i=n;i>=1;) {
        int mn = i;
        for(auto &e : st) {
            mn = min(mn, *ind[e].rbegin());
        }
        for(int k=mn;k<=i;k++) {
            ind[a[k]].extract(k);
            if(ind[a[k]].empty()) st.extract(a[k]);
        }
        ans ++;
        i = mn - 1;
    }
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

论看完题就想到怎么做但是半天搓不出来.txt

G. Tokitsukaze and Power Battle (easy)

题意

给定一个长为 \(n\) 的序列 \(a\)，给定 \(q\) 个询问：

• \(1\ x\ y\)：将 \(a_x\) 修改为 \(y\)；

• \(2\ l\ r\)：从 \([l, r]\) 选择一段连续子序列 \([i, j]\)，其中 \(l \leq i < j \leq r\)。再选择一个分割点 \(x\)，将子序列划分为 \([i, x], [x + 1, j]\)，其中 \(i \leq x < j\)。定义本次选择的价值为 \([i, x]\) 中所有元素的和 \(-\) \([x + 1, j]\) 中所有元素的和。输出所有选择中的最大价值。

本题中，所有元素都是非负数。

思路

首先这个题面就很数据结构，我们考虑一下如何维护。

首先，要让差值尽可能大，在非负数中，我们肯定会尽可能使 \([i, x]\) 包含更多的元素，而 \([x + 1, j]\) 包含更少的元素。

从而我们可以得出结论：当 \(i = l\)，\(x + 1 = j\) 时，以 \(j\) 为右端点的选择中价值最大。

既然左端点固定，那么我们完全可以考虑前缀和，因为左端我们需要减掉的值是一致的。

那么最好想的方式就是维护区间内 \(pre[i - 1] - a[i]\) 的最大值，其中 \(pre[i - 1]\) 为前 \(i - 1\) 个元素的和。

碍于本人线段树能力有限，这里介绍另一个邪道做法。

如果我们考虑暴力从右端点往前枚举，那么选前一个元素更优的条件为 \(pre[i - 2] - a[i - 1] > pre[i - 1] - a[i]\)，化简得：

\(a[i] > 2 \cdot a[i - 1]\)

如果选前一个元素 非 更优，但选前面第二个元素更优，那么我们有：

\(\left \{ \begin{array}{l} a[i] \leq 2 \cdot a[i - 1] \\ pre[i - 3] - a[i - 2] > pre[i - 1] - a[i]\end{array} \right.\)

即：

\(\left \{ \begin{array}{l} a[i] \leq 2 \cdot a[i - 1] \\ a[i] > 2 \cdot a[i - 2] + a[i - 1]\end{array} \right.\)

从而有：

\(a[i] \leq 2 \cdot a[i - 1] < 2 \cdot a[i] - 4 \cdot a[i - 2]\)

化简得：

\(a[i] > 4 \cdot a[i - 2]\)

而显然地，如果选前一个元素更优，而选前面第二个元素比选前一个还更优，我们依然有：

\(a[i] > 2 \cdot a[i - 1] > 4 \cdot a[i - 2]\)

从而我们可以得到一个结论：无论前面的选择如何，不影响当前更优的条件。

继续推导，我们即可归纳得到：选 \(i - k\) 作为右端点比选第 \(i\) 作为右端点更优的条件为 \(a[i] > 2^k \cdot a[i - k]\)。

而显然，元素都是 \(10^9\) 范围内的，从而 \(k\) 最多只能是 \(30\)。

最后我们得到的结论是：我们只需从 \(r\) 开始向前枚举 \(30\) 个元素即可。

至于如何快速维护前缀和，直接上树状数组即可。

时间复杂度：\(O(30q \log n)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

template<class Info = int>
struct BinaryIndexTree {
    int n;
    vector<Info> info;
    BinaryIndexTree() : n(0) {}
    explicit BinaryIndexTree(int _n, Info _v = Info()) : info(_n + 1, _v), n(_n) {}
    static int lowbit(int x) { return x & (-x); }
    void pointUpdate(int pos, Info _info) {
        for (int i = pos; i <= n; i += lowbit(i)) info[i] = info[i] + _info;
    }
    Info rangeQuery(int r) {
        Info ans{};
        for (int i = r; i > 0; i -= lowbit(i)) ans = ans + info[i];
        return ans;
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(r) - rangeQuery(l - 1);
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    BinaryIndexTree bit(n);
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        bit.pointUpdate(i, a[i]);
    }
    while(q --) {
        int op;
        cin >> op;
        if(op == 1) {
            int x, y;
            cin >> x >> y;
            bit.pointUpdate(x, y - bit.rangeQuery(x, x));
        }else {
            int l, r;
            cin >> l >> r;
            int ans = -inf;
            for(int i=1;r-i>=l&&i<=32;i++) {
                ans = max(ans, bit.rangeQuery(l, r - i) - bit.rangeQuery(r - i + 1, r - i + 1));
            }
            cout << ans << '\n';
        }
    }
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

有点神奇，赛时完全不敢这么猜（

H. Tokitsukaze and Power Battle (hard)

待补充

I. Tokitsukaze and Short Path (plus)

题意

给定一个由 \(n\) 个点组成的完全图 \(G\)，顶点编号为 \(1\) 到 \(n\)，点权为 \(a_i\)。

定义两个点 \(<i, j>\) 间的边权为：

\(w_{u, v} = \left \{ \begin{array}{l} 0, & u=v \\ |a_u + a_v|+|a_u - a_v|, &u \neq v\end{array} \right.\)

输出 \(\sum_{i=1}^n \sum_{j=1}^n dist(i, j)\)，其中 \(dist(i, j)\) 为 \(i\) 和 \(j\) 之间的最短路。

思路

我们不妨令 \(a_u \neq a_v\)，从而有 \(w_{u, v} = 2 \cdot \max(a_u, a_v)\)。

很显然，如果对于两个点 \(u, v\)，我们不取他们的边，而是找一个点作为跳板，那么路径和一定会变大。

从而，我们只需将所有边权累加即可。

具体来说，我们先升序排个序，那么第 \(i\) 个点就有 \(i - 1\) 个点的点权比它小，所以我们将这个点权乘上 \(i - 1\) 即可。

不过当然，因为 \(<i, j>\) 和 \(<j, i>\) 都要计入，所以要乘个 \(2\)。

时间复杂度：\(O(n)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    sort(all(a));
    int ans = 0;
    for(int i=2;i<=n;i++) {
        ans += a[i] * 2 * (i - 1);
    }
    cout << ans * 2 << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

当然也可以对着样例找规律就是了

J. Tokitsukaze and Short Path (minus)

题意

给定一个由 \(n\) 个点组成的完全图 \(G\)，顶点编号为 \(1\) 到 \(n\)，点权为 \(a_i\)。

定义两个点 \(<i, j>\) 间的边权为：

\(w_{u, v} = \left \{ \begin{array}{l} 0, & u=v \\ |a_u + a_v|-|a_u - a_v|, &u \neq v\end{array} \right.\)

输出 \(\sum_{i=1}^n \sum_{j=1}^n dist(i, j)\)，其中 \(dist(i, j)\) 为 \(i\) 和 \(j\) 之间的最短路。

思路

我们不妨令 \(a_u \neq a_v\)，从而有 \(w_{u, v} = 2 \cdot \min(a_u, a_v)\)。

此时找跳板就很有用了，因为我们可以用最小的元素作为跳板，从而将边权降为 \(4 \cdot a_{\min}\)。

那么，在前一题的基础上，我们多加一个对 \(4 \cdot a_{\min}\) 取最小值的操作即可，注意此时有 \(n - i\) 个数比第 \(i\) 个数大。

时间复杂度：\(O(n)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    sort(all(a));
    int ans = 0;
    for(int i=1;i<n;i++) {
        ans += min(2 * a[i], 4 * a[1]) * (n - i) * 2;
    }
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

一开始想复杂了，写了好一会儿（

K. Tokitsukaze and Password (easy)

题意

给定一个长度为 \(n \leq 9\) 的不完整数字密码，密码由数字，\(a\)，\(b\)，\(c\)，\(d\) 以及最多 \(1\) 个 \(\_\) 组成。

令最终的密码为 \(x\)，\(x\) 需满足下面的条件：

1. \(x\) 没有前导 \(0\)，但 \(x = 0\) 是合法的；

2. \(x\) 是 \(8\) 的倍数；

3. 给定一个上限 \(y\)，需满足 \(x \leq y\)；

4. 相同字母对应的数字一定相同，不同字母对应的数字一定不相同；

5. \(\_\) 为 \(0 - 9\) 之间的任意一个数字

输出合法密码的构造方案数，对 \(10 ^ 9 + 7\) 取模。

思路

显然，我们可以直接枚举 \(a, b, c, d, \_\) 对应的数字是什么，套 \(5\) 个 \(for\) 模拟一下即可。

注意细节。

时间复杂度：\(O(C_{10}^{4} \cdot 10n^2)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int y;
    cin >> y;
    int ans = 0;
    bool st_a = false, st_b = false, st_c = false, st_d = false, st__ = false;
    for(auto e : s) {
        if(e == 'a') st_a = true;
        else if(e == 'b') st_b = true;
        else if(e == 'c') st_c = true;
        else if(e == 'd') st_d = true;
        else if(e == '_') st__ = true;
    }
    for(int a=0;a<=9;a++) {
        if(s[0] == 'a' && a == 0 && n > 1) continue;
        for(int b=0;b<=9;b++) {
            if(s[0] == 'b' && b == 0 && n > 1) continue;
            for(int c=0;c<=9;c++) {
                if(s[0] == 'c' && c == 0 && n > 1) continue;
                for(int d=0;d<=9;d++) {
                    if(s[0] == 'd' && d == 0 && n > 1) continue;
                    set<int> st;
                    int cnt = 0;
                    if(st_a) st.ep(a), cnt ++;
                    if(st_b) st.ep(b), cnt ++;
                    if(st_c) st.ep(c), cnt ++;
                    if(st_d) st.ep(d), cnt ++;
                    if(cnt != st.size()) continue;
                    for(int _=0;_<=9;_++) {
                        if(s[0] == '_' && _ == 0 && n > 1) continue;
                        string t(s);
                        for(auto &e : t) {
                            if(e == 'a') e = a + '0';
                            else if(e == 'b') e = b + '0';
                            else if(e == 'c') e = c + '0';
                            else if(e == 'd') e = d + '0';
                            else if(e == '_') e = _ + '0';
                        }
                        int x = stoi(t);
                        if((n == 1 || t[0] != '0') && x <= y && x % 8 == 0) {
                            ans ++;
                        }
                        if(!st__) break;
                    }
                    if(!st_d) break;
                }
                if(!st_c) break;
            }
            if(!st_b) break;
        }
        if(!st_a) break;
    }
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

我在打 abc .jpg

L. Tokitsukaze and Password (hard)

待补充

M. Tokitsukaze and Password (EX)

待补充