HDU

· · 个人记录

闲的没事来打打 HDU，队友是 Kubic 和杜老师，号是 826。

1008

如果每个数都出现了 2^k 次，那么先加 k 个 0。

然后从小往大扫描，就可以贪心构造一个字典序最小的线性基。

1005

改边权显然只可能改成 0，那么就相当于把点集划分成若干子集，使得每个子集在两棵树上都是连通块，且缩点之后两棵树同构。

不难发现，当且仅当一条边两端的点集在两棵树上都一样时，这条边的权值可以不用改成 0，所以我们数一数有几条这样的边即可。

判定集合相等可以用个异或哈希。

1010

如果一个长度为 l 的子串是好的，可以推出 S 有周期 l，从而每个长度为 l 的子串（除了前后缀）都是好的。

所以我们预处理 S 的所有周期，设它们构成集合 P，那么 S[2,n-1] 的所有长度属于 P 的子串都是好的。

要统计 T 的一个子串有多少个不同好子串，首先用 SAM 做子串匹配，求出每个 l 往右最多延申多少还是 S[2,n-1] 的子串（记为 T[l,l+suf_l-1]），以及每个 r 往左最多延申多少（记为 T[r-pre_r+1,r]）。

询问时，首先 [l,\min(r,l+suf_l-1)] 这段前缀可以直接统计，然后剩下的那段后缀和 l 没关系，求一下前缀和就行了。

1006

设关键点为 C。答案显然是删掉凸包上一条边 AB，然后将 \triangle ABC 内的点按照 C 的极角分成一个前缀和后缀，分别与 A,C 和 B,C 做凸壳。

只要求出每个前缀和后缀的凸壳周长就行了，这是个动态凸包问题，但是由于有个特殊性质是每次新加的点一定在新的凸壳里和 C 直接相邻，所以每次弹出凸壳的一定是靠近 C 的一段，用一个栈就可以解决了。