牛客算法竞赛入门课第一节习题

题目描述

从前，有n只萌萌的糖糖，他们分成了两组一起玩游戏。他们会排成一排，第i只糖糖会随机得到一个能力值bi。从第i秒的时候，第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。

为了使游戏更加有趣，糖糖的爸爸，娇姐，会发功m次，第i次发功的时间为ci，则在第ci秒结束后，b1,b2,.....,bci都会增加1.

现在，娇姐想知道在第n秒后，会有多少只糖糖存活下来。

输入描述:

第一行只有一个整数T（T<6），表示测试数据的组数。
第二行有两个整数n,m。表示糖糖的个数以及娇姐发功的次数。（1<=n<=50000,1<=bi<=1000000）
第三行到n+2行,每行有两个整数ai,bi,表示第i只糖糖属于那一组以及他的能力值。（0<=ai<=1,1<=bi<=1000000）
第n+3行到第n+m+2行，每行有一个整数ci，表示GTW第i次发功的时间.(1<=ci<=n)

输出描述:

总共T行，第i行表示第i组数据中，糖糖存活的个数。

输入

1
4 3
0 3
1 2
0 3
1 1
1
3
4

输出

3

题解

我们仔细想想，是不是如果一个人后面没有比他更大的另一个队伍的人那么他一定就活下来了吧。
那么其实我们要做的就是从后往前维护2个最大值（两个队伍的最大值），那要做的就是如何把这些ci给他优美的加上。
首先考虑暴力，每次把前面ci个数加上一。时间复杂度是 $n^2$ 。不够优秀，我们可以想到的使用一个差分数组，每次先记录下来区间的更新情况，最后扫一遍线性就出来了。

const int N=50010;
PII a[N];
int b[N];
int n,m;

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;

        for(int i=1;i<=n;i++) cin>>a[i].fi>>a[i].se;

        for(int i=1;i<=n;i++) b[i]=a[i].se-a[i-1].se;

        while(m--)
        {
            int x;
            cin>>x;
            b[1]++;
            b[x+1]--;
        }

        for(int i=1;i<=n;i++) b[i]+=b[i-1];

        int max0,max1;
        max0=max1=-INF;
        int cnt=0;
        for(int i=n;i>=1;i--)
        {
            if(a[i].fi == 0) max0=max(max0,b[i]);
            else max1=max(max1,b[i]);
            if(a[i].fi == 0 && b[i] >= max1) cnt++;
            if(a[i].fi == 1 && b[i] >= max0) cnt++;
        }
        cout<<cnt<<endl;
    }
    // system("pause");
}

题目描述

JC内长度为L的马路上有一些值周同学，每两个相邻的同学之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0,1,2,…L，都有一个值周同学。由于水宝宝有用一些区间来和ssy搞事情，所以为了避免这种事走漏风声，水宝宝要踹走一些区域的人。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的人（包括区域端点处的两个人）赶走。你的任务是计算将这些人都赶走后，马路上还有多少个人。

输入描述:

第一行有2个整数L和M，L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含2个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标

输出描述:

1个整数，表示马路上剩余的人的数目。

输入

500 3
150 300
100 200
470 471

输出

298

说明

对于所有的数据，1≤L≤100000000

对于10%的数据，1<=M<=100

对于20%的数据，1<=M<=1000

对于50%的数据，1<=M<=100000

对于100%的数据，1<=M<=1000000

题解

1.按左区间升序排序，如果左区间相同就按右区间升序排序，统计被移走的人数。
3.如果区间i的左区间比end严格大，移走的人数是r-l+1，标记右区间end=r。
4.如果区间i的右区间不小于end，移走的人数是r-end，标记右区间end=r。
5.答案就是n+1-sum。

const int N=1e6+10;
PII a[N];
int n,m;

int main()
{
    ios;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        a[i]={x,y};
    }
    sort(a,a+m);

    int ans=0,r=-INF;
    for(int i=0;i<m;i++)
        if(a[i].first > r)
        {
            ans+=a[i].second-a[i].first+1;
            r=a[i].second;
        }
        else if(a[i].second >=r )
        {
            ans+=a[i].second-r;
            r=a[i].second;
        }

    cout<<n+1-ans<<endl;

    // system("pause");
}

题目描述

帕秋莉掌握了一种土属性魔法

她使用这种魔法建造了一个大型的土球，并让其一路向下去冲撞障碍

土球有一个稳定性x，如果x < 0，它会立刻散架

每冲撞一个障碍，土球会丧失ai的稳定性，冲撞之后，又会从障碍身上回馈bi的稳定性

帕秋莉想知道，如果合理的安排障碍的顺序，在保证土球不散架的情况下，是否可以将障碍全部撞毁呢？

输入描述:

