Andrew Stankevich’s Contest #1, ZOJ 2313-2320
Review
code量不大，有些有意思的题目，题目类型多样，难度适中
两道有点意思的数学题(2313, 2316)
两道有点意思的图论(2314, 2318)
三道不同类型的DP(树状、拼接型状态压缩、经典DP)(2315, 2317, 2319)
一道模线性方程组(2320)
Highlight
2313 Chinese Girls’ Amusement(数论)(new)
2314 Reactor Cooling(经典题)
2317 Nice Patterns Strike Back(经典题)
2318 Get Out!(图论)(new)
Detail
2313 Chinese Girls’ Amusement
Description: n(3<=n<=10^2000)个数围成一圈，从第一个数开始，每隔k(1<=k<=n/2)个数mark下，问能把n个数mark掉的最大的k是多少
Solution: 数论题
当k与n互质时，方程kx + ny = 1有解，则kx + ny = d(1<=d<=n)有解。所以要找的是与n互质的最大的k。通过找规律得出，当n为奇数时，k = n / 2，当n为偶数时，k = (n / 4 – 1) * 2 + 1。这个结论可以用手动欧几里德证明。
对于奇数：
gcd(2t + 1, t) = gcd(t, 1) = 1
对于偶数：
gcd(4t, 2t – 1) = gcd(2t – 1, 2t + 1) = gcd(2t + 1, 2) = 1
gcd(4t + 2, 2t – 1) = gcd(2t – 1, 2t + 3) = gcd(2t + 3, 4) = 1
2314 Reactor Cooling
Description: 带上下界的环形流
Solution: 经典题。
添加源点和汇点S, T，若存在边(u, v)，则添加边(S, v), (u, T)，容量为l，(u, v)的容量改为c – l。看S, T的最大流是否为sigma(li)
2315 New Year Bonus Grant
Description: 一棵有n(<=500000)个结点的树，每个结点可以分配给它的某一个子结点1000，或者被它的父结点分配1000，两者最多只能发生一种，求最大的分配方案
Solution: 树状DP。
f(i, none) = sigma(max{f(j, assign), f(j, assigned)})
f(i, assign) = max{f(k, assigned) + max{f(j, assign), f(j, none)}}
f(i, assigned) = 1000 + sigma(max{f(j, none), f(j, assign)})
2316 Matrix Multiplication
Description: 给定一个N*M的矩阵A，其中元素等于0或1，其中1有2 * M个，求T(A)*A中所有元素的和
Solution: 数学题
读入时统计出A中第i列1的个数tot(i)，则：
Sum = sigma(tot(i) * tot(i)) (1<=n<=i)
时间复杂度为O(3 * M)
2317 Nice Patterns Strike Back
Description: 求构造满足任意一个2×2矩阵中不同色的N*M(N<=10^100, M<=5)的黑白矩阵的方案数
Solution: 经典拼接型状态压缩DP
长度为2^k, 起始状态和结束状态为s1, s2的方案数为：
f(2^k, s1, s2) = f(2^(k – 1), s1, s3) * f(2^(k – 1), s4, s2)，其中s3, s4为满足要求状态对
计算出长度为2^k的方案数，然后拼起来
时间复杂度为O(log(N) * 2^5 * 2^5 * P)，其中p为预处理满足要求的状态对的个数，时限5s
2318 Get Out!
Description: 给定n(<=300)个点的位置(xi, yi)，以及圆半径ri，求某一个半径为r0的圆(x0, y0)是否能到达距离这个点无穷远的地方。
Solution: 暂缓发表
2319 Beautiful People
Description: 给定n(100000)个二元组(si, bi)，找出最多的二元组，使得对于任意两个二元组(si, bi), (sj, bj)有si > sj && bi > bj或者相反
Solution: DP
先按照si从小到大，然后找出这个新序列中以bk为keyword的最长上升序列。
时间复杂度O(n * log(n))
2320 Cracking’ RSA
Description: 给定m(<=100)个由前t(<=100)个质数乘出的数，问所有数的组合的乘积中完全平方数的个数
Solution: 求解模线性方程组解的个数
分解质因数，求解一个mod 2的线性方程组的解的个数。注意去掉全为0的解
