XJTU ICPC Team Selection - Summer 2021 - Day2
A.Bags of Candies
2s
Description
有(1,2,3...,n) 共(n)个数，你可以将两个不互质的数配对。求最多能配对几对。
(1leq n leq 10^{11})
Solution
首先，记(D=(frac{n}{2},n])中所有质数的集合(cup {1})，(D)中的数一定无法配对，于是得到最多配对数的上界是(lfloorfrac{n-|D|}{2}
floor)。记(S={1,2,3,...,n} ackslash D)。将(S)中的数按最大质因数分组，对于每一组，若组中有偶数个数，则将它们两两配对；若组中有奇数个数，可以证明其中必有一个偶数，将组中的数两两配对并剩下一个偶数。这样一来每个大小为奇数的组都会剩下一个偶数，将剩余的偶数两两配对（若(n-|D|)为奇数则会剩余一个）。这样恰好配对(lfloorfrac{n-|D|}{2}
floor)对。
所以答案就是(lfloorfrac{n-|D|}{2}
floor=lfloorfrac{n-(pi(n)-pi(frac{n}{2}))}{2}
floor)
我们可以使用埃氏筛的改进算法在(O((r-l)loglog(r-l)+sqrt{r}))求一个区间([l,r])内的质数个数（筛出(sqrt{r})内的质数，然后拿这些质数筛区间里的数即可）。
利用此算法，将((1,10^{11}))分成(10^4)块，将每块的质数个数打表。然后再利用此算法求解非完整块的答案即可。
B.Binomial
5s
Description
给你一个序列(a_1,a_2,...,a_n)，求有几对((i,j))满足(1leq i,jleq n)且(C_{a_i}^{a_j})为奇数。若(n<k)，则(C_{n}^{k}=0)。
(1leq nleq 10^6) ， (1leq a_ileq 10^6)
Solution
由Lucas定理可以推出，(C_{n}^{k})为奇数 等价于 (n&k)==k .
然后问题就转化成了一个"Sum over Subsets(SOS) DP"问题。（我不会）
C.
D.
25s
Description
一个周长为(10^6)的圆上有(n)个弧（$1leq nleq 3000）。请选出尽可能多的弧使得它们两两相交。
E.
F.
G.
2s
Description
给你(n)个黑点和(n)个白点。请你将黑点和白点两两配对，然后对每一对点找出一个连接两点的折线，使得(n)条折线互不相交。
要求折线最多折100下且折线上的点横纵坐标绝对值不能超过1000。
(1leq nleq 6) ， 黑白点横纵坐标绝对值不超过100，保证每个点横坐标不同，每个点纵坐标不同，不存在三点共线。
Solution1
将(2n)个点按横坐标排序，依次放入栈中，若栈顶元素与它下面的元素一黑一白则将它们取出，然后连线。连线方式为：从一点向上走到max(黑点纵坐标,白点纵坐标,maxY+1)处，然后向左/右走到另一点上方，然后向下。每次连接后用两个点的纵坐标更新maxY。
Solution2（正确性未证明）
枚举全部的(n!)种连接方式，两点间直接连线段，假装可以证明一定有一种连接方式满足条件。
H.
I.Sum of Palindromes
2s
Description
给你一个数，把它拆成若干回文数的和。输出方案
(z)组询问，(1leq zleq 20000)
(1leq n<10^{100000}) ， (z)次询问(n)的和不超过(10^{3000000})
注意回文数不能有前导0，即3630不是回文数
J.Space Gophers
20s
Description
一个棱长(10^6)的立方体，里面有(n)条平行于(x/y/z)轴的隧道（如(-1,1,1)表示所有形如(x,1,1)的点构成的隧道）。(q)次询问每次给出两个点，判断它们是否联通。（你可以像上下左右前后8个方向走，注意(-1,1,1）和(1,-1,2)两个隧道是可以相互到达的）
K.
L.Wizards Unite
2s
Description
有(n)个箱子，(k)个银钥匙和(1)个金钥匙。
打开箱子要消耗(t_i)的时间。银钥匙是一次性的，金钥匙reusable。多个钥匙可以同时开多个箱子，一个钥匙只能同时开一个箱子。最少用多长时间。
(1leq kleq nleq 10^5)
Solution
max(最长的(k)个取最大值，剩下的加起来)
这场真的难，平均AC 1.1题