题解集合1

K：题解+题意
题目链接
一次淘汰赛有2k个参赛者。每个参赛者赛前都已经有排名（不会并列），你排在第r名。而且名次靠前的总会战胜名次靠后的。但是比赛的安排是不确定的，比赛安排（即谁与谁比赛）很多等可能的情况。你想知道你在这次淘汰赛平均能有多少次胜利。淘汰赛意味着打赢的一方晋级，输的一方被淘汰出比赛。
题解：

只需i从1~k即可求一个SUM（Q(i)）

技巧：求组合数用对数

所以预处理对数的前缀和即可

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
struct node
{
    long long
     x,m;
} a[2000],b[2000];
const int N =1<<21;
double logsum[N];
double Log(int n,int m)
{
    return logsum[n]-logsum[m]-logsum[n-m];
}
int main()
{
    int k,n,r;
    cin>>k>>r;
    n =  (1<<k);

    for(int i=1;i<=(1<<20);i++)
    {
        logsum[i] = logsum[i-1]+log(i);
    }
    int m;
    double ans= 0;
    for(int i=1;i<=k;i++)
    {
        m = (1<<i)-1;
        if(n-r<m)break;
        ans+=exp(Log(n-r,m)-Log(n-1,m));
    }
    printf("%.5f\n",ans);
    return 0;
}

J Gym 101201J Shopping (线段树+取模)
题意：给定 n 个物品，然后有 m 个人买东西，他们有 x 元钱，然后从 l - r 这个区间内买东西，对于每个物品都尽可能多的买，问你最少剩下多少钱。

析：对于物品，尽可能多的买的意思就是对这个物品价格取模，但是对于价格比我的钱还多，那么就没有意义，对取模比我的钱少的，那取模至少减少一半，所以最多只要60多次就可以结束，为了快速找到第一个比我的钱少的，使用线段树。
题目链接

#include<bits/stdc++.h>
using namespace std;
long long key;
#define lson root<<1
#define rson root<<1|1
#define MID int mid = (l+r)/2;
const int MAX = 200000+1000;
const int inf = 0x3f3f3f3f;
struct node
{
    long long  Min,data;

    node operator+(const node&a)
    {
        node uu;
        uu.Min = min(Min,a.Min);
        return uu;
    }
}tree[MAX<<3];

void build(int root,int l,int r)
{
    if(l==r)
    {
        scanf("%lld",&tree[root].Min);
        return ;
    }
    MID
    build(lson,l,mid);
    build(rson,mid+1,r);
    tree[root].Min = min(tree[lson].Min,tree[rson].Min);
}
void query(int root,int l,int r,int L,int R)
{
    if(r<L||R<l)return;
    if(l==r)
    {
        key = key%tree[root].Min;
        return;
    }
    if(L<=l&&r<=R)
    {
        if(tree[root].Min>key)return;
    }
    MID
    query(lson,l,mid,L,R);
 query(rson,mid+1,r,L,R);

}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    build(1,1,n);
    int l,r;
    while(m--)
    {
        scanf("%lld%d%d",&key,&l,&r);
        query(1,1,n,l,r);
        printf("%lld\n",key);
    }
    return 0;
}

2:RMQ

二分+RMQ

3.

H：二分优化dp