Law_Aias

分类

未归档(110) 题解(5)

/ 注册

全部文章（共17篇）

Censoring

USACO15FEB-Censoring 题意：有一个S串和一个T串，长度均小于1,000,000，设当前串为U串，然后从前往后枚举S串一个字符一个字符往U串里添加，若U串后缀为T，则去掉这个后缀继续流程。解法： AC自动机在预处理fail的时候, $ O(n) $ ...

正睿题解

2019-08-24

0 392

BZOJ2938

BZOJ2938-病毒题意：二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。解法：因为是...

题解正睿

2019-08-24

0 438

ZR#954 分组

ZR#954 分组解法：设 $ f[i][a][b] $ 表示考虑了排序后的前 $ i $ 个人，目前已经有 $ a $ 个组配好了，还有 $ b $ 个组只有组员没有组长的最小代价。转移时，考虑当前的人是作为组长，加入一个已经有组员的组，还是作为组员新建一个组即可。然后对于有的...

正睿题解

2019-09-02

0 422

ZR#955 折纸

ZR#955 折纸解法: 可以发现折纸之后被折到上面的部分实际上是没有用的，因为他和下面对应位置一定是一样的，而影响答案的只有每个位置的颜色和最底层的坐标范围。因此，我们只需要考虑最底层即可，即我们可以把折纸等效为裁纸，每次去掉较小的那一部分。用哈希维护每一列和每一行的极大回文子串...

模拟赛题解正睿

2019-09-02

0 381

ZR#956 集合

ZR#956 集合解法：维护一个异或操作的懒标记，并对应的处理插入、删除和异或操作。接下来考虑如何整体加一。考虑一个数字 $ x $ 变为 $ (x+1) \pmod {2^{30}} $ 的过程，设 $ x $ 在二进制表示下从低位到高位依次为 $ a_1,a_2,a_3 \c...

正睿模拟赛题解

2019-09-03

0 418

ZR#999

ZR#999 解法：一道计数题，看到要求必须 $ m $ 个标号，所有标号至少出现一次的方案。很容易想到可以容斥，但容斥这个东西是一种很神奇的东西，你可以看出来一道题需要容斥，但你就是不知道怎么容斥。原题的等价形式为：总方案减去至少不出现一种玩具的方案数。 ...

题解模拟赛正睿

2019-09-08

0 441

ZR#996

ZR#996 解法：若删除长度为 $ x $ 的子串后序列中没有相同元素，那么一定有至少一个长度为 $ x+1 $ 的子串，删除它后序列中也没有相同元素。 CODE: #include <iostream> #include <cstdio> #i...

题解正睿模拟赛

2019-09-08

0 444

ZR#997

ZR#997 解法：找找规律就出来了，全场最简单的一道题。 CODE： #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> usi...

题解模拟赛正睿

2019-09-08

0 359

ZR#998

ZR#998 解法：先把所有物品按照拿走的时间从小到大排序，拿走的时间相同就按照放上去的时间从大到小。那么一件物品上方的物品就一定会在它的前面。考虑 $ dp $ ，设 $ f[i][j] $ 表示 $ i $ 以及 $ i $ 上面物品在所有时刻中最大重量为 $ j $ 时的最大...

题解模拟赛正睿

2019-09-08

0 445

ZR#959

ZR#959 解法：对于一个询问，设路径 $ (u, v) $ 经过的所有边的 $ gcd $ 为 $ g $，这可以倍增求出。考虑 $ g $ 的所有质因子 $ p_1, p_2, \cdots , p_k $ ，因为 $ g \leq 10^6 $ ，所以 $ k \leq 7...

题解模拟赛正睿

2019-09-09

0 439