杂题乱记 - 惯性聚合

Makerlife 的小站

2025-2026 赛季游记 && 退役记 NOIP 2024 游记集训记录 CSP2024 游记板子库动态规划刷题记录数学期望学习笔记数论学习笔记 CF1000F One Occurrence 题解 P6878 [JOI 2020 Final] JJOOII 2 题解 CSP2023 游寄主定理 CF1695C Zero Path 题解字符串算法全家桶学习笔记 AT_ABC306D 题解 2023.06.03 模拟赛 Azure for Students 使用指北 AT_ABC286C 题解洛谷 AT1898 题解洛谷 CF1036A 题解洛谷 CF1040A 题解洛谷 SP3591 题解洛谷 AT278 题解洛谷 CF141B 题解洛谷 AT2561 题解洛谷 AT3525 题解洛谷 CF899B 题解洛谷 AT4787 题解洛谷 AT4810 题解洛谷 SP5450 题解

杂题乱记

Makerlife · 2024-07-15 · via Makerlife 的小站

P8186 [USACO22FEB] Redistributing Gifts S

Problem Link

有一群人收到了礼物，每个人都有对每个礼物的喜爱度列表。他们商量后决定重新分配礼物，每个人都希望可以拿到他更喜爱的礼物，至少不能差于他原来的礼物。现在需要找到每个人重新分配后，他可以拿到的最喜欢的礼物是哪一个。所有人的答案可以不是同一轮中的。

tag: Floyd, 传递闭包

Solution

可以发现礼物的分配是由交换产生的，所以从自身向他希望得到的所有礼物连一条边。由于一开始礼物的编号和人的编号一一对应，所以连边等价于连他可以和谁交换。如果多个人 (≥2\geq 2) 处于同一个环，那么说明这样交换是成立的。

如下面的数据：

可以建出如下的图：

样例解释图片

其中 1 2 3 与 1 5 4 均成环，有两种方案。

在图中，可以通过 Floyd 传递闭包判环，设 fi,jf_{i,j} 为 i→ji\to j 是否有边，特别的，fi,i=1f_{i,i}=1。那么可以轻易写出转移方程 fi,j=fi,j or (fi,k and fk,j)f_{i,j}=f_{i,j}\ \text{or}\ (f_{i,k}\ \text{and}\ f_{k,j})，考虑 bitset 优化。

传递闭包部分代码：

bitset<N> f[N];
for(int k=1;k<=3;k++) {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(f[i][j]) f[i]|=f[j];
        }
    }
}

循环 33 次避免顺序问题。

若 fu,v=fv,u=truef_{u,v}=f_{v,u}=\text{true}，则说明 u,vu, v 在一个环上。

Core Code

bitset<N> f[N];
int main() {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(a[i][j-1]==i) break;
            f[i][a[i][j]]=1;
        }
    }
    for(int k=1;k<=3;k++) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                if(f[i][j]) f[i]|=f[j];
            }
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(f[i][a[i][j]] && f[a[i][j]][i]) {
                printf("%d\n",a[i][j]);
                break;
            }
        }
    }
    return 0;
}

P1485 火枪打怪

Link

有 nn 只怪物排成一排，每只怪物的血量为 mim_i。有 kk 发子弹，每发子弹的威力为 pp。射击第 ii 只怪物时，除了这个怪物受到 pp 点伤害，它左边的怪物也可能受到溅射伤害，溅射伤害为 max⁡(0,p−(i−j)2)\max(0, p - (i - j)^2)，求最小的 pp。

tag: 二分答案, 前缀和

Solution

考虑二分答案。

注意到操作右边要比操作左边优，check 时从后往前循环。
设当前位置为 jj，操作 ii 时能对 jj 产生影响当且仅当 i−j<pi-j<\sqrt{p}。也就是说，只需要考虑 [j+1,j+p][j+1, j+\sqrt{p}] 区间操作的影响，这样的时间复杂度为 O(n2)\mathcal{O}(n^2)。
考虑优化，设区间内共操作了 sumsum 次，每次操作的位置为 ri(1≤i≤sum)r_i(1\leq i\leq sum)。那么对于 jj 受到的伤害，满足下面的式子

∑i=1sum[p−(ri,j)2]=sum×p−∑i=1sumri2+2j×∑i=1sumri−sum×j2\begin{aligned} &\sum_{i=1}^{sum}[p-(r_i, j)^2]\\ =&sum\times p-\sum_{i=1}^{sum}r_i^2+2j\times \sum_{i=1}^{sum}r_i-sum\times j^2 \end{aligned}
这样的复杂度仍为 O(n2)\mathcal{O}(n^2)，考虑预处理其中的变量。首先 sumsum 可以用后缀和优化（sumj′sum^{\prime}_j 表示使 j∼nj\sim n 血量清零需要的操作数）。观察到 rjr_j 和 rj2r_j^2 都需要求和，仍然考虑后缀和优化，令 rj′r^{\prime}_j 表示 j∼nj\sim n 所有操作位置的和，rj′2r^{\prime 2}_j 同理。优化为 O(n)\mathcal{O}(n)。

Core Code

