Atcoder ABC298 D-F

D - Writing a Numeral

链接:

D - Writing a Numeral (atcoder.jp)

简要题意:

• 问题陈述

  我们有一个字符串 \(S\) 。初始值为 \(S=\) 1.
  按以下格式依次处理 \(Q\) 查询。

  • 1 x：在 \(S\) 的末尾添加一个数字 \(x\) 。
  • 2：删除 \(S\) 开头的数字。
  • 3 : 以十进制形式打印 \(S\) 所代表的数字，取模 \(998244353\) 。

思路:

• 我们直接用双端队列模拟题目中的操作
• 注意点是删除s开头的字符,这边的删除是取模意义下的,所以总结答案时候要加上模数再取模
• 两个取模的结果进行相减操作时（易知前面的数理论上应该大，但取模之后可能小于后面的数）此时应该加上MOD的倍数，再对相减结果进行取模，从而保证输出为正

代码:

const int N = 200005;
ll powerMod(ll x, ll n, ll mod){ //快速幂
    ll ans = 1;
    while (n > 0){
        if  (n & 1)
            ans = (ans * x) % mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return ans;
}
void solve(){
    int q;
    cin >> q;
    int mod = 998244353;
    deque<int> dq;
    dq.push_back(1);
    int ans = 1;
    while(q--){
        int op;
        cin >> op;
        if(op==1){
            int x;
            cin >> x;
            dq.push_back(x);
            ans = (ans*10%mod + x)%mod;
        }else if(op==2){
            int sz = dq.size();
            ans=(ans - dq.front()*powerMod(10,sz - 1,mod)%mod +mod)%mod;
            dq.pop_front();
        }else{
            cout << ans <<endl;
        }
    }
}

E - Unfair Sugoroku

链接:

E - Unfair Sugoroku (atcoder.jp)

简要题意:

• 问题陈述

  高桥从 \(A\) 点开始，青木从 \(B\) 点开始。他们将轮流掷骰子。
  高桥的骰子显示 \(1, 2, \ldots, P\) ，概率相同；青木的骰子显示 \(1, 2, \ldots, Q\) ，概率相同。
  当在 \(x\) 点的棋手掷出骰子，结果显示 \(i\) 时，他就会下到 \(\min(x + i, N)\) 点。
  最先到达点 \(N\) 的棋手获胜。
  求高桥先下的概率，模为 \(998244353\) 。

思路:

• 数据量很小,又是求概率所以一眼dp

• 设置 $$dp[i][j][0/1] $$ 表示 先手走到$$i$$这个地方 后手走到$$j$$ 这个地方,当前是先手走还是后手走的概率

• 用刷表法dp

• 最后统计a在n位置上的 b在其他合法位置的总概率累加和

• 注意开long long 笔者是define int long long的

代码:

int mod = 998244353;
int ksm(int x,int n){
    int res = 1;
    while(n){
        if(n&1) res = res*x%mod;
        x = x*x%mod;
        n>>=1;
    }
    return res;
}
int iv(int i){
    return ksm(i,mod - 2);
}
void solve(){
    int n,a,b,p,q;
    cin >> n >> a >> b >> p >> q;
    int dp[n + 1][n + 1][2]; //1先手,0后手
    memset(dp,0,sizeof dp);
    dp[a][b][1] = 1;
    for(int i = a;i< n;i++){
        for(int j = b;j < n;j++){
            for(int k = 0;k<=1;k++){
                if(k){
                    for(int t = 1;t<=p;t++){
                        dp[min(i+t,n)][j][0] = (dp[min(i+t,n)][j][0] + dp[i][j][1]*iv(p)%mod)%mod;
                    }
                }else{
                    for(int t = 1;t<=q;t++){
                        dp[i][min(j+t,n)][1] = (dp[i][min(j+t,n)][1] + dp[i][j][0]*iv(q)%mod)%mod;
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int i = b;i<n;i++){
        ans = (ans + dp[n][i][0])%mod;
    }
    cout << ans <<endl;
}

F - Rook Score

贪心 待补