牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共241篇）

模拟112 题解

A. 装饰分类讨论即可。标程的做法似乎更简单一些：答案为$min(\lfloor \frac{a+b+c}{3} \rfloor,a+b+c-max(a,b,c))$。证明并不难，显然答案不会超过这两个上界。对于两种情况分别取得较小的值，都可以构造出一种方案来达到答案的要求。 ...

拓扑排序 dp

2019-11-12

0 294

模拟111 题解

A. 物理课发现每次反弹之后移动的距离是上一次的$d^2$倍。计算出第一次反弹之前移动的距离的答案$k$，总的答案即$\sum \limits_{i=0}^{inf}d^{2*i}*k$。发现这个东西就是一个等比数列求和。设答案为$s$，那么有$s=\sum \limits_{i...

线段树分治并查集启发式合并组合计数

2019-11-12

0 343

模拟110 题解

A. 最大或因为或运算特殊的性质，从高位到低位进行贪心。将$l$，$r$的二进制位分别取出，从高到低枚举每一位，当存在一个二进制位不同，即在此位$l$为$0$而$r$为$1$。那么$x$可以选择后面每个二进制位中的$1$，保证低位贡献的最大化，$y$只要保证高位的贡献就可以了。 ...

图论单调指针位运算二分答案折半搜索

2019-11-11

0 287

模拟109 题解

A. Adore 似乎是显然的状压。 $dp_{i,S}$表示第$i$层，其中每个点到达终点路径条数的奇偶性为$S$的方案数。直接用位运算转移，复杂度是$O(m*k*2^k)$，然后卡卡常（把$k$循环展开）就过了。似乎考虑单次的变化量，可以继续消掉一个$k$，然后就好了。 ...

贪心 bitset 状压 dp

2019-11-11

0 437

模拟108 题解

A. 打表正确的题意是：求出最优决策下取得的值与答案的差绝对值的期望。考虑到本题中二者选择的概率各占一半。二者都选择各自的最优策略，在按位划分的情况下，只有$0$,$1$两种取值，如果前者选择$0$，那么后者可以选择$1$ 最终每个下标都会被等概率的选择，所以最终的答案就是对绝...

dp Hash 结论题

2019-11-11

0 473

模拟107 题解

A. 字符交换枚举最终出现的字符，那么答案具有单调性。之后枚举相同字符的起点，可以计算出终点。最优策略显然是换到中间的字符旁边，所以用前缀和维护一下就完了。 B. 平方数考虑怎样的两个数相乘可以构成平方数：将两个数分别质因数分解，如果二者奇数的质因子集合相同，...

二分答案 dp 容斥

2019-11-10

0 361

模拟106 题解

A. 合并集合显然的区间dp。断环成链，预处理出每个连续区间集合的元素个数。然后直接dp就完了。 B. climb 想了一些简单的贪心，然后都伪了。所以考虑如何暴力$O(n^2)$来做这个题。枚举最终用来跳最后一步的药丸，显然前面的药丸可以按$a_i-b_i...

并查集博弈论区间dp dp 拓展域分治线段树

2019-11-09

0 490

模拟105 题解

A. 小W的魔术考虑问题的逆问题，怎样的字符串是好的字符串。即长度为$n$，前缀与给定字符串的前缀匹配，后缀与给定字符串的后缀匹配的字符串个数。不妨枚举给定字符串的断开点，那么答案即$(len+1)*26^{n-len}$ 然而这里面有重复计算的方案，把它画出来就可以发现，相邻两次...

结论题 dp 倍增组合计数数位dp

2019-11-08

0 357

模拟104 题解

A. 中间值二分答案在数组$a$中的排名，则得到期望的在数组$b$中的排名。当数组$b$中对应的数恰好是大于二分值的第一个数，代表二分到了答案。通过对应的数与当前数的大小关系，可以确定二分方向。同理还应当二分答案在数组$b$中的排名。然而这个做法实现比较困难，还有另一个更帅的二分...

分治二分答案线段树 dp 单调栈

2019-11-07

0 405

模拟103 题解

A. Game $yxs$大神教你转化题意：将B哥的牌视作左括号，小A的牌视作右括号。那么问题转化为最多匹配多少个括号，并求出最大字典序的一组解。如果不需要最大字典序，问题是简单的贪心，每次取出最小的右括号尝试匹配。考虑一个暴力做法：对于B哥的每一张牌，做$nlogn$的...

启发式合并分治线段树贪心差分树状数组

2019-11-07

0 394