bool check(int p) {
    int maxd = sqrt(p);
    for (int i = 1; i <= n; i++) {
        hp[i] = m[i];
    }
    for (int j = n; j >= 1; j--) {
        sum[j] = sum[j + 1];
        ri2[j] = ri2[j + 1];
        ri[j] = ri[j + 1];
        int nowsum = sum[j] - sum[j + maxd + 1];
        hp[j] -= nowsum * p
               - (ri2[j] - ri2[j + maxd + 1])
               + 2 * j * (ri[j] - ri[j + maxd + 1])
               - nowsum * j * j;
        while (hp[j] >= 0) {
            hp[j] -= p;
            sum[j]++;
            ri2[j] += j * j;
            ri[j] += j;
            if (sum[j] > k) return 0;
        }
    }
    return 1;
}

P6600 「EZEC-2」字母

Link

在 0/10/1 矩阵中，找到有多少个满足下面要求的横长 ww 竖长 hh 的 T 字形

w≥aw\geq a

h≥bh\geq b

w×h≥sw\times h\geq s

w+h≥xw+h\geq x

tag: 二维前缀和

Solution

一眼非常像 NOIP2022 T1。

首先想如何 brute，先枚举矩阵中每个为 11 的点作为 T 的中心点，用前缀和记录它的左、右、下各有多少个 11，不妨分别设为 suml,sumr,sumdsuml, sumr, sumd。然后暴力判断这些 11 能组成多少个中心点重叠的符合条件的 T。

考虑优化掉判断符合条件部分的算法，暴力枚举横长竖长，fw,hf_{w, h} 表示横长 ww 竖长 hh 的 T 字形是否满足条件。时间复杂度 O(n2)\mathcal{O}(n^2)。

计算答案时，对于每个位置 (i,j)(i,j)，枚举它可能的横长竖长，显然对于这个位置 wmax=min⁡{sumli,j,sumri,j}×2−1, hmax=sumdi,jw_{max} = \min\{suml_{i, j}, sumr_{i, j}\}\times 2 - 1,\ h_{max} = sumd_{i, j}。即 ansi,j=∑w=3wmax∑h=2hmaxfw,hans_{i, j} = \sum_{w = 3}^{w_{max}}\sum_{h = 2}^{h_{max}} f_{w, h}，时间复杂度过高。

继续优化掉这一部分，注意到是统计区间和，想到二维前缀和，用 sumi,jsum_{i, j} 表示 ∑w=3i∑h=2jfw,h\sum_{w = 3}^{i}\sum_{h = 2}^{j} f_{w, h}。简单容斥一下得到 sumi,j=sumi−1,j+sumi,j−1+fi,j−sumi−1,j−1sum_{i, j} = sum_{i - 1, j} + sum_{i, j - 1} + f_{i, j} - sum_{i - 1, j - 1}。

这样总体复杂度 O(n2)\mathcal{O}(n^2)。

Core Code

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (in[i][j] == '0') suml[i][j] = 0;
        else suml[i][j] = suml[i][j - 1] + 1;
    }
    for (int j = m; j >= 1; j--) {
        if (in[i][j] == '0') sumr[i][j] = 0;
        else sumr[i][j] = sumr[i][j + 1] + 1;
    }
}
for (int j = 1; j <= m; j++) {
    for (int i = n; i >= 1; i--) {
        if (in[i][j] == '0') sumd[i][j] = 0;
        else sumd[i][j] = sumd[i + 1][j] + 1;
    }
}
for (int w = 3; w <= m; w++) {
    for (int h = 2; h <= n; h++) {
        if ((w & 1) && w >= a && h >= b && w * h >= s && w + h >= x) {
            f[w][h] = 1;
        }
        sum[w][h] = sum[w - 1][h] + sum[w][h - 1] + f[w][h] - sum[w - 1][h - 1];
    }
}
int ans = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        int w = min(suml[i][j], sumr[i][j]) * 2 - 1;
        int h = sumd[i][j];
        if (in[i][j] == '1') ans += sum[w][h];
    }
}
cout << ans << endl;

P7915 [CSP-S 2021] 回文

Link

给定一个整数序列 a1,a2,…,a2na_1, a_2,\dots, a_{2n}，保证包含 1∼n1\sim n 的数各两次。可以在 aa 序列的首或尾选择一个数 push_back 到 bb 序列中并删除 aa 中的这个数，使得 bb 为一个回文串。每次操作记为 L 或 R，表示从开头或结尾选择元素，输出操作串字典序最小的方案。

tag: 双端队列

Solution

以下以第一步取 a1a_1 为例，取 a2na_{2n} 同理。

由于要构成回文串，对于有且仅有的一个 kk 使得 a1=aka_1=a_k，aka_k 一定最后取到。

所以题目可以转化为，对于 a2…ak−1a_2\dots a_{k-1}，从前向后取元素，而对于 ak+1…a2na_{k+1}\dots a_{2n}，从后向前取元素。

即可以把这两部分看作一个栈，从第二次操作开始，每次从栈顶取元素，那么应该从哪边取呢？

可以从最后的操作开始分析，倒数第二次操作只能取 ak−1a_{k-1} 或 ak+1a_{k+1}，由于要构成回文串，就需要满足栈顶等于 aka_k 两侧的元素。那么想到可以将两侧转化为双端队列，每次满足有其中一个队列的队首等于任意一个的队尾，如下图

一个 string 需要注意的点，每次 s = "L" + s 的复杂度是 O(n)\mathcal{O}(n) 的，可以通过 s.push_back("L") 最后 reverse(s.begin(), s.end()) 来解决。

Core Code

