D. Minimum Diameter Tree 题目链接 题目大意 给一棵树和一个s ，s代表树上的边权和。边权为非负数。 让给所有边赋边权，使得树的直径最小。 怎么做，，，我不会太菜了。。 感受到了思维的力量。 题解 给所有叶子节点（度数为1的点）所连的边赋值，其他边赋值0，也就是任意两个叶子节点相连都可以是直径，所以这些边平分s就好了（6666666666） 上代码 #include <cstdio> #include <algorithm> using namespace std; const int maxn = 1e5+5; int a[maxn]; int...

洛谷多校2场E 题目链接 题就是给两个无向图。往图里加边，问是不是两个可以在第一个图中相互到达并且在第二个图中也可以相互到达。第二个图中可以相互到达的在第一个图中也要相互到达。。用讲题大佬的话说 就是 是不是连通同构。连通性是不是一样的/ 题解 起初想到了并查集，但是不会处理。 大佬给的题解：  可以用并查集加哈希。（这个还不会） 可以用两个队列，如果在第一个图中加入一条边，就把第一个的并查集合并，并且把这条边加入第二个队列里，然后每次加完一条边，就判断队列里的边可不可以删除，如果两个队列都为空，就是连通同构的。  #include <cstdio> #include <al...

acwing 239.奇偶游戏 题目链接 题目大意： 有长度为n的01序列，给出m个描述 l , r ,奇/偶 。 表示l~r区间里的1的个数有奇数个或偶数个。问第几个描述与前面的矛盾。输出k - 1； n：1e9； m：1e4； 我还是太菜了 做的时候一下就想到了并查集。奇数为1，偶数为0，然后异或就可以。n虽然太大但是m小，可以离散化一下，并不影响。但是想了一下比如1~2 3~4 5~6 怎么把这些并起来。 他们没有相同的数字呀。。。 于是题解告诉我前缀和的思想：设sum[i]表示 i 之前有奇数或偶数个1.l~r区间里奇数或偶数就等于sum[r]^sum[l - 1]。 所以就可以把l ...

Bicolorings 题目链接 题意 有一个2*n的格子，每个格子可以涂成白色或黑色，然后 根据涂完的颜色可以分成连通块（白色跟白色连通，黑色跟黑色联通）然后 问连通块的数量是k的时候有多少种涂法。。 我还是菜了啊 想不到dp数组表示啥，想到了这个题就很简单了。 题解： dp[1000][2000][4] 。 n是1000 k是2000 后面的4 表示 这竖上面是啥 00 01 10 11 这四种。 把二维变成一维 ，秒啊~~ dp[i][j][p] 表示 到第i列是p连通块为j的有多少种。 状态转移就很好算了。简单又暴力。。就不用说了。 代码: #include <cstdio&gt...

D - GCD Counting 题目链接 题目大意 给一棵树，每个点的点权，然后问路径上的所有点权的gcd > 1的最长路径是多大。 这个感觉就树形dp了。。 但是菜鸡L不会写。。。 点的个数n 1e5. 点权是小于2e5的 刚开始想到了先把点权的质因子弄出来。然后dfs的时候对每个质因子之类的。。 但是呢， 总以为那样的话得开个1e5 * 2e5的数组。。可是用个map不就好了吗。于是就没有写。完了之后查题解恍然大悟。 题解： 先把每个点权的质因子求出来，如果两个节点有相同的质因子gcd就肯定>1。然后dfs的时候，路径过当前根节点枚举每个质因子统计出答案的最大值。。 代码： ...

题目链接 题目大意 给一棵有点权的树。根节点是1号节点，让找两个点，然后保留这两个点到根节点的路径，把其他的点删了。使得图上剩余点的权值异或和最大。 怎么说呢？ 没干出来，，想到了字典树求一对异或值最大的点。 然后 求一个树上点的前缀和 想着枚举一个lca然后再枚举每一个子树，，但是这个肯定是超时的，不敢写。。没写。。也不会写。。 题解： 树上启发式合并或啥啥树。。没听过我太菜了。。 这个的时间复杂度不怎么会算。。。 枚举分叉节点建立一个子树的字典树，然后在另一个子树上挨个解决问题。 然后就是怎么建一个子树上的字典树了。。 可以用树上启发式合并。 代码： #include <cstdio...

Voluntary Hotel 题目链接 题意: 有点乱。。。 有n(1e4)个点。 共有m(1e4)条无向边边。有边权，边权是两个点的距离（1e9）,其中有p（100）个点是医院，第 i 个点在点 yi[i] 处，q个宾馆，第 i 个馆在点 y[i] 处，可以最多容纳 h[i] 个人，有 r 个医生，家在s[i]的点，要去第k[i]个医院上班，k[i] >=1 && k[i] <= p; k[i]是下标也就是在点yi[k[i]]处上班。医生可以住宾馆，然后医生去上班的最远距离是d，问d最小是多少。。。 好绕。。。 题解： 首先找最大的最小值这种基本都是二分的吧，就...