输入一个整数T，代表T组数据，每组数据中：
前一行两个整数n , m，表示障碍个数和土球的稳定性
接下来一行两个整数，分别表示障碍的ai和bi

输出描述:

若可以，输出“Yes”(不含引号)，否则输出“No”(不含引号)

输入

1
5 50
49 49
52 0
5 10
26 24
70 70

输出

No

备注:

Σn <= 500000, 1<=m<=100000,0<=a,b<=100000

题解

这道题非常明显就是一道贪心问题，那我们来讨论贪心策略：
我们是先对球损坏a，再修复b，如果损坏了a就使稳定性变成负数了，就结束了。
所以我们现在的贪心要素有：a的损坏大小，b的修补大小。

显然我们将可以升高稳定性的排在前面，然后我们数组就分成了两个部分：前面是稳定性升高（包括不变）的，后面是稳定性降低的。

然后我们就要考虑，这两块里面怎么排。

稳定性升高内部排序规则：按照损坏程度大小，从小到大排序（也就是在为下一个球的情况做贡献）。
稳定性降低内部排序规则：按照恢复程度的大小，从大到小排序（让下一个有更多空间去破坏）。

const int N=5e5+10;
PII a[N];
int n,m;

bool cmp(PII a,PII b)
{
    if(a.fi <= a.se && b.fi <= b.se) return a.fi < b.fi;//都能回血，伤害小的优先
    if(a.fi > a.se && b.fi > b.se) return a.se > b.se;//都会掉血，恢复大的优先
    if(a.fi <= a.se && b.fi > b.se) return true;//回血在前
    if(a.fi > a.se && b.fi <= b.se) return false;//交换，使得回血在前
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;

        for(int i=0;i<n;i++)
        {
            int x,y;
            cin>>x>>y;
            a[i]={x,y};
        }
        sort(a,a+n,cmp);

        LL sum=m;
        bool ok=1;
        for(int i=0;i<n;i++)
        {
            sum-=a[i].fi;
            if(sum < 0)
            {
                ok=0;
                break;
            }
            sum+=a[i].se;
        }

        if(ok) puts("Yes");
        else puts("No");
    }

    // system("pause");
}

题目描述

牛妹在玩一个名为矩阵消除的游戏，矩阵的大小是 ${n}$ 行 ${m}$ 列，第 ${i}$ 行第 ${j}$ 列的单元格的权值为 $a_{i,j}$ ，牛妹可以进行 ${k}$ 个回合的游戏，在每个回合，牛妹可以选择一行或者选择一列，然后将这一行或者这一列的所有单元格中的权值变为 ${0}$ ，同时牛妹的分数会加上这一行或者这一列中的所有单元格的权值的和。

牛妹想最大化她的得分，球球你帮帮她吧！

输入描述:

第一行三个整数 ${n,m,k}$
接下来 ${n}$ 行每行 ${m}$ 个整数表示矩阵中各个单元格的权值。

输出描述:

输出一个整数表示牛妹能获得的最大分数。

输入

3 3 2
101 1 102
1 202 1
100 8 100

输出

414

备注:

$1\leq n,m\leq 15$
$1\leq a_{i,j}\leq 1e6$

题解

我们知道如果只是行的选择或者只是列的选择就可以贪心。那么我们就把问题转化成只选若干列好了！

如果我们想贪心的选取最好的若干列，那么我们必须提前知道我们选了哪些行，这个怎么知道呢？看看数据范围，二进制枚举就可以了。

如果k>n||k>m，那么我们可以把矩阵全部拿完
枚举选那几行的情况通过二进制表示
确定了行后，计算每一列的和，剩下的次数选列的和最大的。

const int N=20;
int g[N][N];
int tmp[N][N];
int row[N];
bool choose[N];
int col[N];
int n,m,k;

int main()
{
    cin>>n>>m>>k;

    int sum=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
            row[i]+=g[i][j];
            sum+=g[i][j];
        }

    if(k > min(n,m))
    {
        cout<<sum<<endl;
        return 0;
    }

    int ans=0;
    for(int s=0;s<1<<n;s++)
    {
        memcpy(tmp,g,sizeof g);
        int res=0;
        int t=__builtin_popcount(s);
        if(t > k) continue;

        for(int i=0;i<n;i++)
            if(s>>i & 1)
            {
                res+=row[i+1];
                memset(tmp[i+1],0,sizeof tmp[i+1]);
            }

        memset(col,0,sizeof col);
        for(int j=1;j<=m;j++)
            for(int i=1;i<=n;i++)
                col[j]+=tmp[i][j];

        sort(col+1,col+m+1,greater<int>());

        for(int i=1;i<=k-t;i++) res+=col[i];

        ans=max(ans,res);
    }
    cout<<ans<<endl;

    // system("pause");
}