无

无

Codeforces Round #665 (Div. 2)

见本周推荐

无

无

见本周推荐

Codeforces:

Divide Square

题意:

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

tag:线段树,计数

题解:

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

comment:

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

http://poj.org/problem?id=2778

题意

串都是由字母 $\text{A, T, C, G}$ 组成的。 给 $m\in[1, 10]$ 个串，每个长度 $\in [1, 10]$。 给一个长度 $n\in[0, 2\times 10^9]$，求所有长度为 $n$ 的串中，有多少个可能的串，其不包含任意一个之前给的 $m$ 个串。 答案对 $10000$ 取模。

题解

看到 $n$ 这么大，先考虑 $m$ 个串。在 $m$ 个串的 $\text{trie}$ 上考虑构造长度 $n$ 的串。因为是一个子串都不能出现，所以相当于在考虑了 $\text{fail}$ 的、有环的 $\text{trie}$ 图上随便游走，但不能经过某些特殊的点。

那么问题转化为求路径数。刚好 $\text{trie}$ 图的节点数 $=\Sigma len_i\le 100$ 很小，那么邻接矩阵快速幂即可。复杂度 $\text{O}(~(\Sigma len_i)^3 \log{n}~)$

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的异或和应该是一样的。所以按蒙的方式算一次就行了。