CF461E Appleman and a Game
题意有两个字符串 $s,t$，有一个人在玩游戏。他的目标是凑出串 $s$。初始他有一个空串，每次可以找出 $t$ 的一个子串接到这个串的后面，他会最小化他的操作。现在你想找到这样一个长度为 $n$ 的串 $s$，使得他需要的操作次数尽量大。$n \leq 10^{18},1 \leq |t| \leq 10^5$。题解显然先手每次都是暴力找到最长的能和当前这个后缀匹配的 $t$ 的子串然后贪...
题意有两个字符串 $s,t$，有一个人在玩游戏。他的目标是凑出串 $s$。初始他有一个空串，每次可以找出 $t$ 的一个子串接到这个串的后面，他会最小化他的操作。现在你想找到这样一个长度为 $n$ 的串 $s$，使得他需要的操作次数尽量大。$n \leq 10^{18},1 \leq |t| \leq 10^5$。题解显然先手每次都是暴力找到最长的能和当前这个后缀匹配的 $t$ 的子串然后贪...
A一个暴力的想法是找出这条链，暴力跳。跳的定义是走到第一个满足和 $\geq k$ 的位置。于是可以想到用倍增。设 $f_{x,i}$ 表示 $x$ 点跳 $2^i$ 步在哪个点，首先跳 $2^0$ 步可以二分预处理，然后直接转移就好了。但是这只能处理往上的，往下怎么做呢？一种方法是直接树链剖分，就变成了若干个链的问题，但是这是 $O(\log^2n)$ 的，又难写又难调。我们可以观察到对于...
A. 星际穿越感觉也很神。。先将询问拆成前缀和的形式，我们要对于一组询问 $(l,r)$ 求出 $[l,r]$ 内所有点到 $r$ 的最短距离的和。考虑 $r$ 往左走的最短路径是怎么走的：引理一：往右走之前一定不会往左走反证法。如果先往左走在往右走，那么这个右边的点一定能 cover 到起点，所以可以第一步就先往右走，答案不会变劣。引理二：不会存在连续的两次往右走反证法。如果存在两次连续的...
没想到非 Chinese Round 也会出这么毒瘤的题目......题目大意：对于正整数序列 $A$，定义序列 $B$： $B_1=A_1,B_i=B_{i-1}\ or\ A_i,i\in[2,n]B $ 其中 or 为位或运算。 每一个序列合法，满足对于$ \forall i\in[1,n]$，有 $A_i\in[1,2^k])$ 而且对于 $\forall i\in[2,n]$，有$...