wxyww

题解

未归档(12) 精品(28)

/ 注册

全部文章 / 题解（共65篇）

【每日一题】黑白树

solution 比较容易想到的一个思路就是从深度更大的点开始选，每当遇到没有没变黑的点就选择它。但是这样实际上是有问题的，选择当前没有被染色的点向上可以伸长的长度可能还不如选择其子树中的某个点更优。我们可以通过调整选择顺序，使得先选择这个更优的点。所以我们每次更新K[u]为K[u]和所有K[v...

2020-04-08

2 746

【每日一题】树

solution 仔细思考一下题意，发现其实就是要求将树分成不超过K个连通块，然后给每个连通块分配一种颜色。假设连通块个数为x，那么根据乘法原理，给每个连通块分配不同颜色的方案数就是然后问题就只剩下了如何求将树分成不超过K个连通块的方案数。这显然可以用树形dp来求。用f[u][i]表示将u这...

2020-04-06

2 1025

【每日一题】数码

solution 首先利用前缀和思想，用的答案减去的答案就是的答案。所以现在我们只需要考虑如何求出中每个数码在所有数字的约数中出现的次数即可。然后是非常经典的将计算每个数字的约数改为枚举约数计算该约数的倍数有多少个。暴力做就是。这样复杂度是无法通过此题。看到上面式子可以数论分块，所以直接套一个...

2020-04-06

3 854

【每日一题】Shortest Path

solution 答案的最大值不超过n-1条边的权值之和，当n-1条边全部被选时，我们一定可以找到一种配对方案使得条边只被经过依次。然后只需考虑哪些边是必须经过的即可，以1为根，如果某条边所连接的子树大小为奇数，那么这个子树内部肯定无法自己进行配对，所以这条边是必须被选的。找到所有这样的边，输出边...

思考题

2020-04-03

1 662

【每日一题】月月查华华的手机

solution 本来看成了是子段，以为要用ac自动机。注意到就是要求一个字符串是不是母串的子序列（也就是不要求连续）。这是一个非常经典的问题，我们用表示母串中i这个位置的下一个字符j出现的位置。如何求这个数组呢？如果，那么。否则。这样就可以很快的求出f数组。判断一个字符串是不是母串的子序列的时...

2020-04-03

1 684

【每日一题】Rinne Loves Edges

solution 因为m=n，所以题目要求也就是要求断掉一些边，使得根与叶子节点不连通，用f[i]表示以i已经无法到达它子树中的所有叶子节点的最小花费。转移的时候分两种情况，如果断开当前点与父亲相连的边，那么其子树中的边可以都不断开，花费为0.如果不断开当前点与父亲相连的边，那么答案就是其儿子的f...

2020-04-02

1 686

【每日一题】城市网络

solution 倍增思想。用st[i][j]表示从i号节点进行次购买所到达的节点。这个可以通过一遍dfs预处理出来。关键在于怎么找st[i][0]，这个可以通过i号节点的父亲进行转移。具体参考代码。然后考虑对于一次询问，找到u到根路径上比c大的深度最大的点。先跳到这个点然后不断向上跳，一直跳到v...

2020-04-02

1 560

【每日一题】滑动窗口

solution 肥肠经典的极值问题，可以使用ST表（复杂度为）或者单调队列(复杂度)来做，这里讲一下复杂度更优的单调队列做法。题目要求长度为k的区间极值，我们从左往右扫并且维护一个队列，队列里存放的为数字下标，并且这个队列要满足两个条件。条件一：队列中所有位置与当前扫到的位置i之间的距离不超过...

2020-04-02

1 593

【每日一题】数学考试

soltion 我们可以预处理出一个L数组，其中表示以i为右端点的长度为k的区间和。然后预处理一个数组表示以i为左端点的长度为k的区间和。这两个数组都可以通过预处理前缀和然后相减的方法得到。即：记为区间的数字和，那么区间的数字和就是然后考虑如何找到两个最大的不相交的长度为k的区间，很容易想到对做一...

2020-04-02

1 553

codeforces1301解题报告

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

2020-02-19

2 761