题解：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
题解：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
题解：P14358 [CSP-J 2025] 座位 / seat（民间数据）
前言 作者是 xxs，考不了 CSP。 做法 照题意模拟即可。 就是将所有人的成绩和序号放在一个结构体中，再排序。 再求出第 $i$ 行第 $j$ 列是名次为几的人即可。 如下图： 1 8 9 16 2 7 10 15 3 6 11 14 4 5 12 13 用 dfs 跑一遍，再在图中找序号为 $1$ 的名次，输出行和列。 代码： 12345678910111213141516171819202122232425#include<bits/stdc++.h>#define int long longusing namespace std;int n,m,d[15][15],tot,x;//d 序号矩阵，tot 当前序号，x 编号为 1 的数排好序之后的位置。struct stu{int x,id;}a[105];bool cmp(stu x,stu y){return x.x>y.x;};void dfs(int x,int y){ //dfs 求出序号矩阵。 if...
2026-03-09
题解：P10578 [蓝桥杯 2024 国 A] 旋转九宫格
用 BFS。 思路 我们可以使用一个长度为 $3\times3$ 的 string 来表示状态，每一种状态可以进行旋转（左上，右上，左下，右下）。 我们可以用 map 来记录状态。 预处理一下即可。 代码： 12345678910111213141516171819202122#include<bits/stdc++.h>#define int long longusing namespace std;map<string,int> mp; int T,n; char c;signed main(){ cin>>T; queue<string> q; //bfs q.push("123456789"),mp["123456789"]=1; while(q.size()){ string u=q.front(),v[4]={u,u,u,u}; q.pop(); v[3][4]=u[5],v[3][5]=u[8],v[3][7]=u[4],v[3][...
2026-03-09
题解：P7900 [COCI 2006/2007 #2] SJECIŠTA
题意： 给定一个没有任何三个及以上的对角线交于一点的凸多边形。 问对角线交点个数。 思路： 我们注意到任意两个对角线一定可以确定一个点。 那么只要求出对角线数量就行了！ 解法： 确定两个对角线就是找到四个点。 即在 $n$ 个点中选 $4$ 个点。 所以答案就是 $C^4_n$。
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
题解：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+...
评论
公告
This is my Blog