Law_Aias

未归档

题解(5)

/ 注册

全部文章 / 未归档（共110篇）

声明

蒟蒻的博客食用声明一只来自SD的蒟蒻瑟瑟发抖本人的博客包含许多OJ题目题解和模拟赛题解。所以OJ题目可以放心随意食用。不过因为蒟蒻的blog里的模拟赛来源广泛，所以不公开，如有需要，请将页面拖至底层并用QQ私信窝。博客左下角有链接，仅QQ能用。

2019-09-12

0 378

ZR#957

ZR#957 解法：首先 $ T $ 必须得要是 $ S $ 的子序列，不然不存在好的下标序列，因此一定无解。考虑判断一个串 $ T $ 是不是 $ S $ 子序列的贪心做法：每次从没有匹配的位置中，选择第一个和 $ T_i $ 一样的与 $ T_i $ 进行匹配。设这样得到的下标...

题解模拟赛正睿

2019-09-11

0 416

ST表

ST表什么是ST表 ST表是一种神奇的数据结构，它虽说有它的短板——不支持修改，但它的特点同样很鲜明——短小精悍，能做到 $ O (n \log n) $的预处理， $ O(1) $ 的单次查询。实现方法： ST表分为预处理和区间查询两个部分，实现起来十分简单。预处理的预处理： ...

倍增

2019-09-10

0 467

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 432

ZR#999

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

题解模拟赛正睿

2019-09-08

0 438

ZR#998

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

题解模拟赛正睿

2019-09-08

0 438

ZR#997

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

题解模拟赛正睿

2019-09-08

0 357

ZR#996

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

题解正睿模拟赛

2019-09-08

0 441

CF1217C

CF1217C 题意：给定一个01串，一个good01串的定义是这个01串所代表的二进制数字刚好等于它的长度，允许前导零，问这个01串当中有几个good子串解法：枚举每一段连续的 $ 0 $ ，$ num_0 $ 为 $ 0 $ 的个数，后面的数值为 $ res $...

题解 Codeforces

2019-09-06

0 406

CF1217B

CF1217B 题意：有一个有 $ x $ 个头的龙，你有 $ n $ 种方案，每种方案中包含你可以砍掉的头 $ d_i $ 和龙会生长的头 $ h_i $ 找到一种方案，使得操作数最少。解法：考虑贪心，因为没有规定每种方案只能使用一次，所以我们可以记录一个最大的 ...

Codeforces 题解

2019-09-06

0 412