夏晓光(loveJY)的博客

A

乱搞

1. 直接dfs,然后IDA*
2. 搞出一个Dag,然后再Dag上求最长链,求完后打乱再求

std:

先弄出几天不相交的路径,然后考虑加入一些边合并路径

1 -> 2 -> 3

4 -> 5 -> 6

如果我们从2有边连出去,那么就要断掉两条链的一半

然后调整??

你会发现我们如果从3->4,就可以使边数增加

那么我们可以根据两条链这个边加入边数的增量来调整!

有这个退火策略就可以退火啦qwq

匈牙利做一般图最大匹配

小量舍去

?老师去摸了

先写个模拟器,支持输入两个点集输出他们的差

然后背包两个权值尽可能相同的集合

然后考虑退火来交换一下两个集合的元素

std:

让跑的时间尽量长的尽可能短,然后尽可能均分

k比较小,可以暴力dp做啊

k比较大的,可以动态点分治

看上去是带权二分图最大匹配,不行

然后考虑对于一个$A_iB_i$我们连一条边方向不定,这样会发现最后我们形成的图每个连通块不能有多余一个环

因为一个王子只能娶一个公主,所以就是每个点度数为1

边权排序一下

然后合并的时候你会发现就是判断连通块连通性

相邻并查集合并看看这个连通块有没有环就好了

把折线图画出来

显然我们不能有一个小于x轴的时刻

那么我们只能从哪个最低点出发走,这样至少哪个括号序列是合法的

交换一个括号一定是(.....),因为我们合法的数量是括号序列那些零点的数量啊

而如果我们交换)(会使得每个段+2而不是-2,减少了零点数量

交换上述括号会使得折线图中间一段-2

然后考虑从哪个每个数都大于等于2的极长段开始删就好了,直接维护一下前缀和之类的

可以做到线性....

观察蛇移动的贪心性质

我们不封拿出那条链,然后我们先要交换蛇头蛇尾

我们只有在一个链满足有三个叉才能交换

而又三个叉之后我们可以把蛇头移到一个叉中,然后把蛇尾移动到另一个叉上,然后再把蛇头移动到最后一个叉上

而这个点一定在a(叶子)->b(叶子)的那个链上,同时要满足三个叉的最大深度都大于蛇身长度才行

我们才能导进去导出来

线性规划转对偶

在某个时刻在R先生那里寄存信之后,每个时刻都要寄存信....

因为你但凡不去寄存就意味着一封信放到TLE,而这个显然是可以其中让某个人去寄存一次拿走的

那么我们会发现每次我的时间开始的时候就一定去寄存信

因为但凡我不寄存直接送人家的信也一定在那耗钱然后没有意义啊

所以说第一次一定会去寄存,然后之后可能直接送可能寄存

那么我们枚举第一次,然后剩下的每一段都可以贪心暴力了

时间复杂度$O(n)$

首先让所有棋子霸占对角线

然后我们把每个棋子移动到指定位置即可qwq

为什么要做第一步而不是直接移动?

因为我们要避免移动到关键pos被其他棋子挡住的情况啊!

所以你会发现我们先从中间对角线向最远的那个移动,IDA*一下,然后再向次远的......

一直做下去是不会被挡住的

向如果一个格子被一个看不到格子的传感器看到删除

如果一个格子多个看到格子的传感器看到不同颜色,也删除持续这个过程我们就知道每个格子的存在性和他应该的颜色了

直接模拟这个过程!

二分:连续函数...满足勘根定理

汉明码

用2^k位置记录这一位的奇偶性

这样一旦某一位翻转了就能知道是哪一位了qwq

直接二分答案,然后考虑对于一个mid,如何判断是否合法,可以把小于mid的全部加入然后暴力查询

那么整体二分也是一样的,直接二分一下答案然后把小于mid的询问和修改分左边,大于等于mid的修改分到右边

注意值域收缩到一个数会直接赋值啊

wqs二分

很easy,凸优化做全一套,可以斜率优化qwq就斜率优化

直接01分数规划,每个数减去二分值

然后看有多少子串值大于0,这个满足条件子串数能不能大于k

然后你会发现我们要查一个$sum_r$前面的小于等于他的$sum_l$

这个可以树状数组,要是值域太大了就set吧/kk

每次这个gcd值会变小一半吧

所以说我们直接二分那个右端点即可,怎么快速判断?线段树??

QAQ

反正两个log都可吧(方言)

二分这个距离之后,你会发现我们能draw出一个圆

然后交点在园内就是abab的情况(两直线和圆的交点交错)

怎么维护abab情况?

相当于一个序列每个数出现恰好两次然后问你这个交错组有多少种

直接静态二维数点,会发现把靠前的第一个端点放在x轴,然后第二个放在y轴上就能二维数点写公式了.....

最后要找到这些圆和直线的交点?

QAQ

我们要找到前k的交点和

你会发现知道第k个那么前k个一定都在这上面,极角排序

可以用set来维护一下,然后这个复杂度$O(m+nloglog)$

轻松二分???一个串?

等等,$n<1000$?

本质不同的子串只有一些

然后记录一下$n^2dp$?

$f_{i,j}$表示考虑了前i个字符划分了j段,直接向前转移是T的

然后我们考虑向后转移,因为越靠后这个东西字典序越大,所以只会有一个pos可以

做法就是找到这个pos然后向后维护一个差分?或者后缀和即可

Uoj305

先二分一下,会发现我们一个点不能对应一条边

然后你考虑预处理数每个点走到其他点最短路的以及在这个点买入并在那个点卖出,把这个当边

然后你考虑跑一个$floyd$如果得到一个最大环大于等于$0$就是可行的qwq

做完了复杂度$O(logn*N^3)$