威风镰鼬

题解

/ 注册

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

题解 | #Best Cow Fences#

思路求长度不小于L的平均值最大的子区间。可以用前缀和+二分的思想去做，复杂度O(nlogn)。对于每个数减去二分的平均值，并且算出前缀和。那么我们用一个数记录前i个数中总和最小的区间[0,k]，那么只需要判断前i个数最大区间[0,i]-[0,k]是否大于0即可。代码 #include<bi...

二分前缀和

2021-09-14

2 430

题解 | #Petya and Array#

代码转载自https://www.cnblogs.com/cj-xxz/p/9811806.html写得太好了，可惜没有注释，所以这里解释一下CDQ分治的写法。首先处理前缀和，要求的是sum[j]-sum[i]<t的区间数量。离线操作，对前缀和排序，就变成了一个二维偏序问题，对左区间任意i，...

CDQ 分治

2021-09-12

1 483

题解 | #可达性#

思路看到圆就很想吐，但幸好想到了每个圆代表的区间其实就是所以问题就转化为：最少能用多少个子区间将总区间表示出来。然后是怎么选区间的问题，只要将每个区间排序，然后贪心地去选就好了。先排序，每个区间L小在前，然后是R大在前，然后只要我没有达到最大长度，就选一个区间使得我能到达最远的距离，然后ans++...

贪心

2021-09-02

1 345

题解 | #可达性#

思路首先tarjan缩点，保证是一个DAG之后，再输出topo排序的起点就可以了。不过数据是不是放水了，我求出来的强连通分量是按访问顺序定谁是fa的，交上去也是对的。难道不应该是要保证每个scc的fa都是里面编号最小那个点吗？所以我弄了个flag数组意义注释了。莫名其妙就A了希望大佬能帮我解答一下...

图论强连通分量

2021-08-31

3 453

题解 | #字符串的问题#

思路首先如果要求最大前缀的话，我们用Kmp就能线性求出来。题目要求中间也有一个和最大前缀一样的东西，久相对增加了点难度。那我们失配数组每个值出现的次数，如果最终nxt[len]（即整个串的最长后缀）出现过不止一次，就可以输出答案了。但是这样写还需要考虑点细节。比如aaaa的情况，在中间出现的并不能...

kmp 字符串

2021-08-29

1 602

题解 | #[HNOI2006]超级英雄HERO#

思路洛谷上额外要输出匹配方案，大家可以做一做，代码上注释了。对每个问题进行二分图最大匹配，套一个匈牙利算法的模板，如果没有找到匹配，马上跳出。代码 #include<bits/stdc++.h> using namespace std; const int maxn=2005; s...

二分图

2021-08-27

1 471

题解 | #Graph Coloring I#

思路无非就两种情况：可二涂色或者存在奇环。那么我们在dfs的过程中留意有无涂色不符的情况，没有发现就直接输出一种涂色方案就行了。现在问题就是找到奇环该怎么输出呢？因为我是个笨比所以一开始写了个tarjan记录SCC，然后去输出第一个奇数并大于1个点的SCC的每一个点编号，结果只过了45.45%（所...

搜索二分图 tarjan

2021-08-26

3 567

题解 | #[ZJOI2007]矩阵游戏#

思路本来想着这是一道最大匹配的水题，没想到忘了变量初始化WA了。用匈牙利算法水过，题意大概是这个意思，假设我们有两个点集X和Y，那么输入就可以转化为二分图两边点的连线情况。交换行列式的过程，实际上是固定一个点集，另外一个点集内部在交换位置（讲得很抽象，画图试试？）然后就可以想到只要每个点都有与之匹...

二分图图论最大匹配

2021-08-25

2 449

题解 | #Football#

思路我们采用动态规划的思想，从每一轮出发，计算每支队伍这轮获胜的概率。基于全概率公式，队伍概论胜利的概率可以由对阵其他可以打的队伍获胜的概率之和。现在问题就是如何表示该轮可对阵的队伍：假设由2^n只球队，如果j在[0,2^(n-1)]里面，k在[2^(n-1)+1,2^n]里面，那么很明显他们要在...

动态规划数论概率dp

2021-08-20

1 384

题解 | #The Stable Marriage Problem#

思路稳定婚姻问题，可以直接应用Gale-Shapley算法求解。看到没人交我也不写了，抄了一下林厚从的板子，注释很清楚了。代码 #include<stdio.h> #include<queue> #include<cstring> #include<al...

组合数学

2021-08-18

1 421