牛客练习赛102 A-C

前言

读题仔细再仔细。

A

题目： 清楚姐姐的学术群

题意：

清楚姐姐有一个学术群，为了使这个群有学术的风气，她建立了一些群规。

这个学术群有 n 个人，编号1∼n。

总共发了 m 条消息。

以及两个参数 a,b。

每条消息由一个人发出来的，且分为水和不水。

如果在某一条消息，它以及它之前的 a−1 条消息（共 a 条消息）都是在水（不管是不是同一个人发的），那么发这条消息的人就会受到神秘惩罚。

如果一个人，在任意一条消息之前，他发的最后 b 条消息（包括这条）都是在水，那么这个人也要受到神秘惩罚。

现在树剖姐姐想要知道，有哪些人会受到神秘惩罚。

输入格式

第一行，四个正整数n,m,a,b (2 ≤ n,m ≤ 3×10⁵, 2 ≤ a,b ≤ m)

后面 m 行，每行两个整数p_i t_i(1≤p_i≤n,0≤t_i≤1)，表示一条消息。

p_i表示第 p_i 个人发消息的，t_i=1 表示这条消息是在水，t_i=0 表示这条消息不是在水。

输出格式

第一行一个数x,表示有x个人受到了神秘惩罚。

第二行x个数，从小到大排列，输出所有受到神秘惩罚的人的编号。

如果没有人收到神秘惩罚，只用输出 0

输入样例：

5 9 3 2
1 1
2 1
3 1
4 1
3 0
1 0
1 1
5 1
2 1

输出样例：

3
2 3 4

思路：

• 用变量 f 记录当前群中连续水的记录条数，用 map 记录当前某个人发言的连续水的记录条数。如果当前消息是在水，对应 f 和map[p] 加1，否则均清零。

代码：

#include<algorithm>
#include<iostream>
#include<map>
#include<vector>

using namespace std;

int main()
{
    int n,m,a,b;
    cin>>n>>m>>a>>b;
    
    //f记录当前群中连续水的消息数量，c记录谁收到过惩罚，q记录每个人连续水的消息数
    int f=0;
    vector<int>c;
    map<int,int>q;
    
    for(int i=1;i<=m;++i)
    {
        int p,t;
        cin>>p>>t;
        //如果当前消息在水，对应f和map[p]均加1，否则均清零
        if(t)f++,q[p]++;
        else f=0,q[p]=0;
        
        //判断一下当前发言人是否会受到惩罚
        if(f>=a||q[p]>=b)c.push_back(p);
    }
    
    sort(c.begin(),c.end());
    //erase将数组选择部分去除，第一个参数是起点，第二个参数是终点
    //unique将数组选择部分去重，第一个参数是起点，第二个参数是终点，去重后将重复元素放到数组尾，并返回重复元素的起始位置
    c.erase(unique(c.begin(), c.end()), c.end());
    cout<<c.size()<<endl;
    for(int i=0;i<c.size();++i)cout<<c[i]<<" ";
    return 0;
}

B

题目：清楚姐姐带带我

题意：

在牛客群里有一位群友小Y，她实力非常菜，于是每次牛客比赛前，她总是希望清楚姐姐可以带带她。

现在有n场比赛，第i场比赛有两个参数a_i,b_i。

小 Y 的初始实力为0，她将依次参加第 1,2,3,…,n 场比赛。

在第i(1 ≤ i ≤ n)场比赛时，小 Y 有两种选择。一种是小 Y 可以选择自己打，这样赛后她的实力会比原来增加 a_i；另外一种是小 Y 让清楚姐姐带，这样她的实力会是原来的 b_i 倍。

现在小 Y 想知道，经过n场比赛后，她的实力值能达到的最大值对 19980829 取模后的结果。

输入格式

第一行，一个正整数n(1≤n≤5×10⁵)。

后面n行，每行 2 个正整数ai,bi(1≤ a_i,b_i ≤10⁹)。

输出格式

一个正整数，表示小Y能达到的最大实力值对 19980829 取模后的值。

数据范围

输入样例：

4
114514 2000000
1477 3000000
2333 255
10086 3000000

输出样例：

9268298

思路：

• 一眼贪心，然后喜提WA。
• 贪心是没问题的，但是需要考虑一个问题：如果我们每次都进行取余，然后再对 sum*b 和 sum+a 作比较，那么当sum本来是一个极大数，但取余后变的极小，就会出现原本 sum*b>sum+a，但取余后 sum%N*b<sum%N+a 的情况，可是不取余一定会出现数据溢出的情况。所以就需要考虑什么时候可以取余。
• 当 sum<1e9 时显然无需取余，而当 sum>=1e9 时，因为 a<=1e9，所以只要 b 大于1，一定有 sum*b>=sum+a，所以当 b>1 时，直接选择 sum*b 即可。

