转载请注明出处:http://tokitsukaze.live/

题目链接:http://codeforces.com/gym/101981


补题进度:8/13。

 

A.Adrien and Austin

考虑对称操作。先手能拿中间,必胜。

n为奇数,先手只需把中间一个拿了,所以先手必胜。

n为偶数,先手需要拿中间的两个,所以k=1时先手必败,否则先手必胜。

注意特判n=0是先手必败。

 

D.Country Meow

最小包围球。模拟退火的时候往最远点靠近即可。

 

E.Eva and Euro coins

注意题意是能连续翻k个状态相同的硬币。

qls:一个观察是你可以把每个 1 在不跨越其他 1 的情况下往左右移 k 个位置。尽可能把 1 往左靠,出现连续 k 个 1 就消掉。check 两个串处理之后的串是否相同。

一个1能往左移k个位置,那么中间肯定有k个0。所以就变成了消消乐,把连续的k个1或者0都消掉,用栈模拟即可。

 

G.Pyramid

ans=C(n+3,4)。不会推。

 

有位牛逼网友看了说:1

于是这位牛逼网友补充了推导:

对于一个正着的正三角形,他的内部会有边长-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的例子:

2

 

I.Magic Potion

源点与每个英雄连边,容量1。

源点与中转点连边,容量k。

中转点与每个英雄连边,容量1。

每个英雄与能打的怪物连边,容量1。

每个怪物与汇点连边,容量1。

然后跑最大流。

 

J.Prime Game

每种质因数分开算贡献。

记录每种质因数出现的位置。比如第pos位出现了,那么第pos位的贡献为(pos-pre)*(nex-pos+1)。

 

K.Kangaroo Puzzle

solution(1):dfs预处理每只袋鼠到其他袋鼠的第一步的方向。每次随便选两只袋鼠,其中一只向另一只走,直到合并。每走一次,都把其他袋鼠都动一下,直到只剩一只袋鼠。

solution(2):随机输出5e4个’L’,’R’,’D’,’U’。据说卡不掉。

 

M.Mediocre String Problem

题意:给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],求和即为答案。

 

 

代码:

https://github.com/tokitsu-kaze/ACM-Solved-Problems/tree/master/gym/2018-2019%20ACM-ICPC%2C%20Asia%20Nanjing%20Regional%20Contest