ICPC2017西安

orz hhw posted @ 2017年11月24日 00:45 in 做题记录 with tags ACM 解题报告 , 98 阅读

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$排序离线处理,贪心匹配用线段树维护即可