B. Applejack and Storages(模拟)
程序员文章站
2022-04-16 22:24:04
有 n 条边,给出对应的长度,有 m 次询问,每次会 ‘+’:添加一根木棒,或 ‘-’:减少一根木棒,问是否可以组成一个正方形和一个长方形,这两个四边形不可以重合,减少时,保证一定拥有这种长度的木棒一开始以为是到水题,开始暴力,期间穿插了能想到的优化,但 T 到我怀疑人生后,发觉这个题不大对头,开始换思路超时代码:const int N=2e5+5; int n,m,t; int i,j,k; int a[N]; map
有 n 条边,给出对应的长度,有 m 次询问,每次会 ‘+’:添加一根木棒,或 ‘-’:减少一根木棒,问是否可以组成一个正方形和一个长方形,这两个四边形不可以重合,减少时,保证一定拥有这种长度的木棒
一开始以为是到水题,开始暴力,期间穿插了能想到的优化,但 T 到我怀疑人生后,发觉这个题不大对头,开始换思路
超时代码:
const int N=2e5+5;
int n,m,t;
int i,j,k;
int a[N];
map<int,int> mp;
int minn,maxx;
int go()
{
int f4=0;
int f2=0;
for(int i=minn;i<=maxx;i++){
if(mp[i]>=4){
if(mp[i]>=6){
int res=mp[i]/4;
f4+=res;
if(mp[i]-res*4>=2) f2++;
}
else f4++;
}
else if(mp[i]>=2) f2++;
if(f4 && f2>=2) return 1;
if(f4>=2) return 1;
}
if(f4 && f2>=2) return 1;
if(f4>=2) return 1;
return 0;
}
int ans;
void print()
{
if(ans==1) puts("YES");
else puts("NO");
}
int main()
{
//IOS;
while(~sd(n)){
mp.clear();
minn=inf;
maxx=0;
for(i=1;i<=n;i++){
sd(a[i]),mp[a[i]]++;
maxx=max(maxx,a[i]);
minn=min(minn,a[i]);
}
sd(m);
ans=-1;
while(m--){
char ch[3];
ss(ch);
int x;
sd(x);
if(ch[0]=='+'){
mp[x]++;
minn=min(minn,x);
maxx=max(maxx,x);
if(ans==1){ puts("YES"); continue; }
if(mp[x]==1 || mp[x]==3){ print(); continue; }
}
else{
mp[x]--;
if(mp[x]==0){
if(minn==x) for(i=minn;i<=maxx;i++) if(mp[i]) minn=i;
if(maxx==x) for(i=maxx;i>=minn;i--) if(mp[i]) maxx=i;
}
if(ans==0){ puts("NO"); continue; }
if(mp[x]==0 || mp[x]==2){ print(); continue; }
}
//dbg(mp[x]);
ans=go();
print();
}
}
//PAUSE;
return 0;
}
AC 代码 :
const int N=2e5+5;
int n,m,t;
int i,j,k;
int a[N];
map<int,int> mp;
int main()
{
//IOS;
while(~sd(n)){
mp.clear();
int f2=0,f4=0;
for(i=1;i<=n;i++){
sd(a[i]);
mp[a[i]]++;
if(mp[a[i]]==4) f4++,mp[a[i]]=0;
if(mp[a[i]]==2) f2++;
}
sd(m);
while(m--){
char ch[3];
int x;
ss(ch);
sd(x);
if(ch[0]=='+'){
mp[x]++;
if(mp[x]==4) f4++,mp[x]=0;
if(mp[x]==2) f2++;
}
else{
mp[x]--;
if(mp[x]==-1) mp[x]=3;
if(mp[x]==3) f4--;
if(mp[x]==1) f2--;
}
if(f4>=2 || (f4==1 && f2>2)) puts("YES");
else puts("NO");
}
}
//PAUSE;
return 0;
}
本文地址:https://blog.csdn.net/C_Dreamy/article/details/107874417
上一篇: 快消洗牌期到来,后链路增长邀你上车
下一篇: 寻鲜路上遇到沸点天下:让渠道加速增长
推荐阅读
-
B. Applejack and Storages(模拟)
-
Codeforces Round #258 (Div. 2) B. Sort the Array (模拟)
-
Codeforces Round #256 (Div. 2) B. Suffix Structures(模拟)_html/css_WEB-ITnose
-
Codeforces Round #662 (Div. 2) B. Applejack and Storages
-
B. Nastya Is Playing Computer Games---(水题模拟)Codeforces Round #546 (Div. 2)
-
B. Two Arrays(模拟+思维)Codeforces Round #673 (Div. 2)
-
B. Disturbed People(模拟) Codeforces Round #521 (Div. 3)
-
Codeforces Round #258 (Div. 2) B. Sort the Array (模拟)
-
B. Applejack and Storages(模拟)
-
(模拟题)B. Vova and Trophies—— Educational Codeforces Round 55 (Rated for Div. 2)