代码：

#include<algorithm>
#include<iostream>
#include<map>
#include<vector>
 
using namespace std;

#define ll long long
const ll N=19980829;
 
int main()
{
    ll n;
    cin>>n;
    
    //sum表示小Y当前的能力值，nn记录sum是否已经大于等于1e9
    ll nn=0,sum=0;
    for(ll i=1;i<=n;++i)
    {
        ll a,b;
        cin>>a>>b;
        //当sum<1e9时，不取余，直接取两种选择最大值
        if(sum<1e9&&nn==0) sum=max(sum+a,sum*b);
        //当sum>=1e9时，因为a<=1e9，所以只要b大于1，一定有sum*b>=sum+a
        else 
        {
            nn=1;
            //防止第一次进入else时，出现sum*b*b溢出long long的情况
            sum%=N;
            if(b>1) sum=(sum*b+N)%N;
            else sum=(sum+a+N)%N;
        }
    }
    //加N再求余，防止出现负余
    cout<<(sum+N)%N;
    return 0;
}

C

题目： 清楚姐姐的序列

题意：

清楚姐姐希望你能构造出一个长度为n的序列，满足m个限制。

每个限制有l,r,x,y四个参数，表示在区间[l,r]内x出现次数不少于y次，其中任意两个限制的x不同。

如果无法完成要求，输出"qcjjddw"

输入格式

第一行两个正整数n,m(1 ≤ n,m ≤ 2×10³)

后面m行，每行4个正整数l,r,x,y(1 ≤ x ≤ 10⁹,1 ≤ y ≤ n,1 ≤ l ≤ r ≤ n每个限制的x互不相同)表示一个限制条件。

输出格式

一行nnn个数，每个数之间用一个空格隔开，表示你构造的序列。

你需要保证你的序列每个数都在区间[1,10⁹]内。

或者一个字符串 qcjjddw 表示无解

输入样例：

5 2
1 4 1 3
2 5 2 3

输出样例：

qcjjddw

思路：

• 首先考虑什么时候无解，显然当要求填的x的数量总和超过n时，是无法构造序列的。
• 因为每个x只要求最少数量，所以我们可以先将从每个区间的左端点开始填x，填满y个就直接退出，这样会有个问题，如果两个区间范围重合，先填谁的？很容易想到应该先填右端点靠前的区间，因为如果先填右端点靠后的区间，可能会导致已经填的区间占用了后面的区间并且有富余，但是无法给后面的区间用。
• 因为题目要求序列中每个元素都大于1，所以我们最后要遍历一下序列，看是否有没填的格子，将其赋值1。

代码：

#include<algorithm>
#include<iostream>
#include<map>
#include<vector>
 
using namespace std;

#define ll long long
const ll M=19980829;
const int N=2e3+10;

//将所有区间根据右端点升序排序
bool cmp(pair<pair<int,int>,pair<int,int>>a,pair<pair<int,int>,pair<int,int>>b)
{
    return a.first.second<b.first.second;
}

//记录所构造的序列
int c[N];

int main()
{
    int n,m;
    cin>>n>>m;
    
    //mm用来记录所有y的总和。p的1到4属性分别为l,r,x,y
    int mm=0;
    pair<pair<int,int>,pair<int,int>>p[N];
    for(int i=1;i<=m;++i)
    {
        cin>>p[i].first.first>>p[i].first.second>>p[i].second.first>>p[i].second.second;
        mm+=p[i].second.second;
    }
    //如果要填的所有x最少数量大于n，说明无法构造
    if(mm>n)
    {
        cout<<"qcjjddw";
        return 0;
    }
    //将区间按右端点排序
    sort(p+1,p+m+1,cmp);
    
    //遍历所有区间
    for(int i=1;i<=m;++i)
    {
    	//sum记录第i个区间所要求填的x填了多少
        int sum=0;
        //从左开始遍历第i个区间在序列上的位置
        for(int j=p[i].first.first;j<=p[i].first.second;++j)
        {
        	//当前格子还没有填过
            if(c[j]==0)
            {
                c[j]=p[i].second.first;
                sum++;
                //为了能尽可能的满足后面的区间要求，所以只要满足最低需求就直接跳出
                if(sum==p[i].second.second)break;
            }
        }
        //如果所填的数量不足y，说明无法构造
        if(sum<p[i].second.second)
        {
            cout<<"qcjjddw";
            return 0;
        }
    }
    //将未填过的格子填1
    for(int i=1;i<=n;++i)if(c[i]==0)c[i]=1;
    
    for(int i=1;i<=n;++i)cout<<c[i]<<" ";
    return 0;
}