Trips 题目链接 题目大意: 共有n（2e5）个人，刚开始都不认识，有m（2e5）天，第 i 天xi和yi认识了，认识不会传递，也就是a认识b，b认识c，a不一定认识c。这些人每天都想去旅游，如果每个人有他的k个朋友去旅游他才去。问每天最多去多少人。 分析一下。。 可以看成一个图，刚开始是空图，没有边，然后一次连接一个边，如果一个子图中的点要去那么在这个子图中的每个点，在这个子图中的度数都大于等于k。 就想到这里想不出来了。。 一种思想: 倒过来，就是先把所有边加上，然后找个答案就是m天的答案，然后依次删除边，再找答案。 怎么找答案呢？ 刚开始 度数小于k的人肯定不行，加到队列里，然后bf...

Bolshevik 题目链接 题目大意 有n（1e6）个人你是第m个人 第i个人有ai块钱，其中bi块钱在钱包里，如果偷了第i个人的钱，他的钱就会变为ai - bi 你是一个小偷，至少投多少个人的钱才能变成这n个人里最有钱的人（可以有人跟你一样有钱） 怎么做？ 贪心。。 先按ai排序，为什么？ 因为如果偷第二大ai的钱的话，最多的钱就会被第一大的限制住，所以偷钱偷的是一个前缀，然后按ai排序，O(n)枚举前缀，比如现在枚举到了第i个i+1~n得挑bi大的偷。现在只用找出来选取的前缀里最大的ai - bi和没选取的里面的最大的ai，最后要偷完的总钱得大于等于这两个的最大值。 前缀和很好弄，要找的...

T123577 Mana Eel’s Graph 题目链接 题目大意 给出一个无向图，每个点有两个点权a，b。如果这个图中的一个子图是一个完全图（每个点都跟这个子图里其他的点有边）。 一个图的A值等于这个图里的所有点的点权a乘起来， 一个图的B值等于这个图里的所有点的点权b乘起来， 令s1是这个图里的所有团的A值和，s2是这个图里的所有团的B值和 问s1 * s2 % mod 的值… 点的数量有40个 40 40 40 40个 题解 做的时候没有思路，一点点都没有。。。 因为只有40个点，可以爆搜，，但是我也不会 要求完全图里的东西，会想到补图。。 补图里的孤立节点，如果选这个点的话，设之前的...

线性基 线性基是什么？ 是一个数的集合。 原数组中的每个数都可以由这个集合里的树异或得到。 也就是原数组的压缩。 学习参考： 大佬博客 b站视频 性质 1、原数组里的数可以由线性基里的数异或得到。所以原数组里的一些数的异或也可以由线性基里的一些数异或得到。 2、线性基里的任意数异或起来都不可能为0， 3、线性基里的数的个数是确定的，满足性质的前提下是最少的。（插入顺序改变但是线性基里的数的个数不会变） （抄自大佬博客） 插入一个数： int b[35]; bool add(int x) {  for (int i = 30; i >= 0; i -- ) {  if(x & (1...

偏序问题 b站学习链接 偏序问题是什么？ 比如要找比当前数小的个数， 如果有两个值呢? 要求ai <= aj && bi <= bj 的i的个数 三个呢？ ai <= aj && bi <= bj && ci <= cj 说的可能不清楚，， 语言表达不够。。 但是没关系，我看得懂就行 hhhhhhh 一维的： 一维排个序就好。。 二维的： 按一个值排个序。 然后从前往后扫，把另一个值加到树状数组里然后 胡乱搞搞 三维的： 但是没关系，我看得懂就行 hhhhhhh 三维怎么弄？ 按a值排序，然后按b值cdq分治，把c值...

K-th Number 题目链接 题目大意 给一个数组a包含n（1e5）个数，给出 k，m。 构造数组b：在a的所有大于等于k的区间中选出第k大的数加到b里面。 问b数组中第m大的数。 题解 我好菜。。想不到二分，感觉最近脑子不动了，很fan 二分答案， 然后怎么check？ b里的数肯定有m个大于等于mid的数。 怎么看有没有呢？ 可以用m当作check的条件改变二分的l，r。 统计区间里第k大大于等于mid的数量，怎么统计？尺取， 就相当于取k个大于等于mid的数 有多少个区间， 尺取可以枚举区间的左侧，然后尺取 取到右侧，然后统计就可以，， 代码  #include <cstdio...

边的染色 边的染色 题目大意 给一个无向图，边权是0或1，其中一些边上的边权没有给出，要给那些没有边权的边赋值（0或1）使得图上的环中的边权异或下来为0，问有多少种方法. 题解 我想不出来，，我太菜了，害 把边上的边权变成点权，使得这条边端点的点权异或值等于边权， 因为这样的话环上的边就可以表示为(v1^v2) (v2^v3) (v3^v4) (v4^v1)这种的 然后边权异或和就是0了。。 然后 看没确定边权的边对答案的贡献 如果左右两个点在同一个连通块的话这条边得边权确定了 就是两个点的点权异或。 如果不在的话，答案就乘2，这条边可以是0也可以是1。 所以 就是先按有边权的建个图，看一下这...