Difference between revisions of "ACM-ICPC 2017 Asia Xi'an"

From EOJ Wiki
Jump to navigation Jump to search
Line 53: Line 53:
 
== Problem H ==
 
== Problem H ==
  
Solved by dreamcloud.
+
Solved by oxx1108 && dreamcloud.
  
 
== Problem I ==
 
== Problem I ==

Revision as of 06:42, 23 September 2018

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.