bool check_l() {
    int k;
    ans = "L";
    revans = "L";
    for (int i = 2; i <= n; i++) {
        if (a[i] == a[1]) {
            k = i;
            break;
        }
    }
    deque<int> st1, st2;
    for (int i = 2; i < k; i++) st1.push_back(a[i]);
    for (int i = k + 1; i <= n; i++) st2.push_front(a[i]);
    while (!st1.empty() || !st2.empty()) {
        if (st1.size() > 1 && st1.front() == st1.back()) {
            ans.push_back('L');
            revans.push_back('L');
            st1.pop_front(); st1.pop_back();
        } else if (st1.size() && st2.size() && st1.front() == st2.back()) {
            ans.push_back('L');
            revans.push_back('R');
            st1.pop_front(); st2.pop_back();
        } else if (st1.size() && st2.size() && st2.front() == st1.back()) {
            ans.push_back('R');
            revans.push_back('L');
            st2.pop_front(); st1.pop_back();
        } else if (st2.size() > 1 && st2.front() == st2.back()) {
            ans.push_back('R');
            revans.push_back('R');
            st2.pop_front(); st2.pop_back();
        } else {
            return 0;
        }
    }
    return 1;
}
bool check_r() {
    int k;
    ans = "R";
    revans = "L";
    for (int i = 1; i < n; i++) {
        if (a[i] == a[n]) {
            k = i;
            break;
        }
    }
    deque<int> st1, st2;
    for (int i = 1; i < k; i++) st1.push_back(a[i]);
    for (int i = k + 1; i < n; i++) st2.push_front(a[i]);
    while (!st1.empty() || !st2.empty()) {
        if (st1.size() > 1 && st1.front() == st1.back()) {
            ans.push_back('L');
            revans.push_back('L');
            st1.pop_front(); st1.pop_back();
        } else if (st1.size() && st2.size() && st1.front() == st2.back()) {
            ans.push_back('L');
            revans.push_back('R');
            st1.pop_front(); st2.pop_back();
        } else if (st1.size() && st2.size() && st2.front() == st1.back()) {
            ans.push_back('R');
            revans.push_back('L');
            st2.pop_front(); st1.pop_back();
        } else if (st2.size() > 1 && st2.front() == st2.back()) {
            ans.push_back('R');
            revans.push_back('R');
            st2.pop_front(); st2.pop_back();
        } else {
            return 0;
        }
    }
    return 1;
}
int main() {
    T = read();
    while (T--) {
        n = read() * 2;
        for (int i = 1; i <= n; i++) {
            a[i] = read();
        }
        if (check_l()) {
            reverse(revans.begin(), revans.end());
            cout << ans + revans << endl;
        } else if (check_r()) {
            reverse(revans.begin(), revans.end());
            cout << ans + revans << endl;
        }
        else {
            cout << -1 << endl;
        }
    }
    return 0;
}

P1053 [NOIP2005 提高组] 篝火晚会

Link

佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有 n(3≤n≤50000)n(3\le n \le 50000) 个同学，编号从 11 到 nn。一开始，同学们按照 1,2,⋯ ,n1,2,\cdots ,n 的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。

佳佳可向同学们下达命令，每一个命令的形式如下：

(b1,b2,...bm−1,bm)(b_1, b_2,... b_{m-1}, b_m)

这里 mm 的值是由佳佳决定的，每次命令 mm 的值都可以不同。这个命令的作用是移动编号是 b1,b2,⋯ ,bmb_1,b_2,\cdots, b_m 的这 mm 个同学的位置。要求 b1b_1 换到 b2b_2 的位置上，b2b_2 换到 b3b_3 的位置上，……，要求 bmb_m 换到 b1b_1 的位置上。执行每个命令都需要一些代价。我们假定如果一个命令要移动 mm 个人的位置，那么这个命令的代价就是 mm。我们需要佳佳用最少的总代价实现同学们的意愿，你能帮助佳佳吗？

选择的 mm 个人不必连续。

tag: 环

Solution

发现如果有 kk 个人在初始环和目标环中位置相等，那么剩下的人只需要移动 n−kn-k 次即可，因为他们的移动一定可以组成环。

但是建出来的环不一定能使 kk 取到最大值，所以可以通过类似转一下的方式。

初始环	1	2	3	4	5	6
目标环	2	3	4	5	6	1
差值	1	1	1	1	1	1

注意到相同差值的位置可以通过旋转变成 00，所以 kmaxk_{max} 就是最多的相同差值的数量，答案即为 n−kmaxn-k_{max}。

考虑如何构造目标环，首先设 li,ril_i, r_i 分别表示第 ii 个要求的相邻的点，钦定 an=l1,a1=1a_n=l_1, a_1=1。接下来，每次判断第 ii 点的相邻两数是否在环中，若不在则加入进去，然后继续寻找新加入的这个点额相邻两数，知道环中的节点数为 nn。

注意计算差值时，不能直接 ai−ia_i-i，需要加 nn 后 mod n\bmod{n}。另外需要分别计算初始环顺时针和逆时针排列的方式。

Core Code

