2009-2010 ACM-ICPC, NEERC, Western Subregional Contest

@M1saki 2017-07-17T00:03:06.000000Z 字数 1043 阅读 1301

acm 2017年7月 codeforcs 组队训练

rank	ac/all	A	B	C	D	E	F	G	H	I	J	K	L
52/128	9/12	.	O	Ø	O	Ø	O	Ø	O	.	.	O	O

.	尚未通过	O	当场通过	Ø	赛后通过

emmmm...

每个城市有4个城门，城门与城门之间有一条路，问最后能否一次走完所有城门。
一笔画，欧拉回路。

一个序列，求连续子序列中山峰和山谷的最大值。
对于山峰，dpL[i]表示从i连续往左的保持单调递减的最大长度，dpR[i]表示从i连续往右的保持单调递减的最大长度，则ans=max(min(dpL[i], dpR[i]))
山谷类似。

$E(n, k) = E(n, k - 1) + E(n - 1, n - k)$

显然的一种做法，最外围的一圈涂黑，里面交替用黑白染色，这样，能得到最多 $((h-2)*(w-2)+1)/2$ 个spot

对于式子 $Ax+By=N$ ，我们可以枚举A和x，则 $By=N-Ax$ ，因此By的每个因数中大于当前A的值都可以成为B，形成一对(A,B)。
可以预处理1~max各个数的因数。

比较显然的二分+数位dp

推公式题。

$ans=m-m*(\frac{m-1}{m})^n$

$n^2$ 枚举线段，看能否组成L型。