ResurrectionTX

题解

比赛(7) 笔记(6)

/ 注册

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

Luogu P4311 【士兵占领】

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

网络流 Luogu

2020-06-12

0 356

Luogu P4707 【重返现世】

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

min-max反演数论 Luogu

2020-06-12

0 432

Luogu P5856 【「SWTR-03」Game】

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

状压DP 数论 Luogu

2020-06-12

0 420

Luogu P5212 【SubString】

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

Link-Cut-Tree 字符串 SAM Luogu

2020-06-16

0 381

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 P4585 【[FJOI2015]火星商店问题】

Description 传送门 Solution 其实这题是没有必要使用可持久化\(Trie\)的。首先建立一颗线段树，每个节点维护它所代表的那些商店的商品的标价所构成的\(Trie\)。这样如果没有时间上的限制，我们可以将每次的询问拆成对于\(log(n)\)个线段树上的节点的询...

线段树 Trie 树套树 Luogu

2020-07-30

0 346

Luogu P5948 【[POI2003]Chocolate】

Description 传送门 Solution 每次选择花费最大的地方切，然后按照题意(O(n))模拟即可。证明如下： (1.)若两次切割都是横向或竖向，且花费小的比花费大的先切割。设花费小的切割的时候需要切割(a)次，花费大的切割的时候需要切割(b)次，因为中间可能切割了任意次另外一个方向...

贪心 Luogu

2020-08-04

0 469