for (int i = 1; i <= n; i++) {
    if ((i != l[ l[i] ] && i != r[ l[i] ]) || (i != l[ r[i] ] && i != r[ r[i] ])) {
        cout << -1 << endl;
        return 0;
    }
}
a.push_back(0);
a.push_back(1);a.push_back(l[1]);
vis[1] = vis[l[1]] = 1;
int now = l[1];
while (a.size() != n + 1) {
    if (!vis[ l[now] ]) {
        a.push_back(l[now]);
        vis[l[now]] = 1;
        now = l[now];
    } else if (!vis[ r[now] ]) {
        a.push_back(r[now]);
        vis[r[now]] = 1;
        now = r[now];
    }
}
int maxn = 0;
for (int i = 1; i <= n; i++) {
    t[(a[i] + n - i) % n]++;
}
for (int i = 0; i < n; i++) {
    maxn = max(maxn, t[i]);
}
for (int i = 0; i <= n; i++) t[i] = 0;
for (int i = 1; i <= n; i++) {
    t[(a[i] + n - (n - i + 1)) % n]++;
}
for (int i = 0; i < n; i++) {
    maxn = max(maxn, t[i]);
}
cout << n - maxn << endl;

AT_joi2015ho_c JOI Park

Link

时值 20XX20\text{XX} 年，IOI 国为了给办奥赛做准备，将要修缮 IOI 国中的 JOI 公园。JOI 公园里有 NN 个广场，这些广场从 11 到 NN 编号。有 MM 条道路连接各个广场，这些道路从 11 到 MM 编号。第 i(1≤i≤M)i(1 \leq i \leq M) 条道路是一条连接第 AiA_i 和第 BiB_i 个广场的双向边，长度为 DiD_i。任意两个广场间一定有道路（直接或间接）相连。

修缮计划如下：首先，选择一个自然数 XX，将和第一个广场距离等于 XX 或在 XX 以下的所有广场（含第一个广场）相互之间连结一条地下通道。广场 ii 和广场 jj 的距离指，从广场 ii 到广场 jj 经过的道路长度总和的最小值。定义 CC 为一个与修筑地下通道花费有关的量（CC 是整数）。修筑所有地下通道的花费为 C×XC\times X。

接下来，撤去已经通过地下通道连接的广场之间的道路。撤去道路的花费不计。

最后，将没有被撤去的道路进行修补，长为 dd 的道路修补的花费为 dd。

修缮计划实施之前，JOI 公园没有地下通道。请求出 JOI 公园修缮花费总和的最小值。

需要注意的是删除的道路不只是 1→u1\to u，还包含 1→u→v(disu<disv)1\to u\to v(dis_u<dis_v)。

tag: 最短路

Solution

首先注意到选择的 XX 一定是某一个点 uu 到 11 节点的距离，所以先 Dijkstra 跑一遍预处理 disudis_u，然后从小到大排序后枚举每个 disudis_u 来计算答案。比如样例中的遍历顺序为 1,3,2,4,51, 3, 2, 4, 5，可以发现，在枚举到靠后的节点时，它前面的所有点之间的路径都要被拆掉，这些点到当前节点的路径也要被拆掉（如果存在），所以当前拆掉的边可以由上一步拆掉的边转移而来，这也是从小到大的排序的意义。

一个例子，计算完 22 后，1→21\to 2 边会被删掉，按照上面的计算方法，下一步计算 33，此时应该拆掉 1→31\to 3 和 2→32\to 3。

Core Code

#define int ll
int n, m, c;
struct node {
    int pos, dis;
    bool operator<(const node& x) const {
        return dis > x.dis;
    }
};
struct edge {
    int v, w;
};
vector<edge> e[N];
bitset<N> vis;
node dis[N];
int sum = 0ll;
void dij(int u) {
    for (int i = 1; i <= n; i++) {
        dis[i].dis = INF;
    }
    dis[1].dis = 0ll;
    priority_queue<node> q;
    q.push({1, 0});
    while (!q.empty()) {
        int u = q.top().pos;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1ll;
        for (auto x : e[u]) {
            int v = x.v, w = x.w;
            if (dis[v].dis > dis[u].dis + w) {
                dis[v].dis = dis[u].dis + w;
                if (!vis[v]) q.push({v, dis[v].dis});
            }
        }
    }
}
signed main() {
    n = read(); m = read(); c = read();
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read(), w = read();
        e[u].push_back({v, w});
        e[v].push_back({u, w});
        sum += w;
    }
    for (int i = 1; i <= n; i++) {
        dis[i].pos = i;
    }
    dij(1);
    sort(dis + 1, dis + n + 1);
    int minn = INF;
    int last = 0;
    vis.reset();
    for (int i = n; i >= 1; i--) {
        int ans = dis[i].dis * c;
        ans += sum;
        vis[dis[i].pos] = 1;
        for (auto x : e[dis[i].pos]) {
            int v = x.v, w = x.w;
            if (vis[v]) last += w;
        }
        minn = min(minn, ans - last);
    }
    cout << minn << endl;
    return 0;
}

AGC001C Shorten Diameter

给定一颗 nn 个节点的树，你需要删除一些叶子使得树的直径小于等于 kk。求最少的删除的点的个数。

tag: 树的直径

Solution

将题目转化为寻找一个中心，使中心左右两边最多延伸 k2\dfrac{k}{2} 个节点，记能延伸到的节点数为 tottot。删除的点即为 n−totn-tot。

如果 kk 是偶数，一定有一个中点，枚举中点即可。

如果 kk 是奇数，一定有相邻的两个中点，枚举即可。

Core Code

int tot;
void dfs(int u, int fa, int step) {
    tot++;
    if (step == 0) return;
    for (auto v : e[u]) {
        if (v == fa) continue;
        dfs(v, u, step - 1);
    }
}
int main() {
    int ans = INF;
    if (!(k & 1)) {
        for (int i = 1; i <= n; i++) {
            tot = 0;
            dfs(i, 0, k / 2);
            ans = min(ans, n - tot);
        }
    } else {
        for (int u = 1; u <= n; u++) {
            for (auto v : e[u]) {
                tot = 0;
                dfs(v, u, k / 2);
                dfs(u, v, k / 2);
                ans = min(ans, n - tot);
            }
        }
    }
}

