UOJ Logo peehs_moorhsum的博客

博客

如何使用调整法

2023-01-17 17:34:50 By peehs_moorhsum

如果大家不知道调整法是什么,可以去复习我非常民科的集训队论文。

CTS的数据表明,很多网友不太知道调整法咋用。这里分享一点诀窍。

首先,调整法主要用于限制较松散的题目,要找到性质中松散/容易满足的那股劲。如果题目中有些限制难以满足,你就用人类智慧把它们先满足了,剩下的部分交给调整。不要让调整去摁做很严格的限制。

其次,要找到容易变动且和目标相符的估值。这一部分有时是简单的(比如:不满足的条件个数),有时需要用力对着组合结构构造一下(例如:将哈密顿路转化成一些较容易满足的条件)。一般来说,对具体问题需要用具体的估值,不要都转到某个NPC硬做。

一个简单的例题是今年WC T2。做法很简单。容易看出,最大的集合的限制可能很紧,其他集合的限制都很松散。我们首先规定最大的集合中元素放置在哪些位置(例如:放两个空一个,放两个空一格,以此类推)。之后可以调整,调整的内容为不满足的对子数。每次找一个有矛盾的位置,随机选取一个别的和它同在/同不在最大集合的位置,看看换完后矛盾会不会变少。这样一下子就过了,很快啊。

大家学会了吗?

另一道例题:

将 1 ~ nm 放置在 n * m 的方格表中,使得相邻位置互素。

评论

Itst
太深刻,希望今年国家队能拿调整法杀穿 ioi。
masterhuang
今年wc那题复杂度如何证明呢 @peehs_moorhsum
pink_rabbit
邓老师,我记得原来调整法在 UOJ 有个博客展示怎么过掉哈密顿链。 在哪里啊?
AKEE
感受那股劲!
2569276969
问一下最后那道例题的解法是 先黑白染色,给一种颜色全放偶数,然后从大到小随机往里放是么?
JeffZhao
那个例题感觉可以先把 1 ~ nm random_shuffle 一下然后填到网格里,然后随一个不合法的位置,设这个位置的数为 x,然后随一个与 x 不一样数,看看交换之后冲突点对会不会减小,减小了就交换
acwing_gza
感受那股劲!

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。