solution 比较容易想到的一个思路就是从深度更大的点开始选，每当遇到没有没变黑的点就选择它。 但是这样实际上是有问题的，选择当前没有被染色的点向上可以伸长的长度可能还不如选择其子树中的某个点更优。我们可以通过调整选择顺序，使得先选择这个更优的点。 所以我们每次更新K[u]为K[u]和所有K[v]-1中更大的那个。然后向上延伸即可。 code /* * @Author: wxyww * @Date: 2020-04-08 08:32:00 * @Last Modified time: 2020-04-08 09:36:43 */ #include<cstdio> #includ...

solution 仔细思考一下题意，发现其实就是要求将树分成不超过K个连通块，然后给每个连通块分配一种颜色。 假设连通块个数为x，那么根据乘法原理，给每个连通块分配不同颜色的方案数就是 然后问题就只剩下了如何求将树分成不超过K个连通块的方案数。 这显然可以用树形dp来求。 用f[u][i]表示将u这课子树划分为i个连通块的方案数。然后枚举一个u的子树v，同时枚举v子树中的连通块个数j。如果将v所在的连通块与u的颜色设为一样那么就会转移到，如果设为不一样，那么就会转移到。 这个dp过程的复杂度表面上是的，实际上是的。 只要在枚举连通块个数的时候，上限不超过子树大小即可。 原因我们可以考虑连边，也...

solution 首先利用前缀和思想，用的答案减去的答案就是的答案。 所以现在我们只需要考虑如何求出中每个数码在所有数字的约数中出现的次数即可。 然后是非常经典的将计算每个数字的约数改为枚举约数计算该约数的倍数有多少个。暴力做就是。这样复杂度是无法通过此题。 看到上面式子可以数论分块，所以直接套一个数论分块。 然后还有一个小问题就是数论分块如何求区间中x出现的次数。我的做法是先预处理一个10的整数幂，然后查看以x为最高位的每个大小的区间中是否有答案。统计一下。总复杂度就是 code /* * @Author: wxyww * @Date: 2020-04-06 09:59:24 * @Last...

环球旅行 题意就是给出一棵带边权的树。删除上面的一条边，使分成的两棵树中较大的直径尽量小。求该直径。 【20分做法】 枚举删除哪条边，计算直径。复杂度 【30分做法】 对于菊花图，删除最长边即可。 【40分做法】 对于一条链，枚举删边，可以直接算出剩下两条链的直径。 【60分做法】 对于且数据随机的部分，答案肯定是删除直径上的某条边。随机数据树的直径不会很长，所以只枚举删除直径上的边。计算剩下的最长直径即可。 【100分做法】 将直径扯平。从左向右依次计算删除上面某条边后左边子树的直径。如图，删除红色边之后，左边子树的直径就是max(删除蓝色边时的答案，经过x但不经过y的最长链+蓝色边长度+y...

环球旅行 题意就是给出一棵带边权的树。删除上面的一条边，使分成的两棵树中较大的直径尽量小。求该直径。 【20分做法】 枚举删除哪条边，计算直径。复杂度 【30分做法】 对于菊花图，删除最长边即可。 【40分做法】 对于一条链，枚举删边，可以直接算出剩下两条链的直径。 【60分做法】 对于且数据随机的部分，答案肯定是删除直径上的某条边。随机数据树的直径不会很长，所以只枚举删除直径上的边。计算剩下的最长直径即可。 【100分做法】 将直径扯平。从左向右依次计算删除上面某条边后左边子树的直径。如图，删除红色边之后，左边子树的直径就是max(删除蓝色边时的答案，经过x但不经过y的最长链+蓝色边长度+y...

A 咪咪游戏 直接判断奇数位是否均为m，偶数位均为q即可。 /* * @Author: wxyww * @Date: 2020-04-03 19:18:25 * @Last Modified time: 2020-04-03 19:20:35 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<...

solution 答案的最大值不超过n-1条边的权值之和，当n-1条边全部被选时，我们一定可以找到一种配对方案使得条边只被经过依次。 然后只需考虑哪些边是必须经过的即可，以1为根，如果某条边所连接的子树大小为奇数，那么这个子树内部肯定无法自己进行配对，所以这条边是必须被选的。找到所有这样的边，输出边权之和即可。 code /* * @Author: wxyww * @Date: 2020-04-03 07:11:02 * @Last Modified time: 2020-04-03 07:21:05 */ #include<cstdio> #include<iostream...

