A – Barcelonian Distance
先把曼哈顿距离做答案，然后枚举这两个点初始的方向，然后取个最小值即可。
// CF1078A.cpp
#include <bits/stdc++.h>
using namespace std;
double a, b, c, x[3], y[3];
double calcByX(double x) { return (-1.0 * a * x - c) / b; }
double calcByY(double y) { return (-1.0 * b * y - c) / a; }
int main()
{
scanf("%lf%lf%lf%lf%lf%lf%lf", &a, &b, &c, &x[1], &y[1], &x[2], &y[2]);
double ans = fabs(x[1] - x[2]) + fabs(y[1] - y[2]);
if (a != 0 && b != 0)
for (int i = 0; i <= 1; i++)
for (int j = 0; j <= 1; j++)
{
double pos1X, pos1Y, pos2X, pos2Y;
double pans = 0;
if (i == 0)
pos1X = calcByY(y[1]), pos1Y = y[1], pans += fabs(pos1X - x[1]);
else
pos1X = x[1], pos1Y = calcByX(x[1]), pans += fabs(pos1Y - y[1]);
if (j == 0)
pos2X = calcByY(y[2]), pos2Y = y[2], pans += fabs(pos2X - x[2]);
else
pos2X = x[2], pos2Y = calcByX(x[2]), pans += fabs(pos2Y - y[2]);
pans += sqrt((pos1X - pos2X) * (pos1X - pos2X) + (pos1Y - pos2Y) * (pos1Y - pos2Y));
ans = min(ans, pans);
}
printf("%.10lf\n", ans);
return 0;
}
B – The Unbearable Lightness of Weights
这道题要求计算最多能辨别多少个。可以发现：
- 如果只有一种或者两种质量，那么答案就是 \(n\)。
- 如果有更多种类的质量，那么最后答案肯定是单一质量的背包，因为我们需要确定到底是哪个种类。所以，如果这样单一质量 \(w\) 的有 \(k\) 个，且最终选法是 \(cnt_w \choose k\)，那么 \(k\) 可以被作为答案。
然后做个背包就完事了。
// CF1078B.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 110, mod = 1e9 + 7;
int n, ai[MAX_N], cnt[MAX_N], binomial[MAX_N][MAX_N], ans = 1, upper, typ;
map<pair<int, int>, int> dp, pre;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &ai[i]), upper = max(upper, ai[i]), typ += ((++cnt[ai[i]]) == 1);
for (int i = 0; i <= n; i++)
{
binomial[i][0] = binomial[i][i] = 1;
for (int j = 1; j < i; j++)
binomial[i][j] = (0LL + binomial[i - 1][j - 1] + binomial[i - 1][j]) % mod;
}
dp[make_pair(0, 0)] = 1, pre = dp;
for (int i = 1; i <= n; i++)
{
for (auto &x : pre)
{
pair<int, int> curt = make_pair(x.first.first + 1, x.first.second + ai[i]);
dp[curt] = (0LL + dp[curt] + x.second) % mod;
}
pre = dp;
}
if (typ == 1 || typ == 2)
printf("%d\n", n);
else
{
for (int w = 1; w <= upper; w++)
for (int i = 2; i <= cnt[w]; i++)
{
int val = dp[make_pair(i, i * w)];
if (dp[make_pair(i, i * w)] == binomial[cnt[w]][i])
ans = max(ans, i);
}
printf("%d\n", ans);
}
return 0;
}
C – Vasya and Maximum Matching
考虑如何去构造一个有独特的完美匹配的图：我们可以把一些点作为孤点且孤点所在的连块只有自己，使得剩下的连通块都拥有完美匹配。一开始我们可以全部删去，然后我们再来考虑构造合法的连边方案：如果一个连通块拥有独特的完美匹配，那么我们在这个连通块上加长两条边的链，也能构成合法的连通块。根据这个性质进行 DP 即可。
// CF1078C.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3e5 + 200, mod = 998244353;
int n, head[MAX_N], current, dp[MAX_N][3], tmp[3];
struct edge
{
int to, nxt;
} edges[MAX_N << 1];
void addpath(int src, int dst)
{
edges[current].to = dst, edges[current].nxt = head[src];
head[src] = current++;
}
void dfs(int u, int fa)
{
dp[u][0] = 1;
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa)
{
dfs(edges[i].to, u);
tmp[0] = 1LL * dp[u][0] * ((0LL + dp[edges[i].to][0] + dp[edges[i].to][2]) % mod) % mod;
tmp[1] = (1LL * dp[u][0] * dp[edges[i].to][2] % mod + 1LL * dp[u][1] * ((dp[edges[i].to][0] + 2LL * dp[edges[i].to][2] % mod) % mod) % mod) % mod;
tmp[2] = (1LL * dp[u][0] * (dp[edges[i].to][0] + dp[edges[i].to][1]) % mod + 1LL * dp[u][1] * (dp[edges[i].to][0] + dp[edges[i].to][1]) % mod + 1LL * dp[u][2] * ((dp[edges[i].to][0] + 2LL * dp[edges[i].to][2] % mod) % mod) % mod) % mod;
swap(tmp, dp[u]);
}
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%d", &n);
for (int i = 1, u, v; i <= n - 1; i++)
scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
dfs(1, 0);
printf("%d\n", (dp[1][0] + dp[1][2]) % mod);
return 0;
}
D – Chattering
刚想这题的时候想过一种很暴力的转移，最后发现有环所以就 GG 了。
我们可以考虑用双倍增(?)来搞定这个。我们可以把这个棋盘(?)左右各复制一份，然后在先用 ST 表处理出左右横跳的信息。处理好之后，在这个基础上再跳一次，然后回答询问的时候就在二进制位上从大到小处理即可。
// CF1078D.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3e5 + 200;
int n, ai[MAX_N], lft[20][MAX_N], rig[20][MAX_N], log2_[MAX_N];
struct ST
{
int table[20][MAX_N], val[MAX_N], typ;
int gmax(int x, int y) { return val[x] > val[y] ? x : y; }
void build(int *arr, int len, int type)
{
typ = type;
for (int i = 1; i <= len; i++)
table[0][i] = i, val[i] = typ * arr[i];
for (int i = 1; i <= 19; i++)
for (int j = 1; j + (1 << i) - 1 <= len; j++)
table[i][j] = gmax(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
}
int query(int l, int r)
{
int d = log2_[r - l + 1];
return gmax(table[d][l], table[d][r - (1 << d) + 1]);
}
} lrmq, rrmq;
int main()
{
scanf("%d", &n);
for (int i = 2; i <= 3 * n; i++)
log2_[i] = log2_[i >> 1] + 1;
for (int i = 1; i <= n; i++)
scanf("%d", &ai[i]), ai[i + n] = ai[i + (n << 1)] = ai[i];
if (n == 1)
return puts("0"), 0;
for (int i = 1; i <= 3 * n; i++)
lft[0][i] = max(1, i - ai[i]), rig[0][i] = min(3 * n, i + ai[i]);
for (int i = 0; i <= log2_[3 * n]; i++)
lft[i][1] = 1, rig[i][3 * n] = 3 * n;
lrmq.build(lft[0], 3 * n, -1), rrmq.build(rig[0], 3 * n, 1);
for (int i = 1; i <= log2_[3 * n]; i++)
for (int j = 1; j <= 3 * n; j++)
{
int posl = lrmq.query(lft[i - 1][j], rig[i - 1][j]);
int posr = rrmq.query(lft[i - 1][j], rig[i - 1][j]);
lft[i][j] = min(lft[i - 1][posl], lft[i - 1][posr]);
rig[i][j] = max(rig[i - 1][posl], rig[i - 1][posr]);
}
for (int j = n + 1; j <= (n << 1); j++)
{
int wl = j, wr = j, ans = 0;
for (int i = log2_[3 * n]; i >= 0; i--)
{
if (max(rig[i][wl], rig[i][wr]) - min(lft[i][wl], lft[i][wr]) + 1 >= n)
continue;
int wwl = lrmq.query(lft[i][wl], rig[i][wr]);
int wwr = rrmq.query(lft[i][wl], rig[i][wr]);
ans += (1 << i), wl = wwl, wr = wwr;
}
ans++;
printf("%d ", ans);
}
puts("");
return 0;
}