P8677 [蓝桥杯 2018 国 A] 采油

Link

tag: 贪心

Solution

第一问显然最优情况下答案为边权和的两倍。

考虑第二问，对于一个点 uu，至少需要耗费 SuS_u 的人。

首先认为 Bu≥SuB_u\geq S_u，因为即使 Bu<SuB_u<S_u，该节点也需要 SuS_u 的人。

若只有一个节点，那么耗费的人显然为 BuB_u；

若有两个节点，不妨设为 xx 和 yy，且 Bx−Sx>By−SyB_x-S_x>B_y-S_y，即 xx 剩下的人数比 yy 多，那么感性理解肯定要先走 xx，才能充分发挥剩余的人。试图证一下，先 xx 后 yy 的总花费为 max⁡{Bx,Bx+By−(Bx−Sx)}=max⁡{Bx,By+Sx}\max\{B_x, B_x+B_y-(B_x-S_x)\}=\max\{B_x, B_y+S_x\}，则先 yy 后 xx 的总花费为 max⁡{By,Bx+Sy}\max\{B_y, B_x+S_y\}，将上面的式子移项可得 By+Sx<Bx+SyB_y+S_x<B_x+S_y，结论得证；

将结论推广到同一层上有 kk 个节点，可以通过两两依次缩点的形式转化为两个节点。

再考虑更一般的情况，在满足第一问的限制下，即按照最短路径，一定是先遍历完每个子树最短。所以搜到一个点时，先将这个点为根的所有子树缩点，按照剩余人数排序，递归继续缩点。

注意搜索时需要从 B−SB-S 最大的点开搜。

Core Code

struct node {
    int b, s;
    bool operator<(const node &x) const {
        return b - s > x.b - x.s;
    }
    node operator+(const node &x) const {
        node res;
        res.b = max(b, s + x.b), res.s = s + x.s;
        return res;
    }
}a[N];
node dfs(int u, int fa) {
    vector<node> p;
    p.push_back(a[u]);
    for (auto v : e[u]) {
        if (v == fa) continue;
        p.push_back(dfs(v, u));
    }
    node res;
    res.b = res.s = 0;
    sort(p.begin(), p.end());
    for (auto v : p) res = res + v;
    return res;
}
int main() {
    n = read();
    int sum = 0;
    int maxn = 0, maxpos = 1;
    for (int i = 1; i <= n; i++) {
        a[i].b = read();
    }
    for (int i = 1; i <= n; i++) {
        a[i].s = read();
        a[i].b = max(a[i].b, a[i].s);
        if (a[i].b - a[i].s > maxn) {
            maxn = a[i].b - a[i].s;
            maxpos = i;
        }
    }
    for (int i = 1; i < n; i++) {
        int v = read(), w = read();
        e[i + 1].push_back(v);
        e[v].push_back(i + 1);
        sum += w;
    }
    cout << sum * 2 << " " << dfs(maxpos, 0).b << '\n';
    return 0;
}

P2659 美丽的序列

Link

给定一个序列，找到一个区间使得区间最小值与区间长度的乘积最大，输出乘积。

tag: 单调栈

Solution

维护区间最小值，想到用单调栈。

单调递增栈，当遍历后面的元素时，如果此时元素比之前元素最小值小，那么之前元素的最小值地位从当前元素开始失效，也就可以得到之前元素所管辖的区间右端点。同理，也可以找到当前元素管辖区间的左端点，即为弹栈后的栈顶，也就是前面第一个大于当前元素的位置。

Core Code

for (int i = 1; i <= n; i++) {
    q[i].l = 1, q[i].r = n;
    while (!st.empty() && a[st.top()] > a[i]) {
        q[st.top()].r = i - 1;
        st.pop();
    }
    if (!st.empty()) q[i].l = st.top() + 1;
    st.push(i);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
    ans = max(ans, (q[i].r - q[i].l + 1) * a[i]);
}

P12177 [蓝桥杯 2025 省 Python B] 异或和

Link

求：

∑i=1n∑j=i+1n(ai⊕aj)×(j−i)\sum_{i=1}^{n} \sum_{j=i+1}^{n} (a_i \oplus a_j) \times (j - i)

tag: 二进制按位

Solution

按位考虑，注意到为 1⊕0=11\oplus0=1，也就是说只有两个数当前位不同才能产生贡献。

按位枚举，对于每一位的数正向扫，统计之前有多少个数可以产生贡献 numnum，和产生贡献数的位置和 lsumlsum。

当前枚举到第 jj 个数。

如果当前位为 00，那么产生的贡献为 2i×(j×num−lsum)2^i\times (j\times num - lsum)；
如果为 11，各变量直接用总数减去 11 的即可。

时间复杂度 O(nlog⁡n)\mathcal{O}(n\log n)。

Core Code

for (int i = 0; i <= 20; i++) {
    int lsum = 0, num = 0;
    for (int j = 1; j <= n; j++) {
        int v = ((a[j] >> i) & 1);
        if (!v) {
            ans += (1 << i) * (num * j - lsum);
        } else {
            ans += (1 << i) * ((j - 1 - num) * j - ((j - 1) * j / 2 - lsum));
            num++, lsum += j;
        }
    }
}

