CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
B 题沙雕了，卡了四十分钟，然后突然发现排序一下就好了…
把 E 转成组合数学的模型后发现还是不会求…
F 一觉醒来 TLE99，然后发现原来按照子树深度去筛点的做法最坏情况下要查询根号次…
Ehab Fails to Be Thanos
#include <bits/stdc++.h>
using namespace std;
const int N = 1023;
long long s1, s2;
int n, a[2 * N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < 2 * n; ++i)
scanf("%d", &a[i]), s1 += a[i];
sort(a, a + 2 * n);
for (int i = 0; i < n; ++i)
s2 += a[i];
if (s2 * 2 == s1)
return printf("-1"), 0;
for (int i = 0; i < 2 * n; ++i)
printf("%d ", a[i]);
}
Ehab Is an Odd Person
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int n, cnt[2], a[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d", &a[i]), ++cnt[a[i] & 1];
if (cnt[0] && cnt[1])
sort(a, a + n);
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
}
Ehab and a Special Coloring Problem
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int n, a[N];
int main()
{
scanf("%d", &n);
for (int i = 2, tot = 0; i <= n; ++i)
{
a[i] = N;
for (int j = 2; a[i] == N && j * j <= i; ++j)
if (i % j == 0)
a[i] = a[j];
if (a[i] == N)
a[i] = ++tot;
}
for (int i = 2; i <= n; ++i)
printf("%d ", a[i]);
}
Ehab and the Expected XOR Problem
#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 18;
int n, x, y, a[N];
int main()
{
scanf("%d %d", &n, &x);
if (x >= (1 << n))
{
printf("%d\n", (1 << n) - 1);
for (int i = 0, len = (1 << n) - 1; i < len; ++i)
{
int t = i ^ (i + 1);
printf("%d ", t);
}
return 0;
}
for (y = 1; y <= x; y <<= 1)
if (y & x)
break;
printf("%d\n", (1 << n - 1) - 1);
for (int i = 0, len = (1 << n - 1) - 1; i < len; ++i)
{
int t = i ^ (i + 1);
t = t % y + t / y * 2 * y;
printf("%d ", t);
}
}
Ehab and the Expected GCD Problem
#include <stdio.h>
#include <math.h>
#define N 1000007
#define M 1000000007
typedef long long ll;
ll n, b = 1, dp[2][N][2];
int main()
{
scanf("%I64d", &n);
ll v = 1 << (ll)log2(n), u = v / 2 * 3;
for (dp[0][1][0] = 1, dp[0][1][1] = u <= n; u >>= 1, v >>= 1, v >= 1; b ^= 1)
for (ll j = 1, w = n / v, x = n / (v * 2), y = n / (v * 3), z = n / u; j <= w; ++j)
dp[b][j][0] = (dp[b][j - 1][0] * (w - (j - 1)) % M + dp[b ^ 1][j - 1][0] * (w - x) % M + dp[b ^ 1][j - 1][1] * (w - y) % M) % M,
dp[b][j][1] = (dp[b][j - 1][1] * (z - (j - 1)) % M + dp[b ^ 1][j - 1][1] * (z - y) % M) % M;
printf("%I64d", dp[b ^ 1][n][0]);
}
Ehab and the Big Finale
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
vector<int> g[N];
int n, dx, d[N], sz[N], ch[N], to[N];
int query(char c, int u)
{
return printf("%c %d\n", c, u), fflush(stdout), scanf("%d", &u), u;
}
void build(int u)
{
sz[to[u] = u] = 1;
for (int c : g[u])
if (!sz[c])
{
d[c] = d[u] + 1;
build(c);
sz[u] += sz[c];
if (sz[ch[u]] < sz[c])
to[u] = to[ch[u] = c];
}
}
int dfs(int u)
{
for (int dy = dx + d[to[u]] - query('d', to[u]) >> 1; d[u] < dy;)
u = ch[u];
return d[u] == dx ? u : dfs(query('s', u));
}
int main()
{
scanf("%d", &n);
for (int i = 1, x, y; i < n; ++i)
{
scanf("%d%d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
build(1);
dx = query('d', 1);
printf("! %d\n", dfs(1));
}