ZOJ Monthly, March 2014(更新ing)

2014-11-24 10:15:41 · 作者: · 浏览: 0

Yes

3757 Alice and Bob and Cue Sports 25.54% (35/137)
Yes 3758 Singles' Day 44.00% (55/125)
3759 3456 25.00% (3/12)
Yes 3760 Treasure Hunting 13.74% (18/131)
Yes 3761 Easy billiards 38.09% (48/126)
3762 Pan's Labyrinth 26.41% (14/53)
3763 Plasma Field 23.52% (4/17)
3764 New Governor's Problem 33.33% (16/48)
Yes 3765 Lights 34.48% (30/87)
3766 Gao the grid III

28.57% (4/14)


Code: https://github.com/9974/ZOJ_Month

A(3757)大模拟,题意很清楚,对着一条一条规则写,

B(3758)unsigned long long直接sqrt(n)暴力判素数

D(3750)注意到p是偶数, 所以x[i]^x[i]奇偶性一样的点一定在一个集合内, 因为gcd(偶数, p) > 1

所以按x[i]^y[i]的奇偶性来构造二分图, 然后按冲突建边 用总权值-最大流(最小割)即可

E(3761)把球处理成多个联通块,每个联通块通过dfs构造成一棵树,然后让叶子节点撞击其父亲节点即可,可以用栈来保存答案

I(3765)伸展树裸体, 不过我用可持久化treapA掉了,相比之下后者比较好调