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.

#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多个数要大，所以如果想更快就自己写个线段树。