2020牛客寒假算法基础集训营4 G（概率题），H（线段树），I（经典 偏序）

题目链接

G-音乐鉴赏

二分这个期末成绩占比重，然后判断下到达优秀的期望是否大于等于n/10

卡这题卡半天 还没搞出来

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
const int w=1e5+5;
const ll mod=1e9+7;
int a[w];
int n;
double cheak(double x)
{
    double ans=0;//ans是统计成绩到达优秀的人数的期望值
    for(int i=1;i<=n;i++)
    {
        double k=1.0*(90-a[i]*(1-x))/x;//到达优秀所需的期末成绩k  最少需要 
        if(k>=90)//大于90 不可能了 
            continue;
        if(k<=0)//平时成绩足够优秀了，这个人已经到达优秀了 
        {
            ans++;
            continue;
        }
        ans+=(90-k)/90;//假设10分  那么 k可以取10 11 12 ...90  概率就是（90-k)/90 
    }
    return ans;
}
int main()
{
    int i,j;
    cin>>n;
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    double l=0,r=1;
    int t=100;
    double mid;
    while(t--)
    {
        mid=(l+r)/2;
        if(cheak(mid)>=n/10)
            l=mid;
        else
            r=mid;
    }
    printf("%.2f%\n", mid*100);
    return 0;
}

H-坐火车

这题本来是水之又水的题，我居然wa了好多发，两颗线段树维护左边和右边不同颜色的车厢数就可以了。很多细节

单点更新 区间查询。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n;
ll suml[4*N],sumr[4*N];
ll sum[4*N];
 
ll vis[N];
 
struct node
{
    int col,l,r;
}a[N];
 
void build(int id,int l,int r,int pos)
{
    if(l==r){
        sumr[id]++;
        return ;
    }
    int mid=l+r>>1;
    if(pos<=mid) build(id<<1,l,mid,pos);
    else build(id<<1|1,mid+1,r,pos);
}
 
void up(int id,int l,int r,int pos)
{
    if(l==r)
    {
        suml[id]++;
        sumr[id]--;
        sum[id]=suml[id]*sumr[id];
        return ;
    }
    int mid=l+r>>1;
    if(pos<=mid) up(id<<1,l,mid,pos);
    else up(id<<1|1,mid+1,r,pos);
    sum[id]=sum[id<<1]+sum[id<<1|1];
}
ll qu(int id,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr){
        return sum[id];
    }
    int mid=l+r>>1;
    ll res=0;
    if(ql<=mid) res=res+qu(id<<1,l,mid,ql,qr);
    if(qr>mid) res=res+qu(id<<1|1,mid+1,r,ql,qr);
    return res;
}
 
int main()
{
    scanf("%d",&n);
    int mx=1;
    for(int i=1;i<=n;++i) {
       int col,l,r;
       scanf("%d%d%d",&a[i].col,&a[i].l,&a[i].r);
       mx=max(mx,a[i].col);
       mx=max(mx,a[i].l);
       mx=max(mx,a[i].r);
    }
    //mx++;
    for(int i=1;i<=n;++i) {
       build(1,1,mx,a[i].col);
    }
 
    for(int i=1;i<=n;++i){
        ll t=0;
        if(a[i].l<=a[i].col&&a[i].col<=a[i].r) t=vis[a[i].col];
 
        //printf("t:%lld\n",t);
        printf("%lld ",qu(1,1,mx,a[i].l,a[i].r)-t);
        vis[a[i].col]++;
        up(1,1,mx,a[i].col);
        //if(i!=n) printf(" ");
        //else printf("\n");
    }
    return 0;
}

I-匹配星星

我以为z的范围也很大，赛后看数据，怎么只有0和1

然后群友说这是经典偏序问题，我才恍然大悟，不知多久以前才搞了专题 对 偏序的，然后子集仔细想了想的确是偏序，一发AC

具体怎么偏：题解说的不错

z=1的时候 采取对y进行二分查询就可以了

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node
{
    int x,y,z;
}a[N];
multiset<int>st;
int n;
bool cmp(node a,node b)
{
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
node tmp[N];
int len;
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i){
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    }
    sort(a+1,a+1+n,cmp);
    node t;
    t.x=-1;
    tmp[len]=t;
    int ans=0;
    for(int i=1;i<=n;++i){
        if(a[i].z==0) {
            if(a[i].x>tmp[len].x){
                for(int i=len;i;--i) st.insert(tmp[i].y);
                len=0;
                tmp[++len]=a[i];
            }
            else tmp[++len]=a[i];
            
        }
        else{
            if(a[i].x>tmp[len].x){
                for(int i=len;i;--i) st.insert(tmp[i].y);
                len=0;
            }
            if(st.size()==0) continue;
            
            int x=a[i].y;
            auto it=st.upper_bound(x);
            if(it!=st.begin()){
                ans++;
                --it;
                st.erase(it);
            }

        }
    }
    printf("%d\n",ans);
}