CF1393B Applejack and Storages 题解

Problem

Solution

注意到能拼出时必须要存在 \(2\) 组及以上的四个相同的木棍，或者 \(1\) 组及以上的四个相同的木棍和除此之外的 \(2\) 组及以上的两个相同的木棍。

同时又注意到 \(a_i\) 很小，所以可以用桶统计，同时实时更新四个相同木棍的组数和两个相同木棍的组数即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define FOR(i,a,b) for(int i=(a);i>=(b);i--)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

const int N=1e5;
int n,t[N+4],_4,_2;
void solve()
{
	char ch;int x;cin>>ch>>x;
	// cout<<ch<<"\n";
	if(ch=='+')
	{
		if((t[x]+1)/4>t[x]/4)_4++;
		if((t[x]+1)/2>t[x]/2)_2++;
		if(_4>=2 || (_4>=1 && _2>=4))cout<<"YES\n";// 注意这里的 _2 要 >=4，因为 _4 的那一组不能算上，准确写应为 _2-2>=2。下同。
			else cout<<"NO\n";
		t[x]++;
	}
	if(ch=='-')
	{
		if((t[x]-1)/4<t[x]/4)_4--;
		if((t[x]-1)/2<t[x]/2)_2--;
		if(_4>=2 || (_4>=1 && _2>=4))cout<<"YES\n";
			else cout<<"NO\n";
		t[x]--;
	}
	// cout<<_4<<" "<<_2<<"\n";
}
int main()
{
	IOS;
	cin>>n;
	For(i,1,n){int x;cin>>x;t[x]++;}
	For(i,1,N)_4+=(t[i]/4),_2+=(t[i]/2);
	int q;cin>>q;
	while(q--)solve();

	return 0;
}