ACM-ICPC 2017 Asia Xi'an

Problem A

Upsolved by dream_cloud

题意：给你一个数组，和和一个数K，每次询问一个区间，从区间中的数随便取算出异或和，问你K和这个异或和最大能是多少。

题解：首先，K这个存在是没有多大意义的，只需要把数组里面所有的数和~K取and。剩下的就是求区间内异或和最大的。采用线性基和ST表思想，线性基可以用于记录一段区间内所有线性无关的数。

Problem B

Solved by dreamcloud.

题意：n个男同学，和n个女同学，每个人互相有个值，只有男女同学值之和超过某个值才能两两连线，问最多能配对多少。

题解：温暖的签到，分别排序之后，尽可能配对。

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Solved by Xiejiadong && dreamcloud && oxx1108.

题意：在图上任意的添加边权为$1$，使得$\sum (a[i]-dist[i])$最小。

题解：建图，最小割。

设源点为$S$，汇点为$T$。

对于原图中每个点$u$，设其在原图中与$1$的距离为$dist[u]$。在新图中，$u$被拆为$u_0,u_1,$…$,u_{dist[u]}$。$ui$向$u_{i+1}$连一条容量为$(A[u]−(i+1))^2$的边，$udist[u]$向$T$连一条容量为无穷的边。如果$u$不是$1$，则$S$向$u_0$连一条无穷的边，否则连一条容量为$(A[1]−0)^2$的边。

对于原图中的每条无向边$(u,v)$，在新图中连若干条形如$(u_i,v_{i−1})$和$(v_i,u_{i−1})$的容量为无穷的有向边。

新图上的一个割对应了一个满足三角不等式的图，流量为该种方案的代价，因此在新图上跑个最大流即可。

Problem F

Solved by oxx1108.

题意：两个人赌钱，求一个人最后那全部钱的概率。

题解：温暖的签到。

Problem G

Solved by Xiejiadong.

题意：每次询问一个区间里面所有子区间的异或和。

题解：似乎想复杂了。想了一个巨难写的算法。

用线段树的每一个结点表示维护一个区间的某一位的所有自区间中$0$和$1$的个数。

然后自底向上合并线段树的结点。因为要合并，所以每一个结点需要记录三个值：区间左边开始的子区间的$0$、$1$个数，区间右边开始的子区间的$0$、$1$个数，区间中间的子区间的$0$、$1$个数。

但是要注意这样的话，整个区间会被左边和右边同时算一次，我是把整个区间的单独拿出来做了一次。

不过有更简单的方法处理，附题解：预处理前缀异或值，问题转化为区间里选两个点异或的所有可能之和。按位处理，对于每个位计算出区间里有多少个$0$和$1$即可确定这一位对答案的贡献。

Problem H

Solved by oxx1108 && dreamcloud.

题意： 拆顺子。

题解：贪心+线段树区间修改，维护最小值

Problem I

Unsolved.

Problem J

Solved by oxx1108.

题意：五个人在自己已购买的英雄选英雄，问有多少种选法。

题解：数据范围小，枚举三个人，剩下两个人bitset算一下就行，复杂度四方除以64。

还有个做法是状压以后类似容斥一样推个dp，这样写起来稍微麻烦一点。

Problem K

Solved by dreamcloud.

题意：n个女同学，m个男同学，只有男同学和女同学的值之和大于某个值时，才能连线。给你一段男同学的区间，问你区间内的男同学是否能使得所有女生都有伴。

题解：对女同学按照权值从小到大排序，分别给女生按顺序-1，-2……，-n。使用双指针，加入某个男生的时候，给他所有能匹配的女生都加上一（线段树区间加），减去某个男生的时候，给他所有能匹配的女生都减去一。查询区间最小值，如果满足大于等于0，就说明所有女生都能有伴。枚举每个男生开始，至少到哪个男生为止，所有女生都有伴