P3831 [SHOI2012] 回家的路

Link

有一个 n×nn\times n 的网格图，给定起点和终点，给定若干格点作为换乘站，非换乘站只能沿之前的方向行走，在换乘站可换向。

换乘花费为 11，行走一格花费为 22，求最小花费。

tag：分层图, 最短路

Solution

考虑将起点、终点和可换乘的格点作为节点，对两两直接可达的节点连边。

显然同一行或同一列内相邻两换乘站应当连边，想到分层图。

所有行为一层、所有列为一层建图。同时，上下两层对应相同的节点连边权为 11 的边表示可以换乘。在这个图上跑最短路即可。

Core Code

bool cmpx(node a, node b) {
    if (a.x != b.x) return a.x < b.x;
    else return a.y < b.y;
}
bool cmpy(node a, node b) {
    if (a.y != b.y) return a.y < b.y;
    else return a.x < b.x;
}
int main() {
    m = read(), n = read();
    for (int i = 1; i <= n; i++) {
        int x = read(), y = read();
        p[i].x = x, p[i].y = y, p[i].id = i;
        e[i].push_back({i + n + 2, 1});
        e[i + n + 2].push_back({i, 1});
    }
    p[0].x = read(), p[0].y = read(), p[0].id = 0;
    p[n + 1].x = read(), p[n + 1].y = read(), p[n + 1].id = n + 1;
    sort(p, p + n + 2, cmpy);
    for (int i = 0; i <= n; i++) {
        if (p[i].y == p[i + 1].y) {
            int dis = abs(p[i].x - p[i + 1].x);
            e[p[i].id].push_back({p[i + 1].id, 2 * dis});
            e[p[i + 1].id].push_back({p[i].id, 2 * dis});
        }
    }
    sort(p, p + n + 2, cmpx);
    for (int i = 0; i <= n; i++) {
        if (p[i].x == p[i + 1].x) {
            int dis = abs(p[i].y - p[i + 1].y);
            e[p[i].id + n + 2].push_back({p[i + 1].id + n + 2, 2 * dis});
            e[p[i + 1].id + n + 2].push_back({p[i].id + n + 2, 2 * dis});
        }
    }
    int ans = INF;
    w.s = 0;
    w.dij();
    ans = min({w.dis[n + 1], w.dis[n + 1 + n + 2]});
    w.s = n + 2;
    w.vis.reset();
    w.dij();
    ans = min({ans, w.dis[n + 1], w.dis[n + 1 + n + 2]});
    cout << ans << endl;
}

P3594 [POI 2015 R3] 狼坑 Trous de loup

Link

给定一个长度为 nn 的序列，你有一次机会选中一段连续的长度不超过 dd 的区间，将里面所有数字全部修改为 00。找到最长的一段连续区间，使得该区间内所有数字之和不超过 pp。

tag: 双指针, 单调队列

Solution

首先容易得到，选择的区间长度一定为 dd 最优。

考虑暴力，枚举左右端点和选择的区间，时间复杂度 O(n3)\mathcal{O}(n^3)。

考虑优化，不难想到双指针，可以把暴力的枚举左右端点部分优化掉，时间复杂度 O(n2)\mathcal{O}(n^2)。

观察最终答案的式子：

max⁡l,r(r−l+1)s.t.∑i=lrwi−max⁡k∈[l,r−d+1]∑j=kk+d−1wj≤p\max_{l, r} \left(r - l + 1\right)\quad \text{s.t.} \quad\sum_{i=l}^r w_i - \max_{k\in \left[l, r - d + 1\right]}\sum_{j=k}^{k+d-1} w_j \leq p

注意到复杂度瓶颈在于 max⁡k∈[l,r−d+1]∑j=kk+d−1wj\max_{k\in \left[l, r - d + 1\right]}\sum_{j=k}^{k+d-1} w_j 的计算，发现可以用单调队列维护这个值。当右端点右移时，加入新的区间和，同时弹出不在区间内的区间和。

Core Code

deque<int> q; // [i - d + 1, i]
q.emplace_back(d);
int ans = d;
for (int r = d + 1; r <= n; r++) {
    while (!q.empty() &&
           sum[q.back()] - sum[q.back()-d] <= sum[r] - sum[r-d]) {
            q.pop_back();
        }
    q.emplace_back(r);
    while (!q.empty() && q.front() - d + 1 < l) q.pop_front();
    while (!q.empty() && sum[r] - sum[l-1] - (sum[q.front()] - sum[q.front()-d]) > p) {
        l++;
        while (!q.empty() && q.front() - d + 1 < l) q.pop_front();
    }
    ans = max(ans, r - l + 1);
}

P10957 环路运输

Link

在一条环形公路旁均匀地分布着 NN 座仓库，编号为 1∼N1 \sim N，编号为 ii 的仓库与编号为 jj 的仓库之间的距离定义为 dist(i,j)=min⁡⁡(∣i−j∣,N−∣i−j∣)dist(i,j)=\min⁡(|i-j|,N-|i-j|)，也就是逆时针或顺时针从 ii 到 jj 中较近的一种。每座仓库都有权 aia_i。

在 ii 和 jj 两座仓库之间运送货物需要的代价为 ai+aj+dist(i,j)a_i+a_j+dist(i,j)。求最大代价。

tag: 单调队列

Solution

首先断环为链，考虑化简最终答案的式子：

