A.Bags of Candies
题目大意：
给(1 sim n)的整数，(gcd)不为(1)的两个数可以匹配，问最多匹配多少对，(n leq 10^{11})
题解：
考虑在(lceil frac{n}{2} ceil sim n)的质数和(1)不能匹配，剩下的枚举质数从大向小匹配，剩下的是(p,2p,cdots)。若个数是偶数，则正好完全匹配，若个数是奇数，则留下(2p)。不难发现剩下的(2p)匹配完是否剩余仅和奇偶有关，所以问题的本质就是求(lceil frac{n}{2} ceil sim n)的质数个数，用Min25筛求解即可，复杂度为(O(frac{n^{frac{3}{4}}}{log n}))
B.Binomial
题目大意：
给长度为(n)的序列(a)，求(inom{a_i}{a_j})为奇数的个数，(n,a_i leq 1e6)
题解：
通过卢卡斯定理可得，(inom{a_i}{a_j})为奇数，当且仅当二进制下(a_j)是(a_i)的子集，高维前缀和即可，复杂度为(O(20*2^{20}))
C.Bookface
题目大意：
给定长度为(n)的数列(a)，每次可以花(1)次操作使数列中某数(pm 1)，问最少多少次操作，使得操作后序列排序后，相邻元素之差大于等于(d)，(n leq 2 cdot 10^5)
题解：
考虑先在数列前面添上(-d sim -(n+1) cdot d)，这样就保证了最优解一定不会把数减到0以下。再将序列排序，第(i)个数减去(i cdot d)，这样问题就转化为将序列变成不降的最小代价。考虑应该是将数列分成一些段，每段都变成中位数，可以用堆来实现这个操作，复杂度为(O(n log n))
D.Clique
题目大意：
给定一个圆，上面有(n)段弧，问最多选出多少段弧，使得两两有交，(n leq 3000)
题解：
E.Contamination
题目大意：
二维平面上有(n)个圆形障碍，保证不相交，(Q)次询问(p,q)两点是否能只通过([ymin,ymax])的地方互相到达，(n,Q leq 1e6)
题解：
本质就是询问圆心([p_x,q_x])内的圆，是否有一个圆上下界将([ymin,ymax])完全覆盖。然后就是个数点问题了，随便解决，复杂度为(O(n log^2 n))
F.The Halfwitters
题目大意：
给定一个排列(P)，可花(a)的代价交换位置相邻两数，(b)的代价翻转排列，(c)的代价重新随机生成一个排列。给(T)个排列，问变成(1 sim n)的最小代价，(T leq 2 cdot 10^4 , n leq 16)
题解：
G.Invited Speakers
题目大意：
二维平面中，有(n)个红点和(n)个蓝点，用折线链接红蓝点对来匹配，构造一组最大匹配方案，保证横坐标和纵坐标都不同
题解：
将红点蓝点都排序，记所有点横纵坐标绝对值的(max)为(c)，构造如下，对于第(i)个红点和第(i)个蓝点，((r_i.x,r_i.y)-(r_i.x,c+i)-(-c-i,c+i)-(-c-i,-c-i)-(b_i.x,-c-i)-(b_i.x,b_i.y))
H.Lighthouses
题目大意：
二维平面上有(n)个点，保证这些点构成一个凸包，在这些点之间有连边，要求出一条最长的路径，使得走过的边没有相交，(n leq 300)
题解：
考虑一条边走完后再向中间的点走这种情况，会发现再也不能走出。这是个很显然的区间dp模型，记(f_{i,j,0/1})表示第一步走((i,j))这条路径，方向是(i->j)或(j->i)的方案数，复杂度为(O(n^3))
I.Sum of Palindromes
题目大意：
给定数(S)，将其分成不超过(25)个回文数的和，(S)的位数小于等于(10^5)
题解：
每次对着前面一半构造，这样的次数大概是(O(log 10^5))的
J.Space Gophers
题目大意：
有一个大正方体，中间挖去(n)个形如((x,y,forall z),(x,forall y,z),(forall x,y,z))的长方体，(T)次询问两点是否连通，(n,T leq 3 cdot 10^5)
题解：
考虑如何方便的表示这些空洞的连接关系，如果有((x,y,forall z))，那么他会与((forall x,y,z))与((x,forall y,z))的空洞，连接这里(z)不重要，我们通过建虚点来减小连边复杂度，然后染色即可，复杂度为(O(n log n))，瓶颈在于给点编号
K.To argue, or not to argue
题目大意：
给定一个(n*m)矩阵，表示可用的座位，有(k)对人不能坐在一起（每个人都不同），问合法方案数，(n cdot m leq 144)
题解：
我们求出至少(i)对相邻的方案数来容斥，问题转化为在矩阵中选恰好i对相邻的座位的方案数。考虑轮廓线dp，设(f_{i,j,msk})表示考虑了前(i)个位置（原来的变成(n*(y-1)+x)的形式），选了(j)对，轮廓线上利用状况为(msk)的方案数。复杂度为(O((nm)^2 2^{min(n,m)}))
L.Wizards Unite
题目大意：
(n)个箱子，(k)把银钥匙，(1)把金钥匙，每个箱子需要一定时间打开，只有金钥匙可以多次使用，求最短时间，(n leq 10^5)
题解：
贪心，时间最大的(k)个箱子用银钥匙，复杂度为(O(n log n))