AtCoder ABC189

这套题值得写一写，从C题开始就很有技巧

C - Mandarin Orange

给定一个数组$a_1.....a_n$
对于每个$a_i$，找到其左边第一个比他小的位置$l_i,a_{l_i}<a_i$，找到其右边第一个比他小的位置$r_i$，计算$max((r_i?l_i?1)?a_i)$
找左边第一个比他小的位置可以用单调栈，手推一下就可以看出来
栈顶维护当前的数，把前面比它大的数都出栈，因为后面的数再去扫描时已经没有必要维护前面大的数了

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @file     : atcoder.py
# @software : PyCharm

import bisect
import copy
import sys
from itertools import permutations
from sortedcontainers import SortedList
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(100010)


def main():
    items = sys.version.split()
    fp = open("in.txt") if items[0] == "3.10.6" else sys.stdin
    n = int(fp.readline())
    a = list(map(int, fp.readline().split()))
    l = [0] * n
    r = [0] * n
    st = [-1]
    for i in range(n):
        while st[-1] >= 0 and a[st[-1]] >= a[i]:
            st.pop()
        l[i] = st[-1]
        st.append(i)
    st = [n]
    for i in range(n - 1, -1, -1):
        while st[-1] < n and a[st[-1]] >= a[i]:
            st.pop()
        r[i] = st[-1]
        st.append(i)
    ans = 0
    for i in range(n):
        t = (r[i] - l[i] - 1) * a[i]
        ans = max(t, ans)
    print(ans)


if __name__ == "__main__":
    main()

D - Logical Expression

dp，记录当前操作后为0的种类和操作后为1的种类

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @file     : atcoder.py
# @software : PyCharm

import bisect
import copy
import sys
from itertools import permutations
from sortedcontainers import SortedList
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(100010)


def main():
    items = sys.version.split()
    fp = open("in.txt") if items[0] == "3.10.6" else sys.stdin
    n = int(fp.readline())
    dp = [[0] * 2 for _ in range(n + 1)]
    dp[0][0] = dp[0][1] = 1
    for i in range(1, n + 1):
        s = fp.readline().strip()
        if s == "AND":
            dp[i][1] = dp[i - 1][1]
            dp[i][0] = dp[i - 1][1] + dp[i - 1][0] * 2
        else:
            dp[i][1] = 2 * dp[i - 1][1] + dp[i - 1][0]
            dp[i][0] = dp[i - 1][0]
    ans = dp[n][1]
    print(ans)


if __name__ == "__main__":
    main()

E - Rotate and Flip

如果对坐标变换熟悉，那么很简单：
操作1：$(x,y):(y,?x)$
$$\left[\begin{array}{cc}0& ?1\\ 1& 0\end{array}\right]\times \left[\begin{array}{c}x\\ y\end{array}\right]=\left[\begin{array}{c}y\\ ?x\end{array}\right]$$
操作2：
$$\left[\begin{array}{cc}0& 1\\ ?1& 0\end{array}\right]\times \left[\begin{array}{c}x\\ y\end{array}\right]=\left[\begin{array}{c}?y\\ x\end{array}\right]$$
操作3：
$$\left[\begin{array}{cc}?1& 0\\ 0& 1\end{array}\right]\times \left[\begin{array}{c}x\\ y\end{array}\right]+\left[\begin{array}{c}2p\\ 0\end{array}\right]=\left[\begin{array}{c}2p?x\\ y\end{array}\right]$$

操作4：
$$\left[\begin{array}{cc}1& 0\\ 0& ?1\end{array}\right]\times \left[\begin{array}{c}x\\ y\end{array}\right]+\left[\begin{array}{c}0\\ 2p\end{array}\right]=\left[\begin{array}{c}x\\ 2p?y\end{array}\right]$$
每一步都左乘即可。需要维护的是
$Ax+d$中两个矩阵$A,d$

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#define LT(x) (x * 2)
#define RT(x) (x * 2 + 1)

using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef vector<int> vi;


int n, m, q;
struct Query {
    int step, x, i;
};

struct Mat {
    LL a[2][2] = {0};
    int r, c;
};

Mat raw[200020];
vector<pii> trans;
Query query[200020];
pll ans[200020];

bool cmp(Query& lhs, Query& rhs) {
    return lhs.step < rhs.step;
}

Mat mul(Mat& a, Mat& b) {
    Mat ret;
    ret.r = a.r, ret.c = b.c;
    for (int i = 0; i < a.r; ++i) {
        for (int j = 0; j < b.c; ++j) {
            for (int k = 0; k < a.c; ++k) {
                ret.a[i][j] += a.a[i][k] * b.a[k][j];
            }
        }
    }
    return ret;
}


