Solved | A | B | C | D | E | F | G | H | I | J | K |
---|---|---|---|---|---|---|---|---|---|---|---|
6/11 | O | O | . | . | . | O | O | O | . | O | . |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A - XOR
题目描述
给一个序列ai和一个正整数k,Q次询问,每次询问一个区间l,r,求该区间中任取元素集合的异或和v与k取或(v|k)的最大值。
解题思路
先不考虑k,考虑求区间异或和最大值,显然用线段树合并线性基即可求解。
考虑k的每一位,如果为1,则这一位在最终结果必然为1,故线性基中可以不考虑这一位,把所有的数这一位都置为0。其他位对线性基没有影响,照常取最大值即可。
我们发现这是一个对k取反变成k′,再把每个数与k′取与的操作。
线段树+线性基合并即可。复杂度O(Pn+QP3),P=27。
AC代码
B - Lovers
题目描述
有两个数列ai,bi,ai+bj≥k则i,j可匹配。每个i最多只能配对一个j,反之亦然,问最多能够匹配多少对。
解题思路
问题转化成ai≥cj=(k−bj),排序双指针模拟即可。
AC代码
C - Naomi with Array
题目描述
解题思路
AC代码
D - Islands
题目描述
解题思路
AC代码
E - Naomi with Graph
题目描述
解题思路
AC代码
F - God of Gamblers
题目描述
有一个赌博游戏,你有n个RMB,对方有m个RMB,从1个RMB开始赌起,每次每个人胜利的概率均为50,如果某个人在赌注为i的时候输了,这i个RMB都归对方,两方都会拿出2i的RMB继续下一轮赌博。当某个人没有RMB时,对方获胜。问你获胜的概率是多少。
解题思路
不会做,但感觉是个很公平的游戏,输出nn+m即可。
AC代码
G - Sum of xor sum
题目描述
给一个数列,每次询问一个区间[l,r]中的所有连续子区间异或和的和是多少。
解题思路
考虑拆位。
对于每一位,相当于询问在[l,r]区间内有多少个不同的连续子区间,其总1的个数为奇数(或者说:异或和为1)。
考虑用线段树维护这个数据。要进行合并操作,还需要维护区间的异或和、前缀后缀各有多少个异或和为0/1的子区间。
AC代码
H - Arrangement for Contests
题目描述
给定每个难度的题的个数,问最多能出多少套题。难度连续的k个题可以出成套题。
解题思路
贪心,每次找到区间最小值删除并更新答案,用线段树维护即可。
AC代码
I - Acedia
题目描述
解题思路
AC代码
J - LOL
题目描述
一共100个英雄,我方五人,敌方五人,每人可以选择一个英雄、禁掉一个英雄,这20个英雄互不相同。已知敌方什么英雄都能选,而我方英雄只能从给定输入里的1中挑选。问有多少种方案。
解题思路
枚举我方前四个人的选法,第五个人的选法可以由此确定下来,设总方案数为p。我方英雄选好后,敌方可以有顺序选5个英雄,我方和敌方可无顺序选5个英雄禁掉。故答案为p×A595×C590×C585。
AC代码
K LOVER II
题目描述
解题思路
AC代码
L
题目描述
解题思路
AC代码
M
题目描述
解题思路
AC代码
v1.5.2