wxyww

题解

未归档(12) 精品(28)

/ 注册

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

【每日一题】比赛

solution 先考虑对于如何求出解出第道题的概率。直接求并不好求，但是解不出第道题的概率很好求，就是。那么解出第到题的概率就是。因为题目数量非常小。所以可以枚举每道题是否解出来了，然后统计一下每种情况的概率，记录到答案里面即可。 code /* * @Author: wxyww * @Date...

状态压缩概率

2020-05-18

1 662

【每日一题】NC53676「土」秘法地震

solution 因为地震的区域是固定的。所以枚举一下地震矩形的右下角，然后判断一下这个矩形内是不是含有1就行了。怎么判断一个矩形内是不是有1？二维前缀和一下，然后计算一下查询矩阵得和是不是比0大就行了。 code /* * @Author: wxyww * @Date: 2020-05-17...

2020-05-17

2 916

【题解】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