-
Notifications
You must be signed in to change notification settings - Fork 0
Editorial
考虑和第1条直线平行的那些直线，答案肯定在这里面。于是枚举这个答案d，把那些平行的且距离是d的直线连边，最后得到一些链。如果每条链都是偶数长度，那么这个d可行，否则不可行。
要有解，一定是b <= r * 3 + 1或者r <= b * 3 + 1。就是一条黑白相间的链，然后上下伸出一些脚，直接构造就好了。
令sum[i,j]是以(i,j)为右下角的子矩形的和，化简下S的公式可以发现S和sum[n,m]，sum[n,c1]，sum[n, c2]，sum[r1, m]，sum[r2, m]的和的奇偶性有关。随便统计下就好了。
可以观察到所有分母里面有11, 13, 17或19的分数之和必须要是个整数，否则最后不可能消掉这些因子。于是，可以按照分母分成5类搞。每一类对分母通分，然后搞个背包就好了。
dp(i, mask)表示点i结尾的简单路径，颜色集合恰好是mask的路径数。然后按照mask二进制里1的个数，一层一层转移即可。
hash大法好。搞个数magic，令第i行权值是weight(i)=magic^i，然后计算f(x, c)表示第x列中字符c所在行的权值和。
枚举一个i，假设这一行是答案，那么用f(x, c)就可以计算出，不同位置的权值和，如果和理想答案k * sum weight(·)一致，那么i就是个可行的答案。
搞出所有可行的答案后，暴力check每个是否合法。期望只要O(n^2)。
如果一个序列排好序了，即a[1] <= ... <= a[n]，那么diversity number是prod (a[i]-i+1) 1 <= i <= n。
于是可以按照递增的顺序枚举almost monotonic subsequences的下标，进行dp。
令dp(i, j, l)表示已经处理了l个数，处理后almost monotonic subsequences最左在位置i，最右再位置j，那么考虑枚举下一个位置i < k < j进行转移，有几点要求：
- a[k] >= a[i], a[k] >= a[j]
- 为了避免重复计算，prev[k] <= i且a[i] != a[k]或者next[k] >= j的时候才进行转移。
其中prev[k]是a[k]上一次出现位置，next[k]是a[k]下一次出现位置。
先构造出secret的转移图，那么根据第一个数，就知道初始secret可能的值，然后根据第二个数又可以删掉一大半，直到最后确定出唯一一个secret为止。
sort，比较函数改成[](string& x, string& y) {return x + y < y + x;}
n比较小，也可以全排列暴力。
可以把操作想象成一颗有根树，不同操作方案数实际就是所有可能的树的拓扑序列方案数的和。
dp(l, r, step, a, b, one)表示区间[l, r]总共操作了step次，操作结束后有没有a，有没有b，长度是否是1。
转移实际就是类似树拓扑序列方案数的做法，枚举每个儿子，以及儿子的操作次数等等信息，乘上一些组合数。
对于一个没有未知数的序列a[1], a[2], ..., a[n]，令s是前缀和，那么s[i]-s[j] > 0 (1 <= j < i < n)个数的奇偶性决定了先手是否必胜，奇数的话必胜，偶数不一定。（why?）
于是随便算下就好了。
dp(mask, i)表示以i为根的树，已经联通了mask这些点的最小权值，类似Steiner Tree的dp转移。