转载请注明出处:http://tokitsukaze.live/
题目链接:http://codeforces.com/gym/101981
补题进度:8/13。
考虑对称操作。先手能拿中间,必胜。
n为奇数,先手只需把中间一个拿了,所以先手必胜。
n为偶数,先手需要拿中间的两个,所以k=1时先手必败,否则先手必胜。
注意特判n=0是先手必败。
最小包围球。模拟退火的时候往最远点靠近即可。
注意题意是能连续翻k个状态相同的硬币。
qls:一个观察是你可以把每个 1 在不跨越其他 1 的情况下往左右移 k 个位置。尽可能把 1 往左靠,出现连续 k 个 1 就消掉。check 两个串处理之后的串是否相同。
一个1能往左移k个位置,那么中间肯定有k个0。所以就变成了消消乐,把连续的k个1或者0都消掉,用栈模拟即可。
G.Pyramid
ans=C(n+3,4)。不会推。
有位牛逼网友看了说:
于是这位牛逼网友补充了推导:
对于一个正着的正三角形,他的内部会有边长-1个正三角形,和他本身一共就会有边长个正三角形,
一个边长为n的大三角形,他内部会有从边长从1到n的正三角形,
对于边长为i的正三角形,会有(1+(n-i+1)) * (n-i+1) /2 个,
则他的贡献为(1+(n-i+1)) * (n-i+1) /2 * i,
则答案为Σ(1+(n-i+1)) * (n-i+1) /2 * I (i从1到n)
把sigma展开,就是一个x的三次方和x的二次方和x的求和公式化简。
化简结果是 (n^4+6*n^3+11*n^2+6*n) / 24;
至于他为什么恰好就是C(n+3,4), 我也不知道。
大小为4的例子:
源点与每个英雄连边,容量1。
源点与中转点连边,容量k。
中转点与每个英雄连边,容量1。
每个英雄与能打的怪物连边,容量1。
每个怪物与汇点连边,容量1。
然后跑最大流。
每种质因数分开算贡献。
记录每种质因数出现的位置。比如第pos位出现了,那么第pos位的贡献为(pos-pre)*(nex-pos+1)。
solution(1):dfs预处理每只袋鼠到其他袋鼠的第一步的方向。每次随便选两只袋鼠,其中一只向另一只走,直到合并。每走一次,都把其他袋鼠都动一下,直到只剩一只袋鼠。
solution(2):随机输出5e4个’L’,’R’,’D’,’U’。据说卡不掉。
题意:给S串与T串。S[i..j]+T[1..k]为回文串,且|S[i..j]|>|T[1..k]|,求(i,j,k)个数。
将S[i..j]分为两个部分,S[i..p]为T[1..k]的反转,S[p+1..j]为回文串。
由于|S[i..j]|>|T[1..k]|,所以S[p+1..j]必须不为空。
枚举回文串的起始点p+1,那么我们要求的是:
1.由于S[i..p]为T[1..k]的反转,我们只要求有多少个(i,k)。这个部分是exkmp的基础。
将S反转,跟T跑exkmp,求出ex[],再把ex[]反过来即可。
2.S[p+1..j]为回文串,我们只要求有多少个j,即求的是以p+1为起点的回文串个数cnt[]。
那么只要把S串倒着插入回文自动机,cnt[i]=插入第i个字符后,fail树的深度。
最后枚举回文串起点p+1,算出ex[p]*cnt[p+1],求和即为答案。
代码: