XCPC wiki - 搜索、枚举

DFS

2024-08-11：2024 PTA 环境测试 D

constexpr int dx[] = { 1, 0, 0, -1 };
constexpr int dy[] = { 0, -1, 1, 0 };

int n, m, k;
pair<int, int> a[N];

bool check(int black) {
    vector<vector<int>> mp(n + 2, vector<int>(m + 2, 0));
    vector<vector<int>> vis(n + 2, vector<int>(m + 2, 0));
    for (int i = 0; i < black; ++i) {
        mp[a[i].first][a[i].second] = 1;
    }

    int white = 0;
    auto dfs = [&] (auto self, int x, int y) {
        if (x < 0 || x > n + 1 || y < 0 || y > m + 1 || vis[x][y]) {
            return;
        }
        if (mp[x][y] == 1) {  // 黑格
            vis[x][y] = 1;
            return;
        }
  
        // 白
        if (x >= 1 && x <= n && y >= 1 && y <= m) {
            white += 1;
        }
        vis[x][y] = 1;
  
        for (int i = 0; i < 4; ++i) {
            self(self, x + dx[i], y + dy[i]);
        }
    };
    dfs(dfs, 0, 0);
  
    if (black + white == m * n) return false;
    else return true;
}
  
void eachT() {
    n = read(), m = read(), k = read();
  
    for (int i = 0; i < k; ++i) {
        a[i].first = read(), a[i].second = read();
    }
  
    int l = 1, r = k;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid - 1;
        else l = mid + 1;
    }
  
    string res(r, '1');
    string res2(k - r, '0');
    cout << res << res2 << '\n';
}

2024 牛客多校 1I - Mirror Maze

[[…/contests/2024牛客多校/2024-07-16：2024牛客暑期多校训练营1#*I - Mirror Maze|2024-07-16：2024牛客暑期多校训练营1]]

有一个$n \times m$ 的镜子迷宫，每个网格上都有一面镜子，镜子有“-” “|” “/” “" 四种类型。

• “-”，来自上方或下方的光将被反射回来，来自左边或右边的光将分别继续向前移动而不会被反射;
• “|”，左边或右边的光会被反射回来，上面或下面的光会继续向前走，分别不被反射;
• “/”，来自左、右、上、下的光将分别反射到上方、下方、左侧、右侧;
• “\”，来自左、右、上、下的光将分别反射到下方、上方、右侧、左侧。

现在有$q$ 个光源。小G 是光的信徒，他想知道每个光源在足够的时间内，发射的光将被反射的不同镜子的数量。

Input	Output
2 3 /- /| 2 1 2 below 2 2 right	4 2

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
using namespace std;
using ll = long long;
const int N = 1e3 + 8;
char mp[N][N];
const int dx[] = { -1, 1, 0, 0 };
const int dy[] = { 0, 0, -1, 1 }; // 上下左右
int vis[N][N][5];
int visnow[N][N];
int ans[N][N][5];
int q; 

// '/' : ^= 3 (0->3,3->0,1->2,2->1)
// '\\' : ^= 2 (0->2,2->0,1->3,3->1)
// '-' : <=1 ^= 1 (0->1,1->0)
// '|' : >1 ^=1 (3->2,2->3)
//高超的异或使用例

void dfsh(int x, int y, int d, int step) {
    if (vis[x][y][d] >= 2) return;
    ans[x][y][d] = step;
    int nd;
    if (mp[x][y] == '/') {
        nd = d ^ 3;
    }
    else if (mp[x][y] == '\\') {
        nd = d ^ 2;
    }
    else if (mp[x][y] == '-') {
        if (d <= 1) nd = d ^ 1;
        else nd = d;
    }
    else if (mp[x][y] == '|') {
        if (d > 1) nd = d ^ 1;
        else nd = d;
    }
    vis[x][y][d]++;
    dfsh(x + dx[nd], y + dy[nd], nd, step);
}

int dfs(int stx, int sty, int std, int x, int y, int d, int step = 0) {
    if (mp[x][y] == '*') {
        return step;
    }
    if (ans[x][y][d] && step == 0) {
        return step + ans[x][y][d];
    }    
    if (x == stx && y == sty && std == d && step != 0) { // 进环
        return step;
    }

    int nd;
    if (mp[x][y] == '/') {
        nd = d ^ 3;
        if (visnow[x][y] != q) visnow[x][y] = q, step++;
    }
    else if (mp[x][y] == '\\') {
        nd = d ^ 2;
        if (visnow[x][y] != q) visnow[x][y] = q, step++;
    }
    else if (mp[x][y] == '-') {
        if (d <= 1) {
            nd = d ^ 1;
            if (visnow[x][y] != q) visnow[x][y] = q, step++;
        }
        else {
            nd = d;
        }
    }
    else if (mp[x][y] == '|') {
        if (d > 1) {
            nd = d ^ 1;
            if (visnow[x][y] != q) visnow[x][y] = q, step++;
        }
        else {
            nd = d;
        }
    }
    return dfs(stx, sty, std, x + dx[nd], y + dy[nd], nd, step);
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mp[i][j];
        }
    }
    for (int i = 0; i <= m + 1; i++) mp[0][i] = mp[n + 1][i] = '*';
    for (int i = 0; i <= n + 1; i++) mp[i][0] = mp[i][m + 1] = '*';
    cin >> q;
    while (q) {
        int x, y;
        string d;
        cin >> x >> y >> d;
        if (d == "above") {
            x--;
            ans[x][y][0] = dfs(x, y, 0, x, y, 0);
            cout << ans[x][y][0] << endl;
        }
        else if (d == "below") {
            x++;
            ans[x][y][1] = dfs(x, y, 1, x, y, 1);
            cout << ans[x][y][1] << endl;
        }
        else if (d == "left") {
            y--;
            ans[x][y][2] = dfs(x, y, 2, x, y, 2);
            cout << ans[x][y][2] << endl;
        }
        else {
            y++;
            ans[x][y][3] = dfs(x, y, 3, x, y, 3);
            cout << ans[x][y][3] << endl;
        }
        q--;
    }
    return 0;
}

