hdu-6600 Just Skip The Problem
题意:
这题从比赛开始到比赛结束就没理解对。。。读错题了。
就是给你一个数字x,但是你不知道数字x是多少,你需要去通过询问来获得关于x的信息,求最小询问次数的情况下,有多少种方案。
- 你知道x的二进制形式有n位。
- 对于每次询问你可以给出一个0到x之间的整数y,并询问到
x&y==y
吗。
题解:
因为询问次数最少,所以只需要判断二进制的每一位就行了,y可以取1<<0,1<<1,1<<2…..,1<<(n-1)。所以方案数为n!,因为答案对$10^6+3$取模,所以当$n \geq 10^6+3$时,方案数为0
So the question is really simple.
1 |
|
hdu-6601Keen On Everything But Triangle
题意加分析:
就是给你n根长度分别为$a_1,a_2,…,a_N(1 \leq a_i \leq 10^9,N \leq 10^5)$的棍子,然后每次询问一个区间$l_i$ 到 $r_i$$1\leq l_i,r_i \leq N$,询问$Q(Q\leq 10^5)$次,问你区间l到r中的棍子可以组成的三角形的最大周长。首先可以知道西面几点:
- 求组成的三角形最大周长肯定从最大的三个数依次往小的找,知道找到可以组成三角形的三个棍子。
- 根据斐波那契数列,至多45根1e9范围内的数字就可以组成一个三角形(最坏情况下是1,1,2,3,5,,,,第45项就超过1e9了),所以线段树区间维护46个最大值就可以了。
也可以直接用主席树来维护区间,主席树求区间第K大时间复杂度为$O(logn)$,不过主席树的常数比上面线段树维护40多个数要大,所以如果想更快就自己写个线段树。
1 |