C. Socks 2
-
若 \(2\times n-k\) 为偶数，那么直接从小到大一对一对选即可。
-
若 \(2\times n-k\) 为奇数，则必定剩下一只。考虑不好知道到底剩下哪一只，那么直接暴力枚举剩第 \(i\) 只，则 \(1\sim i-1\) 和 \(i+1\sim n\) 的袜子搭配起来，可以用前缀和后缀和预处理。
E. Christmas Color Grid 1
对于每一个格子，考虑 . 变成 # 会增加什么贡献，其实就会使周围本来 互相不连通的连通块 变得连通。
然后就看周围四个格子的变化量，不太好说，看代码吧。
注：期望只是虚晃一枪，骗人的。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 4e6 + 5, M = 1005, mod = 998244353;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
int n, m;
char a[M][M];
int p[N], p2[N];
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) p[fx] = fy;
}
int find2(int x) {
if (p2[x] != x) p2[x] = find2(p2[x]);
return p2[x];
}
void merge2(int x, int y) {
int fx = find2(x), fy = find2(y);
if (fx != fy) p2[fx] = fy;
}
int get(int x, int y) {
return (x - 1) * m + y;
}
int qpow(int a, int k, int p ){
int res = 1;
while(k) {
if (k & 1) res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res;
}
map<pair<int, int>, int> vis;
map<int, int> vs, vs2;
int res, ss;
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) cin >> a[i][j];
}
for (int i = 0; i <= N - 5; i++) p[i] = i;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 0; k < 4; k++) {
int dx = i + dir[k][0], dy = j + dir[k][1];
if (dx < 1 || dx > n || dy < 1 || dy > m) continue;
if (a[dx][dy] == a[i][j] && a[i][j] == '#') merge(get(dx, dy), get(i, j));
}
}
}
int qq = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int t = get(i, j);
if (a[i][j]=='#'&&find(t) == t) qq++; .// 算出原来连通块数量
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] == '#') continue;
vis.clear();
vs.clear();
vs2.clear();
ss++;
int idx = 0, vvv = 0;
vs[get(i,j)] = ++idx;
for (int k = 0; k < 4; k++) {
int dx = i + dir[k][0], dy = j + dir[k][1];
if (dx < 1 || dx > n || dy < 1 || dy > m) continue;
if (a[dx][dy] == '#') vs[get(dx, dy)] = ++idx;
if (a[dx][dy] == '#' && !vs2[find(get(dx, dy))]) vvv++, vs2[find(get(dx, dy))] = 1;
} // vs是给"自己和周围4个格子"编号，vvv统计原来周围4个格子的连通块数量
for (int k= 1; k <= idx; k++) p2[k] = k;
for (int k = 0; k < 4; k++) {
int dx = i + dir[k][0], dy = j + dir[k][1];
if (dx < 1 || dx > n || dy < 1 || dy > m) continue;
if (x < 1 || x > n || y < 1 || y > m) continue;
if (a[dx][dy] == '#') {
merge2(vs[get(i, j)], vs[get(dx, dy)]);
}
}
int now = 0;
for (int k = 1; k <= idx; k++) {
if (find2(k) == k) now++; // 统计 .变#之后的周围4个格子的连通块数量
}
res += qq - (vvv - now) ; // vvv-now就是局部变化量
res%=mod; // 这里可能要取模
}
}
cout << res * qpow(ss, mod - 2, mod) % mod<<endl;
}
F. Christmas Present 2
典中典。\(dp_i\) 表示前 \(i\) 个走完的最小花费。
枚举 \(j\)，\(dp_i=\min\{dp_j+d(j+1)+d(i)+sum(j+1\to i)\}(i-j\leq k)\)
\(d(i)\) 表示从家走到第 \(i\) 个点的距离，\(sum(i\to j)\) 表示路程上的距离。
单调队列模板题。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5 + 5;
int n, c, q[N];
double dp[N], sx, sy, s[N], sum[N], d[N];
struct edge {
double x, y;
}ed[N];
double dist(double a, double b, double c, double d) {
return sqrt((a - c) * (a - c) + (b - d) * (b - d));
}
signed main() {
cin >> n >> c >> sx >> sy;
for (int i = 1; i <= n; i++) cin >> ed[i].x >> ed[i].y;
for (int i = 1; i <= n; i++) dp[i] = 2e18;
dp[0] = 0;
ed[0].x = sx, ed[0].y = sy;
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + dist(ed[i - 1].x, ed[i - 1].y, ed[i].x, ed[i].y);
d[i] = dist(sx, sy, ed[i].x, ed[i].y);
}
int hd = 1, tl = 1;
q[1] = 0;
for (int i = 1; i <= n; i++) {
while (hd <= tl && i - q[hd] > c) hd++;
if (hd <= tl) dp[i] = dp[q[hd]] + d[i] + d[q[hd] + 1] + sum[i] - sum[q[hd] + 1];
while (hd <= tl && dp[q[tl]] + d[q[tl] + 1] - sum[q[tl] + 1] > dp[i] + d[i + 1] - sum[i + 1]) tl--;
q[++tl] = i;
}
printf("%.10lf", dp[n]);
}
G. Christmas Color Grid 2
把一个 # 变成 . 有啥变化？
不太好考虑，考虑对原数组建图（相邻的 # 连边）。
一个 # 变成 . 等价于删掉这个点和与它相连的所有边。等价于割点。
若一个割点被 \(x\) 个点双分量所包含，那么删掉他就会增加 \(x-1\) 个连通分量。
注意特判孤立点的情况。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 4e6 + 5, M = 1005, mod = 998244353;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
vector<int> G[N];
int n, m, low[N], dfn[N], cut[N], idx, sv[N];
stack<int> stk;
char a[M][M];
int p[N], cc[N];
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) p[fx] = fy;
}
int get(int x, int y) {
return (x - 1) * m + y;
}
int qpow(int a, int k, int p ){
int res = 1;
while(k) {
if (k & 1) res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res;
}
void tarjan(int root, int u) {
sv[u] = root;
dfn[u] = low[u] = ++idx;
stk.push(u);
if (u == root && G[u].size() == 0) {
cc[u]++;
return;
}
int cnt = 0;
for (auto v : G[u]) {
if (!dfn[v]) {
tarjan(root, v);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
cnt++;
if (u != root || cnt > 1) cut[u] = 1;
int y;
do {
y = stk.top(); stk.pop();
cc[y]++;
} while (v != y);
cc[u]++;
}
}
else low[u] = min(low[u], dfn[v]);
}
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) cin >> a[i][j];
}
for (int i = 0; i <= N - 5; i++) p[i] = i;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 0; k < 4; k++) {
int dx = i + dir[k][0], dy = j + dir[k][1];
if (dx < 1 || dx > n || dy < 1 || dy > m) continue;
if (a[dx][dy] == a[i][j] && a[i][j] == '#') G[get(dx, dy)].push_back(get(i, j)), G[get(i, j)].push_back(get(dx, dy));
}
}
}
int qq = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!dfn[get(i, j)] && a[i][j] == '#') tarjan(get(i, j), get(i, j)), qq++;
}
}
int cnt = 0, ss = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] == '#') {
ss++;
if (cut[get(i, j)]) cnt += qq + cc[get(i, j)] - 1;
else {
if (G[get(i, j)].size() == 0 && sv[get(i,j)] == get(i, j)) cnt += qq - 1;
else cnt += qq;
}
cnt %= mod;
}
}
}
cout << cnt * qpow(ss, mod - 2, mod) % mod << endl;
}
- Beginner AtCoder Contest 334beginner atcoder contest 334 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 310 beginner atcoder contest 327 beginner atcoder contest 332