Flash_plus

分类

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

/ 注册

全部文章（共60篇）

题解 | #Nim游戏#

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

C++ 博弈论

2021-11-08

2 485

题解 | #Commentator problem#

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

2021-04-23

0 643

牛客提高23 - C 题解

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

贪心

2021-03-07

2 691

生成函数

生成函数简介生成函数 \(\text{(generating function)}\)，又称母函数，是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。 by wiki 用人话来说生成函数就是把一个序列变成了一个函数。一个形如 \(F(x) = \sum_{n > ...

生成函数

2020-12-27

0 454

题解 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

矩阵那些事

什么是矩乘一些好题这里没什么板题，都是些比较妙的矩乘，逐步深入。这是一个蒟蒻的刷题历程，大佬轻喷。这里面的题目都没放代码，因为矩阵的代码一定要自己写一遍，每个人的都不一样的。 [NOI2012]随机数生成器题目大意给你很多数字：\(\text{m, a, c, x0 n, ...

矩阵乘法

2020-11-01

0 568

一些很妙的思维题

P4643 [国家集训队]阿狸和桃子的游戏题目大意有一张 \(n\) 个点 \(m\) 条边的图，点有点权，边有边权。先手后手轮流染黑白两色，最后的得分是自己染的点权和 + 两端均为自己的颜色的边权和。双方都希望自己的得分 - 对手的得分最大，求结果。 \(1 \le n \le ...

好题

2020-10-18

0 545