Flash_plus

题解

好题总结(6) 未归档(3) 杂(1) 游记(1) 知识点总结(9)

/ 注册

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

题解 | #Nim游戏#

最近学了一点博弈论。来写写blog造福人民(怕自己忘了)希望可以写出一篇比较好懂的文章,这里没有一些绕口的定义，也没有什么麻烦的代码，只有思维上的火花：先来讨论讨论什么是博弈论: 博弈论就是指有若干个人进行一些对弈，并且窝们默认每个人都是最聪明的，不会失误，都可以找到当前的最优解，然后来寻找有...

C++ 博弈论

2021-11-08

2 485

题解 | #Commentator problem#

推荐理由：细节较多的计算几何，适合一做。 Describe 在平面上有三个没有公共部分的圆，求平面上一点使得到三个圆的切线的夹角相等。 Solution 容易得出：稍加转换：那么我们只要找到一个点，满足他到个点的距离符合给定比例。我们设出平方一下，然后乘以分母。可以得到我们把 ...

2021-04-23

0 643

牛客提高23 - C 题解

题目大意有个数连成环，可以互相和相邻的交换，问最少交换多少次使得每个位置上的数相同。题解首先最终状态是已知的。这个问题有个很显然的性质是：必定有个相邻的位置不用交换。那么我们枚举交换的位置，就相当与把环化成了链。那么接下来再考虑链怎么化？设表示前个人最少需要交换的次数,...

贪心

2021-03-07

2 691

题解 CF1451B 【Non-Substring Subsequence】

题目大意给你一个长度为 \(n\) \(0/1\) 字符串，以及 \(m\) 个询问。每个询问会告诉你一个 \(l, r\)。问你在原字符串中有没有一个子序列和子串 \(s_l \to s_r\) 一样。题解你考虑只改变首或者尾，看能不能找到符合要求的子序列。我们来验证，如果...

分类讨论

2020-11-22

0 418

题解 CF1446A 【Knapsack】

题目大意给你 \(n\) 个物体，体积为 \(w_i\) 。并且给你一个大小为 \(c\) 的背包。要求你取若干个物品使得 : \(\lceil \frac{c}{2} \rceil \le \sum{w_i} \le c\) 并且输出取了哪些。题解考虑贪心。排序后从大往小的地...

贪心

2020-11-22

0 362

题解 CF222E 【Decoding Genome】

看到题，感觉预处理下 \(O(nm)\) 可以很容易的做到。大概处理下每一个串作为前缀，后缀所可以选择的数的数量。然后直接枚举，然后转移就行了。再看一眼数据范围， \(n \le 10 ^ 15\)。那没事了，很显然的矩乘的数据范围。但是矩乘就不可以这么做了，要换一种转移方法。 ...

矩阵乘法

2020-11-12

0 448

题解 CF1387B1 【Village (Minimum)】

CF1387B1 题解题目大意给你一棵树，你可以把所有节点重排，不能回到原来的位置，移动一个点从 \(a\) 到 \(b\) 的代价是 \(2\) 点之间的边数。题解贪心的思路很显然，因为要总移动最小，那么一个点肯定只会和自己相邻或者隔2个点的点连边。接下来考虑对于一个节点，他有...

树

2020-11-06

0 564

题解 P3545 【[POI2012]HUR-Warehouse Store】

P3545 [POI2012]HUR-Warehouse Store Describe 一共 \(n\) 天，每天上午会进 \(A_i\) 的物品，中午会有一个客人想要买走 \(B_i\) 的物品，当然你也可以选择不买，问你最后最多可以交易多少次。数据范围 : \(1 <= n <...

贪心

2020-10-18

0 419

题解 CF1225D

CF1225D：题意：\(a_i * a_j = x^k\) 求有多少组不同的\((i,j)\)对很妙的一道hash题/雾对于原来的柿子： \(a_i * a_j = x^k\) 我们可以转化成一种什么问题呢？看到后面的 \(x^k\)你就会想到分解原式，利用唯一分解定理可以得出：...

hash

2020-10-18

0 452

题解 CF813D

1. CF813D 题意：给一个长度为\(n\)的序列,求两个不相交的子集长度之和最大是多少，能放入同一子集的条件是首先顺序不能变，然后每一个相邻的要么相差\(1\)或者相差\(7\)的倍数。 \(n < 5000\) 题解： \(f[i][j]\) 表示第一序列到了第 \(i\) ...

桶 dp

2020-10-18

0 486