牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共3篇）

省选模拟13 题解

A. 同桌的你每个人渴望与一个人当同桌。容易发现这个关系形成内向基环树森林。问题转化为求基环树森林的最大匹配。任意选一条环上的边，分别尝试该边为匹配边、非匹配边即可。 B. 大水题一个常用的但想不到的东西：将每种颜色出现次数的差值为定值，转化为对颜色序列差分后相等。然...

二分图二分答案 Hash 差分基环树 2sat

2020-02-01

0 474

省选模拟18 题解

A. 编码一眼原题，是一道数据结构（？）优化2-SAT建图的题。 2-SAT还是比较容易看出来的，每一个串只有$0/1$两种取值，一个串对另一个串起到了限制的作用。于是暴力的做法就是先将所有的串按照长度排序，由小到大分别将两个副本插入字典树。对字典树上每个节点维护一个vector，表示...

单调指针 Hash dp 高斯消元二分答案折半搜索 2sat trie树

2020-02-05

0 387

省选模拟42 题解

A. coin 容易发现每种假钞的期望贡献是独立的。对于每种假钞，做一个 $n^2$的 dp 求出来选择 $i$张假钞的贡献。然后对这个贡献做一个背包就完事了。考虑一个东西，就是对于每种假钞，只能选择一个数目加入背包的贡献中。所以可以考虑对于每种假钞一张张加入贡献。然后发现发现...

矩阵树定理二项式反演 dp 2sat

2020-03-10

0 353