Codeforces Round 899 (Div. 2)

待我称王封你为后i 2024-02-28 06:56 12阅读 0赞

[Dashboard - Codeforces Round 899 (Div. 2) - Codeforces][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;
    }

[Dashboard - Codeforces Round 899 _Div. 2_ - Codeforces]: https://codeforces.com/contest/1882