题解：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
题解：P10161 [DTCPC 2024] 小方的疑惑 10
思路 我们注意到答案串一定是若干个可以变成一个可以做出 $k$ 个合法的括号序列的长度 $\le n$ 的序列再补上若干个 )。 显然，设答案串 $s$ 有 $k$ 对括号在最外层，那么合法子串个数为 $\frac{k(k+1)}{2}$。我们就可以构造了！ 这样就可以在不浪费括号的情况下将答案串分成多个括号串。 设 $dp_i$ 为构造出 $i$ 个合法子串（即 $k$）所需的最小括号对数。 状态转移就是：$dp_i=dp_{i-\frac{j(j+1)}{2}}+j$。 我们先把这部分预处理出来。 如果 $2dp_k>n$ 则说明无解，否则在 dp 数组上递归构造（如果$dp_i=dp_{i-\frac{j(j+1)}{2}}+j$，那么就转移）。 代码： 1234567891011121314151617#include<bits/stdc++.h>#define int long longusing namespace std;int T,n,k,dp[100005];void print(int x){ if(!x) return; ...
2026-03-09
题解：CF1766C Hamiltonian Wall
题目就是求 $s$ 是否可以一笔画。 像这样（样例）： 12BWBBWBBBBBBB 走法： 123B W B--B W B| | | |B--B--B B--B--B 我们发现如果上面或下面没有走过且可以走，是一定要走。 如果上面或下面都走过了，就向后走。 另外形如： 12BBBW 就要特判是开始是第一行还是第二行，我的做法是都枚举一遍。 最后放上超长代码： 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include<bits/stdc++.h>#define int long longusing namespace std;int T,n,fg,as,x,y,vis[200005][2]; char s[200005][2];signed main(){ cin>>T; while(T--){ cin>>n,fg=as=0; for(int...
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
题解：CF2086C Disappearing Permutation
题意 给定两个排列 $p$ 和 $d$，第 $1 \le i \le n$ 次将 $p_{d_i}$ 设为 0。 然后进行操作，一次操作定义为指定一个 $i$，将 $a_i = i$，问最少多少次操作能将它复原为一个排列（可能与原排列相同）。 思路 我一看，每次 $p_{i}$ 一定要做一次操作 $p_i=i$，那么 $p_{p_i}$ 也要操作，以此类推，直到 $p_k$ 等于 $k$。 那就好办了，每次讲 $p_i$ 和 $i$ 连在一起，分成几个联通块，每次的答案就是联通块的大小。 code 123456789101112131415161718192021222324#include<bits/stdc++.h>#define int long longusing namespace std;int T,n,p[100005],d[100005],f[100005],sz[100005],fg[100005],ans;int fd(int x){ if(f[x]==x) return x; return f[x]=fd(f[x]);&#...
2026-03-09
题解：P7900 [COCI 2006/2007 #2] SJECIŠTA
题意： 给定一个没有任何三个及以上的对角线交于一点的凸多边形。 问对角线交点个数。 思路： 我们注意到任意两个对角线一定可以确定一个点。 那么只要求出对角线数量就行了！ 解法： 确定两个对角线就是找到四个点。 即在 $n$ 个点中选 $4$ 个点。 所以答案就是 $C^4_n$。
公告
This is my Blog