15 沈阳
B
D
(k_1a+k_2b) 表示 (gcd(a,b)) 的倍数。
E
轮廓线DP,显然我们必须维护当前轮廓线的联通情况,选好状态表示很重要,
我采取的憨憨表示法是每个点记录上一个和我联通的点的标号,这样状态数为m!<=5040(状态转移有点烦人)
勇敢的朝着TLE就去了,但结果AC了
这样表示的好处是状态相对较少,就不需要hash了,另外还可以事先删除掉不合法的状态,比如多个点有相同的前驱
F
第 (i) 只青蛙会访问到 (gcd(a_i, m)) 的倍数。先考虑 brute 的容斥,枚举青蛙子集,求出它们的 lcm,统计答案,如果子集 size 是奇数则贡献为正,否则贡献为负。注意到 lcm 种类数是 (O(因子个数)) 级别的。考虑 DP,(f[i][j][0/1]) 表示考虑前 i 只青蛙,lcm 为 j,size % 2 = 0/1 的集合方案数。
G
需要细心分类讨论
- 特判掉 (v_1=0,v_2=0,v_1=v_2) 这些 corner case。
- 三种策略:
- 去 23 边上拦截对手,去 2,3,4,1(可以注意到拦截越早越好)
- 直接去 34 边上拦截对手,再去 2,3,4,1
- 先去 2,再去 34 边上拦截对手,再去 3,4,1
- 注意到 (v_2=3v_1) 是会 lose 的,因为结算顺序是先 touch 杆子,再斗殴。
H
反过来考虑,让障碍物去撞空格子,每个障碍物会在每一步撞一个空格子,所以复杂度为(O(o*l))
由于题目卡空间,所以统计答案时可以分开考虑横纵坐标以及各个分量
I
将((a,b)(c,d,e))按(b=e)安排进桶里,然后可以发现仅需保留最大的(a)然后笛卡儿积((b,e))即可,这样将得到(O(m))级别的待选答案,然后再排序去个重
现在问题变成了给定若干个三元组,求哪些三元组是极大的
可以使用cdq分治,二维树状数组(本题(c,d)范围很小),或一维树状数组
L
满足题目条件可以等价于如下:
- 奇数点出度1,入度0
- 偶数点出度0,入度1
- 其他店出度1,入度1
根据上述条件拆点跑费用流即可,(dij版本T,spfa版本A)
M
对团建个中间点,中间点向团内的点连 (w/2) 的边,dij 即可。