fi,j=ai+aj+min⁡ ⁣(∣i−j∣, n−∣i−j∣)(1≤j<i≤n)=ai+aj+(i−j)(1≤j<i≤2n, i−j<⌊n2⌋)ans=max⁡1≤j<i≤2nfi,j=max⁡1≤j<i≤2n,i−j<⌊n2⌋(ai+i)+(aj−j).\begin{aligned} f_{i,j} &= a_i + a_j + \min\!\left( |i-j|,\; n - |i-j| \right) &&\left(1 \leq j < i \leq n\right) \\ &= a_i + a_j + (i-j) &&\left(1 \leq j < i \leq 2n,\; i-j < \left\lfloor \frac{n}{2} \right\rfloor \right)\\ \text{ans} &= \max_{1 \leq j < i \leq 2n} f_{i,j} \\ &= \max_{1 \leq j < i \leq 2n, i-j < \left\lfloor \frac{n}{2} \right\rfloor} \left(a_i + i \right) + \left(a_j - j \right). \end{aligned}

注意到 (ai+i)(a_i + i) 与 jj 无关，可以枚举 ii，然后在 [i−⌊n2⌋,i−1]\left[i - \left\lfloor\dfrac{n}{2}\right\rfloor, i - 1\right] 范围内寻找 aj−ja_j - j 的最大值，可以用单调队列维护这个值。

Core Code

for (int i = 1; i <= 2 * n; i++) {
    while (!q.empty() && i - q.front() > n / 2) {
        q.pop_front();
    }
    if (!q.empty()) ans = max(ans, a[q.front()] - q.front() + a[i] + i);
    while (!q.empty() && a[q.back()] - q.back() <= a[i] - i) {
        q.pop_back();
    }
    q.push_back(i);
}

P1948 [USACO08JAN] Telephone Lines S

Link

给定一个简单无向图，有边权。最小化 1→n1\to n 路径上第 k+1k + 1 大的边权。

tag: 二分答案, 最短路

Solution

二分答案枚举答案 mid\text{mid}，将边权大于 mid\text{mid} 的边权设为 11，否则设为 00，然后跑最短路，判断 1→n1\to n 最短路是否小于等于 kk。

Core Code

auto check = [&](int mid) -> bool{
    vector<int> dis(n + 1, numeric_limits<int>::max() / 2);
    vector<char> vis(n + 1);
    dis[1] = 0;
    priority_queue<Node> q;
    q.push(Node{1, 0});
    while (!q.empty()) {
        int u = q.top().pos;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto x : e[u]) {
            int v = x.v, w = x.w;
            if (w > mid) w = 1;
            else w = 0;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!vis[v]) q.push(Node{v, dis[v]});
            }
        }
    }
    if (dis[n] <= k) return true;
    else return false;
};
int l = 0, r = MAXN;
while (l < r) {
    int mid = (l + r) >> 1;
    if (check(mid)) r = mid;
    else l = mid + 1;
}

P10454 奇数码问题

Link

给定一个初始矩阵和一个目标矩阵。其中的 0 可以与其四联通的块交换位置。通过若干次操作，判断是否能从初始矩阵变为目标矩阵。

tag: 逆序对

Solution

考虑将矩阵按行展开为一维数组，忽略 0。

考虑两种操作：上下移动和左右移动。

左右移动：注意到元素在忽略 0 后相对顺序不变，所以不会改变逆序对数量的奇偶性；
上下移动：考虑一个元素 xx 向上移动一格，有：
1
2
3
5 2 8 5 _ 8 1 _ 3 1 2 3 4 6 7 4 6 7
可以发现这样会对新位置与原位置之间的 n−1n-1 个数产生的贡献造成影响，即原来的逆序对和非逆序对都会变成相反的关系。由于 nn 是奇数，所以这样并不会改变逆序对数量的奇偶性。

所以，两矩阵可互相转化和充要条件是两序列的逆序对数量奇偶性相同。

P2512 [HAOI2008] 糖果传递

有 nn 个小朋友坐成一圈，每人有 aia_i 个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 11。求最小代价使得每人糖果数相同。

tag: 贪心, 推式子

Solution

我们设每人最终糖果数为 xˉ\bar x，每人向左边传递的糖果数为 xix_i，则有：

