ACM-ICPC 2017 Asia Xi'an

Problem A

Unsolved.

Problem B

Solved by dreamcloud.

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

Unsolved.

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.

Problem K

Solved by dreamcloud.