悲伤的发现自己非常菜，尝试通过补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$时式子与上面式子吻合找到答案。
#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;
}