苟且的狮子

题解

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

/ 注册

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

Optimal Milking 来自专栏

floyd+多重匹配+二分先使用floyd求得最短距离我们二分答案，然后跑多重匹配就好了。 #include<iostream> #include<algorithm> #include<vector> using namespace std; const in...

2020-11-10

2 631

Jamie's Contact Groups 来自专栏

想法都是二分答案。我的想法是跑网络流，建图。还有一种想法是，多重匹配。即在匹配时增加匹配数的判断。这是很有趣的。solution2是多重匹配的匈牙利算法。注意，我用HK算法实现多重匹配时发现非常慢！！！！所以建议用匈牙利！solution1： #include<iostream> #in...

2020-11-10

1 730

Cat VS Dog 来自专栏

真的是很巧妙的建边。我刚开始就想着猫和狗了。但事实上我们应该把小孩子当作节点，相互冲突的小孩连上边然后求最大独立集真的女少口阿我们事实上建造的是一个有向图，对一个有向图求解最大匹配。因为这里我们没有将整个图分为左右节点所以我选择的是匈牙利算法而不是hk算法。其实我想用hk算法的，但是我没有在不分...

2020-11-10

1 604

Strategic Game 来自专栏

最小不可相交路径覆盖。点数-最大匹配数代码如下： #include<iostream> #include<algorithm> #include<queue> using namespace std; const int max_n = 2000; const...

2020-11-10

1 589

Treasure Exploration 来自专栏

我又回来了！！！！这是典型的求最小可相交路径覆盖我们先求闭包，利用闭包连边，然后求解最小不可相交路径就可以了。什么？如何求解最小不可相交路径覆盖？点数-最大匹配数代码如下： #include<iostream> #include<algorithm> #include&l...

2020-11-10

1 393

Life Forms 来自专栏

算是挺简单的。有一些坑点。我们通过分隔符将字符串们连接起来。注意分隔符不可以相等，否则在匹配时分隔符可能被算上。然后我们二分答案长度，进行height分组，判断是否可行。得到正确的长度后我们再去找子串，只要找到分组就好了，然后随便记录下分组中的一个坐标。之后将这些坐标按照ranks[i]序排序就好了...

2020-10-21

2 569

Game of Hyper Knights 来自专栏

这也是nim游戏，但是sg就不是一个数了，而是一个二元组。考虑到数据量，我们可以直接记忆化递归暴力求解sg值，然后再异或就可以了##代码如下： #include<iostream> #include<algorithm> #include<vector> #inc...

2020-10-20

1 580

Again Stone Game 来自专栏

很明显是nim游戏，考虑到数据量，我们无法老老实实的求解sg值。于是我选择打表找规律。老老实实地打到sg[100]我们就发现了规律。sg[i] i为偶数时sg[i]=i/2i为奇数时，如果sg[i-1]为偶数(此时i-1为偶数)那么sg[i]=sg[i-1]/2 如果sg[i-1...

2020-10-20

1 627

Treblecross 来自专栏

nim 这算是一道变形的nim游戏的题目。这是从我学博弈论开始第一次独立做出来的还算有点意思的博弈题目。其实这里面的nim特征并不难发现。因为有符号'X'的存在将string划分成了几个小段。我们可以分别将这几个小段看成独立的nim游戏。最后再异或和，得到当前的sg值。从而判断这场游戏的胜负。 ...

2020-10-19

1 751

Caocao's Bridges 来自专栏

就是求桥而已，但是坑点很多。求出权值最小的桥，然后输出其权值。但是如果权值为零，我们仍要派一名士兵。另外如果图本身就不连通，我们优先输出0 代码如下： #include<iostream> #include<algorithm> using namespace std; co...

2020-10-19

0 827