{ai+xi+1−xi=xˉ,1≤i<nan+x1−xn=xˉ,i=n\begin{cases} a_i+x_{i+1}-x_i &= \bar x ,&& 1\leq i< n\\ a_n+x_1-x_n &= \bar x ,&& i=n\\ \end{cases}

对 1≤i<n1\leq i<n 简单变形，即有：

xi+1=xˉ+xi−aix_{i+1} = \bar x+x_i-a_i

将 x=i+1x=i+1 带入到 x=i+2x=i+2 的式子中，递推，化简可得：

xn=(n−1)xˉ+x1−∑i=1n−1aix_n = (n-1)\bar x+x_1-\sum_{i=1}^{n-1}a_i

设 ci=∑j=1iaj−ixˉc_i=\sum_{j=1}^{i} a_j-i\bar x，则有：

xi=x1−cix_i=x_1-c_i

题目要求最小化 ∑i=1n∣xi∣\sum_{i=1}^{n} |x_i|，即最小化 ∑i=1n∣x1−ci∣\sum_{i=1}^{n} |x_1-c_i|。注意到 ∑i=1n∣x1−ci∣\sum_{i=1}^{n} |x_1-c_i| 在 x1x_1 处取得最小值时，x1x_1 为 cic_i 的中位数。

Core Code

vector<int> sum(n + 1);
for (int i = 1; i <= n; i++) {
    int a = read();
    sum[i] = sum[i - 1] + a;
}
for (int i = 1; i <= n; i++) {
    c[i] = i * sum[n] / n - sum[i];
}
sort(c.begin() + 1, c.begin() + n + 1);
int ans = 0;
int mid = c[(n + 1) >> 1];
for (int i = 1; i <= n; i++) {
    ans += abs(mid - c[i]);
}

P14401 [JOISC 2016] 电报 / Telegraph

Link

有一个 nn 个点的有向图，每个点的出度均为 11。给出这 nn 个点初始指向的点 AiA_i，和改变这个点指向的目标所需要的价值 CiC_i。求让所有点强连通的最小花费。

tag: 贪心

Solution

首先题意可以转化为最小代价使得图变为包含所有 nn 个点的大环。

考虑证明这一点：若存在一点 uu 不在环上，则其一定指向环，但环上的点因为唯一出度已被占用而无法指回 uu，所以图不连通。若存在多个环，环之间不连通。

将总代价转化为 ∑Ci\sum C_i 减去保留下来的边代价和，即最大化保留下来的边的权值和。

我们想保留一些原始边，并添加一些新边（修改后的边）将他们连成一个大环，那么保留下来的边集一定满足：

不存在环。若存在一个环且环外有别的点，则该环无法通过加边与环外的点连通。
图中每个点入度不超过 11。因为在最终的大环中每个点入度为 11。

考虑贪心删掉不满足条件的边，显然对于一个入边数量大于 11 的节点 uu，其所有入边中我们保留且一定保留权值最大的一条边。

经过上述操作，可以得到一个由若干个链和环构成的新图。我们仍需打破得到的环来满足要求。

仍然考虑贪心，对于每个环，可以干掉环上的一条边，或者其替换为原图中指向该点的次优边。对于环上的每个点，其换边的代价即为当前最优入边的权值减次优入边的权值。特别地，若仅有一条入边，代价即为该边权值。

特判初始即为一个大环的情况，因为此时我们无需将该环断掉重连。

Core Code

vector<vector<pair<int, int>>> in(n + 1);
for (int i = 1; i <= n; i++) {
    int a = read(), c = read();
    p[i] = Node{a, c};
    sumc += c;
    in[a].emplace_back(make_pair(i, c));
}
auto check = [&]() -> bool {
    for (int i = 1; i <= n; i++) {
        if (in[i].size() != 1) return 0;
    }
    vector<char> vis(n + 1, 0);
    int curr = 1, cnt = 0;
    while (!vis[curr]) {
        vis[curr] = 1;
        curr = p[curr].a;
        cnt++;
    }
    if (cnt == n) return 1;
    else return 0;
};
if (check()) {
    cout << 0 << '\n';
    return 0;
}
int sum = 0;
vector<int> from(n + 1);
for (int i = 1; i <= n; i++) {
    if (in[i].size() >= 1) {
        sort(in[i].begin(), in[i].end(), [](const pair<int, int>& x, const pair<int, int>& y){
            return x.second > y.second;
        });
        sum += in[i][0].second;
        from[i] = in[i][0].first;
    }
}
vector<int> vis(n + 1, 0); // 0: not visited, 1: in current path, 2: have visited
for (int i = 1; i <= n; i++) {
    if (vis[i] == 2) continue;
    int curr = i;
    vector<int> nodes;
    nodes.reserve(n);
    while (curr != 0 && vis[curr] == 0) {
        vis[curr] = 1;
        nodes.emplace_back(curr);
        curr = from[curr];
    }
    if (curr != 0 && vis[curr] == 1) {
        int minn = numeric_limits<int>::max() / 2;
        bool flag = 0;
        for (int nw : nodes) {
            if (nw == curr) flag = 1;
            if (!flag) continue;
            int diff = in[nw][0].second;
            if (in[nw].size() > 1) diff -= in[nw][1].second;
            minn = min(minn, diff);
        }
        sum -= minn;
    }
    for (int nw : nodes) {
        vis[nw] = 2;
    }
}
cout << sumc - sum << '\n';

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

Makerlife 的小站

P8186 [USACO22FEB] Redistributing Gifts S

Solution

Core Code

P1485 火枪打怪

Solution

Core Code

P6600 「EZEC-2」字母

Solution

Core Code

P7915 [CSP-S 2021] 回文

Solution

Core Code

P1053 [NOIP2005 提高组] 篝火晚会

Solution

Core Code

AT_joi2015ho_c JOI Park

Solution

Core Code

AGC001C Shorten Diameter

Solution

Core Code

P8677 [蓝桥杯 2018 国 A] 采油

Solution

Core Code

P2659 美丽的序列

Solution

Core Code

P12177 [蓝桥杯 2025 省 Python B] 异或和

Solution

Core Code

P3831 [SHOI2012] 回家的路

Solution

Core Code

P3594 [POI 2015 R3] 狼坑 Trous de loup

Solution

Core Code

P10957 环路运输

Solution

Core Code

P1948 [USACO08JAN] Telephone Lines S

Solution

Core Code

P10454 奇数码问题

Solution

P2512 [HAOI2008] 糖果传递

Solution

Core Code

P14401 [JOISC 2016] 电报 / Telegraph

Solution

Core Code