2016 CCPC 合肥站 解题报告

Tips

仅含题解，代码详见github。~~喜欢的话点个star~~
前几天终于把合肥的题补了一些。。。再往下就是lct了，暂时不学。

A、传递

题解：将P图和Q图的边取并生成一个新图（下称“合成”），有环则原来是不传递的。再将P图和Q的反图合成，有环则原来不传递的。
感觉知道结论还是不难理解的。。。反正我根本想不到。。。结束的时候听到有用最短路做的，这个才是重大失误，我们都没想到。
代码是按题解写的。

C、朋友

分析：不与根相连的值为1的边操作两次可以变为0，与根相连的值为1的边操作一次可以变为0。推理可知，答案仅和与根直接相连的那些1有关。

全场代码最短的题。。。我一直以为它代码是个几何题，好像读题的时候直接跳过了。。。现在发现只要敢做就能做出来= = 又是一个重大失误。
这题主要是一个数学推导的题目。。。
取两点 $v_1,v_2\in S,v_1\neq v_2$，可以利用平行四边形性质解得直线上的两点 $v_3,v_4$ 。
$$\begin{cases}
x_1+x_2=x_3+x_4 \\
y_1+y_2=y_3+y_4 \\
ax_3+by_3=0 \\
a’x_4+b’y_4=0
\end{cases}$$解得：$$\begin{cases}
x_3=\cfrac{a′bx_1+a′bx_2+bb′y_1+bb′y_2}{a′b-ab’} \\
y_3=\cfrac{aa′x_1+aa′x_2+ab′y_1+ab′y_2}{ab′-a′b}
\end{cases}$$再利用叉积计算面积：$$S=2\times \frac{1}{2}\times |\overrightarrow{v_1v_2}×\overrightarrow{v_1v_3}|=|(x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)| \\
=|(ax_2+by_2)(a′x_2+b′y_2)-(ax_1+by_1)(a′x_1+b′y_1)|\triangleq |f(v_2)-f(v_1)|$$

E、扫雷

相邻两格的差等于外面两列的差，直接递推。要特判 $n=1$ 的情况。

H、异或密码

直接暴力。

I、最大的位或

简单的来说，应该使$x(l\leq x\leq r)$与$r$或运算后尽可能将$r$高位的0变为1。

J、最大公约数

函数 f(x, y):
{
     c=0
     当 y>0:
     {
          c +=1
          t = x % y
          x = y
          y = t
      }
      返回 c * x * x
}

首先题目中给出的这个函数核心很像gcd，我们可以看出它的一个性质：f(u,y)==f(v,y), if u==v (mod y) 。这个性质是很显然的，因为这个函数的第一步就是 t = x % y ~~然而我并没有看出来~~。
所以，在该式$\lfloor \frac{i*j}{f(i,j)}\rfloor$中先枚举$j$，再枚举$i(1\leq i\leq j)$，此时其实每一个$i$都对应一个等差数列${i,i+j,i+2j,\dots}$ 。当然这题没这么简单，还有一个向下取整没有考虑。
将计算$f(x,y)$过程中的$c$值记为$c(x,y)$，则有$f(i,j)=c(i,j)(gcd(i,j))^2$。考虑把一个$i$对应的数列拆分成多个数列使得取整后仍为等差，可以发现当新的数列的公差为$c(i,j)*j$时，整个分式的公差为$\frac{(c(i,j)*j)*j}{f(i,j)}=(\frac{j}{gcd(i,j)})^2$，必为整数。因此，我们把数列拆分为${i,i+c(i,j)*j,\dots}$, ${i+j,i+j+c(i,j)*j,\dots}\dots$, 共$c(i,j)$个，分别使用求和公式即可。

最后贴一下坎普的题解。。。总共10个题都有 https://post.icpc-camp.org/d/628-2016

=========2016/02/20=========

这篇博客本来写了我一个下午。。。结果今天发现它出了点问题了。。。又补了一个晚上。。。哭死了。。。第一次这么感谢百度快照。。。

—— Summon, Light!

2016 CCPC 合肥站解题报告