当前位置: 首页 > 工具软件 > AppleJack > 使用案例 >

B. Applejack and Storages (662 div2 思维 模拟)

呼延承平
2023-12-01

B. Applejack and Storages**

题意: 初始给定n个长度已知的木板,然后q次操作,每次加入或减少一个长度为x的木板(保证减少前存在长度为 x 的木板),每次操作后询问:是否可以利用现在的木板组成一个正方形和一个长方形(可为正方形)。
思路: 显然可以很暴力去做,每次操作后寻找出现次数前三大的数,然后分类讨论是否能组成,但是复杂度太大。
由于四条形同的木板组成一个正方形,两条形同的木板组成一对边,所以,我们只统计 2 ≤ k ≤ 4 2\le k \le4 2k4 k = 4 k=4 k=4 k k k 的个数,分别记为 f 2 、 f 4 f_2、f_4 f2f4,其中 k k k 为每个长度的木板出现的次数 (当 k 等于4后,重新计数),然后在询问时动态维护个数即可,当 2 ≤ f 4 2\le f_4 2f4 或者 3 ≤ f 2 3\le f_2 3f2并且 f 4 = 1 f_4=1 f4=1 ,这两种情况时才能组成两个正方形或者一个正方形一个长方形。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+7;

int vis[N];
int n,x,f2,f4;

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		vis[x]++;
		if(vis[x]==2) f2++;
		if(vis[x]==4) f4++,vis[x]=0;
	}
	int q;scanf("%d",&q);
	char c[2];
	while(q--){
		scanf("%s%d",c,&x);
		if(c[0]=='-'){
			vis[x]--;
			if(vis[x]==-1) vis[x]=3,f4--;   //少一个正方形
			if(vis[x]==1) f2--; 
		}else {
			vis[x]++;
			if(vis[x]==4) f4++,vis[x]=0;  //多一个正方形
			if(vis[x]==2) f2++; 
		}
		if(f4>=2||(f4==1&&f2>=3)) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}
 类似资料: