ResurrectionTX

题解

比赛(7) 笔记(6)

/ 注册

全部文章 / 题解（共32篇）

Topcoder SRM713 DFSCount

Description 传送门 Solution 注意到\(DFS\)的时候每次选择一个\(DFS\)树的子树后必然会走所有子树中的节点，所以原问题变成所有子树内的顺序乘子树外的顺序。这样可以将还没有经过的节点状压，进行记忆化搜索。\(DFS\)树的子树个数就是去掉当前点之后的连通块个...

Topcoder 状压DP

2020-07-07

0 420

Luogu P3714 【[BJOI2017]树的难题】

Description 传送门 Solution 设点\(i\)到根的第一条边的颜色为\(col_i\)，根到点\(i\)的路径上的颜色和是\(sum_i\)，经过观察发现\(col_i\)相同的不在同一个子树里的两个点之间的简单路径拼接后的答案是\(sum_i + sum_j - w_{...

点分治单调队列 Luogu

2020-06-17

0 322

Luogu P5212 【SubString】

Description 传送门 Solution 动态加入字符就用\(SAM\)，发现答案就是一个点的子树的\(siz\)之和，所以需要动态维护子树和，上\(LCT\)。 \(lCT\)上每个节点，\(siz\)表示\(Splay\)上大小，\(lsiz\)表示虚子树大小，修改\(Upd...

Link-Cut-Tree 字符串 SAM Luogu

2020-06-16

0 381

BZOJ 3145 Str

Description 传送门 Solution 如果直接暴力的话，可以枚举那个不同的字符在串一和串二里的位置分别是什么，然后算一下他们的\(lcp\)和\(lcs\)来更新答案，也就是\(\sum_{i = 1, j = 1} ^{i <= n, j <= m} lcp(i ...

启发式合并字符串 SA BZOJ

2020-06-15

0 397

Luogu P5856 【「SWTR-03」Game】

Description 传送门 Solution 读完题面之后我们首先可以想到要进行质因数分解。因为每次只能除以\(prime^z\)也就是说每次我们只能消除某一个质因子多出来的部分，所以对于每个质因子可以分开考虑。消去某个质因子多出来的部分只需要把这个质因子所有出现过的在每个数中...

状压DP 数论 Luogu

2020-06-12

0 420

Luogu P4707 【重返现世】

Description 传送门 Solution 对于每种原料，如果我们能求出它们的期望出现时间，那么第\(k\)小的期望出现时间就是答案。因为在第\(k\)小的原料被收集之前，比它更早出现的原料已经被收集过了，第\(k\)小的原料就是第\(k\)个被收集到的原料。第\(k\)小的原料...

min-max反演数论 Luogu

2020-06-12

0 432

Luogu P4311 【士兵占领】

Description 传送门 Solution 首先如果士兵只能给一行或一列造成贡献的答案是\(\sum_{i = 1}^m l_i + \sum_{i = 1}^n c_i\)。但是发现有的士兵可以同时给一列和一行造成贡献。那就算出这些士兵的个数就行了。 \(S\)向每一行连...

网络流 Luogu

2020-06-12

0 356

Luogu P4174 【[NOI2006]最大获利】

Description 传送门 Solution 经典的最大权闭合子图问题。首先\(S\)向每个中转站连容量为费用的有向边。每个群体向\(T\)连容量为收益的有向边。如果一个中转站的点被割了，那么相当于建立这个中转站；如果一个群体被割了相当于不选这个群体。那么答案就是所有群...

网络流 Luogu

2020-06-12

0 348

Luogu P1646 【[国家集训队]happiness】

Description 传送门 Solution 一种列方程的套路。我们先单独找出两个点的关系来考虑。假设有\(x\)和\(y\)两个同学，向\(S\)连边代表选理科，向\(T\)连边代表选文科。设\(S\)向\(x\)连的有向边为\(a\)，\(S\)向\(y\)连的有向边为\(...

网络流 Luogu

2020-06-12

0 419

Luogu P4313 【文理分科】

Description 传送门 Solution 每个点只有两种选择，不是选文科就是选理科，从\(S\)向每个同学连容量为选文科的满意值的有向边，从每个同学向\(T\)连容量为选理科的满意值的有向边，那么总的满意值减去最小割就是答案。现在考虑如何在所有相邻的同学选同一个课时增加满意值，...

网络流 Luogu

2020-06-12

0 341