[省赛] 2021 CCPC 新疆 ABCDE

前言

传送门 : 翻译水瓶真的不够,太影响做题了

勉强水了个铜,这场并没有多少体验

需要加强训练的地方 :

1. 优先队列 处理区间问题
2. Tarjan缩点
3. 翻译水瓶
4. 二分
5. 3小时的阀座训练
6. CF的训练

A.基础二分

题目意思就是摘气球,前面摘了后面就不可以摘了

求一遍二分就行

心路历程 :

这题虽然说一开始看完之后就知道是二分,但是还是做了一个小时我才A出来, 实在是太废了

1.实在是太紧张了 2.对于lower_bound和upper_bount以及greater 不是非常熟练 3.对于手写二分 完全不熟悉

CODE

void solve()
{
    cin>>n>>m;
    for(int i=1;i>a[i];
        b[i]=a[i];
    }

    sort(a+1,a+1+n);
    for(int i=1;ih[i];
    sort(h+1,h+1+m);
    for(int i=1;i= m)
        {
            d = m;
        }
        ans[i] = d;
        temp[i] = d;
        ans[i] -= temp[i-1];
        mp[a[i]]=ans[i];
        if(ans[i]m;

    for(int i=1;i>w[i];
        f[i] = 0;

    }
    reverse(w+1,w+1+n);
    reverse(f+1,f+1+n);

    for(int i=1;im)
        {   
            if(i-d-1>=1)
            f[i] = max(f[i-1],f[i-d-1]+w[i]);
            else 
            f[i] = max(f[i-1],w[i]);
            continue;
        }
        f[i] = f[i-1]+w[i];
    }
    coutm;
    while(m -- )
    {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
    }

    for(int i=1; i