牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共241篇）

省选模拟1 题解

A. 天空碎片正解很麻烦，所以打表找规律 B. 未来拼图发现这个式子是一个简单的循环卷积式，所以要求的实际上是一个多项式在$mod\ x^n$意义下的平方根个数和最小字典序平方根。然而本题所要求的循环卷积与一般情况下的$2^k$不同。然而这个复杂度，可以直接做暴力DFT，即直...

多项式网络流

2019-12-24

0 393

关于斯特林数

第一类斯特林数定义 $S_1(n,m)$表示$n$个元素，形成$m$个环的方案数，记作$\begin{bmatrix}n\\m\end{bmatrix}$。其中每个元素是不同的，每个环是相同的。递推公式从实际含义上去考虑，第一类斯特林数递推公式为： $\begin{bmat...

容斥组合计数数学斯特林数二项式反演

2019-12-11

0 428

关于原根

时隔两三个月重新打$ntt$的时候，已经忘记了常见模数的原根。想要回忆原根的求法，以备不时之需，然而也忘记了。所以颓了大神$yxs$的证明博客，为了防止再次遗忘，来复读一遍大神的做法和证明。做法：因为原根往往很小，所以可以采用暴力枚举的方法。然而直接暴力$check$的复杂...

原根

2019-12-09

0 303

网络流杂题三

A. 1565: 植物大战僵尸考虑保护关系可能会出环，也就是其中任何一个一定不能被选。注意环的出边也是无法被选的。注意要找的环的出边并不是网络流建的图的出边，因为网络流反映的是必须选的关系，即由被保护者到保护者。然后就是简单的最大权闭合子图。 B. 寿司餐厅似乎并不是很难...

网络流二分答案

2019-12-09

0 290

网络流杂题二

A. 无限之环正解的思路并没有局限于原图中的网络流，而是将网格图黑白染色。将源点向黑点建边，黑点向可以连接的白点建边，之后原图无缝拼接可以简单地转化为跑最大流之后能够满流。所以只要考虑如何加入翻转次数的限制。因为流量必须全部流向同一个状态，简单拆分为四个方向似乎并不是可行的。题解...

网络流二分图

2019-12-09

0 405

网络流杂题一

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

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

2019-12-08

0 523

CSP-S 2019 题解

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

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

2019-12-02

0 477

模拟115 题解

A. Tiny Counting 考虑枚举$a$，可以直接用树状数组查找合法的$b$，接着直接乘逆序对个数就好了。然而这个时候就存在一些非法的状态，$b$作为逆序对出现了。所以只要再枚举一遍$b$，减掉对应的贡献就好了。 B. Medium Counting 因为...

数位dp 树状数组组合计数

2019-11-14

0 379

模拟114 题解

A. A 正解是给二次函数除一个$x$，于是问题转化为简单的单调栈维护凸包问题。最后直接乘回一个$x$就好了。然而考场上并没有想到这个东西，所以维护答案$x$的最优转移点，暴力枚举最优转移点的前后三百个最优的二次函数就好了。本来以为自己打了个乱搞特别没素质，后来发现因为数据保证值域...

倍增单调栈凸包

2019-11-14

0 333

模拟113 题解

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

dp 基环树结论题

2019-11-13

0 322