int main() { 
    //freopen("in.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        LL x, y;
        scanf("%lld%lld", &x, &y);
        Mat mat;
        mat.r = 2, mat.c = 1;
        mat.a[0][0] = x, mat.a[1][0] = y;
        raw[i] = mat;
    }
    Mat m0;
    m0.r = m0.c = 2;
    m0.a[0][0] = 0, m0.a[0][1] = 1, m0.a[1][0] = -1, m0.a[1][1] = 0;
    Mat m1 = m0;
    m1.a[0][0] = 0, m1.a[0][1] = -1, m1.a[1][0] = 1, m1.a[1][1] = 0;
    Mat m2 = m0;
    m2.a[0][0] = -1, m2.a[0][1] = 0, m2.a[1][0] = 0, m2.a[1][1] = 1;
    Mat m3 = m0;
    m3.a[0][0] = 1, m3.a[0][1] = 0, m3.a[1][0] = 0, m3.a[1][1] = -1;
    scanf("%d", &m);
    for (int i = 0; i < m; ++i) {
        int op;
        scanf("%d", &op);
        op--;
        if (op == 0 || op == 1) {
            trans.push_back({ op, 0 });
        }
        else {
            int p;
            scanf("%d", &p);
            trans.push_back({ op, p });
        }
    }
    Mat cur;
    cur.r = cur.c = 2;
    cur.a[0][0] = 1, cur.a[1][1] = 1;
    Mat d0;
    d0.r = 2, d0.c = 1;
    scanf("%d", &q);
    for (int i = 0; i < q; ++i) {
        int p, x;
        scanf("%d%d", &p, &x);
        x--;
        query[i].step = p, query[i].x = x, query[i].i = i;
    }

    sort(query, query + q, cmp);
    int i = 0, j = 0;
    while (i <= m && j < q) {
        int step = query[j].step;
        int ri = query[j].i;
        int x = query[j].x;
        if (i == step) {
            Mat nm = mul(cur, raw[x]);
            ans[ri] = { nm.a[0][0] + d0.a[0][0], nm.a[1][0] + d0.a[1][0] };
            j += 1;
        }
        else {
            if (trans[i].first == 0) {
                cur = mul(m0, cur);
                d0 = mul(m0, d0);
            }
            else if (trans[i].first == 1) {
                cur = mul(m1, cur);
                d0 = mul(m1, d0);
            }
            else if (trans[i].first == 2) {
                LL p = trans[i].second;
                cur = mul(m2, cur);
                d0 = mul(m2, d0);
                d0.a[0][0] += p * 2;
            }
            else {
                LL p = trans[i].second;
                cur = mul(m3, cur);
                d0 = mul(m3, d0);
                d0.a[1][0] += p * 2;
            }
            i += 1;
        }
    }
    for (int i = 0; i < q; ++i) {
        printf("%lld %lld\n", ans[i].first, ans[i].second);
    }
    return 0;
}

F - Sugoroku2

本题的思路和强化学习中贝尔曼方程非常类似
当递推式中存在未知数，可以将未知数设为一个需要解的元，最后列方程求解。
具体到此题中，
$$\begin{gathered} f(i)=0,i>=n \\ f(i)=f(0),i\in A \\ f(i)=(f(i+1)+f(i+2)...f(i+m))/m+1,i\notin A \end{gathered}$$
由于只存在一个未知数，可以将其单独列出求系数
即
$f(i)=a_{i}f(0)+b_i$
对两者进行dp递推
最后$f(0)=a_{0}f(0)+b_0$
求解$f(0)$

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#define LT(x) (x * 2)
#define RT(x) (x * 2 + 1)

using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef vector<int> vi;


int n, m, k;
double a[400040], b[400040], sa[400040], sb[400040];
set<int> ks;


int main() { 
    //freopen("in.txt", "r", stdin);
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < k; ++i) {
        int t;
        scanf("%d", &t);
        ks.insert(t);
    }
    for (int i = n - 1; i >= 0; --i) {
        if (ks.count(i)) {
            a[i] = 1.0;
            b[i] = 0.0;
        }
        else {
            a[i] = (sa[i + 1] - sa[i + m + 1]) / m;
            b[i] = (sb[i + 1] - sb[i + m + 1]) / m + 1;
        }
        sa[i] = sa[i + 1] + a[i];
        sb[i] = sb[i + 1] + b[i];
    }
    if (1 - a[0] < 1e-7) {
        printf("-1\n");
    }
    else {
        printf("%.9f\n", b[0] / (1 - a[0]));
    }
    return 0;
}