solution 本来看成了是子段，以为要用ac自动机。注意到就是要求一个字符串是不是母串的子序列（也就是不要求连续）。这是一个非常经典的问题，我们用表示母串中i这个位置的下一个字符j出现的位置。 如何求这个数组呢？如果，那么。否则。这样就可以很快的求出f数组。 判断一个字符串是不是母串的子序列的时候，直接从0号位置开始，每次跳到原序列中下次出现t[i]的位置即可，如果跳出了母串的最后一个字符，表示不是母串的子序列。 code /* * @Author: wxyww * @Date: 2020-04-03 06:32:01 * @Last Modified time: 2020-04-03 0...

solution 因为m=n，所以题目要求也就是要求断掉一些边，使得根与叶子节点不连通，用f[i]表示以i已经无法到达它子树中的所有叶子节点的最小花费。 转移的时候分两种情况，如果断开当前点与父亲相连的边，那么其子树中的边可以都不断开，花费为0.如果不断开当前点与父亲相连的边，那么答案就是其儿子的f值之和。 树形dp即可。 code /* * @Author: wxyww * @Date: 2020-04-02 20:47:38 * @Last Modified time: 2020-04-02 22:53:06 */ #include<cstdio> #include<io...

solution 倍增思想。用st[i][j]表示从i号节点进行次购买所到达的节点。这个可以通过一遍dfs预处理出来。关键在于怎么找st[i][0]，这个可以通过i号节点的父亲进行转移。具体参考代码。 然后考虑对于一次询问，找到u到根路径上比c大的深度最大的点。先跳到这个点然后不断向上跳，一直跳到v即可。复杂度 code /* * @Author: wxyww * @Date: 2020-04-02 19:59:55 * @Last Modified time: 2020-04-02 20:39:22 */ #include<cstdio> #include<iostream...

solution 肥肠经典的极值问题，可以使用ST表（复杂度为）或者单调队列(复杂度)来做，这里讲一下复杂度更优的单调队列做法。 题目要求长度为k的区间极值，我们从左往右扫并且维护一个队列，队列里存放的为数字下标，并且这个队列要满足两个条件。 条件一：队列中所有位置与当前扫到的位置i之间的距离不超过k。条件二：队列中下标对应的位置和下标均为有序的。 这样每当我们从i枚举到了i+1，我们都从队首找到与距离大于k的下标弹出去。这样就保证了条件一。 然后考虑维护条件二，我们向队列中添加元素时，需要保证这个元素所添加到的位置前的数字均大于（求最小值是为小于）当前位置的数字。那么我们考虑队尾的数字j，如...

soltion 我们可以预处理出一个L数组，其中表示以i为右端点的长度为k的区间和。然后预处理一个数组表示以i为左端点的长度为k的区间和。这两个数组都可以通过预处理前缀和然后相减的方法得到。即：记为区间的数字和，那么区间的数字和就是 然后考虑如何找到两个最大的不相交的长度为k的区间，很容易想到对做一个前缀最大值，对做一个后缀最大值。然后枚举一下左边区间的右端点，找到右边区间中的最大值就可以保证两个区间不相交了。 单组数据复杂度 注意因为输入有负数，所以赋的初值应为极小值而不是0. code /* * @Author: wxyww * @Date: 2020-04-02 14:08:41 * @...

A.Three Strings 【题意】 给出三个长度为的字符串,,。对于的每个字符都要和或中对应位置的字符交换，问是否有一种交换方法使得最终,两个字符串相同。 【思路】 如果中的每个字符都与或 中对应位置的字符相同，那么肯定存在解。否则无解。 【代码】 #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include&...

A. Erasing Zeroes 【题意】 给出一个串求出最小删除多少个0，使得所有的1是连续的。 【思路】 特判全是的情况。 答案就是最左边的和最右边的之间的的个数。 【代码】 #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string&...