2017 ACM/ICPC Asia Regional Qingdao Online

1001 Apple
设三点式解圆方程,因为会爆所以用了java的分数类。

1003 The Dominator of Strings
AC自动机搞,加骚读入。PS:据说kmp直接就能过了。

1007 Zuma
首先预处理出每一段一样的长度和类型,会使后面的dp更简洁。
设\(f[l][r]\)表示区间\([l,r]\)消掉的最少步数。
首先\(i\)跟\(i+1\)必定不同色,所以\(f[l][r]=min(f[l][i]+f[i+1][r])\)。
如果区间左右断点一样的话,考虑最左端和最右端可以在最后的时候合并,那么\(f[l][r]=min(f[l+1][r-1]+cost)\).
然后考虑枚举中间可以作为连接的点,考虑这样的一个形态:最左端是1个,最右端随便,此时可以考虑以一个中间点合并时先连接左边,在连接右边一起消除。反之右边为1同理.即\(f[l][r]=min(f[l+1][i-1]+f[i+1][r-1]+cost)\).

1008 Chinese Zodiac
if判断。

1009 Smallest Minimum Cut
括弧··容量乘以(变数+1)+1 然后把dinic的板子改成LL 直接跑答案就行了。
答案mod(边数+1)+1就行了.

1010 Brute Force Sorting
每一次把其中不符合要求的数删去,对于删去的数,影响的只是前者和后者,在后续的判断中,只需要把前后仍在数组中的加在队列里判断。

1011 A Cubic number and A Cubic Number
\(p=x^3-y^3=(x-y)(x^2+xy+y^2)\).
显然\(x-y=1\),然后二分check。

Leave a Reply

Your email address will not be published. Required fields are marked *