绍兴游记Day8 b 题解

Link

官方题目传送门
官方题解传送门

题意

$Hzy$有一个集合,一开始有$[0\dots a]$这些数字(如果$a=-1$则说明集合为空)。接下来有$m$个时刻,每个时刻都会有一种操作。
1. 插入一个数字$x$,保证$x$不在集合中。
2. 删去一个数字$x$。
3. 把目前不在集合中的最早被删除的数字,插回到集合中(如果一个数字曾经被删去被插回来过然后再删去,这里认为其删去的时间为最近一次删去的时间)。
由于描述这$m$个时刻的操作实在太麻烦了,所以$Hzy$用了一个长度为$m$的序列$p$来描述每个时刻的操作种类。对于每个操作,满足以下约定。
1. 这个序列$p$里所有元素均为$[-1,b)$的整数
2. 若$p_i=-1$,则表示时刻i的操作为第三种,如果此时并不存在满足条件且被删去的数字,则忽略此操作。
3. 否则,如果时刻$i$中,大小为$p_i$的数字一开始不在集合中且也从来没有通过第一种操作插入集合中,则表示第$i$个操作为向集合中插入一个大小为$p_i$的数字,即第一种操作。
4. 否则,如果时刻$i$中,大小为$p_i$的数字在集合中,则把$p_i$从集合里删除,即第二种操作。
5. 否则,表示时刻i的操作为第三种,如果此时并不存在满足条件且被删去的数字,则忽略此操作。
$Hzy$现在想知道在第$i$个时刻的操作进行完后,集合的$mex$是什么,即在集合中未出现过的最小的自然数。第$i$个操作的答案设为$ans_i$(如果第$i$个操作被忽略,$ans_i=0$)。但是她不满足仅知道$ans_i$,她想知道$ans_i×(i^2+7i) \mod 998244353$的异或和
如果某个时刻的操作被忽略,那么$Hzy$将不会进行任何操作,也不计算此时的答案。
下面是$IO$输入代码:

namespace IO{
    int c;
    unsigned int seed;
    unsigned int randnum(){seed^=seed<<13;seed^=seed>>17;seed^=seed<<5;return seed;}
    inline int read(int &x){scanf("%d",&x);return x;}
    inline void init_case(int &m,int &a,int &b,int &d,int p[]){scanf("%d%u%d%d%d%d",&m,&seed,&a,&b,&c,&d);for(int i=1;i<=m;i++){if(randnum()%c==0)p[i]=-1;else p[i]=randnum()%b;}}
    inline void update_ans(unsigned int &ans_sum,unsigned int cur_ans,int no){const static unsigned int mod=998244353;ans_sum^=(long long)no*(no+7)%mod*cur_ans%mod;}
}

题解&Code

#include<bits/stdc++.h>
using namespace std;
namespace IO{
    int c;
    unsigned int seed;
    unsigned int randnum(){seed^=seed<<13;seed^=seed>>17;seed^=seed<<5;return seed;}
    inline int read(int &x){scanf("%d",&x);return x;}
    inline void init_case(int &m,int &a,int &b,int &d,int p[]){scanf("%d%u%d%d%d%d",&m,&seed,&a,&b,&c,&d);for(int i=1;i<=m;i++){if(randnum()%c==0)p[i]=-1;else p[i]=randnum()%b;}}
    inline void update_ans(unsigned int &ans_sum,unsigned int cur_ans,int no){const static unsigned int mod=998244353;ans_sum^=(long long)no*(no+7)%mod*cur_ans%mod;}
}
void write(int x){if(x<0) putchar('-'),x=-x;if(x<10) putchar(x+'0');else{write(x/10);putchar(x%10+'0');}}
unsigned int ans_sum;
int T,m,a,b,d,ans,p[4000010],f[4000010],vis[4000010],num[4000010],h,t,g[4000010];
bool did[4000010],tag;
queue<int> q;
namespace Solve{
    inline void Step1(int x){vis[x]=1;did[x]=1;while(vis[ans]&&ans<=b) ans++;}//操作1:加入一个数字,把这个数标记在集合中(did)以及之前或现在加入过(vis),while求出范围内没有加入过的最小值
    inline void Step2(int x){if(d==1){tag=1;return ;}did[x]=0;q.push(x);while(h<=t&&g[t]>x) t--;g[++t]=x;}//操作2:删除一个数,如果d=1那么忽略,否则将这个数取消在集合中这个标记(did)并且加入到"删除过的"队列中,再插入到删除的单调度队列
    inline void Step3(){if(d||q.empty()){tag=1;return ;}did[q.front()]=1;q.pop();}//操作3:加入最早删除的值,d=1、之前没有删除时忽略,否则把该数字标记在集合中,并且在队列中pop掉这个数
}
signed main(){
    IO::read(T);//输入数据组数
    while(T--){
        IO::init_case(m,a,b,d,p);//调用IO读入
        for(int i=0;i<=a;i++) vis[i]=1,did[i]=1;//初始化,一开始[0,a]区间内所有的数都在集合中
        for(int i=a+1;i<=b;i++) vis[i]=0,did[i]=0;//初始化,一开始(a,b]区间内所有的数都不在集合中
        ans=a+1;h=1;t=0;tag=0;ans_sum=0;//一开始ans=a+1(因为[0,a]区间内所有的数已经在集合中)
        while(!q.empty()) q.pop();//清空队列
        for(int i=1;i<=m;i++){
            tag=0;//tag表示该操作是否忽略(0表示不忽略,1表示忽略)
            if(p[i]==-1) Solve::Step3();//如果操作为-1,那么进行操作3
            else if(vis[p[i]]==0) Solve::Step1(p[i]);//如果之前没有加入过该数,那么进行操作1
            else if(did[p[i]]) Solve::Step2(p[i]);//如果现在还是有这个数,那么进行操作2
            else Solve::Step3();//否则进行操作3
            if(tag==1) continue ;//如果忽略,那就忽略
            while(h<=t&&did[g[h]]) h++;//如果在集合中,那就下一个
            if(h>t) IO::update_ans(ans_sum,ans,i);//如果队列里没有了,那么就是ans(加入操作中的最小值)
            else IO::update_ans(ans_sum,min(ans,g[h]),i);//否则就是加入操作最小值与删除操作最小值的最小值
        }
        write(ans_sum);putchar('\n');//输出最终结国
    }
}

完结撒花✿✿ヽ(°▽°)ノ✿

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