牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共132篇）

模拟105 题解

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

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

2019-11-08

0 357

模拟106 题解

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

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

2019-11-09

0 490

模拟107 题解

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

二分答案 dp 容斥

2019-11-10

0 361

模拟108 题解

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

dp Hash 结论题

2019-11-11

0 473

模拟109 题解

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

贪心 bitset 状压 dp

2019-11-11

0 437

模拟112 题解

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

拓扑排序 dp

2019-11-12

0 294

模拟113 题解

A. ZYB建围墙手玩发现这个东西好像有一点规律。考虑在最优的方案下，每增加一个点对答案的贡献$0/1$，然后随便写写就好了。 B. ZYB和售货机把$x$向$x$能偷的节点建边。发现这个东西一定会形成森林，其中一些树为基环树，其余为普通形态的树。对于普通...

dp 基环树结论题

2019-11-13

0 322

CSP-S 2019 题解

D1T1-格雷码题中给出了构造格雷码的方法。 $solve(n,k)$表示求出$2^n$意义下排名为$k$的格雷码，只要比较一下考虑最高位的0/1取值就好了。部分分提示了要开$unsigned\ long\ long$，注意一下就可以了。 D1T2-括号树子序列...

倍增单调队列 dp 并查集贪心

2019-12-02

0 477

网络流杂题一

A. 奇怪的游戏网格图在网络流中往往对应着黑白染色，当然还有四色染色等奇怪的东西。建图并不难，但是二分的思想是很好的。考虑如何检验一个答案$x$，将黑点视为二分图的左部点，白点视为二分图的右部点。一次操作对应一组相邻黑白点$+1$，所以直接建图看能否跑满流就完了。然而需要注意，显...

区间dp dp 二分答案网络流二分图

2019-12-08

0 523

省选模拟2 题解

A. 铁轨建设暴力插头dp+网络流判断可行性，可以拿到85分。然而这个题看起来就很像无限之环，只要稍微改一下建图就好了。然而这个建图还蛮难想到的。 B. 圈地游戏因为不会做+看不懂题解+std太长，所以咕掉了。 C. 组合数学 70分部分分：考虑到状态数很少，直接暴...

dp 网络流二项式反演容斥组合计数

2019-12-24

0 408