wxyww

分类

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

/ 注册

全部文章（共395篇）

【题解】NC5531F 牛牛的飞行棋

solution 求出每个点的sg函数，然后异或起来得到x，如果x为0那么就是先手必败，否则就是先手必胜。如何求每个点sg函数？对于节点,,(i是j的祖先)。对于第二问，也就是需要操作一步使得异或和为0。如果我们把上的一个棋子挪到了上，那么的异或和就会变为，（v位于u的子树中）。也就是说我们要...

博弈论

2020-05-11

1 891

【题解】NC5531D 牛牛的01限定串

solution 考虑dp。用表示对于t的前个位置，有个位置为1最小得分。显然当前面1的个数确定之后，后面1的个数也确定了。也就是我们可以计算对于位置它的前缀是否和s相似，它的后缀是否和s相似，然后就可以计算出i位置的贡献。枚举i位置是'0'还是'1'转移即可。 code /* * @Author...

动态规划

2020-05-11

2 723

【题解】NC5531C 牛牛的揠苗助长

solution 显然答案具有单调性，如果答案为c。而对于任意一个，我们都可以在(c+1)~a的这些天里，让生长1的那个植株减1. 所以我们考虑二分答案，如果我们二分了一个答案x，我们可以先让那些水稻按照规则生长x天，最后再进行最多x次操作使他们高度相同即可。那么现在问题就变为了，已经知道所有水稻...

二分答案

2020-05-11

1 674

【题解】NC5531B 牛牛的鱼缸

solution 分为两种情况，第一种情况就是用整个鱼缸的体积减去绿色部分即可，绿色部分中标出的角与下面大三角形中标出的角一样大，所以可以利用红色变就可以求出绿色三角形的另一条直角边，进而求出绿色三角形的体积。另一种情况就是图中红色角是相等的，和上面一样可以求出绿色三角形的体积，就是答...

2020-05-10

1 789

【题解】NC5531A 牛牛的三角形

solution 暴力枚举三个数字，看一下是不是满足“任意两数之和大于第3个数”就行了。 code /* * @Author: wxyww * @Date: 2020-05-08 19:01:05 * @Last Modified time: 2020-05-08 19:02:36 */ #incl...

2020-05-10

1 753

【每日一题】「火」皇家烈焰

solution 一开始考虑用表示前i个位置，第个位置有(1)没有(0)烈焰，的方案数。发现不好转移。当一种状态无法转移时，就再加一维状态用表示前i个位置，第i个位置的状态为j，第个位置状态为的方案数。然后就可以转移了。当第个位置的信息为时，就有当第个位置的信息为时，就有当第个位置的信息...

2020-05-07

1 814

【每日一题】tokitsukaze and Soldier

solution 考虑枚举所选择的数中最小的。然后就是要在所有的数中找到最大的个。所以先按照s从大到小排序，然后再维护一个小根堆，存放当前的答案。每当堆的大小大于当前的s时，就弹出元素。最后找到一个最大的答案即可。 code /* * @Author: wxyww * @Date: 2020-05...

2020-05-05

1 599

【每日一题】换个角度思考

solution 发现可以离线。将所有询问离线下来，按照查询的从小到大排序。并且将数组从小到大排序。按照从小到大的枚举每次询问，同时将所有的数字，将树状数组上位置。然后直接区间查询就行了。 code /* * @Author: wxyww * @Date: 2020-04-29 11:36:4...

树状数组

2020-04-29

3 991

【每日一题】NC14704 美味菜肴

solution 贪心+dp。做这个题我们需要处理两个问题。第一个是如何确定这些菜的顺序，第二个是确定了菜的顺序之后如何计算答案。先来确定菜的顺序。仔细观察之后，发现其实这个问题贪心思路和“国王的游戏”一样。如果只考虑两种菜。我们如果让在前，那么选这两种菜的答案就是，否则就是。发现都有，所以我们...

贪心 dp

2020-04-27

2 876

【题解】 NC5205E 水灾

solution 首先可以发现，这张图其实可以转化为一棵最大生成树。我们按权值从大到小加入边，如果新加入的边所连接的两点，已经可以通过其他权值更大的边相连，后面的询问中只删除这条边起不到任何作用。所以我们考虑建出重构树。具体建立方法:对于在生成树中的一条边，新建一个节点，并且从向所在的集合...

生成树

2020-04-25

1 743