• 周六. 7月 2nd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

Wannafly挑战赛1

admin

11月 28, 2021

康复训练的第一套题,感觉质量还是蛮高的

Treepath

题意:给你一棵树,求长度为偶数的路径条数。$(n<=10^5)$

题解:从根出发做一遍dfs,统计长度为奇数的路径条数。对于其他点,可以根据到根路径的奇偶性得到长度为奇数的路径条数,最后用总路径数减去长度为奇数的即可。

Xorto

题意:给定一个长度为$n$的整数数组,问有多少对互不重叠的非空区间,使得两个区间内的数的异或和为$0$。
题解:把所有区间按异或和存进vector,然后暴力统计即可。
题意:懒得抄题直接上图

 

题面还挺大。

题解:一眼建虚树求直径,后来发现直径端点一定是深度最大的点,所以直接暴力求出来直径就好了。

Color

题意:给定一张二分图,问最少用多少种颜色染色,使得每个点相连边颜色不同

题解:考虑最大的点度,必要性显然。按照点度排序,每次做最大匹配,点度大的点优先

Cut

题意:给定一个无向简单图(即无重边无自环). 每条边都有一个权值. 这个图的一个鸽, 指的是将它的点集划分为两个不重不漏的集合S和T. 这个鸽的权值, 是所有两个端点分别属于S和T的边的权值的异或和(即, S内部的边和T内部的边都不算). 现在问这个图的鸽的所有可能权值的和是多少. 由于这个数很大, 只需要输出前9位, 不足9位则全部输出.

题解:用边权不好考虑,将他转化为点权,每个点的点权是其相连边的边权异或和。考虑两个点权异或,即相当于把他们放到同一组集合。于是题目转化为从一些数中随便选几个数,求异或和的和,线性基即可。

发表评论

您的电子邮箱地址不会被公开。