CF1543D / CF913E

smallfang

2022 年 07 月 20 日

492 次浏览

暂无评论

1237字数

悲伤的发现自己非常菜，尝试通过补CF题来提高水平（雾。

大概是从去年暑假的CF开始补，基本上尝试Div2的DE, 和Div1的后面 $\leq 2900$

CF1543D diff:2200

首先这是D1/D2. D2与D1的区别在一个 $k=2$ 一个 $k=[1, 100]$
我们发现它所定义的符号在 $k=2$ 时就为异或，我们可以通过这个下手完成D1。
我们开始研究D2的做法。

我们看到 $a \oplus_k b = c$ 这一个式子。

题目中 $x\oplus_kz=y$ 所以我们考虑如何通过 $y$ 来推到 $x$ .

我们发现可以定义 $\ominus$，是操作相反，发现 $y\ominus_kx = z$。

此时我们回到题目，题目要求我们猜测 $x$ 的值。

每一次我们猜测后，$x\oplus_kz=y$ 新值 $z$ 和原来的 $x$ 符合的式子。

那么根据刚才我们的定义。我们发现新的 $x$ 数值等于 $q_1\ominus_kx$

这是第一次。那么我们可以发现第二次就是$q_2\ominus(q_1\ominus_kx)$

显然我们可以发现第 $q_i$ 次时 $x$ 的值为

$$ q_{i}\ominus_k(q_{i-1}\ominus_k(q_{i-2}\ominus_k(q_{i - 3}\ominus_k(...\ominus_k(q_1\ominus_k x))))) $$

那么我们想猜测到 $x$ 的值。

发现我们可以询问$n$次。那么我们探究x的规律，使得式子在某时与上面的式子完全吻合。此时我们就找到了答案。

那我们发现

$$ q_{i}\ominus_k(q_{i-1}\ominus_k(q_{i-2}\ominus_k(q_{i - 3}\ominus_k(...\ominus_k(q_1\ominus_k (i-1)))))) $$

当$i = x+1$时式子与上面式子吻合找到答案。

Code

#include <iostream>
#include <cstdio>
#include <cmath>

typedef long long ll;

const int N = 1e5 + 5;

using namespace std;

int n, m, k;

ll ask, sum;

ll add(ll a, ll b) {
    ll ts = 1, res = 0;
    for (int i = 1; i <= 25; i ++ ) {
        if (!a && !b)
            break;
        ll t = (a % k + b % k) % k;
        res += t * ts;
        ts *= k;
        a /= k, b /= k;
    }
    return res;
}

ll su(ll a, ll b) {
    ll ts = 1, res = 0;
    for (int i = 1; i <= 25; i ++ ) {
        if (!a && !b)
            break;
        ll t = (a % k - b % k + k) % k;
        res += t * ts;
        ts *= k;
        a /= k, b /= k;
    }
    return res;
}

int main() {
    int T;
    cin >> T;
    while (T -- ) {
        cin >> n >> k;
        for (int i = 1; i <= n; i ++ ) {
            if (i == 1) {
                sum = 0, ask = 0;
            }
            if (i != 1) {
                if (i % 2) {
                    ask = add(sum, i - 1);
                } else {
                    ask = su(sum, i - 1);
                }
            }
            cout.flush();
            cout << ask << endl;
            cout.flush();
            int r; cin >> r; if (r == 1) {
                break;
            }
            sum = su(ask, sum);
        }
    }
}

话说现在开始大括号不换行了qwq.

CF913E diff:2400

一道神奇的题。题意比较难理解。理解之后，我们可以考虑状压dp。我们用 $f_{i, j, k}$ 表示在第 $i$ 次下最终答案 $j$ ,优先级为 $k$ 的最短方案。

优先级遵循其规则分为 $0, 1, 2$ $0$ 为进行 $|$ 的数值。$1$ 为进行 $\&$ 之后的数值。 $2$ 表示加 $()$ or $!$ 之后的数值。

我们发现可以递推。参照代码的方式可以进行。

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = (1 << 8) + 5, M = 12;

string f[M][N][3];

string good(string x, string y) {
    if (x == "") {
        return y;
    } else if (y == "") {
        return x;
    }
    if (x.size() < y.size()) {
        return x;
    } else if (y.size() < x.size()) {
        return y;
    }
    return x < y ? x : y;
}

string cs(string x, int ms) {
    if (x == "" || x == "|" || x == "!" || x == "&") {
        return "";
    }
    if (ms) {
        return x;
    }
    return "(" + x + ")";
}


string sh(int x) {
    string res = "";
    if (x == 0) {
        return "0";
    }
    while (x) {
        res = char((x % 2) + '0') + res;
        x /= 2;
    }
    return res;
}

int main() {
    f[0][15][2] = 'x';
    f[0][51][2] = 'y';
    f[0][85][2] = 'z';
    for (int i = 0; i < M - 1; i ++ ) {
        for (int j = 0; j < (1 << 8); j ++ ) {
            for (int x = 0; x <= 2; x ++ )
                f[i + 1][j][x] = good(f[i + 1][j][x], f[i][j][x]);
            f[i + 1][j][2] = good(f[i + 1][j][2], good(cs(f[i][j][0], 0), cs(f[i][j][1], 0)));
            f[i + 1][((1 << 8) - 1) ^ j][2] = good(f[i + 1][((1 << 8) - 1) ^ j][2], cs('!' + f[i][j][2], 1));
        }
        for (int j = 0; j < (1 << 8); j ++ ) {
            for (int k = 0; k < (1 << 8); k ++ ) {
                for (int x = 0; x <= 2; x ++ ) {
                    for (int y = 1; y <= 2; y ++ ) {
                        if (f[i][j][x] != "" && f[i][k][y] != "")
                            f[i + 1][j | k][0] = good(f[i + 1][j | k][0], f[i][j][x] + '|' + f[i][k][y]);
                    }
                } 
                for (int x = 1; x <= 2; x ++ ) {
                    for (int y = 2; y <= 2; y ++ ) {
                        if (f[i][j][x] != "" && f[i][k][y] != "") {
                            f[i + 1][j & k][1] = good(f[i + 1][j & k][1], f[i][j][x] + '&' + f[i][k][y]);
                        }
                    }
                } 
            }

        }
    }
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T -- ) {
        int n;
        int j = 0;
        cin >> n;
        int k = 1;
        while (n) {
            j += k * (n % 10);
            n /= 10;
            k *= 2;
        }
        cout << good(good(f[M - 1][j][2],f[M - 1][j][1]), f[M - 1][j][0]) << '\n';
    }
    return 0;
}

CF1543D / CF913E