C题
题意：给定 个盒子，你需要满足一下三种操作：
- ，把数字 扔到盒子 里面；
- ，查询盒子 里面的数字，按升序输出；
- ，查询数字 出现在的盒子编号，按升序输出。（若多个同一数字出现在一个盒子，那么这个盒子编号只输出一次。）
思路：用set存盒子编号,用mulitset存数字编号
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,a[200001];
set<int> s[200001];
multiset<int> ss[200001];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>q;
while(q--){
int op,i;cin>>op>>i;
if(op==1){
int j;cin>>j;
ss[j].insert(i);
s[i].insert(j);
}
if(op==2){
for(multiset<int>::iterator it=ss[i].begin();it!=ss[i].end();it++){
cout<<*it<<" ";
}
cout<<"\n";
}
if(op==3){
for(set<int>::iterator it=s[i].begin();it!=s[i].end();it++){
cout<<*it<<" ";
}
cout<<"\n";
}
}
return 0;
}
D题
题意：有一序列，初始有 你需要满足以下三种操作：
-
：将一个数字 加到序列最后面；
-
：删除 最前面；
-
：查询 从前往后，由数位拼凑的数字。对 取模。
思路：用queue直接模拟,对于操作2,用当前ans减去pow(10,len-1)则为操作后的数组
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int Q,ans=1,len;
queue<int> q;
int qpow(int x,int y){
int out=1;
while(y){
if(y&1) out=out*x%mod;
x=x*x%mod;
y>>=1;
}
return out;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>Q;
q.push(1);
while(Q--){
int opt;
cin>>opt;
if(opt==1){
int x;
cin>>x;
ans=(ans*10%mod+x)%mod;
q.push(x);
len++;
}
if(opt==2){
ans=(mod+(ans-qpow(10,len)*q.front()%mod)%mod)%mod;
len--;
q.pop();
}
if(opt==3){
cout<<ans<<"\n";
}
}
}
E题
题意:两个人（分别记甲和乙）手上分别有初始值 和 。
甲有个骰子，等概率从 中出现一个数，让甲当前值加上出现的数。乙同理，不过是等概率从 中出现一个数。
当前的数先大于等于 的人胜利。甲先甩，甲乙轮流。问甲获胜的几率。答案对 取模。
思路：概率DP，求出逆元之后五重循环枚举轮数,甲的位置,乙的位置，甲的步数，乙的步数，用刷表的方法转移
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int n,a,b,p,q,dp[102][102][102],ans;
int qpow(int x,int y=mod-2){
int out=1;
while(y){
if(y&1) out=out*x%mod;
x=x*x%mod;
y>>=1;
}
return out;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>a>>b>>p>>q;
int inv=qpow(p)*qpow(q)%mod;
dp[0][a][b]=1;
for(int i=1;i<=n;i++){
for(int l=a;l<n;l++){
for(int r=b;r<n;r++){
for(int lstep=1;lstep<=p;lstep++){
for(int rstep=1;rstep<=q;rstep++){
dp[i][min(n,l+lstep)][min(n,r+rstep)]=(dp[i][min(n,l+lstep)][min(n,r+rstep)]+inv*dp[i-1][l][r]%mod)%mod;
}
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=b;j<=n;j++){
ans=(ans+dp[i][n][j])%mod;
}
}
cout<<ans;
}