牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共5篇）

模拟36 题解

A. 字符题中保证$p_i<=1e5$，还可以很显然地发现当总长度大于$p_{max}+c$，一定不会更优。于是枚举长度的大小。将每一个限制对长度取模。显然如果相邻两个字符所在的区间存在交集，就表示状态非法。于是得到$O(m*p_{max})$的暴力。发现在取模的过程中...

最短路 ST表区间dp dp

2019-09-05

0 381

模拟106 题解

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

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

2019-11-09

0 490

网络流杂题一

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

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

2019-12-08

0 523

数学专题测试1 题解

A. 解方程考虑没有任何限制的东西， m个元素分为n个连续的区间，直接用组合数插板法就好了。考虑如何去掉元素大于$a_i$的限制，只要给最终的元素个数减掉$a_i$就好了。考虑如何搞元素个数小于$a_i$的限制，不妨使用子集反演，要求的是恰好$0$个元素大于$a_i$。只要...

容斥 lucas定理组合计数数学多项式倍增 fwt dp 区间dp

2020-01-02

0 493

省选模拟59 题解

A. 杨柳考虑实际上有这样一个结论，棋子之间是互不干扰的。可以使得最优方案上不存在两个棋子中途碰上的情况。然后问题就是一个二分图最小匹配，一个简单的想法就是 bfs 然后跑一个费用流，点数不多，边数很多。另外一个做法是直接在原图上建图跑个费用流，点数很多，边数不多。经过实验，只有...

区间dp 二分图 tarjan dp 网络流

2020-04-01

0 336