【简单模拟】ABC240 D - Strange Balls

浅浅的花香味﹌ 2024-03-23 11:23 57阅读 0赞

**虽然是简单模拟，但是不妨碍我不会**

[D - Strange Balls (atcoder.jp)][D - Strange Balls _atcoder.jp]

题意：

![012422e6724d480baee3a027f8764531.png][]

思路：

在模拟的时候，先去明确要维护的是什么东西，然后再去考虑修改操作对要维护的东西的影响，再去添加需要维护的量

答案是每次操作之后栈里剩余多少球

那么考虑每次操作

如果进球之后不消，那么cnt++，栈里加球即可

但是如果消掉之后，栈里一个个球出来复杂度会很高

因此考虑不进重复的球，然后维护每个球的出现次数

如果消掉了，只pop一次即可

Code：

#include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int Inf=1e18;
    
    stack<pair<int,int> > S;
    int n;
    int a[mxn];
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        int cnt=0;
        for(int i=1;i<=n;i++){
            if(S.empty()){
                S.push({a[i],1});
                cnt++;
            }else if(S.top().first==a[i]){
                S.top().second++;
                cnt++;
                if(S.top().second==a[i]){
                    cnt-=a[i];
                    S.pop();
                }
            }else{
                S.push({a[i],1});
                cnt++;
            }
            cout<<cnt<<'\n';
        }
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[D - Strange Balls _atcoder.jp]: https://atcoder.jp/contests/abc240/tasks/abc240_d
[012422e6724d480baee3a027f8764531.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/9df38e1061784aad91629e3b8ff53ccc.png

发表评论取消回复

表情：

评论列表（有 0 条评论，57人围观）

还没有评论，来说两句吧...

相关阅读

相关 Atcoder ABC 139D

Atcoder ABC 139D 解法： > 等差数列求和公式，记得开 $ long long $ CODE: include<iostre...

末蓝、/ 2024年04月20日 10:31/ 0 赞/ 96 阅读

相关 ABC252 D - Distinct Trio

还有一天就篮球被了，好紧脏.... 我的世界将被摧毁，也许事与愿违是时候放弃一些东西了呢 [D - Distinct Trio (atcoder.jp)][D - Di

小灰灰/ 2024年03月24日 15:45/ 0 赞/ 63 阅读

相关 ABC292 D - Unicyclic Components

ABC刷起来好爽，我要刷爆ABC！ [D - Unicyclic Components (atcoder.jp)][D - Unicyclic Components _atc

偏执的太偏执、/ 2024年03月24日 15:12/ 0 赞/ 18 阅读

相关【简单DP】ABC312 D

[D - Count Bracket Sequences][] 题意：括号匹配,需要满足以下两个性质前i个字符中,左括号的数量必须大于等于右括号最后左括号的数量要

朱雀/ 2024年03月23日 18:46/ 0 赞/ 79 阅读

相关【简单容斥】ABC253 D - FizzBuzz Sum Hard

嘻嘻，被我秒了 [D - FizzBuzz Sum Hard (atcoder.jp)][D - FizzBuzz Sum Hard _atcoder.jp] 题意： !

快来打我*/ 2024年03月23日 17:14/ 0 赞/ 58 阅读

相关【简单模拟】ABC240 D - Strange Balls

虽然是简单模拟，但是不妨碍我不会 [D - Strange Balls (atcoder.jp)][D - Strange Balls _atcoder.jp] 题意：

浅浅的花香味﹌/ 2024年03月23日 11:23/ 0 赞/ 58 阅读

相关 240.简单的 CSS 波浪

效果 (源码网盘地址在最后) ![b7658345800490a58de027d9adbaed15.gif][] 源码 index.html <!DOC

一时失言乱红尘/ 2022年09月12日 11:59/ 0 赞/ 162 阅读

相关 HDOJ 5645-DZY Loves Balls【模拟】

DZY Loves Balls Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K

刺骨的言语ヽ痛彻心扉/ 2022年07月29日 09:16/ 0 赞/ 2 阅读

相关 codeforces-305A Strange Addition（思维+模拟）

A. Strange Addition time limit per test 2 seconds memory limit per test 256 megabyte

拼搏现实的明天。/ 2022年06月10日 09:22/ 0 赞/ 204 阅读

相关 AtCoder ABC 128D equeue

题目链接：[https://atcoder.jp/contests/abc128/tasks/abc128\_d][https_atcoder.jp_contests_abc1

ゝ一世哀愁。/ 2021年11月01日 06:18/ 0 赞/ 247 阅读