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

From EOJ Wiki
Jump to navigation Jump to search
 
(7 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
== Problem A ==
 
== Problem A ==
  
Unsolved.
+
Upsolved by dream_cloud
 +
 
 +
题意:给你一个数组,和和一个数K,每次询问一个区间,从区间中的数随便取算出异或和,问你K和这个异或和最大能是多少。
 +
 
 +
题解:首先,K这个存在是没有多大意义的,只需要把数组里面所有的数和~K取and。剩下的就是求区间内异或和最大的。采用线性基和ST表思想,线性基可以用于记录一段区间内所有线性无关的数。
  
 
== Problem B ==
 
== Problem B ==
  
 
Solved by dreamcloud.
 
Solved by dreamcloud.
 +
 +
题意:n个男同学,和n个女同学,每个人互相有个值,只有男女同学值之和超过某个值才能两两连线,问最多能配对多少。
 +
 +
题解:温暖的签到,分别排序之后,尽可能配对。
  
 
== Problem C ==
 
== Problem C ==
Line 33: Line 41:
 
== Problem F ==
 
== Problem F ==
  
Unsolved.
+
Solved by oxx1108.
 +
 
 +
题意:两个人赌钱,求一个人最后那全部钱的概率。
 +
 
 +
题解:温暖的签到。
  
 
== Problem G ==
 
== Problem G ==
Line 54: Line 66:
  
 
Solved by oxx1108 && dreamcloud.
 
Solved by oxx1108 && dreamcloud.
 +
 +
题意: 拆顺子。
 +
 +
题解:贪心+线段树区间修改,维护最小值
  
 
== Problem I ==
 
== Problem I ==
Line 62: Line 78:
  
 
Solved by oxx1108.
 
Solved by oxx1108.
 +
 +
题意:五个人在自己已购买的英雄选英雄,问有多少种选法。
 +
 +
题解:数据范围小,枚举三个人,剩下两个人bitset算一下就行,复杂度四方除以64。
 +
 +
还有个做法是状压以后类似容斥一样推个dp,这样写起来稍微麻烦一点。
  
 
== Problem K ==
 
== Problem K ==
  
 
Solved by dreamcloud.
 
Solved by dreamcloud.
 +
 +
题意:n个女同学,m个男同学,只有男同学和女同学的值之和大于某个值时,才能连线。给你一段男同学的区间,问你区间内的男同学是否能使得所有女生都有伴。
 +
 +
题解:对女同学按照权值从小到大排序,分别给女生按顺序-1,-2……,-n。使用双指针,加入某个男生的时候,给他所有能匹配的女生都加上一(线段树区间加),减去某个男生的时候,给他所有能匹配的女生都减去一。查询区间最小值,如果满足大于等于0,就说明所有女生都能有伴。枚举每个男生开始,至少到哪个男生为止,所有女生都有伴

Latest revision as of 14:13, 30 September 2018

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,就说明所有女生都能有伴。枚举每个男生开始,至少到哪个男生为止,所有女生都有伴