0%

2019 Multi-University Training Contest 2

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
using namespace std;
const int mod=1e6+3;
#define LL long long
int main(){
int n;
while(~scanf("%d",&n)){
LL ans=1;
if(n>=mod) printf("0\n");
else{
for(LL i=1;i<=n;i++){
ans*=i;
ans%=mod;
}
printf("%lld\n",ans);
}
}
return 0;
}

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