苟且的狮子

题解

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

/ 注册

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

Silver Cow Party 来自专栏

水题反向建边，再跑一遍dij就可以了##代码如下： #include<iostream> #include<algorithm> #include<queue> #include<vector> #include<functional> ...

2020-10-11

1 499

Milk Patterns 来自专栏

二分+height分组 height分组真的很常用。我们只要二分长度就可以了。值得注意的是，第一次满足长度的height[i]此是贡献的相等的为2个后缀代码如下 #include<iostream> #include<algorithm> #include<map&g...

2020-10-10

1 518

The Accomodation of Students 来自专栏

二分图的判断+二分图最大匹配数使用黑白染色法进行判断，用HK算法高效计算最大匹配数##代码如下： #include<iostream> #include<algorithm> #include<cstdio> #include<queue> usin...

2020-10-10

1 536

Heavy Transportatio 来自专栏

松弛操作我们改变松弛操作为d[v]=min(d[u],e.cost)并维护一个大顶堆。注意输出格式代码如下： #include<iostream> #include<algorithm> #include<queue> #include<cstdio&g...

2020-10-10

1 437

Network 来自专栏

版子题，求割点代码如下： #include<iostream> #include<algorithm> #include<cstdio> #include<functional> using namespace std; const int max_...

2020-10-10

1 515

Dining 来自专栏

建图我们可以看看如何建图。首先保证每一份食物和饮品都只使用过一次。饿哦们可以把食物建在牛的左边，饮品建在牛的右边。食物连源点，饮品连汇点。这样就满足了。但是还有一个要注意的地方。就是每一头牛只能用一次。也就是说，我们每一头牛只能用一次。所以，要对牛进行拆点。代码如下： #include<...

2020-10-10

1 600

Network of Schools 来自专栏

缩点首先第一个任务，我们要找到至少应该发布任务的点数。我们很清楚的一点：如果这个图是一个DAG的话，我们只要在入度数为0的点处放置就可以了。但是在所给的测试样例中，我们可以看到节点1在一个环中。我们会注意到，在这个环中无论在那个点放置都可以到达所有的点。那边给了我们思路，我们先缩点，将图变为一个D...

2020-10-10

2 482

Musical Theme 来自专栏

最长不重叠子串很容易就会让人想到后缀数组。我们前后做一个差，然后就是类似求最长不重叠子串了。若两后缀的相同前缀长为i，那么最后就有i+1长的主题。所以这里不光是不重叠，还要空一。如何求解最长不重叠子串？二分，对height数组进行分组。(非常的巧妙！建议百度) 代码如下： #include<...

2020-10-09

1 542

ACM Computer Factory 来自专栏

水题看到oj下面好多人说拆点。但是，我没有拆点却也做出来了。从网络流的角度都去想没有什么障碍。我们构造出源点s和汇点t然后看有哪些机器可以和源点连，即input清一色为0或2 连(s,i)cap=Q[i]看有哪些可以可以与汇点连，即output都为1 连(i,t) cap = Q[i] 然后再看那...

2020-10-09

1 657

Fire Net 来自专栏

二分图匹配水题如果没有墙，我们直接放碉堡的话。我们可以肯定在所有放置的坐标中同一个行不能出现两次，同一个列不能出现两次。那么，有了墙的话意味着什么呢？意味着，我们有了额外的行和列！！！我们只要重新规定行和列就可以了。即，我们要找每个新出的区域。代码如下： #include<iostr...

2020-10-09

1 591