苟且的狮子

题解

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

/ 注册

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

Cyclic Nacklace HDU - 3746 来自专栏

循环节问题经典的利用kmp算法解决。n-net[n]就是最小循环节cyc。如果n%cyc==0那么我们可以说正好，不用加否则就得加后缀但是有一个需要判断的地方，当cyc==n的时候没有循环节，那么我们要特殊判断了 #include<iostream> #include<algor...

循环节

2020-12-25

0 562

剪花布条 HDU - 2087 来自专栏

kmp轻改这里有一个条件就是我们在kmp匹配时，匹配的子串不能交错。很简单稍微改一下就可以了。当我们匹配成功时，直接让j=0从头开始匹配就好了。 #include<iostream> #include<algorithm> #include<cstring> u...

2020-12-25

0 605

Oulipo HDU - 1686 来自专栏

kmp模板题 #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int max_n = 1e6+100; int net[11000]; void...

2020-12-25

0 495

Number Sequence HDU - 1711 来自专栏

kmp模板题上模板就行了 #include<iostream> #include<algorithm> #include<string> #include<vector> using namespace std; const int max_n = ...

2020-12-25

0 455

MAX Average Problem

**题目，出题人说的什么G2玩意还是有收获的目前的斜率dp问题大致分为两类1.总结公式后，进行线性规划求解2.数形结合，与凸包相似。本题属于第二种。我们可以求一个前缀和。然后我们可以知到，对于目前的节点j其实就是在0->j-k中找一个点，使得(sum[j]-sum[i])/(j-i)最大...

2020-12-23

0 550

Marriage Match II HDU - 3081 来自专栏

sb问题，出题人题意说的什么G2玩意 #include<iostream> #include<algorithm> #include<vector> #include<bitset> #include<set> #include<ma...

2020-12-23

1 525

Escape HDU - 3605 来自专栏

状态压缩+最大流首先我们可以很明显的看出这是一个最大流问题。其实我们也是可以将这题看成一个匹配问题，用hk算法可能能过。我没有试。我们给出最大流做法。我们发现这里的点数实在是太多了，直接使用最大流算法肯定会超时。那么，我们分析题目。发现，行星m最多只有10颗。这意味着什么呢？意味着，对于一个人她...

2020-12-23

0 614

0 or 1 HDU - 4370 来自专栏

最短路、邻接矩阵这题拿到手里，我很是迷茫。我不知道这道题该怎么做？刚开始认为是构造，看不出来图论模型。原来，如果我们把给的矩阵看成图的邻接矩阵的话，那么我们就可以建立图论模型了。正如题解所说。condition1：节点1有一个出度condition2：节点n有一个入度condition3：节点2...

2020-12-23

0 601

Marriage Match IV 来自专栏

最短路+最大流刚开始没有理解题意，总感觉求一个最大流不就行了吗？原来真正的题意是，最短路始终不变的。我们每一次必须从最短路走。正确的做法是，我们正反方向求一次最短路。然后，枚举边。如果边<u,v> d[1->u]+e.cost+d[v->n] == mincost那么我们...

2020-12-23

0 533

Picnic Cows

斜率dp 斜率dp都不大好写啊，细节的边界处理感觉好麻烦啊。这里我们很容易就总结出状态和状态转移方程了。我们首先从小到大排序(在斜率dp中排序很重要，有利于保持决策的单调性)dp[i] 表示到第i个点为止的最小花费。dp[i] = min(dp[j-1]+sum[i]-sum[j]-(i-j+1)a...

2020-11-26

2 553