2020-07-24

Codeforces 631(Div.2)

字数统计: 1.1k字 | 阅读时长: 5分

A题

题意：给你一个a序列代表每次的排名，在n个比赛之后还有x场比赛，然后你去寻找一个最大的v代表这n+x比赛后比赛的连续的最大的排名是多少。

思路：这道题的话，我们可以用cnt去记录此时的最高排名有没有出现过，如果没有的话，那就将x−−，最后当x=0并且cnt此时最后排名没有出现过的话，那么前一个就是答案了。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
const int mod = 1000000009;
using namespace std;
int a[110];
int cnt[1010];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t, n, x;
    cin >> t;
    while (t--)
    {
        cin >> n >> x;
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            cnt[a[i]]++;
        }
        int k = 0;
        for (int i = 1; x; i++)
        {
            if (cnt[i] == 0)
                x--, k = i, cnt[i]++;
        }
        for (int i = k;; i++)
        {
            if (cnt[i] == 0)
            {
                k = i - 1;
                break;
            }
        }
        printf("%d\n", k);
    }
    return 0;
}

B题

题意：给出一组数，要求分成两部分，一部分假设有m个数，保证这部分的数字从1-m均出现而且仅出现一次。输出所有可能。

思路：这道题的话，显然分出的两段是合法的，当且仅当段的最大值等于段的长度时段内没有重复元素，于是先扫一遍得到正序倒序第一个重复元素的位置，再正反各扫一遍得到前缀后缀最大值即可。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 200010;
const int inf = 0x3f3f3f3f;
using namespace std;
int a[maxx], p[maxx], q[maxx];
int t, n, l, r;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        set<int> s;
        for (int i = 1; i <= n; i++)
        {
            if (s.find(a[i]) == s.end())
            {
                s.insert(a[i]);
            }
            else
            {
                l = i - 1;
                break;
            }
        }
        s.clear();
        for (int i = n; i >= 1; --i)
        {
            if (s.find(a[i]) == s.end())
            {
                s.insert(a[i]);
            }
            else
            {
                r = i + 1;
                break;
            }
        }
        for (int i = 1; i <= n; i++)
            p[i] = max(p[i - 1], a[i]);
        for (int i = n; i >= 1; --i)
            q[i] = max(q[i + 1], a[i]);
        vector<int> ans;
        for (int i = 1; i < n; i++)
        {
            if (i <= l && i + 1 >= r && p[i] == i && q[i + 1] == n - i)
            {
                ans.push_back(i);
            }
        }
        cout << ans.size() << endl;
        for (int i : ans)
            cout << i << " " << n - i << endl;
        for (int i = 1; i <= n; i++)
            p[i] = q[i] = 0;
    }
    return 0;
}

C题

题意：给你n和m，表示你有m个操作要让n涂满颜色而且每种颜色都要存在，每个m操作都给你一个ai表示涂色的范围，现在问要求你求出pi（pi表示从pi~pi+ai全部都涂成i颜色）。

这道题的话，根据题意我们先想出不能实现的情况。分为两种，第一种就是把所有的ai加在一起都小于n的话，就不能实现；第二种就是n−ai+1<i的话那么也是不可以的，因为这样会把之前的ith覆盖。然后我们才可以求序列，可以先求出后缀和，然后求出max(i,n−sumi+1)因为sumi是后缀和，表示的是后面的是否可以让此时的i满足剩余的ai涂满色到结尾。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
using namespace std;
ll a[maxx], sum[maxx];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
    {
        if (n - a[i] + 1 < i)
        {
            cout << "-1" << endl;
            return 0;
        }
    }
    memset(sum, 0, sizeof(0));
    for (int i = m; i >= 1; i--)
        sum[i] = sum[i + 1] + a[i];
    if (sum[1] < n)
    {
        cout << "-1" << endl;
        return 0;
    }
    for (int i = 1; i <= m; i++)
    {
        int ans = max(1ll * i, n - sum[i] + 1);
        cout << ans << " ";
    }
    return 0;
}