2024 CCPC 网络赛热身赛 A. 数洞

[[…/contests/2024-09-07-2024 CCPC 网络赛热身赛|2024-09-07-2024 CCPC 网络赛热身赛]]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
const ll INF = 0x3f3f3f3f;

inline ll read() {
	ll x = 0, f = 0; char c = getchar();
	while (c > 57 || c < 48) f |= c == 45, c = getchar();
	while (c <= 57 && c >= 48) x = (x << 3) + (x << 1) + c - 48, c = getchar();
	return f ? -x : x;
}

char a[1010][1010];
int vis[1010][1010];
int n, m;
int xx[10] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int yy[10] = { 0, 0, 1, -1, 1, -1, -1, 1 };
vector<pair<int, int>>v;

void dfs0(int x, int y) {
	for (int i = 0; i < 8; i++) {
		int newx = x + xx[i];
		int newy = y + yy[i];
		if (0 <= newx && newx <= n + 1 && 0 <= newy && newy <= m + 1 && vis[newx][newy] == 0) {
			if (a[newx][newy] == '.') {
				vis[newx][newy] = -1;
				dfs0(newx, newy);
			}
		}
	}
}

void dfs(int cnt, int x, int y) {
	for (int i = 0; i < 4; i++) {
		int newx = x + xx[i];
		int newy = y + yy[i];
		if (0 <= newx && newx <= n + 1 && 0 <= newy && newy <= m + 1 && vis[newx][newy] != cnt && vis[newx][newy] != -1) {
			vis[newx][newy] = cnt;
			v.push_back({ newx, newy });
			if (a[newx][newy] == '#') {
				dfs(cnt, newx, newy);
			}
		}
	}
}

void dfs2(int cnt, int x, int y) {
	for (int i = 0; i < 4; i++) {
		int newx = x + xx[i];
		int newy = y + yy[i];
		if (0 <= newx && newx <= n + 1 && 0 <= newy && newy <= m + 1 && vis[newx][newy] == cnt) {
			vis[newx][newy] = INF;
			if (a[newx][newy] == '.') {
				dfs2(cnt, newx, newy);
			}
		}
	}
}

