合肥网站策划深圳市交易服务中心
目录
C. Socks 2
D. Reindeer and Sleigh
E. Christmas Color Grid 1
C. Socks 2
首先先对 k 进行分类：
（1） k 为偶数，直接从头开始两两配对
（2）k 为奇数，此时一定会有一只袜子无法配对。当没有思路的时候，就去想把什么作为枚举量，显然这里枚举哪一只袜子丢弃不配对。容易证明丢弃的袜子一定是奇数位。此时的问题就类似于讲一个数组从某一点切成两端，典型的需要同时维护前后缀。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, INF = 1e18;int T, n, k, cnt, ans, a[N], f[N], g[N];signed main()
{cin >> n >> k;for (int i = 1; i <= k; i ++)cin >> a[i];sort(a + 1, a + k + 1);if (k % 2 == 0){for (int i = 2; i <= k; i += 2)ans += a[i] - a[i - 1];}else{ans = INF;for (int i = 2; i <= k; i += 2)f[i] = f[i - 2] + a[i] - a[i - 1];for (int i = k - 1; i >= 1; i -= 2)g[i] = g[i + 2] + a[i + 1] - a[i];for (int i = 1; i <= k; i += 2)ans = min(ans, f[i - 1] + g[i + 1]);}cout << ans;return 0;
}
D. Reindeer and Sleigh
首先明确，最后是要查询 n 匹鹿能拉多少雪橇，那么用来查询的答案数组的下标就一定是鹿的匹数，这样就能实现 O(1) 的查询。看到鹿匹数数据量达 1e9，可以想到肯定不可能把答案数组填满，但是可以通过 upper 查询来实现。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, INF = 1e18;int T, n, q, cnt, ans, a[N], d[N];signed main()
{cin >> n >> q;for (int i = 1; i <= n; i ++)cin >> a[i];sort(a + 1, a + n + 1);for (int i = 1; i <= n; i ++)d[i] = d[i - 1] + a[i];while (q --){int x;cin >> x;if (x > d[n])ans = n;else{int pos = upper_bound(d + 1, d + n + 1, x) - d;ans = pos - 1;}cout << ans << '\n';}return 0;
}
E. Christmas Color Grid 1
看到判连通块数量，而且后续存在连通块合并的操作，用并查集。
对于每一红色的点，如果将它染成绿色会导致与它相邻的绿色连通块合并，那么连通块数量是减少的。
如何在二维地图上用并查集呢？方法是把二维坐标转换成一维数组
行优先
n 行 m 列的地图，行列下标都从 1 开始
(x, y) --> (x - 1) * m + y下标从 0 开始
(x, y) --> x * m + y - 1
在枚举红色的点的时候，将其四周的绿色的点所在集合的代表存入 set 即可去重，set.size()就是红点直接相邻的绿色集合数。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3 + 5, INF = 1e18, mod = 998244353;struct node
{int x, y;
};int T, n, m, cnt, tot, cnth, ans, fa[N * N];
char c[N][N];
set<int> se;int fpow(int a, int b)
{int res = 1;while (b){if (b & 1)res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}int find(int x)
{if (x == fa[x])return x;return fa[x] = find(fa[x]);
}void join(int x, int y)
{x = find(x), y = find(y);if (x != y)fa[x] = y;
}int get(int x, int y)
{return (x - 1) * m + y;
}signed main()
{cin >> n >> m;int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++)cin >> c[i][j];for (int i = 1; i <= n * m; i ++)fa[i] = i;for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++)if (c[i][j] == '#')for (int k = 0; k < 4; k ++){int tx = i + dx[k], ty = j + dy[k];if (tx < 1 || tx > n || ty < 1 || ty > m || c[tx][ty] == '.')continue;join(get(i, j), get(tx ,ty));}for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++)if (c[i][j] == '#')se.insert(find(get(i, j)));cnt = se.size();for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++)if (c[i][j] == '.'){cnth ++;set<int> se2;for (int k = 0; k < 4; k ++){int tx = i + dx[k], ty = j + dy[k];if (tx < 1 || tx > n || ty < 1 || ty > m || c[tx][ty] == '.')continue;se2.insert(find(get(tx, ty)));}if (se2.size() == 0)tot += cnt + 1;elsetot += cnt - (se2.size() - 1);}ans = tot % mod * fpow(cnth, mod - 2) % mod;cout << ans;return 0;
}