-
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类搞。每一类对分母通分，然后搞个背包就好了。
按照a[i]的大小sort一下，然后可以把相同的归为同一类。令S[i,j]是第二类Stirling number，然后令dp[i][j][0/1/2/3]分别表示处理完前i类，总共恰好分了j组，这一类的分组状态是：0. 这一类有一些人和上一类在同一组但是没有人会和下一类在同一组；1. 这一类没有人和上一类在同一组但是会有些人和下一类在同一组；2. 这一类有一些人和上一类在同一组并且也有些人会和下一类在同一组；3. 这一类的人都之和自己类的人归为一组。
然后转移就是可以从0->1, 0->3, 1->0, 1->2, 2->0, 2->2, 3->1, 3->3. 有些系数需要自己算一算。
考虑直接暴力做，每次删一条边的话，就从这个树中把较小的子树分裂出去。于是就和启发式合并差不多，复杂度是O(n log n)的。
尝试枚举那个完全平方数$s$，然后看能否将他拆分为$k-1$个数，并且不用到$n-s$。这个显然可以直接贪心：尽量用$1,2,3,\dots$这些连续自然数来构造，如果$n-s$出现在这些数中，那么将$n-s$移除，再新加一个数。如果这样都不能拆分成$k-1$个数，那么这个$s$肯定不行。
原图如果有3个连通分量，那么肯定无解。如果有2个连通分量，那么不能删桥边。如果只有1个连通分量，分删不删桥边来统计。
可以知道，每个环恰好要删掉一条边，也就是说每个环可以剩下环长-1条边。于是考虑网络流，每个环和非环边都当做图中一个点，每种颜色也当做图中一个点。对应边和对应颜色连边，每个颜色流量为1，每个环流量为环长-1，每个非环边流量为1。用dinic跑个最大流就好了。
枚举$a[1]$所在的集合的最大公约数是$g$，如果剩下部分的最大公约数是$g$的倍数，那么答案显然不超过$g$，于是剩下部分的最大公约数不是$g$的倍数比较好，也就是把那些不是$g$倍数的数放到另一个集合。
考虑一个不合法的字符串$s$，肯定可以拆分成$s=uv$，其中$u$是字典中出现的最长单词，$v$是一个不能被贪心拆分的字符串。然后为了dp算法可以拆分，可以知道$s=xy$，其中x是$u$的前缀，$v$是$y$的后缀。
为了使得长度最短，稍微分析一下可以知道$y$一定是一个在字典内的单词。于是就是从长到短枚举$u$，然后枚举一个$u$的前缀$x$，然后再枚举$y$就差不多了。中间用hash瞎判判。
从$[0,0]$出发，维护可以走到的区间集合，同时维护当前的障碍物区间集合。每到一个时刻，集合内的区间会扩张， 但是不能超过障碍物。对于新增的障碍物，会把新扩展出来的区间截断。这些都可以用$O(n \log n)$的时间轻松维护。总共只有$O(n)$个时刻，障碍物集合会变化。于是复杂度是$O(n^2 \log n)$。