结束了，一切都结束了。 先浅谈一下这次 NOIP 首先本来这次是抱着很大的希望的，毕竟准备了那么久，还是希望能够拿到比较高的奖项，然而结果却非常令人失望。 DAY 0 考前为了鼓舞士气，我特意做了个主题，现在看来却是讽刺至极。 因为考试当天是星期六，所以在此之前一天我们收拾收拾就回去了，刚好还能不占月假（因为学竞赛，这可能是我们第一次放月假），回到家后想起同学说的长 RP 的...

这是一篇图论做法题解 闲话：我看到基本上都是动态规划做法，但我考场上第一时间想到了图论，并且个人认为图论做法更好想到一些，故写此题解。 思路 首先，容易知道对于一个点的贡献，可以认为是一定比该点小的点的个数，而在这里很容易想到可以从该点连边到比该直接点小的点（即题目描述中直接用 或 连接的点），而题目描述中出现若干的点值可能相等，我们可以将这些点合并为一个点并统计相同的个数，然...

闲话 基于本题没有题解，那我来水一发网络流，先声明一下，本篇题解可能有部分口胡现象（本人太菜不会证明，但结论是对的，感性理解一下）。 正文 本题的结果不能直接用网络流跑出来（至少我不能）。网络流的题重在建图，但这题不一样，他更多是在考察对残余网络的操作。 首先我们看这个东西和二分图匹配有点像所以先把图拆点然后画出来，如下。 显然这个图的最大流（最大匹配）是 ，即最多能选出三...

闲话 基于本题已经有人写了匈牙利的题解，这里我就来写一篇关于网络流的题解。 能做这道题的人应该都能看出是裸的最小重复路径覆盖问题吧。 虽然最小路径覆盖原代码只会红一个点。 思路 首先网络流的难点一直都是在于建图，那么这道题该怎么建图呢？ 引入 先想一下普通的最小路径覆盖集问题，我们的见图方式是将每个点拆为出点和入点，目的是保证每个点刚好只被所有路径经过一次。 然后将源点和入点...

题意简化 每次修改一个点的横坐标，求斜率最大值 如何思考 首先考虑，如果没有修改操作，只是单纯的问你任意两点之间的斜率，该怎么办？ 暴力 这里有一个 的做法是任意点都算一遍求最大斜率但显然不可能。 优化 其实学过斜率优化的都知道可以先以横坐标为关键词排个序（可以理解为在坐标轴上画出来），然后要求的任意两点的斜率最大值就是是排序后相邻两点的斜率的最大值。 那没学过怎么办，这...

P9384 构造题，首先考虑爆搜，但结果跑不出来。 既然题目中描述相同元素不能构成三元环或五元环，其实可以把条件用的更局限，考虑相同元素只能构成偶环，即同一权值的边构成二分图，可以发现本题刚好 种颜色，刚好 。 接下来考虑怎么构造二分图，本题大部分思路都是令 ，并将 作为染色的依据，但没有提到怎么去想出这样的思路。 首先，令一个集合 ，其中的元素互不相同,且都不为零。 令另...

最大流_dinic EK算法 由于最大流中一定没有增广路由于最大流中一定没有增广路 可以不断从源点出发寻找增广路可以不断从源点出发寻找增广路 并在残余网络上修改并在残余网络上修改 直到不存在增广路为止 dinic 由于EK每次只能搜索1条增广路 在EK算法的基础上,建立分层图,并搜索多条增广路 123456789101112131415161718192021222...

最短路 SPFA 12345678910111213141516171819202122232425void spfa(int start){ queue<int>q; memset(dis,0x3f,sizeof(dis)); memset(cis,0x3f,sizeof(cis)); dis[start]=0; q.push(start); ...