void eachT() {
	n = read(), m = read();
	int ans1 = 0, ans8 = 0, ans0 = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 0; i <= n + 1; i++) {
		a[i][0] = a[i][m + 1] = '.';
	}
	for (int j = 0; j <= m + 1; j++) {
		a[0][j] = a[n + 1][j] = '.';
	}
	dfs0(0, 0);

	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			if (!vis[i][j] && a[i][j] == '#') {
				v.clear();
				dfs(i * n + j, i, j);
				int num = 0;
				for (auto [x, y] : v) {
					if (a[x][y] == '.' && vis[x][y] != INF) {
						// cerr << x <<" "<< y << "\n";
						dfs2(vis[x][y], x, y);
						num++;
					}
				}
				// cerr << num << '\n';
				if (num == 0) ans1++;
				else if (num == 1) ans0++;
				else if (num == 2) ans8++;
			}
		}
	}
	// for (int i = 0; i <= n + 1; i++)
	// {
	//     for (int j = 0; j <= m + 1; j++)
	//     {
	//         cerr << vis[i][j] << " ";
	//     }
	//     cerr << "\n";
	// }

	cout << ans1 << " " << ans0 << " " << ans8 << endl;
}

signed main() {
	int T = 1;
	while (T--) {
		eachT();
	}
	return 0;
}

枚举子集

2024 杭电多校 4001 - 超维攻坚

