题解：P10928 走廊泼水节
发表于|更新于|题解
|浏览量:
回顾 kruskal：
取边权最小的一条边，若两个点在不同连通块（并查集），则连边合并。
我们把以上规则改一下：
如果点 $A$ 的老大的小弟数<点 $B$ 的老大的小弟数，$A$ 成为 $B$ 小弟。
反之，$B$ 成为 $A$ 小弟。
我们定义 $s_i$ 是点 $i$ 的老大的小弟数，$w$ 是 $a$ 到 $b$ 的边权。
贡献和为：$(s_A×s_B−1) \times (w+1)$。
代码楼上楼下都已经写的很明白了，我就不在赘述了。
文章作者: heyZzz
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 heyZzz's OI Blog！
相关推荐
2026-03-09
题解：CF333B Chips
原题传送门 题目大意： 有一个 $n \times n$ 的棋盘，$m$ 个格子是障碍物，然后移动芯片使它们返回到初始对边位置，不能经过障碍物、重叠或交换位置。问最多可以放置多少个芯片完成游戏。 思路： 本题直接按题意模拟即可： 使用桶记录障碍，$a_i$ 代表第 $i$ 行的芯片个数，同理 $b_i$ 代表第 $i$ 列的芯片个数。 如果第 $i$ 行或第 $j$ 没有芯片，$cnt+1$。 如果相遇，就是 $n$ 为奇数且中间行且列有值，$cnt-1$。 下面是样例 $3$ 的解释： 列1 列2 列3 列4 行1 无芯片 可放芯片 可放芯片 无芯片 行2 放芯片 ______ ______ 放芯片 行3 障碍物 障碍物 障碍物 可放芯片 行4 无芯片 可放芯片 可放芯片 无芯片 行2的两个芯片可以连通，$cnt=1$。 没有相遇情况，输出 $1$。 上代码： 1234567891011121314151617#include<bits/stdc++.h>using namespace std;int n,m,x,y...
2026-03-09
题解：P12131 [蓝桥杯 2025 省 B] 客流量上限
思路 因为对于任意分店 $i$ 和 $j(1\le i,j\le2025)$，它们的客流量上限 $A_i$ 和 $A_j$ 的乘积不得超过 $ij+2025$。 所以，对于任意分店 $i$，$A_i\le\sqrt{i^2+2025}$。 我们直接打表： 1for(int i=1;i<=2025;i++) cout<<(int)sqrt(i*i+2025)<<' '; 发现在 $i\ge1013$ 时 $A_i \le i$。 那么当 $1\le i<1013\le j\le2025$ 时，$A_iA_j=A_ij,A_iA_j\le ij+2025$。 两边同除 $j$：$A_i\le i+\frac{2025}{j}$。 发现：$A_i\le i+\lfloor\frac{2025}{j}\rfloor$。 由于 $1013\le j\le2025$，所以，$A_i\in[1,i+1]$。 所以我们可以得出： $A_1$ 有 $2$ 种选择； $A_k$ 为了不与 $A_1$~$A_{k-1}$ 选的重复，总是有 $i+...
2026-03-09
题解：P10414 [蓝桥杯 2023 国 A] 2023 次方
前言 这个应该小学生都可以看懂吧（本题解没有用到任何较难的知识）。 好像我也是小学生唉。 前置小知识 $a\bmod b=c$ 代表取模，即 $a$ 除 $b$ 的余数是 $c$。 题意 求 $ 2{(3{(4^{(\ldots ^{2023})})})} \bmod2023$。 思路 因为这个式子过于复杂，所以要简化一下。 根据小学的知识，找规律！！！ 但是手算是不行的，写个程序： 123456int s=3,sum=0,vis[2025]={};while(!vis[s]){ vis[s]=1; s=(s*3)%2023; sum++;}cout<<sum; 得出每 $408$ 个数为一个周期。 之后我们还需要知道指数在周期外的个数（即$ 3{(4{(\ldots ^{2023})})}\bmod 408$）。 一样，还是找规律： 123456int s=3,sum=0,vis[2025]={};while(!vis[s]){ vis[s]=1; s=(s*3)%2...
2026-03-09
题解：P11601 『Fwb』狼人の杀戮
比较烦的中模拟。 注意事项： 猎人死时必须带走一个人。 女巫只有一份毒药和解药。 在同一晚，同一位女巫只能做一次操作。 如果错误撤回当晚所有操作。 操作： 我们维护十个数组： $die$，所有死亡的记录。 $nw1$，女巫的毒药操作。 $nw2$，女巫的解药操作。 $nd$，当晚死亡人数。 $nnw$，当晚女巫的操作。 $lr$，当晚狼人的操作。 $er$，猎人带走的操作。 $die1$，$die$ 的副本。 $nw1_1$，$nw1$ 的副本。 $nw2_1$，$nw2$ 的副本。 然后，几个 $\texttt {if}$ 判断一下： 判断是否出界。 判断是否死亡。 如果是猎人或女巫，要判断是否当晚死亡。 如果是狼人或女巫，要判断是否当晚用。 接着，记录死亡，是否用技能： 12345678910111213141516if(op==0){ //狼人 if(a[x]==1&&!die[x]&&!die[y]&&!lr[x]&&x<=n&&x&&y<...
2026-03-09
题解：CF1598D Training Session
题目翻译： 给定 $n$ 个互不相同二元组，现在要从其中选出三个二元组，使得这三个二元组的的前一项互不相同或后一项互不相同。求有几种方案。 思路： 正难则反，先算总数：有 $\Large\frac{n \times (n-1) \times (n-2)}{6}$ 种情况。 不满足的情况是没有一个二元组与另一个二元组元素两两不相同（同一个元素）。 也就是就是一个二元组与另一个二元组元素至少一个相同（也是同一个元素）。 考虑用桶记录，$x_i$ 代表 $a_i$ 的出现个数，$y_i$ 代表 $b_i$ 的出现个数。 第一组固定，第二组有 $x_{a_i}-1$ 种，第三组有 $y_{b_i}-1$ 种。 一共有 $(x_{a_i}-1) \times (y_{b_i}-1)$。 代码楼上楼下都已经写的很明白了，我就不在赘述了。
2026-03-09
题解：P10043 [CCPC 2023 北京市赛] 广播
线性 DP。 不难想到 $dp_{i,j}$ 代表在 $a$ 中前 $i$ 个数和 $b$ 中前 $j$ 个数满足要求。 状态转移方程是： 边界： 如果 $i=m$，$dp_{i,j+1}=\min{dp_{i,j}}$。 如果 $j=n$，$dp_{i+1,j}=\min{dp_{i,j}}$。 之后： $a_{i+1}=b_{j+1}$ 或者 $a_{i+1}=1$ 或者 $b_{j+1}=1$，$dp_{i+1,j+1}=\min{dp_{i,j}}$。 最后 $dp_{i+1,j}=\min{dp_{i,j}+1},dp_{i,j+1}=\min{dp_{i,j}+1}$。 代码楼上楼下都已经写的很明白了，我就不在赘述了。
评论
公告
This is my Blog