ICPC2017西安
A - XOR
给定长度为$N$的数列和整数$K$，有$Q$次询问，每次询问一段数中选出若干个元素异或和$K$取或操作的最大值。
先把所有和$K$有关的位都赋为$0$，然后用线段树维护线性基，每次询问只用合并$lgN$段线性基，时间复杂度$O(Qlg^3N)$，常数小。
B - Lovers
有$n$个男生$a_i$和$n$个女生$b_i$，并给出一个$k$，两个男女生$i,j$匹配当且仅当$a_i+b+j\geq k$，问最多能选多少对匹配。$n\leq200000$。
排序，然后贪心扫一遍就好了
C - Naomi with Array
有一行$n$个数$a_i$，想用最小代价让数列变有序。每次操作选择两个位置$i,j$，花费$i+j$的代价将$i$移动到$j$的位置。$n\leq1000$
不会
D - Islands
给出一个$n$个点的树，现在$n-1$条边可段可不段，共$2^{n-1}$种方案，问和$1$所在联通块大小为$1~n$的方案数。$n\leq100000$
据说是树剖分治NTT
E - Naomi with the Graph
有一个$n$个点$m$条边的边权为$1$的无向图，并给每个点一个值$a_i$。你可以在上面加若干条边，令$dist_i$表示$i$号点和$1$的距离，使$\sum_{i=1}^n(a_i-dist_i)^2$最小
比赛时贪心水过去了。正解是最小割，考虑对每个点拉链，割的地方就是$dist_i$，按照要求在可行的地方连边就可以了。待写
F - God of Gamblers
考虑到每局胜率都是50%，而一个人的钱不会小于$0$，故答案一定是$\frac{n]{n+m}$。这道题告诉我们赌博是不可能赚钱的，稍微想想就好了
G - Sum of Xoe Sums
长度为$N$的数列，$Q$次询问$[l,r]$，问所有$l\leq i\leq j\leq r$的异或和
赛场上做法比较复杂，按位维护并记录了一个前缀和，感觉菜的抠脚
H - Arrangement of Contests
一个长度为$n$的数列，每次可以选长度为$k$的连续一段$-1$，求把所有数都减为不超过$0$的数的最小步数。
贪心，用线段树处理一下就好了。
I - Acedia
有$n$个数和$m$个询问，每个询问$[l,r]$将$a_l...a_r$取出，将这些数排在数列上，将数列上连续一段统计入答案（如3、4、5就是3；7、8就是2），求不超过10的段的个数。$n,m\leq100000$。
用莫队，考虑加入一个数就往左、往右看11个数，删除也一样，就可以维护每种长度出现的次数了。时间复杂度$O(10(n+m)\sqrt{n})$。比赛时候我搞笑了，背锅。。。
J - LOL
我不打LOL
K - Lovers II
有$n$个女生$a_i$和$m$个男生$b_i$，女生$i$和男生$j$能匹配当且仅当$a_i+b_j\geq k$。现在有$Q$个询问$[l,r]$，问$[l,r]$中的男生是否能让所有女孩都有匹配。 $n,Q\leq100000,m\leq200000$。
根究Hall定理按$r$排序离线处理，贪心匹配用线段树维护即可
评论 (0)
