Codeforces Round 1040 (Div. 2)（A~C）

这场最大的感受就是题意看不懂 ···

A. Submission is All You Need

来源：Problem - A - Codeforces

思路

昨天刚好见到mex的定义，以为跟那题一样，note都没看交了一发，上来先-50 ···

• 如果是正数直接相加
• 每个0都能+1

代码

void solve()
{
	cin >> n;
	int f=0;
	int maxx=0;
	for(int i=1; i<=n; i++)
	{
		cin >> a[i];
		if(a[i]==0) f++;
		maxx+=a[i];
	}
	maxx+=f;
	cout << maxx << endl;
}

B. Pathless

来源：Problem - B - Codeforces

思路

就从这个题开始就看不懂了，理解了半天不知道题目具体是啥意思。中间题一直都没理解对，直到现在我还对题中的一些描述有疑问

交的时候只把样例过了，但感觉非常不对劲。本来以为肯定wa2呢，结果叫我碰对了

• 序列之和sum不能小于s，因为至少都得遍历一遍
• 要么$sum==s$，要么$sum-s>=2$
• 如果$sum-s==1$，我只让02在一起不让01在一起，这样的话它返回来加的时候最少都得+2

代码

void solve()
{
	int x=0,y=0,z=0;
	cin >> n >> s;
	int sum=0;
	for(int i=1;i<=n; i++)
	{
		cin >> a[i];
		sum+=a[i];
		if(a[i]==0) x++;
		if(a[i]==1) y++;
		if(a[i]==2) z++;
	}
	if(sum>s)//此时怎么排都不行
	{
		for(int i=1; i<=n; i++) cout << a[i] << ' ';
		cout << endl;
		return ;
	}
	if((s-sum)==1)//让0和1分开
    {
        for(int i=1; i<=x; i++) cout << 0 << ' ';
        for(int i=1; i<=z; i++) cout << 2 << ' ';
        for(int i=1;i <=y; i++) cout << 1 << ' ';
        cout << endl;
        return ;
    }
	cout << -1 << endl;
}

C. Double Perspective

来源：Problem - C - Codeforces

思路

赛时题目依旧看不懂 ··· 补题的时候依然对题目有很多新发现

• 由于要让$f\left(S^{\prime }\right)-g\left(S^{\prime }\right)$最大化，要让$g\left(S^{\prime }\right)$小点，也就是不让它成环
• 成环的前提是左右端点重合，我们遍历右端点，如果右端点有重复就选左端点远的（这样区间更长）
• 这样一来不仅不会重复还能找到更大的$f\left(S^{\prime }\right)$

代码

pii mp[N];  // 存储(r对应的最小l, 点索引)
int ex[N];  // 标记r是否存在
int n;

void solve() {
    cin >> n;
    memset(ex, 0, sizeof(ex));  // 重置标记
    for(int i = 1; i <= n; ++i) 
    {
        int l, r;
        cin >> l >> r;
        if(!ex[r]) //首次出现该r 
        {  
            mp[r] = {l, i};
            ex[r] = 1;
        } 
        else if(l < mp[r].fi) // 存在更小的l
            mp[r] = {l, i};
    }
    if (n == 1) 
    { 
        cout << 1 << endl;
        cout << 1 << endl;
        return;
    }
    vector<int> res;
    for(int r = 1; r<=2*n; ++r)
        if(ex[r]) res.push_back(mp[r].se);
    
    sort(res.begin(), res.end());
    
    cout << res.size() << endl;
    for(int x : res) cout << x << ' ';
    cout << endl;
}