wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共395篇）

【每日一题】华华给月月准备礼物

solution 其实就是要求一个最大的x使得。显然当x增大时答案会变小，具有单调性，所以考虑二分答案。二分一个x，检查答案是否大于等于K即可。 code /* * @Author: wxyww * @Date: 2020-04-16 11:12:25 * @Last Modified ti...

二分答案

2020-04-16

1 663

luogu2000 拯救世界

solution 该博文刚写完，就不小心手残清空了，只好重写。生成函数练手题先写上这个式子题目中描述了两种限制。第一种限制：神石的块数必须是的倍数，那么他的生成函数就是。这就相当于用替换掉了上方式子中的。所以该生成函数就是第二中限制：神石的数目不超过，那么他的生成函数就是。我们将其看作...

2020-04-16

1 532

【每日一题】逆序对

solution 枚举一个为0的位置，然后想办法统计该位置产生的贡献。显然，一个为0的位置产生的贡献就是它前面1的个数。如果位置为0，那么他前面共有种可能的序列，每种序列都有个数字，那么总的数字数量就是。显然的，这些数字中0和1的数量应该是相等的。所以其中1的个数就是。然后考虑后面的位置共有种可能...

数学排列组合

2020-04-15

7 765

【每日一题】Treepath

solution 枚举起点和终点的LCA，然后将他们两两组合即可。具体的，设f[i][0/1]表示以i为根的子树中，与根节点i的距离为偶数(0)奇数(1)的点的数量。转移显然就是。然后考虑统计答案，以为的两个节点，肯定不能在的同一个儿子里，所以转移的过程中,表示已经当前已经计算过得儿子造成的贡...

dp

2020-04-14

1 872

【每日一题】Xorto

solution 计算区间异或和可以利用前缀异或和计算。因为n只有，所以只要在复杂度内解决就好了。然后考虑如何保证区间不相交。枚举一个点。用表示右端点小于等于x的区间中异或和为的区间数量。然后枚举一下左端点大于x的区间，如果该区间的异或和为那么就将答案加上。 code /* * @Author: ...

简单题

2020-04-13

2 724

【每日一题】Accumulation Degree

solution 经典的的方式。转化一下题意就是:选一个根，使得所有叶子节点到该节点路径上最小边权之和最大。先考虑的做法用表示以1为根时i这棵子树内的答案。那么就有。所以枚举一下根，然后每次这样dfs一遍，就可以在时间内解决问题了。考虑优化该算法我们只要在以1为根做一遍上面自下而上的dp...

树形dp

2020-04-12

1 634

【题解】牛客练习赛61

迟到1h，险些掉分，呼~ A 数据范围很小，模拟签到题。 /* * @Author: wxyww * @Date: 2020-04-10 19:52:33 * @Last Modified time: 2020-04-10 20:02:50 */ #include<cstdio> #in...

搜索动态规划点分治

2020-04-11

1 609

【每日一题】二分图染色

solution 首先单独考虑蓝色和红色的染色方式。如果只染蓝色（红色）和绿色，我们枚举一个蓝色边的数量x,然后方案数就是。所以总的方案数就是。然后容斥合并蓝色和红色的方案。枚举蓝色和红色边重复的数量x,那么答案就是。所以最终答案就是注意到上面求单个的过程是的。预处理f数组的复杂度就是。所以考...

2020-04-09

1 1157

【每日一题】Running Median

solution 题目就是要求对于每奇数个数字，输出其中位数。我们只要维护两个堆，第一个大根堆维护较小的数字，第二个小根堆维护较大的个数字。每当新加入一个数字的时候将其与大根堆的队首比较，并维护两个堆的大小。要求的中位数就是大根堆里的最大值。 code /* * @Author: wxyww *...

2020-04-08

1 627

【每日一题】黑白树

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

2020-04-08

2 746