Processing math: 100%

ACM-ICPC 2017 现场赛(西安) 题解

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和一个正整数kQ次询问,每次询问一个区间l,r,求该区间中任取元素集合的异或和vk取或(v|k)的最大值。

解题思路

先不考虑k,考虑求区间异或和最大值,显然用线段树合并线性基即可求解。

考虑k的每一位,如果为1,则这一位在最终结果必然为1,故线性基中可以不考虑这一位,把所有的数这一位都置为0。其他位对线性基没有影响,照常取最大值即可。

我们发现这是一个对k取反变成k,再把每个数与k取与的操作。

线段树+线性基合并即可。复杂度O(Pn+QP3)P=27

AC代码

点击

B - Lovers

题目描述

有两个数列ai,biai+bjki,j可匹配。每个i最多只能配对一个j,反之亦然,问最多能够匹配多少对。

解题思路

问题转化成aicj=(kbj),排序双指针模拟即可。

AC代码

点击

C - Naomi with Array

题目描述

解题思路

AC代码

点击

D - Islands

题目描述

解题思路

AC代码

点击

E - Naomi with Graph

题目描述

解题思路

AC代码

点击

F - God of Gamblers

题目描述

有一个赌博游戏,你有nRMB,对方有mRMB,从1RMB开始赌起,每次每个人胜利的概率均为50,如果某个人在赌注为i的时候输了,这iRMB都归对方,两方都会拿出2iRMB继续下一轮赌博。当某个人没有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代码

点击
Powered By Valine
v1.5.2