【CF闯关练习】—— 1400分（C. Make Good、B. Applejack and Storages）

🌏博客主页：PH_modest的博客主页
🚩当前专栏：cf闯关练习
💌其他专栏：
🔴每日一题
🟡 C++跬步积累
🟢 C语言跬步积累
🌈座右铭：广积粮，缓称王！

一.关卡1（C. Make Good）

👉传送门👈

1.Tutorial

XOR运算就是按位异或：相同为0，不同为1
这个操作符有两个结论：

• $X\oplus X=0$
• $0\oplus X=X$

本题从这两点入手，题目中说最多添加3个数，我们不妨大胆假设只需要两个数，一个数将原数组中的数按位异或之后变成0，再用一个数^0*2等于所有数之和，这边只需要解个方程即可

2.Solution

//https://codeforces.com/problemset/problem/1270/C
//
//
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve()
{
    int n;
    cin>>n;
    int sum=0;
    int tmp=0;
    for(int i=0;i<n;i++)
    {
    	int x;
    	cin>>x;
    	sum+=x;
    	tmp^=x;
	}
	cout<<"2\n"<<tmp<<" "<<tmp+sum<<"\n";
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

---

二.关卡2（B. Applejack and Storages）

👉传送门👈

1.Tutorial

正方形由4个相同的边组成，长方形由2组2个相同的边组成，sum2表示两个一组的个数，sum4表示4个一组的个数，首先sum4 >= 1是必须的，然后还需要知道一点，sum4+1的时候sum2+2，原因参考下面这张图

所以我们得出结论：

• sum4>=1&&sum2>=4时输出“YES”；
• 否则输出“NO”

2.Solution

//https://codeforces.com/problemset/problem/1393/B
//
//
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve()
{
	map<int,int>mp;
	int n;
	cin>>n;
	int sum4=0;
	int sum2=0;
	for(int i=0;i<n;i++)
	{
		int a;
		cin>>a;
		mp[a]++;
		if(mp[a]%4==0) sum4++;
		if(mp[a]%2==0) sum2++;
	}
	int q;
	cin>>q;
	while(q--)
	{
		string a;
		cin>>a;
		if(a[0]=='+')
		{
			int x;
			cin>>x;
			mp[x]++;
			if(mp[x]%4==0) sum4++;
			if(mp[x]%2==0) sum2++;
		}
		else
		{
			int x;
			cin>>x;
			if(mp[x]%4==0) sum4--;
			if(mp[x]%2==0) sum2--;
			mp[x]--;
		}
		if(sum4>=1&&sum2>=4) cout<<"YES\n";
		else cout<<"NO\n";
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
	return 0;
}

---

最后：

闯关系列旨在养成刷题的习惯，所以对代码的解释并不会特别详细，但足够引导大家写出来，选的题目都不会特别难，但也不是特别简单，比较考验大家的基础和应用能力，我希望能够将这个系列一直写下去，也希望大家能够和我一起坚持每天写代码。

之后每个星期都会不定期更新codeforces和atcoder上的题目，想要学习算法的友友们千万别错过了，有什么疑问欢迎大家在评论区留言或者私信博主！

在这里送大家一句话：广积粮，缓称王！