ResurrectionTX

题解

比赛(7) 笔记(6)

/ 注册

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

Luogu P3295 【[SCOI2016]萌萌哒】

Description 传送门 Solution 首先先考虑如果限制不是区间，而是告诉你两个位置的字符相等的做法。这样的话，我们可以把相等的位置加进一些集合里，最后答案就是\(9 \times 10 ^ {num - 1}\)，其中\(num\)代表不同的集合个数，这个可以简单地用并查...

倍增并查集 Luogu

2020-06-12

0 355

Luogu P5840 【[COCI2015]Divljak】

Description 传送门 Solution 首先看到这题就想SAM对吧，然后qwaszx写了一发常数太大过不了就果断改AC自动机对吧。考虑对\(S\)建立\(AC\)自动机，因为字符串的所有前缀的所有后缀是字符串的所有子串，而\(fail\)指针指的状态就是该状态的最长可识别后缀...

AC自动机字符串 Luogu

2020-06-12

0 435

Luogu P5842 【[SCOI2012]Blinker 的仰慕者】

Description 传送门 Solution 不难想到这题用数位\(dp\)解决。那么首先可以想到\(dp_{i, j, num2, num3, num5, num7}\)表示从高到低填了\(i\)位，是否卡位，乘积中的每个质因子数量是多少此时的方案数，\(sum_{i, j, n...

数位DP Luogu

2020-06-12

0 437

Luogu P4101 【[HEOI2014]人人尽说江南好】

Description 传送门 Solution 如果每个人每次都只是将一个大小为\(1\)的石子堆放到当前最大的石子堆里，那么当游戏不能玩的时候局面必定是有\(n / m\)个大小为\(m\)的石子堆和\(\left [ n \mod m \neq 0 \right ]\)个大小为\(n...

博弈论 Luogu

2020-06-12

0 425

Luogu P3181 【[HAOI2016]找相同字符】

Description 传送门 Solution 这题就是让求两个串的相同子串的个数。众所周知，字符串所有的子串就是字符串所有的后缀的所有前缀。利用这个性质我们可以将问题转化，变成求两个字符串的所有后缀的\(lcp\)的长度的和。求后缀的\(lcp\)我们可以使用\(SA\)。...

单调栈 SA 字符串 Luogu

2020-06-12

0 374

Luogu P4249 【[WC2007]剪刀石头布】

Description 传送门 Solution 首先发现直接求这种三元组不打好求，那么考虑球不满足这种关系的三元组的数量。注意到一个三元组，如果不满足这种关系，肯定分别赢了\(0\)，\(1\)，\(2\)场。那么我们如果知道了每个人赢的场数\(y_i\)，不具有这种关系的三元组...

网络流 Luogu

2020-06-12

0 348

Luogu P2754 【[CTSC1999]家园 / 星际转移问题】

Description 传送门 Solution 判断有无解可以使用并查集，如果最后地球和月球能处在同一个集合中，那么肯定可以到达，只是时间长短的问题。因为多个飞船是同时飞行的，这样的问题不好直接处理。考虑星球的个数特别少，这时可以考虑按照时间轴建立分层图，\(S\)向每个时间点的地球...

分层图网络流并查集 Luogu

2020-06-12

0 386

Luogu P4313 【文理分科】

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

网络流 Luogu

2020-06-12

0 341

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

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

网络流 Luogu

2020-06-12

0 419

Luogu P4174 【[NOI2006]最大获利】

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

网络流 Luogu

2020-06-12

0 348