无

无

Codeforces Round #665 (Div. 2)

见本周推荐

无

无

见本周推荐

Codeforces:

Divide Square

题意:

给出一个边长为$1e6$的正方形,在这个正方形内部有一些线段,每一个线段都和坐标轴中的一个平行,且一定和正方形的某条边相交.求这些线段将正方形内部划分为了几个部分.

tag:线段树,计数

题解:

应该算是结论题吧.依次将这些线段添加到正方形内部,如果和之前的线段有$x$个交点,那么答案增加$x$;如果这条线段和正方形的两条边都相交,那么答案再加1.

comment:

比赛的时候没有想到通过数交点的方式来计数,这个思路挺神奇的.

https://atcoder.jp/contests/abc171/tasks/abc171_e

题意

有一个长为n(n为偶数)的非负整数序列a[i]，生成另一个序列b[i]，生成方法是b[i]=a[1]^a[2]^…^a[i-1]^a[i+1]^…^a[n]。给定序列b[i]，问a[i]。

comment

直接对着样例蒙了一下a[i]=b[1]^b[2]^…^b[i-1]^b[i+1]^…^b[n]好像是对的，然后想证明的时候发现为什么要确保n是偶数。

题解

将b[1]到b[n]全部异或起来，发现值相当于a[1]到a[n]全部异或了(n-1)=1（mod 2）次，说明a和b的异或和应该是一样的。所以按蒙的方式算一次就行了。