Codeforces Round 899 (Div. 2)-蒲公英云

Codeforces Round 899 (Div. 2)

Dashboard - Codeforces Round 899 (Div. 2) - Codeforces

A. Increasing Sequence

由于a与b不相等，但b必须算出最小故可以从最小开始（1），故如果b = a就将其值++，使其改变即可，其余由于b1 < b2 < b3…顺着赋值即可

#include<bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10; 
int b[N], a[N];
void solve()
{
    int n, cnt = 0;
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
    }
    int k = 1;
    for(int i = 1; i <= n; i ++)
    {
        if(k != a[i])
        {
            b[i] = k;
            k ++;
        }
        else
        {
            k ++;
            b[i] = k;
            k ++;
        }
    }
    cout << b[n] << '\n';
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --)
    {
        solve();
    }
    return 0;
}

B. Sets and Union

对于每一个集合，我们可以先将这些集合中的数都存放在v[i]这个数组里，每一个i代表了一个集合，再将集合中有哪些数存在set中，因为set自动排序去重，我们可以不重的在set中看到每个数的存储，我们要找到几个集合的交集使其有最大的元素，最好的方案就是在所有元素中去掉一个元素，我们可以枚举每一个元素，看它在每个集合中是否出现，将没有出现过这个元素的集合全部相加，每找一个元素就比较一个元素，找到最大的缺少这个元素的集合的数为答案（将没有这个数的集合的元素存入set（ss)，set(ss)会自动去重），最大值即为答案

#include<bits/stdc++.h>
using namespace std;
void solve()
{
    int n, ans = 0;
    int s, len;
    vector<int> v[100];
    vector<int> v1;
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        cin >> len;
        for(int j = 0; j < len; j ++)
        {
            cin >> s;
            v[i].push_back(s);
        }
    }
    set<int>st;
    for(int i = 0; i < n; i ++)
    {
        for(auto j : v[i])
        {
            st.insert(j);    
        }    
    }
    for(int i : st)
    {
        set<int> ss;
        ss.clear();
        int x = i;
        for(int j = 0; j < n; j ++)
        {
            int flag = 1;
            for(auto k : v[j])
            {
                if(k == x)flag = 0;
            }
            if(flag)
            {
                for(auto o : v[j])
                {
                    ss.insert(o);
                }
            }
        }
        ans = max(ans, (int)ss.size()); 
    }
    cout << ans << '\n';
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --)
    {
        solve();
    }
    return 0;
}

C. Card Game

题意：奇数位的a[i]进行删除并获得分数，偶数位的a[i]只用删除即可

eg.1 2 3 4 5

会发现奇数位可以算上自己以及后面的所有正整数

偶数位可以算上出自己之外的所有正整数

进行后缀和的维护即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
void solve()
{
    ll n, a[N], s[N];
    memset(a, 0, sizeof a);
    memset(s, 0, sizeof s);
    cin >> n;
    for(int i = 1; i <= n; i ++)cin >> a[i];
    for(int i = n; i >= 1; i --)s[i] += max(s[i + 1], s[i + 1] + a[i]);
    ll ans = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(i % 2)
        {
            ans = max(ans, a[i] + s[i + 1]);
        }
        else ans = max(ans, s[i + 1]);
    }
    cout << ans << '\n';
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --)
    {
        solve();
    }
    return 0;
}