[[…/contests/2024杭电多校/2024-07-29：2024“钉耙编程”中国大学生算法设计超级联赛（4）|2024-07-29：2024“钉耙编程”中国大学生算法设计超级联赛（4）]]
[[…/计算几何/三维计算几何#2024 杭电多校 4001 - 超维攻坚|三维计算几何]]

求满足如下条件的点集$S$ 的数量：

• $S$ 的凸包表面与内部的所有点都在$S$ 中。

数据范围：$n \leqslant 15$。

2024 杭电多校 4004 - 分组

[[…/contests/2024杭电多校/2024-07-29：2024“钉耙编程”中国大学生算法设计超级联赛（4）|2024-07-29：2024“钉耙编程”中国大学生算法设计超级联赛（4）]]

Description

给定$n$ 个正整数$a_1,a_2,\dots,a_n$ ($1 \leqslant a_i<2^m$) 以及$0$ 到$2^m-1$ 的权重$w_0,w_1,\dots,w_{2^m-1}$；你需要把这$n$ 个正整数分成四组$A,B,C,D$，令$f ( A ) , f ( B ) , f ( C ) , f ( D )$ 分别表示每组中所有数字的异或和，你的分组方案需要最小化$w_{f(A)},w_{f(B)},w_{f(C)},w_{f(D)}$ 的极差，即最小化

$$\max\left(w_{f(A)},w_{f(B)},w_{f(C)},w_{f(D)}\right)-\min\left(w_{f(A)},w_{f(B)},w_{f(C)},w_{f(D)}\right)$$

注意：每组都可以为空，此时规定$f ( \cdot ) = 0$，即空集的异或和为$0$。

数据范围：$4 \leqslant n \leqslant 18$，$1 \leqslant m \leqslant 10$，$1 \leqslant a_{i}<2^{m}$，$0 \leqslant w_i \leqslant 10^9$，时限 10s。

Notes

枚举子集最大允许复杂度为$2^{26},\ 3^{16}$，本题可以使用$\Theta(2^{m+n})$ 的方法。

不妨设$a_{1}$ 在$A$ 中，暴力枚举每个$a_{i}\ (2 \leqslant i \leqslant n)$ 在哪个集合中，复杂度是$\Theta(4^{n-1})$ 的，不能通过。我们拆解问题，首先枚举每个$a_{i}\ (2 \leqslant i \leqslant n)$ 在$A\cup B$ 中，还是在$C\cup D$ 中，可以大大降低复杂度，这部分的复杂度是$\Theta(2^{n-1})$ 的。

于是问题化为：将一个集合$S$ 中的若干元素分成两组$A,B$，尽可能地使这两组异或和的最大值最小，最小值最大。

直接做是不易的，我们接着枚举，枚举集合$A$ 的异或和$f(A)$，因为$S$ 中元素已经确定，且总的异或和$f(S)$ 可算，这样就得到了$B$ 的异或和$f(B)=f(S)\oplus f(A)$，这部分的复杂度是$\Theta(2^{m})$ 的。如果再枚举$f(C)$，得到$f(D)$，又需要$\Theta(2^{m})$ 的时间，是不行的。但我们偏要枚举，所以可以把枚举$f(A)$ 和枚举$f(C)$ 写在同一个循环中，时间仍然是$\Theta(2^{m})$ 的。

思考如何计算答案，不妨设$w_{f(A)} \geqslant w_{f(B)},\ w_{f(C)} \geqslant w_{f(D)}$，对于一个确定的$w_{f(A)}$，答案为$w_{f(A)}-\min\lbrace w_{f(B)},\max\lbrace w_{f(D)} \rbrace \rbrace$，这里$w_{f(A)}, w_{f(B)}$ 都是已知的，而$\max\lbrace w_{f(D)} \rbrace$，只需要将权值排序后在循环中记录最大值即可。对于一个确定的$w_{f(C)}$，答案可类似求得，不再赘述。

需要边枚举边计算$A\cup B$ 的异或和，使用 DFS 枚举。最终时间复杂度$\Theta(2^{n-1+m})$。

Code

const int inf = 0x3f3f3f3f;
void eachT() {
	int n, m;
	cin >> n >> m;

	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	vector<int> w(1 << m);
	for (int i = 0; i < 1 << m; i++) {
		cin >> w[i];
	}

	vector<int> rk(1 << m);
	iota(rk.begin(), rk.end(), 0);
	sort(rk.begin(), rk.end(), [&](int x, int y) { return w[x] < w[y]; });
	// rk[i]表示w的第i小的数的下标

	vector<vector<int>> AB(n + 1, vector<int>(1 << m)), CD(n + 1, vector<int>(1 << m));  // bool可能表示出的所有异或和
	AB[1][0] = CD[1][0] = 1;
	AB[1][a[0]] = 1;  // 不妨a0放在AB集合里

	int ans = inf;
	auto dfs = [&](auto&& self, int id, int ab, int cd) {  // ab表示AB的异或和 即A的异或和^B的异或和
		if (id == n) {   // 枚举完毕
			int maxb = -inf, maxd = -inf;  // 记录最大值
			for (int i = 0; i < 1 << m; i++) {
				int a = rk[i], b = ab ^ a;    // 枚举得到A的异或和a B的异或和b
				if (AB[n][a] && w[a] >= w[b]) {  // a这个异或和是能表示的 且不妨设w[a]>=w[b]
					maxb = max(maxb, w[b]);
					ans = min(ans, w[a] - min(w[b], maxd));
				}

				int c = rk[i], d = cd ^ c;
				if (CD[n][c] && w[c] >= w[d]) {
					maxd = max(maxd, w[d]);
					ans = min(ans, w[c] - min(w[d], maxb));
				}
			}
			return;
		}

		// 枚举将a[id]放在AB中
		for (int i = 0; i < 1 << m; i++) {
			AB[id + 1][i] = AB[id][i] | AB[id][i ^ a[id]];   // 可选arr[id] 能表示出的异或和有i^a[id]
			CD[id + 1][i] = CD[id][i];
		}
		self(self, id + 1, ab ^ a[id], cd);

		// 枚举将a[id]放在CD中
		for (int i = 0; i < 1 << m; i++) {
			AB[id + 1][i] = AB[id][i];
			CD[id + 1][i] = CD[id][i] | CD[id][i ^ a[id]];
		}
		self(self, id + 1, ab, cd ^ a[id]);
	};
	dfs(dfs, 1, a[0], 0);

	cout << ans << '\n';
}

枚举

给你一个$n$ 和两个序列$a,b$。求有多少个数对$(i,j)$ 满足$1 \le i < j \le n$ 且$a_i \times a_j = b_i + b_j$。思路是枚举$j$ 和$a_{j} \leqslant B$。

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        int B = ceil(sqrt(2 * n));
        vector cnt(B + 1, vector<int>(n + 1));
        vector<int> a(n), b(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> b[i];
            if (a[i] <= B) {
                cnt[a[i]][b[i]]++;
            }
        }

        ll res = 0;
        for (int j = 0; j < n; j++) {
            for (int ai = 1; ai <= B; ai++) {
                ll bi = 1LL * ai * a[j] - b[j];
                if (ai < a[j] && bi >= 1 && bi <= n) {
                    res += cnt[ai][bi];
                }
            }
        }
        for (int ai = 1; ai <= B; ai++) {
            int sum = ai * ai;
            for (int bi = 1; bi < (sum + 1) / 2; bi++) {
                if (sum - bi <= n) {
                    res += 1LL * cnt[ai][bi] * cnt[ai][sum - bi];
                }
            }
            if (sum % 2 == 0) {
                if (sum / 2 <= n) {
                    res += 1LL * cnt[ai][sum / 2] * (cnt[ai][sum / 2] - 1) / 2;
                }
            }
        }
        cout << res << endl;
    }

    return 0;
}