D Logical Expression

Description

Solution

设 $dp[i][0 / 1]$ 表示前 $i + 1(i > 0)$ 个变量进行逻辑运算后结果为 false 或 true 的方案数。边界条件为 $dp[0][0] = dp[0][1] = 1$ 。状态转移显然。

Code

Logical Expression

#include <bits/stdc++.h>
 
#define debug(x) cerr << #x << " = " << x << endl
 
using namespace std;
typedef long long LL;
 
const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
LL n;
string s;
LL dp[64][2];
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    dp[0][1] = dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        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] = dp[i - 1][1] * 2 + dp[i - 1][0];
            dp[i][0] = dp[i - 1][0];
        }
    }
    cout << dp[n][1];
    return 0;
}

E Rotate and Flip

Description

题目链接

Solution

首先需要离线处理。对于第 $A_i$ 操作，可将待询问的棋子编号与询问编号存放到 $A_i$ 对应的 vector 中。
设棋子的坐标为 (x, y)，那么进行一次操作后的坐标可以用 (x, y) 表示出来，进而可得到若干操作后最终的坐标:

顺时针旋转 90 度，坐标为 (-x, y)
逆时针旋转 90 度，坐标为 (-y, x)
关于直线 x = p 对称，坐标为 (2 * p - x, y)
关于直线 y = p 对称，坐标为 (x, 2 * p - y)

于是可以维护 x、y 坐标的符号标记 signx, signy；增量标记 addx, addy 以及 x、y 的交换标记。若有交换标记，则将 (x, y) 变换为 (y, x)，然后判断符号以及加上对应增量，即可得到某次操作后的点的坐标。

Code

Rotate and Flip

#include <bits/stdc++.h>
#define int long long

using namespace std;

#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 2e5 + 5, MOD = 1e9 + 7;

int n, m, q;
int revx, revy;
int addx, addy;
int swapxy;
array<int, MAXN> x, y, a, b;
array<int, MAXN> op, p, ansx, ansy;
vector<pair<int, int>> vec[MAXN];

signed main() {
    boost;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> op[i];
        if (op[i] > 2) cin >> p[i];
    }
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> a[i] >> b[i];
        vec[a[i]].emplace_back(b[i], i);
    }
    for (auto& i : vec[0]) {
        ansx[i.second] = x[i.first];
        ansy[i.second] = y[i.first];
    }
    for (int i = 1; i <= m; i++) {
        if (op[i] == 1) {
            swapxy ^= 1, revx ^= 1, addx *= -1;
            swap(revx, revy), swap(addx, addy);
        } else if (op[i] == 2) {
            swapxy ^= 1, revy ^= 1, addy *= -1;
            swap(revx, revy), swap(addx, addy);
        } else if (op[i] == 3) {
            revx ^= 1, addx *= -1;
            addx += p[i] * 2;
        } else {
            revy ^= 1, addy *= -1;
            addy += p[i] * 2;
        }
        for (auto& ii : vec[i]) {
            ansx[ii.second] = x[ii.first];
            ansy[ii.second] = y[ii.first];
            if (swapxy) swap(ansx[ii.second], ansy[ii.second]);
            if (revx) ansx[ii.second] *= -1;
            if (revy) ansy[ii.second] *= -1;
            ansx[ii.second] += addx;
            ansy[ii.second] += addy;
        }
    }
    for (int i = 1; i <= q; i++)
        cout << ansx[i] << " " << ansy[i] << "\n";
    return 0;
}

F Sugoroku2

Description

题目链接

Solution

设 $f_i$ 表示从 $i$ 到 $n$ 的期望步数。则有

f_{i} = \begin{cases} 0 & i > n\\ f_0 & 如果会从 i 传送到 0\\ 1 / M * (f_{i+1} + ... + f_{i + M}) + 1 & 其它\\ \end{cases}

于是发现 $f_i$ 可以表示为 $A_i * f_0 + B_i$ 的形式，最终 $f(0) = A_0 * f_0 + B_0$ ，解出 $f_0$ 即为从起点到终点的步数。 (通过后缀和分别求出 $A_i$ 和 $B_i$ ，注意分母为 0 时无解)

Code

Sugoroku2

#include <bits/stdc++.h>
#define double long double

using namespace std;

#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 1e5 + 5, MOD = 1e9 + 7;

int n, m, k;
array<int, 11> a;
array<double, MAXN * 2> sufa, sufb;

int main() {
    boost;
    cin >> n >> m >> k;
    cout << setprecision(4) << fixed;
    set<int> s;
    for (int i = 1; i <= k; i++) cin >> a[i], s.insert(a[i]);
    for (int i = n - 1; i >= 0; i--) {
        if (s.count(i)) {
            sufa[i] = sufa[i + 1] + 1;
            sufb[i] = sufb[i + 1];
            continue;
        }
        double tmpa = (sufa[i + 1] - sufa[i + m + 1]) / m;
        double tmpb = (sufb[i + 1] - sufb[i + m + 1]) / m + 1;
        sufa[i] = sufa[i + 1] + tmpa;
        sufb[i] = sufb[i + 1] + tmpb;
        if (i == 0) {
            if (abs(1.0 - tmpa) > 1e-15)cout << tmpb / (1.0 - tmpa) << endl;
            else cout << -1 << endl;
        }
    }   
    return 0;
}