Codeforces Round #545 (based on Moscow Open Olympiad in Informatics)


Div2A-Sushi for Two

把连续相同的数看作一段,连续的两段的贡献就是两个段长度的 min ,找所有连续段中的最大值即可。

Div2B-Circus

没想到被Div2 B搞自闭了。

我们先假设把所有的都分到第二组,那么接下来划分回第一组的话,只需要看这个人能表演的节目数量。他能表演的节目数量就是他对\(x\)和\(y\)差值的贡献。

表演两个节目的人有\(a\)个在第一组,我们设表演两个节目的人有\(a\)个在第一组,表演零个节目的人有\(c\)个在第一组,满足方程\(2a+b=y,a+b+c=n/2\),暴力枚举\(a\)的取值,输出即可。

Div1A/Div2C-kyscrapers

预处理每一个位置在行和列中的相对大小排序。

一个位置的标号即是,行和列中相对大小的 max (为了所有保证比他小的数都有标号),他所在的十字区域的最大值,即是他的大小 +max(行里比他大的数个数,列里比他大的数个数)。

Div1B/Div2D-Camp Schedule

要使得匹配量最大,显然每次构造完一个以后,要从前后缀的极大匹配位置继续往后构造。

KMP预处理前后缀的最大匹配位置,暴力构造即可。

Div1C/Div2E-Museums Tour

Div1D/Div2F-Cooperative Game

我们考虑派出\(0\)和\(1\)去寻找结束节点。

保持每回合\(0\)前进的总步数是\(1\)前进总步数的两倍,可以发现,当\(0\)和\(1\)相遇的时候正好是离结束节点\(t\)步的位置。

证明一下这个结论:我们假设\(0\)走了\(x\)步,那么\(1\)走了\(\frac{x}{2}\)步。

显然有\((x-t)\%s=(\frac{x}{2}-t\%s)\),即\(x\%s=\frac{x}{2}\%s\)。

我们设\(x=2k\),则\(x=k\),设\(2k\%s=p\),那么\(k\%s=2k\%s=p\),于是有\((2k\%s)-(k\%s)=0\),即\(k\%s=0\)。

也就是说\(0\)和\(1\)的结束位置再走\(t\)步恰好\(\%s=0\)的位置,即结束节点。

于是在\(0\)和\(1\)相遇以后,让所有的节点一起走,当所有节点重合的时候,就是在结束节点的时候了。

You may also like

2019 CSP-J2 题解

【TJOI2015】弦论

LEAVE A COMMENT

Statistics

  • 0
  • 2,490

Categories

Archive