1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

const int MOD = 998244353;
void solve() {
    string s;
    cin >> s;
    int n = sz(s);
    vl dp(3);
    ll ans = 0;
    rep(i, 0, n - 1) {
        int tem = s[i] - 'a';
        ll tot = ((dp[0] + dp[1]) % MOD + dp[2] % MOD) % MOD;
        ll tem2 = (1 + tot - dp[tem] + MOD) % MOD;
        dp[tem] = (dp[tem] + tem2) % MOD;
        ans = (ans + tem2) % MOD;
    }
    cout << ans << endl;
    return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

void solve() {
    int n, m, w, x, y;
    cin >> n >> m;
    vvi ma(n);
    rep(i, 0, m - 1) {
        cin >> x >> y;
        ma[x - 1].push_back(y - 1);
        ma[y - 1].push_back(x - 1);
    }
    cin >> w;
    vector<string> a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vvi ma2(n * w);
    vi deg(n * w);
    int tem = 0;
    rep(i, 0, w - 1) {
        rep(j, 0, n - 1) {
            if (a[j][i] == 'o') tem++;
        }
    }
    rep(i, 0, n - 1) {
        for (int& p : ma[i]) {
            rep(j, 0, w - 1) {
                if (a[i][j] == 'o' && a[p][(j + 1) % w] == 'o') {
                    ma2[j * n + i].push_back((j + 1) % w * n + p);
                    deg[(j + 1) % w * n + p]++;
                }
            }
        }
    }
    rep(i, 0, w - 1) {
        rep(j, 0, n - 1) {
            if (a[j][i] == 'o' && a[j][(i + 1) % w] == 'o') {
                ma2[i * n + j].push_back((i + 1) % w * n + j);
                deg[(i + 1) % w * n + j]++;
            }
        }
    }
    queue<int> q;
    rep(i, 0, w - 1) {
        rep(j, 0, n - 1) {
            if (a[j][i] == 'o' && deg[i * n + j] == 0) q.push(i * n + j);
        }
    }
    int tem2 = 0;
    while (!q.empty()) {
        auto node = q.front();
        q.pop();
        tem2++;
        for (int& p : ma2[node]) {
            if (--deg[p] == 0) q.push(p);
        }
    }
    if (tem2 < tem)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return;
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

struct Info {
    ll dp[2][2];
    Info(ll x = 0) {
        dp[0][0] = 0;
        dp[0][1] = x;
        dp[1][0] = 0;
        dp[1][1] = -LLONG_MAX / 3;
    }
};
Info operator+(const Info& a, const Info& b) {
    Info c;
    rep(i, 0, 1) {
        rep(j, 0, 1) { c.dp[i][j] = -LLONG_MAX / 3; }
    }
    rep(i, 0, 1) {
        rep(j, 0, 1) {
            rep(k, 0, 1) { c.dp[i][j] = max(c.dp[i][j], a.dp[i][k] + b.dp[k][j]); }
        }
    }
    return c;
}
template <typename T>
class SegmentTree {
    int n;
    vector<T> tree;
    T merge_val(T a, T b) const { return a + b; }  // 合并子树

    void maintain(int node) {  // 维护整棵树
        tree[node] = merge_val(tree[node * 2], tree[node * 2 + 1]);
    }

    void build(const vector<T>& a, int node, int l, int r) {
        if (l == r) {
            tree[node] = a[l];
            return;
        }
        int m = (l + r) / 2;
        build(a, node * 2, l, m);
        build(a, node * 2 + 1, m + 1, r);
        maintain(node);
    }  // 建树

    void update(int node, int l, int r, int i, T val) {
        if (l == r) {
            tree[node] = val;
            return;
        }
        int m = (l + r) / 2;
        if (i <= m)
            update(node * 2, l, m, i, val);
        else
            update(node * 2 + 1, m + 1, r, i, val);
        maintain(node);
    }  // 更新i处的值为val

    T query(int node, int l, int r, int ql, int qr) const {
        if (ql <= l && r <= qr) return tree[node];
        int m = (l + r) / 2;
        if (qr <= m) return query(node * 2, l, m, ql, qr);
        if (ql > m) return query(node * 2 + 1, m + 1, r, ql, qr);
        T l_res = query(node * 2, l, m, ql, qr);
        T r_res = query(node * 2 + 1, m + 1, r, ql, qr);
        return merge_val(l_res, r_res);
    }  // 查询[ql,qr]的值

    int find_first(int node, int l, int r, int ql, int qr, T val) const {
        if (r < ql || l > qr) return -1;
        if (tree[node] < val) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int res = find_first(node << 1, l, m, ql, qr, val);
        if (res != -1) return res;
        return find_first(node << 1 | 1, m + 1, r, ql, qr, val);
    }  // 若遇到固定左端点的情况，需要使用全局变量（或者传入引用）记录前缀分段最大值，加一个被待求区间完全覆盖的剪枝

    int find_last(int node, int l, int r, int ql, int qr, T val) const {
        if (r < ql || l > qr) return -1;
        if (tree[node] < val) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int res = find_last(node << 1 | 1, m + 1, r, ql, qr, val);
        if (res != -1) return res;
        return find_last(node << 1, l, m, ql, qr, val);
    }

public:
    SegmentTree(int n, T init_val) : SegmentTree(vector<T>(n, init_val)) {}

    SegmentTree(const vector<T>& a) : n(a.size()), tree(2 << bit_width(a.size() - 1)) { build(a, 1, 0, n - 1); }  // 传入一个数组维护

    void update(int i, T val) { update(1, 0, n - 1, i, val); }  // 更新i的值为val

    T query(int ql, int qr) const { return query(1, 0, n - 1, ql, qr); }  // 查询[ql,qr]的值

    T get(int i) const { return query(1, 0, n - 1, i, i); }  // 取出i处的值

    int find_first(int ql, int qr, T val) const { return find_first(1, 0, n - 1, ql, qr, val); }  // 查询[ql,qr]中第一个满足条件的下标

    int find_last(int ql, int qr, T val) const { return find_last(1, 0, n - 1, ql, qr, val); }  // 查询[ql,qr]中最后一个满足条件的下标
};
void solve() {
    int n, k;
    cin >> n >> k;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vector<Info> b(n);
    rep(i, 0, n - 1) b[i] = Info(a[i]);
    SegmentTree<Info> tree(b);
    ll ans = LLONG_MAX;
    vl pre(n + 1);
    rep(i, 1, n) pre[i] = pre[i - 1] + a[i - 1];
    rep(i, 0, n - k) {
        ll tem = pre[i + k] - pre[i];
        ll tem2 = 0;
        if (k > 2) tem2 = max(tree.query(i + 1, i + k - 2).dp[0][0], tree.query(i + 1, i + k - 2).dp[0][1]);
        ans = min(ans, tem - tem2);
    }
    rep(i, 0, n - k - 1) {
        ll tem = pre[i + k + 1] - pre[i];
        ll tem2 = 0;
        if (k + 1 > 2) tem2 = max(tree.query(i + 1, i + k - 1).dp[0][0], tree.query(i + 1, i + k - 1).dp[0][1]);
        ans = min(ans, tem - tem2);
    }
    cout << ans << endl;
    return;
}