2009-2010 ACM-ICPC, NEERC, Southern Subregional Contest

@M1saki 2017-07-18T16:47:36.000000Z 字数 1465 阅读 1607

acm 2017年7月 codeforces 组队训练

rank	ac/all	A	B	C	D	E	F	G	H	I	J	K
42/128	9/11	O	.	O	O	Ø	Ø	O	O	.	Ø	O

.	尚未通过	O	当场通过	Ø	赛后通过

比较复杂的模拟。

按可靠值从大到小排个序，贪心去取即可。
注意输出路径的时候要重新排个序。

考虑寻找循环节，若循环节存在且不超过2e7，则必然存在 $a[i]==a[i+T]$ ，其中T为循环节。
因此找到循环节之后，从小到大for一遍i，找到的第一个满足上式的即为答案。
否则则为-1。

这道题如果考虑跑的周期的话，最末尾的那一段处理起来会很麻烦，所以我们可以考虑相遇的周期。
记 $p=v_1+v_2, q=|v_1-v_2|$ ，那么两个人第一次相遇时，总路程走了 $L$ ，之后每次再相遇都需要走 $2L$ ，因此有

$\begin{equation} pt=(2k_1-1)L \\ qt=(2k_2-1)L \end{equation}$
由于上面考虑的是相遇点在中间的情况，所以你还要考虑，两个人在端点相遇的情况，这些情况被算了两遍，需要减掉。
有:

$\begin{equation} v_1t=k_3L \\ v_2t=k_4L \end{equation}$
由于在端点相遇，那么k1与k2为一奇一偶。记

$g=gcd(v_1,v_2)$ 由上式可以得到，

$\begin{equation} \frac{v1}{v2}=\frac{k1}{k2} ==>\frac{gv_{1x}}{gv_{2x}}=\frac{k1}{k2} ==>\frac{v_{1x}}{v_{2x}}=\frac{k1}{k2} \end{equation}$
因此

$v_{1x}$ 和

$v_{2x}$ 也必须为一奇一偶，此时有

$gt_0=L$ ，得到

$t_0=\frac{L}{g}$ ，记

$cnt=\frac{T}{t\_0}=\frac{Tg}{L}$ 。这样可以得到在端点相遇的次数为

$m=\frac{cnt+1}{2}$
所以，最后的答案即为，

$ans=k1+k2-m$

可以考虑建一棵1e6的线段树。
那么对于a[i]，查询1~a[i]-2,a[i],a[i]+2~10^6三段的最大值，以a[i]结尾的最大值就是该值加1，在将值插入线段树，更新，最后求答案时从末尾在遍历一边即可。

模拟。

比较显然的二分。

妙啊！！！
考虑每次相对变化只能变化一个人或者邻近的一个人，这个时候发现，@格雷码这个神奇的东西恰好可以满足这个性质。
因此，枚举1~(1<

比较有趣的递归。