简单题。
void slv() {
int a = Read<int>(), b = Read<int>();
if (a > b) Puts("Bat");
else Puts("Glove");
return;
}
也是简单题。
constexpr i128 INF = - 1e18;
i128 a, m, l, r;
void slv() {
a = Read<i128>(), m = Read<i128>(), l = Read<i128>(), r = Read<i128>();
a -= m * ((a - INF) / m + 10);
auto calc = [&](i128 pos) -> i128 { return (i128)(pos - a) / m + 1; };
Write(calc(r) - calc(l - 1), '\n');
return;
}
首先可以发现，如果匹配方案在值域上交叉一定不优，因为可以调整使得不交叉且不劣。
所以对于 \(2n - k\) 是偶数的时候，可以相邻的两两匹配。
对于 \(2n - k\) 是奇数的时候，就是空出来一个不匹配，这个可以先求出最后一个不匹配时的代价，然后调整出每一个不匹配时的代价，最后取 \(\min\) 即可。
constexpr int MAXN = 2e5 + 9;
int n, k, a[MAXN];
vector<int> num;
void slv() {
n = Read<int>(), k = Read<int>();
for (int i = 1; i <= k; i ++) a[Read<int>()] --;
for (int i = 1; i <= n; i ++) {
num.emplace_back(i);
if (!a[i]) num.emplace_back(i);
}
int ans = 0;
for (int i = 1; i < num.size(); i += 2)
ans += num[i] - num[i - 1];
if (k & 1) {
int ret = ans;
for (int i = (int)num.size() - 2; i >= 0; i --) {
if (i & 1) ret += num[i + 1] - num[i];
else ret -= num[i + 1] - num[i];
cmin(ans, ret);
}
}
Write(ans, '\n');
return;
}
基础二分题。先排个序，然后在前缀和上二分就行。
constexpr int MAXN = 2e5 + 9;
int n, q;
ll sum[MAXN];
void slv() {
n = Read<int>(), q = Read<int>();
for (int i = 1; i <= n; i ++) sum[i] = Read<ll>();
sort(sum + 1, sum + n + 1);
for (int i = 1; i <= n; i ++) sum[i] += sum[i - 1];
while (q --) {
ll x = Read<ll>();
int l = 0, r = n;
while (l < r) {
int mid = l + r + 1 >> 1;
if (sum[mid] <= x) l = mid;
else r = mid - 1;
}
Write(l, '\n');
}
return;
}
先 dfs 一遍求出每个绿点所属的连通块，然后枚举每个红点，将他染绿后只会影响到相邻 4 个点的连通性，求出将他染绿后的连通块个数，然后求平均值就行。
constexpr int MAXN = 1e3 + 9;
constexpr int dx[] = {0, 0, 1, -1},
dy[] = {1, -1, 0, 0};
int n, m, a[MAXN][MAXN], cnt = 0, bel[MAXN][MAXN],
tot = 0, ans = 0;
char s[MAXN];
bool vis[MAXN][MAXN];
void slv() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i ++) {
scanf("%s", s + 1);
for (int j = 1; j <= m; j ++)
a[i][j] = (s[j] == '.');
}
function<void(int, int)> dfs = [&](int x, int y) {
vis[x][y] = true, bel[x][y] = tot;
for (int o = 0; o < 4; o ++) {
int nx = x + dx[o], ny = y + dy[o];
if (nx < 1 || nx > n || ny < 1
|| ny > m || a[nx][ny] || vis[nx][ny]) continue;
dfs(nx, ny);
}
return;
};
for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++)
if (a[i][j]) cnt ++;
else if (!vis[i][j]) tot ++, dfs(i, j);
auto qpow = [&](int a, int b) {
int ans = 1;
for (; b; b >>= 1, cmul(a, a))
if (b & 1) cmul(ans, a);
return ans;
};
int inv = qpow(cnt, MOD - 2);
vector<int> id;
for (int x = 1; x <= n; x ++) for (int y = 1; y <= m; y ++)
if (a[x][y]) {
id.clear();
for (int o = 0; o < 4; o ++) {
int nx = x + dx[o], ny = y + dy[o];
if (nx < 1 || nx > n || ny < 1
|| ny > m || a[nx][ny]) continue;
id.emplace_back(bel[nx][ny]);
}
sort(id.begin(), id.end());
id.erase(unique(id.begin(), id.end()), id.end());
cadd(ans, mul(inv, tot - id.size() + 1));
}
Write(ans, '\n');
return;
}
设 \(f_i\) 表示送完前 \(i\) 个人的最短距离，转移为：
\[f_{i} \leftarrow \min_{j \in [i - k - 1, i - 1]} \{f_{j} + \operatorname{Distance}(0, j) + \operatorname{Distance}(0, j + 1) + \sum_{k = j + 1}^{i - 1} \operatorname{Distance}(k, k + 1)\}
\]
这很明显可以单调队列优化，后面的求和可以前缀和优化。
时间复杂度 \(O(n)\)。
constexpr int MAXN = 2e5 + 9;
int n, k, x[MAXN], y[MAXN],
q[MAXN], head = 1, tail = 0;
ldb sum[MAXN], f[MAXN];
void slv() {
n = Read<int>(), k = Read<int>();
for (int i = 0; i <= n; i ++)
x[i] = Read<int>(), y[i] = Read<int>();
x[n + 1] = x[0], y[n + 1] = y[0];
auto sqr = [&](int x) -> ll { return 1ll * x * x; };
auto Get_Dis = [&](int i, int j) -> ldb {
return sqrt(sqr(x[i] - x[j]) + sqr(y[i]- y[j]));
};
for (int i = 1; i <= n; i ++)
sum[i] = Get_Dis(i, i - 1) + sum[i - 1];
q[++ tail] = 0, f[0] = - sum[1] + Get_Dis(1, 0);
for (int i = 1; i <= n; i ++) {
while (head <= tail && q[head] < i - k) head ++;
int j = q[head];
f[i] = f[j] + sum[i] - sum[i + 1] + Get_Dis(i, 0) + Get_Dis(i + 1, 0);
while (head <= tail && f[q[tail]] >= f[i]) tail --;
q[++ tail] = i;
}
printf("%.12Lf\n", f[n]);
return;
}
说说我的做法吧，可能比较唐。
受 E 的启发，我们会做染绿的情况，不会做染红，所以可以看成一张全是红格子的图，要把其中的几个格子染成绿色，求分别不染每一个绿格子的方案数。
这个是可以用分治来做，就是对于一次分治 \([l, r]\)，分治中心是 \(mid\)，先把 \([l, mid]\) 的染色都染上，然后递归 \([mid + 1, r]\)，再撤销染色；然后把 \([mid + 1, r]\) 都染上，然后递归 \([l, mid]\)，再撤销染色。这样当递归到 \(l = r\) 时，就是不染这个格子时连通块的个数。
时间复杂度 \(O(n \log^2 n)\)。太唐了。
constexpr int MAXN = 1e3 + 9;
constexpr int dx[] = {0, 0, 1, -1},
dy[] = {1, -1, 0, 0};
int n, m, a[MAXN][MAXN], tot = 0, ans = 0;
vpii pos;
char s[MAXN];
struct Disjoint {
static constexpr int N = MAXN * MAXN;
int fa[N], sz[N];
vector<int> stk;
void Init(int n) {
stk.clear();
for (int i = 1; i <= n; i ++)
fa[i] = i, sz[i] = 1;
return;
}
int Find(int u) {
return (fa[u] == u) ? u : Find(fa[u]);
}
bool Merge(int u, int v) {
u = Find(u), v = Find(v);
if (u == v) return false;
if (sz[u] > sz[v]) swap(u, v);
fa[u] = v, sz[v] += sz[u];
stk.emplace_back(u); return true;
}
void Reset() {
int u = stk.back(); stk.pop_back();
sz[fa[u]] -= sz[u], fa[u] = u; return;
}
} D;
void slv() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i ++) {
scanf("%s", s + 1);
for (int j = 1; j <= m; j ++) if (s[j] == '#')
pos.emplace_back(i, j), tot ++;
}
auto qpow = [&](int a, int b) {
int ans = 1;
for (; b; b >>= 1, cmul(a, a))
if (b & 1) cmul(ans, a);
return ans;
};
int inv = qpow(tot, MOD - 2), cnt = 0;
D.Init(n * m);
auto get_id = [&](int x, int y) { return (x - 1) * m + y; };
function<void(int, int)> solve = [&](int l, int r) {
if (l == r) {
cadd(ans, mul(cnt, inv));
return;
}
int mid = l + r >> 1, ct = 0, _cnt = cnt;
auto Add = [&](int x, int y) {
a[x][y] = 1, cnt ++;
for (int o = 0; o < 4; o ++) {
int nx = x + dx[o], ny = y + dy[o];
if (nx < 1 || nx > n || ny < 1
|| ny > m || !a[nx][ny]) continue;
if (D.Merge(get_id(x, y), get_id(nx, ny)))
cnt --, ct ++;
}
return;
};
auto Reset = [&]() {
for (int i = l; i <= mid; i ++)
a[pos[i].fir][pos[i].sec] = 0;
while (ct --) D.Reset(); cnt = _cnt, ct = 0;
return;
};
for (int i = l; i <= mid; i ++)
Add(pos[i].fir, pos[i].sec);
solve(mid + 1, r), Reset();
for (int i = mid + 1; i <= r; i ++)
Add(pos[i].fir, pos[i].sec);
solve(l, mid), Reset();
return;
};
solve(0, pos.size() - 1);
Write(ans, '\n');
return;
}