CF思维体操
Plus and Multiply
Luogu
CF
题意简述：
\(\qquad\)给定 \(n,\) \(a,\) \(b\)，要求判断 \(n\) 能不能由 \(a\) 通过若干次 \(\times a\) 或者 \(+b\)得到。
解题思路：
\(\qquad\)我们首先应该找到能由上述操作得到的数的普遍形式。
\(\qquad\)我们可以证明一下这个形式可行，对于第一个数 \(1\)，显然可以表示成 \(a^0+0·b\)，所以对于 \(1\) 是成立的。如果 \(a^x+by\) 是成立的，那么进行 \(\times a\) 操作后变为 \(a^{x+1}+by\)，进行 \(+b\) 操作后变为 \(a^x+b(y+1)\)，形式仍然不变，所以我们这个形式是具有普遍可行性的。
\(\qquad\) 因此我们只需要依次枚举 \(x\)，并且判定即可，另外要注意的是 \(a = 1\) 要特判，否则 \(TLE\)
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
using PII = pair<int, int>;
int main() {
int tc;
scanf("%d", &tc);
while (tc -- ) {
int n, a, b;
scanf("%d%d%d", &n, &a, &b);
if (a == 1)
puts((n - 1) % b == 0 ? "Yes" : "No");
else {
int flag = 0;
for (long long i = 1; !flag && i <= n; i *= a)
if ((n - i) % b == 0) flag = 1;
puts(flag ? "Yes" : "No");
}
}
return 0;
}
Ehab the Xorcist
Luogu
CF
题意简述
\(\qquad\)给定两个数 \(u,\ v\)，要求构造一个数列使得数列的异或和为 \(u\), 数列的数值和为 \(v\)。
解题思路
\(\qquad\)定义 \(\Delta = v - u\)从异或的角度出发，因为异或是二进制下的不进位加法，所以异或和一定不能大于数值和。所以当 \(\Delta < 0\)的时候，无解。另外这里有一个很重要的性质，即数列的异或和与数值和的奇偶性相同。证明如下：
\(\qquad\)因为 \(2(a\&b)\) 是偶数，所以两个数的异或和与数值和奇偶性相同，以此类推即可.
\(\qquad\)所以我们可以对 \(\Delta\) 进行一下分类讨论：
第 \(5\) 种情况需要一定的思考，因为 \(\Delta\) 一定是偶数，两个相同的数异或和为 \(0\), 一个数与 \(0\) 异或得本身，那不妨把 \(\Delta\) 拆成两块，每块为 \(x\)，目标数列为\(\{x,x,u\}\)
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
using PII = pair<int, int>;
using LL = long long;
int main() {
LL u, v;
scanf("%lld%lld", &u, &v);
LL delta = v - u;
if (delta & 1 || delta < 0) puts("-1");
else {
if (delta == 0) {
if (u == 0) puts("0");
else printf("1\n%lld\n", u);
}
else {
LL x = delta >> 1;
if ((u ^ delta) != u) {
if ((x ^ (x + u)) != u) {
puts("3");
printf("%lld %lld %lld\n", x, x, u);
} else {
puts("2");
printf("%lld %lld\n", x + u, x);
}
} else {
puts("2");
printf("%lld %lld\n", delta, u);
}
}
}
return 0;
}
Orac and Medians
Luogu
CF
题意简述
给定一个序列，每次可以将一段区间修改为区间中位数，问能否将整个序列全部改为 \(k\)
解题思路
\(\qquad\)我们可以先看看我们的操作有什么性质：
\(\qquad\)由这两条性质可以推出以下几条：
以上条件只要满足任意一个，就可以成功，否则不行。
逐个判定就行了。
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
using PII = pair<int, int>;
using LL = long long;
int a[100010];
int main() {
int tc;
scanf("%d", &tc);
while (tc -- ) {
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
if (n == 1 && a[n] != k) puts("no");
else {
if (n == 1) puts("yes");
else {
int flag = 0, has = 0;
for (int i = 1; i <= n; i ++ )
has |= a[i] == k;
if (!has) puts("no");
else {
for (int i = 1; i < n && !flag; i ++ )
flag |= (a[i] >= k && a[i + 1] >= k);
if (flag) puts("yes");
else {
for (int i = 1; i < n - 1 && !flag; i ++ )
flag |= (a[i] >= k && a[i + 2] >= k);
if (flag) puts("yes");
else puts("no");
}
}
}
}
}
return 0;
}