苟且的狮子

题解

2020多校(6) CF(27) 作业(3) 区域赛真题题解(提升思维！！！)(8) 寒假模拟赛(1) 未归档(1) 苏州大学排位赛(7) 随笔(1)

/ 注册

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

Power Strings 来自专栏

KMP!!!!骗子！！！！！骗子！！！！骗子！！！！！！这道题被放进后缀数组题单里面。但是用后缀数组的方***超时。t到死。。。。。。。。。骗子！后缀数组思路：我们要求最小的循环子串。利用后缀数组：如果 a1 a2 a3 a4 a5 a6 a7 a8 a9 的最小循环子串长为3即以a1 a2 a...

2020-10-13

0 523

Swap HDU - 2819 来自专栏

思维题我们仔细想想对于行列交换如果是这种情况：1 0 0 01 0 0 01 0 0 01 0 0 0 我们是必死的。因为行列交换无法是我们将第一列中那聚在一块的4个1分散到其他的列中。也就是说，行列交换无法使原本没有1的行/列有1 那么一个充分条件就是，对于每一行每一列，我们至少要有一个1.这...

2020-10-13

1 582

Game of CS 来自专栏

树上博弈，真难。。。。。。 https://blog.csdn.net/lr7682/article/details/100067840 Colon Principle：当树枝在一个顶点上时，用一个非树枝的杆的长度来替代，相当于他们的n异或之和。 #include<iostream> #...

2020-10-13

1 495

Network 来自专栏

LCA+tarjan+桥+dsu 蒟蒻刷到个难题。。。。。。题目给的图一定是联通的。我们大致的想法是：先进行缩点。把图变成一个树。节点与节点之间用桥连接。这并不难，我们tarjan一下，找到桥然后染色就可以了。然后添加边时。在书上的两个节点之间连一条边。一定会构成一个环。这个环中原本的边会失去桥的...

2020-10-12

1 631

Going Home 来自专栏

最小费用流的水题我们可以以每一个格点为节点建图，也可以根据曼哈顿距离建图。都无所谓。这题如果根据曼哈顿距离的话，其实还可以用KM算法去做。这里给出费用流的dijstra写法： #include<iostream> #include<algorithm> #include&...

2020-10-12

0 471

Wormholes 来自专栏

判断负圈的版子题之前的题用Bellman法判断过了。这里就用spfa判断一下负圈吧。用spfa判断负圈的方法有两种：1.记录节点入队的次数，若次数>n-1则有负圈2.记录起点到节点经历的边数，若边数>n-1则有负圈（也可以理解为途经的节点数）第二种会更快一点代码如下： #incl...

2020-10-12

1 533

New Distinct Substrings 来自专栏

我们枚举后缀，以当前后缀开头为起点计算不同的子串。那么重要的就是，我要知道有多少当前后缀的前缀是重复的。即别的后缀也有。我们按照排名，遍历后缀。假如我们遍历到后缀i。然后我们知道后缀1到后缀i-1与其最长的公共前缀长为k那么后缀i能贡献出len(后缀i)-k个不同的子串而与前i-1个后缀的最长公共前...

2020-10-12

1 569

棋盘游戏来自专栏

增广路这道题，关键就是让我们判断。二分图匹配时，有哪些边是必须被用上的。一个简单朴素的思想就是：我们枚举边，删除这条边后在求其最大匹配数。看是否减少了。能过，但是复杂度其实是极高的。那我们想一想是否可以优化这个算法？事实上就是增广路的思想。我们删除这条边后，不需要再从头开始求最大匹配数。而是，我们...

2020-10-12

2 736

Critical Links 来自专栏

判断桥代码如下： #include<cstdio> #include<iostream> #include<algorithm> #include<vector> using namespace std; typedef pair<int, i...

2020-10-11

1 585

A Plug for UNIX 来自专栏

水题注意建图，转换器是无限的。另外不能建设备。会t##代码如下 #include<iostream> #include<algorithm> #include<queue> #include<cstdio> #include<set> #...

2020-10-11

1 498