2020牛客寒假算法基础集训营4

题目
题解

G.音乐鉴赏【概率】：

还没有做过概率题，感觉都被以前的概率题吓怕了。主要是推公式：
设期末分数占比为： $x$x，期末分数为： $y$y，平时分数： $score$score
那么最终的分数为优秀：
$score\ast (1-x)+y\ast x\ge 90$score∗(1−x)+y∗x≥90
化简得：
$y\ge \frac{90-score\ast (1-x)}{x}$y≥x90−score∗(1−x)​
所以概率为：
$P=\frac{90-w}{90}=\frac{90-\frac{90-score\ast (1-x)}{90}}{90}$P=9090−w​=9090−9090−score∗(1−x)​​
所以有：
$\sum ^n\frac{90-\frac{90-score\ast (1-x)}{90}}{90}=0.1\ast n$∑n​9090−9090−score∗(1−x)​​=0.1∗n
可以解得：
$x=\frac{\sum _{i=1}^{n}score\left[i\right]-90\ast n}{\sum _{i=1}^{n}score\left[i\right]-81\ast n}$x=∑i=1n​score[i]−81∗n∑i=1n​score[i]−90∗n​
即为最终结果。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,sum=0,a;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        sum+=a;
    }
    double f=1.0*(sum-90*n)/(1.0*sum-81*n)*100;
    printf("%.2f",f);
    printf("%\n");
}

<mark>H.坐火车</mark>：

  从左向右遍历，用树状数组维护每只颜色的左右车厢的对数。具体见代码。很巧妙的思路。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
ll bit[N];
int col[N],l[N],r[N],rnum[N],lnum[N];
void update(int p,int m)
{
    while(p<=N)
    {
        bit[p]+=m;
        p+=p&(-p);
    }
}
ll query(int p)
{
    ll res=0;
    while(p>0)
    {
        res+=bit[p];
        p-=p&(-p);
    }
    return res;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&col[i],&l[i],&r[i]);
        rnum[col[i]]++;
    }
    for(int i=1;i<=n;i++)
    {
        rnum[col[i]]--;//对于当前的i车厢，自身的颜色的车厢在其右边的数量-1
        update(col[i],-lnum[col[i]]);//那么其左右的自身颜色的车厢的对数-=左边该颜色车厢数
        printf("%lld%c",query(r[i])-query(l[i]-1),i==n?'\n':' ');//查询
        lnum[col[i]]++;//对于下一个车厢，当前车厢为前一个车厢，故该颜色的左边车厢数+1
        update(col[i],rnum[col[i]]);//该颜色的对数+=该颜色右边车厢数
    }
    return 0;
}

I.匹配星星：

  贪心。
  先按 $x$x 坐标升序排列，当 $x$x 坐标相同时，按 $z$z 坐标逆序排列。
  如何遍历排好序的数组，当z坐标为0时，把该点的 $y$y 坐标放入待选的集合排序，对于 $z$z 坐标为1的点，待选的集合中选择小于取 $y$y 坐标的最大的 $y$y 坐标,如果有就表示匹配成功，从待选集合中删除选择的坐标，否则匹配失败。
还有就是 $stl$stl的应用，原来 $multiset还$multiset还 可以用 lower_bound(val)，返回指向第一个大于等于 $val$val 的数的迭代器。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct node
{
    int x,y,z;
    bool operator < (const node b)const
    {
        if(x==b.x)
            return z>b.z;//z降序
        return x<b.x;//x升序
    }
}point[N];
int main()
{
    int n,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&point[i].x,&point[i].y,&point[i].z);
    sort(point+1,point+1+n);
    multiset<int>st;//待选
    multiset<int>::iterator it;
    for(int i=1;i<=n;i++)
    {
        if(point[i].z)
        {
            it=st.lower_bound(point[i].y);//第一个大于等于
            if(it!=st.begin())//找第一个小于等于
            {
                it--;
                st.erase(*it);
                ans++;
            }
        }
        else
            st.insert(point[i].y);
    }
    printf("%d\n",ans);
    return 0;
}

<mark>?J.二维跑步</mark>：

没理解题解，待补。