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;
}