26寒假营第二场 包围圈结论|贡献法|根号分治
比赛安排（PDF题面存放于本题）
https://ac.nowcoder.com/acm/contest/120562/A
A
思维
三种东西，构造一个序列，让连续三个元素都不同。
每次选三个东西接到序列末尾，每次的三个东西的排列都相同，最后一轮可以不满三个。这样则受限于，如果差距过大，一个用完了，另一个还有超过一个，就不行。
void solve() {
vi a(3);
for (int &x : a) {
cin >> x;
}
sort(a.begin(), a.end());
if(a[1]-a[0]>1||a[2]-a[0]>1){
cout<<"NO\n";
}
else{
cout<<"YES\n";
}
}
B
思维 博弈
思维太难。。。个人玩淘汰赛，每次选两个人出来比，较小的被淘汰，相等则两个人都被淘汰。问每个人，是否有可能成为活到最后的一个人。
从每种能力值的角度来考虑，一如果最大值出现了奇数次，即使两两同归于尽，也会剩下一个最大的。这个最大的可以赢下剩下的任何人，所以能赢的只有所有最大值。如果出现了偶数次，最大值是肯定赢不了了，最后剩下的最大值一定是偶数个，必然同归于尽，可以先让最大值淘汰一些竞争对手，然后同归于尽，此时会赢的是剩下的最大值，实际上可以控制淘汰哪些人，来决定剩下的最大值是谁，所以除了最大值的任何值都可以赢.
void solve() {
int n;
cin >> n;
map<int, int>mp;
vi a(n + 1);
int mx = 0;
rep(i, 1, n) {
cin >> a[i];
mp[a[i]]++;
mx = max(mx, a[i]);
}
if (mp[mx] % 2) {
rep(i, 1, n) {
cout << (a[i] == mx);
}
} else {
rep(i, 1, n) {
cout << (a[i] != mx);
}
}
cout << '\n';
}
C
并查集 包围圈结论
给一些点，形成一些包围圈，问一个点是否处于某个包围圈内？
这里可以用走迷宫的一个经典思想：左手扶墙，如果一个迷宫是可以走出去的，就是没有形成封闭圈，有出口，那么我们左手扶着墙，一直走总可以走出去。应用在这里，是否位于包围圈内，显然就等价于身处一个迷宫中，问能不能走出去，那么可以先往上下左右，走到靠墙的位置，然后检查靠墙走，能不能走出去。
如果一个点的上下左右存在一个方向能走到无穷远，我们用一个特殊点表示无穷远，把这个点和无穷远连上，用并查集维护连通性。然后我们把靠墙的所有点，都和上下左右遇到的第一个点合并，这样如果一个靠墙点，能靠墙走，走出迷宫，走到无穷远，那他就和无穷远在同一个连通块内。
查询时，让查询点找上下左右第一个靠墙点，如果有任何一个方向没有靠墙点，也就是能直接走到无穷远，肯定能走出。否则检查四个靠墙点，是否存在一个，和无穷远在一个连通块内，如果存在也能走出去
查询上下左右方向的第一个靠墙点，可以存所有墙点，然后
二分。
int fx[] = {1, -1, 0, 0, 1, 1, -1, -1};
int fy[] = {0, 0, 1, -1, 1, -1, -1, 1};
int f[N];
set<int>sx[N], sy[N];
pii o = {-1, -1};
int find(int x) {
if (f[x] == x)return x;
return f[x] = find(f[x]);
}
void merge(int x, int y) {
x = find(x), y = find(y);
if (x != y) {
f[x] = y;
}
}
pii findl(int x, int y) {
auto it = sx[x].lower_bound(y);
if (it == sx[x].begin()) {
return o;
}
it--;
return {x, (*it) + 1};
}
pii findr(int x, int y) {
auto it = sx[x].lower_bound(y);
if (it == sx[x].end()) {
return o;
}
return {x, (*it) - 1};
}
pii findu(int x, int y) {
auto it = sy[y].lower_bound(x);
if (it == sy[y].begin()) {
return o;
}
it--;
return {(*it) + 1, y};
}
pii findd(int x, int y) {
auto it = sy[y].lower_bound(x);
if (it == sy[y].end()) {
return o;
}
return {(*it) - 1, y};
}
void solve() {
int n, q;
cin >> n >> q;
map<pii, int>vis, idx;
vector<pii>p(n);
rep(i, 0, n - 1) {
int x, y;
cin >> x >> y;
p[i] = {x, y};
vis[ {x, y}] = 1;
sx[x].insert(y);
sy[y].insert(x);
}
int cnt = 0;
vector<pii>a;
for (auto [x, y] : p) {
rep(i, 0, 7) {
int xx = x + fx[i], yy = y + fy[i];
if (vis[ {xx, yy}])continue;
idx[ {xx, yy}] = ++cnt;
a.push_back({xx, yy});
}
}
rep(i, 0, cnt) {
f[i] = i;
}
idx[o] = 0;
for (auto [x, y] : a) {
auto [lx, ly] = findl(x, y);
auto [rx, ry] = findr(x, y);
auto [ux, uy] = findu(x, y);
auto [dx, dy] = findd(x, y);
int now = idx[ {x, y}];
merge(now, idx[ {lx, ly}]);
merge(now, idx[ {rx, ry}]);
merge(now, idx[ {ux, uy}]);
merge(now, idx[ {dx, dy}]);
}
while (q--) {
int x, y;
cin >> x >> y;
auto [lx, ly] = findl(x, y);
auto [rx, ry] = findr(x, y);
auto [ux, uy] = findu(x, y);
auto [dx, dy] = findd(x, y);
bool flag = 0;
if (find(idx[ {lx, ly}]) == find(idx[o])) {
flag = 1;
}
if (find(idx[ {rx, ry}]) == find(idx[o])) {
flag = 1;
}
if (find(idx[ {ux, uy}]) == find(idx[o])) {
flag = 1;
}
if (find(idx[ {dx, dy}]) == find(idx[o])) {
flag = 1;
}
if (!flag) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
}
E
构造
构造一个的01矩阵，满足行，列的元素和序列，都是0到n-1的排列。并且相同元素组成的连通块个数为
。
手玩可以发现，构造一个上三角或者下三角就可以满足行列元素和的要求，难点在于连通块。我们把下三角，每次平移一行或者一列，并不会破坏行列元素和的约束，于是平移试试，手玩发现了一个模式：我们让最大的两行两列呈现一个这样的模式：倒数第二行和倒数第二列都是0，其余是1。。
??01
??01
0000
1101
这样增加了三个1连通块，并且给左上方的子矩阵每一行，每一列都提供了一个
，相当于归约到一个问题规模更小的子问题。考虑按这个模式递归下去，每次都能增加三个连通块，直到某一个，剩余需要的连通块不足三个了，考虑在下三角的基础上略微修改，如果差一个连通块，则直接下三角
0000
0001
0011
0111
如果还差两个，则把下三角边上的一个往外挪
0001
0000
0011
0111
如果差三个，就把下三角边上的两个都往外挪
0001
0000
0011
1011
这个构造方式实际上比题目要求还要强，不一定是个连通块，可以构造
范围内的任意个连通块。
void solve() {
int n;
cin >> n;
if(n==1){
cout<<0;
return;
}
int cnt = 1;
vvi a(n + 1, vi(n + 1));
for (int i = n; i >= 1; i -= 2) {
if (cnt + 3 == n) {
int cur = 0;
for (int j = 2; j <= i; j++) {
++cur;
for (int k = i; k >= i - cur + 1; k-- ) {
a[j][k] = 1;
}
}
a[i][1] = a[1][i] = 1;
a[i][2] = a[2][i] = 0;
break;
} else if (cnt + 2 == n) {
int cur = 0;
for (int j = 2; j <= i; j++) {
++cur;
for (int k = i; k >= i - cur + 1; k-- ) {
a[j][k] = 1;
}
}
a[i][1] = 1;
a[i][2] = 0;
break;
} else if (cnt + 1 == n) {
int cur = 0;
for (int j = 2; j <= i; j++) {
++cur;
for (int k = i; k >= i - cur + 1; k-- ) {
a[j][k] = 1;
}
}
break;
} else {
cnt += 3;
for (int j = 1; j <= i; j++) {
a[i][j] = a[j][i] = 1;
}
a[i][i - 1] = a[i - 1][i] = 0;
}
}
rep(i, 1, n) {
rep(j, 1, n) {
cout << a[i][j];
}
cout << '\n';
}
}
题目这个条件其实有更简单的构造方式，这样就可以
F
数论 构造 位运算
对于一个,找到
，满足
最小。
看起来像是数学结论题，先打表，发现异或最小值就是，并且存在一种解是
，根据裴蜀定理，这显然满足
，接下来问题是如何找到一个
，使得
注意这个奇特的取值范围，意味着我们可以令，这样左移的部分和
没有位上的重叠，异或起来就是
。
void solve() {
uint64_t n;
cin >> n;
uint64_t x = n << 32;
uint64_t y = x + n;
cout << x << ' ' << y << '\n';
assert(gcd(x, y) == n && (x ^ y) == n);
}
H
贡献法 子数组计数
这个权值的计算方法，就是计算元素种类数的前缀和。但这是子数组计数，情况太多，考虑贡献法，计算每个有多少贡献。从这个角度来讲的话，
如果在某个子数组里是第一次出现，假设后面还有
个元素，则会产生
的贡献，因为在这里第一次出现，使得从这里开始，后面的元素种类数都增加了
。
那么我们可以枚举元素，假设他是子数组第一次出现，求这样的子数组个数，也就是求子数组左右端点的方案数。左端点，为了让是子数组内第一次出现，我们可以维护每一个值的前一次出现
，那么左端点的范围就是
，右端点可以随便取
，但是不同的右端点，贡献的系数不一样，对于一个
，贡献是
，因此右端点这边的方案数还需要乘上系数，也就是求
，这是等差数列求和，可以
求
int cal(int x) {
return (1 + x) * x / 2;
}
void solve() {
int n;
cin >> n;
vi a(n + 1);
rep(i, 1, n) {
cin >> a[i];
}
map<int, int>pre;
int ans = 0;
rep(i, 1, n) {
int l = i - pre[a[i]];
pre[a[i]] = i;
int r = cal(n - i + 1);
ans += l * r;
}
cout << ans << '\n';
}
如果改成子序列，会难一点，也可以做。仍然考虑贡献法，左边的元素不能选，其他元素任选，维护前缀
个数，剩余
个元素每个都可以选或不选，也就是
。右边元素每个也可以选或不选，也有系数的问题，就是要求
。这玩意暴力算是
的，不能对每个
都暴力算，应该也有组合数学上的线性递推方法
I
诈骗 思维 回文串
一个01矩阵，问从每个点出发，是否都存在一个终点和起点不同，走过的格子组成回文串的路径。
手玩可以发现，如果起点终点都是，途经的都是
，不论路径长度奇数偶数，一定是回文的，而这只要求图中至少有两个
。对于起点
，同理。
所以只需检查是否至少有个
。
void solve() {
int n, m;
cin >> n >> m;
vvi a(n + 1, vi(m + 1));
int c0 = 0, c1 = 0;
rep(i, 1, n) {
rep(j, 1, m) {
char c;
cin >> c;
if (c == '1') {
a[i][j] = 1;
c1++;
} else {
c0++;
}
}
}
rep(i, 1, n) {
rep(j, 1, m) {
if (a[i][j]) {
if (c1 == 1) {
cout << "N";
} else {
cout << "Y";
}
} else {
if (c0 == 1) {
cout << "N";
} else {
cout << "Y";
}
}
}
cout << '\n';
}
}
J
根号分治 多源bfs
每个点的点权是这个点的度数，对每个点，问走到点权更大的点的最短路径长度？
看起来可以多源，对于点权相同的一组点，可以把点权更大的点作为源点，bfs计算到这组点的最短距离。这样每一轮
最坏都是
的，如果有
组，不就炸了？
但是让我们来注意这个奇怪的点权定义，假设点权为的点数
，那么有
，这是经典根号分治等式，这除了意味着对于每个
，都有
，还意味着
的
只有
个。考虑每个
都有一个，那么整个图的度数就是
的了，但是度数只能有
。
所以我们前面那个的
只会执行
轮，就是对的。
void solve() {
int n, m;
cin >> n >> m;
vvi g(n + 1);
vi d(n + 1), a;
rep(i, 1, m) {
int u, v;
cin >> u >> v;
d[u]++;
d[v]++;
g[u].push_back(v);
g[v].push_back(u);
}
rep(i, 1, n) {
a.push_back(d[i]);
}
sort(a.begin() + 1, a.end());
a.erase(unique(a.begin() + 1, a.end()), a.end());
int tot = a.size();
rep(i, 1, n) {
d[i] = lower_bound(a.begin(), a.end(), d[i]) - a.begin() + 1;
}
vvi bin(tot + 1);
rep(i, 1, n) {
bin[d[i]].push_back(i);
}
vi ans(n + 1, -1);
rep1(i, tot, 1) {
vi dis(n + 1, inf);
queue<int>q;
rep(j, i + 1, tot) {
for (int x : bin[j]) {
q.push(x);
dis[x] = 0;
}
}
while (q.size()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (dis[v] > dis[u] + 1) {
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
for (int x : bin[i]) {
ans[x] = dis[x];
}
}
rep(i, 1, n) {
cout << (ans[i] < inf ? ans[i] : -1) << ' ';
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int test = 1;
// cin >> test;
while (test--) {
solve();
}
}
字节跳动公司福利 1371人发布