Week8

7-1 100...07是不是素数？

每个数暴力 \(O(\sqrt{v})\) 找最小质因子即可，时间复杂度 \(O(n\cdot \sqrt{v})\)

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

int min_p(ll x){
    if(x % 2 == 0) return 2;
    for(int i=3; 1ll*i*i<=x; i+=2){
        if(x % i == 0) return i;
    }
    return x;
}

void solve(){
	int n;
    cin >> n;
    ll cur = 10;
    for(int k=0; k<=n; k++){
        int p = min_p(cur + 7);
        if(p == cur+7){
            cout << cur+7 << " is prime!\n";
        }
        else{
            cout << cur+7 << " factor=" << p << '\n';
        }
        cur *= 10;
    }
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1; // cin >> t;
	while(t--) solve();
	
	return 0;
}

7-2 President's Office

先找 c，找到 c 之后去找周围的字母，找到就 dfs 把整个区域都标记为 true，ans++。

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

vector<pii> moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
void solve(){
    int n, m; char c;
    cin >> n >> m >> c;
    vector<vector<char>> mat(n + 2, vector<char>(m + 2, '.'));
    for(int i=1; i<=n; i++){
        string s; cin >> s;
        for(int j=1; j<=m; j++){
            mat[i][j] = s[j-1];
        }
    }

    int ans = 0;

    vector<vector<bool>> vis(n + 2, vector<bool>(m + 2));
    auto dfs = [&](auto&& self, int x, int y) ->void {
        vis[x][y] = true;
        for(int i=0; i<4; i++){
            int dx = moves[i].first, dy = moves[i].second;
            int nx = dx + x, ny = dy + y;
            if(!vis[nx][ny] && mat[nx][ny] == mat[x][y]){
                self(self, nx, ny);
            }
        }
    };

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(mat[i][j] != c) continue;
            for(int k=0; k<4; k++){
                int dx = moves[k].first;
                int dy = moves[k].second;
                int x = dx + i, y = dy + j;
                if(!vis[x][y] && mat[x][y] != c && mat[x][y] != '.'){
                    dfs(dfs, x, y);
                    ans++;
                }
            }
        }
    }

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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1; //cin >> t;
	while(t--) solve();
	
	return 0;
}

7-3 L-shapes

找到 * 就 dfs，维护连通块中每个 * 的坐标，然后根据坐标判断形状是否合法，一共有 4 种合法情况，之后判断有没有别的连通块相邻

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

vector<pii> moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
void solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<char>> mat(n + 2, vector<char>(m + 2, '.'));
    for(int i=1; i<=n; i++){
        string s; cin >> s;
        for(int j=1; j<=m; j++){
            mat[i][j] = s[j-1];
        }
    }

    vector<vector<bool>> vis(n + 2, vector<bool>(m + 2));
    // dfs 时 , 用 set 收集连通块的点
    set<pii> st;
    auto dfs = [&](auto&& self, int x, int y) ->void {
        vis[x][y] = true;
        st.insert({x, y});
        for(int i=0; i<4; i++){
            int dx = moves[i].first, dy = moves[i].second;
            int nx = dx + x, ny = dy + y;
            if(!vis[nx][ny] && mat[nx][ny] == '*'){
                self(self, nx, ny);
            }
        }
    };

    bool ok = true;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(!vis[i][j] && mat[i][j] == '*'){
                dfs(dfs, i, j);

                if(st.size() >= 4) ok = false; // 只能是 3 个方块
				
                // 这里取出的是 x 最小的那个点
                int x = (*st.begin()).first;
                int y = (*st.begin()).second;
                // 若不是这 4 种情况, 则为 false
                if((st.count({x+1, y}) && st.count({x+1, y+1})) || 
                (st.count({x+1, y}) && st.count({x+1, y-1})) ||
                (st.count({x, y+1}) && st.count({x+1, y+1})) ||
                (st.count({x+1, y}) && st.count({x, y+1}))){}
                else ok = false;
                
                // 检查是否和别的 L 相邻
                for(auto it : st){
                    int cx = it.first, cy = it.second;
                    for(int k=0; k<8; k++){
                        int dx = moves[k].first, dy = moves[k].second;
                        int nx = dx + cx, ny = dy + cy;
                        if(mat[nx][ny] == '*' && !st.count({nx, ny})) ok = false;
                    }
                }

                st.clear();
            }
        }
    }

    cout << (ok? "YES":"NO") << '\n';
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1; cin >> t;
	while(t--) solve();
	
	return 0;
}

7-4 h0324. 走方格

每一步要么往右走，要么往下走，直接 dfs 暴搜即可

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

void solve(){
	int n, m;
	cin >> n >> m;

	ll ans = 0;
	auto dfs = [&](auto&&self, int x, int y) ->void {
		if(x>n || y>m) return;
		if(x == n && y == m){
			ans++;
			return; 
		}
		self(self, x+1, y);
		self(self, x, y+1);
	};
	dfs(dfs, 0, 0);
	cout << ans << '\n';

}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1; //cin >> t;
	while(t--) solve();
	
	return 0;
}

7-5 h0193. 排列

( 样例是每个数字后都有空格，题目竟然没说 )

进行 n 轮，每次都从没选的点中选择一个点，用 track 记录路径，回溯

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

constexpr int inf = 0x3f3f3f3f;

void solve(){
	int n;
	cin >> n;

	vector<bool> used(n + 1);
	vector<int> track;
	auto dfs = [&](auto&& self, int x) ->void {
		if(x == n){
			for(int i=0; i<n; i++){
				cout << track[i] << ' ';
			}
			cout << '\n';
			return;
		}

		for(int i=1; i<=n; i++){
			if(used[i]) continue;
			used[i] = true;
			track.push_back(i);
			self(self, x+1);
			used[i] = false;
			track.pop_back();
		}
	};
	dfs(dfs, 0);

}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1; //cin >> t;
	while(t--) solve();
	
	return 0;
}

推荐直接 next_permutation

void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    iota(a.begin(), a.end(), 0); // 递增赋值 , a = {0, 1, 2, ...}

    do{
        for(int i=1; i<=n; i++){
            cout << a[i] << " ";
        }
        cout << '\n';
    }while(next_permutation(a.begin()+1, a.end()));
}

7-6 h0115. 算24

把 4 个数放进一个数组里，每次取出两个数进行 + - * / 操作，将结果放入。重复操作，仅剩一个数时即为结果。因为设计 double 运算，判相等时最好使用 abs(A-B) <= eps 而不是直接 A == B

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

constexpr double eps = 1e-6;

bool ed = false;
void solve(){
    vector<double> a(4);
    for(int i = 0; i < 4; i++) cin >> a[i];
    if(a[0] == 0 && a[1] == 0 && a[2] == 0 && a[3] == 0){
        ed = true;
        return;
    }

    bool ok = false;
    auto dfs = [&](auto&& self, vector<double>& v) -> void {
        if(ok) return;
        int n = v.size();
        if(n == 1){
            if(fabs(v[0] - 24.0) < eps) ok = true;
            return;
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i == j) continue;

                vector<double> nxt;
                for(int k = 0; k < n; k++){
                    if(k != i && k != j) nxt.push_back(v[k]);
                }

                double x = v[i], y = v[j];

                // +
                nxt.push_back(x + y);
                self(self, nxt);
                nxt.pop_back();

                // -
                nxt.push_back(x - y);
                self(self, nxt);
                nxt.pop_back();

                // *
                nxt.push_back(x * y);
                self(self, nxt);
                nxt.pop_back();

                // /
                if(fabs(y) > eps){
                    nxt.push_back(x / y);
                    self(self, nxt);
                    nxt.pop_back();
                }
            }
        }
    };

    dfs(dfs, a);

    cout << (ok ? "YES" : "NO") << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while(!ed){
        solve();
    }

    return 0;
}

7-7 生命游戏II

根据题意模拟即可

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

int k, n;
vector<vector<int>> cur, nxt;
vector<vector<bool>> vis;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> k >> n;
    cur.assign(n+2, vector<int>(n+2, 0));
    nxt.assign(n+2, vector<int>(n+2, 0));

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> cur[i][j];
        }
    }

    while(k--) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                nxt[i][j] = 0; // 默认边界为0
            }
        }
        for(int i = 2; i < n; i++) {
            for(int j = 2; j < n; j++) {
                int live = 0;
                for(int dir = 0; dir < 8; dir++) {
                    int ni = i + dx[dir], nj = j + dy[dir];
                    live += cur[ni][nj];
                }
                if(cur[i][j] == 1) {
                    nxt[i][j] = (live == 2 || live == 3);
                } else {
                    nxt[i][j] = (live == 3);
                }
            }
        }
        swap(cur, nxt);
    }

    // DFS 统计八连通块大小
    int cnt = 0;
    auto dfs = [&](auto&&self, int x, int y) ->void {
        vis[x][y] = true;
        cnt++;
        for(int dir = 0; dir < 8; dir++) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if(nx >= 1 && nx <= n && ny >= 1 && ny <= n && !vis[nx][ny] && cur[nx][ny] == 1) {
                self(self, nx, ny);
            }
        }
    };


    // DFS 统计最大连通块
    vis.assign(n+2, vector<bool>(n+2, false));
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(cur[i][j] == 1 && !vis[i][j]) {
                cnt = 0;
                dfs(dfs, i, j);
                ans = max(ans, cnt);
            }
        }
    }

    cout << ans << "\n";
    return 0;
}

7-8 L-朋友圈

题意：给你一个无向图，找连通块的个数和最大的连通块大小

使用邻接表存边，gra[u] 是一个数组 {v0, v1, v2...}，表示 u 和 v0, v1, v2... 有边

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

void solve(){
    int n, m;
    cin >> n >> m;

    vector<vector<int>> gra(n);
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        gra[u].push_back(v);
        gra[v].push_back(u);
    }

    vector<int> vis(n, 0);

    int cnt = 0;        // 朋友圈个数
    int mx = 0;         // 最大朋友圈人数

    int sz = 0;
    auto dfs = [&](auto&& self, int u) ->void {
        vis[u] = 1;
        sz++;
        for(int v : gra[u]){ // 遍历 u 的每条边
            if(!vis[v]){
                self(self, v);
            }
        }
    };

    for(int i = 0; i < n; i++){
        if(!vis[i]){
            sz = 0;
            cnt++;
            dfs(dfs, i);
            mx = max(mx, sz);
        }
    }

    cout << cnt << ' ' << mx << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

7-9 回溯法的通用伪代码（以分书问题为例）

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

void solve(){
    int n, m;
    cin >> n >> m;   // m = 4

    vector<vector<int>> like(n + 1, vector<int>(m + 1));
    vector<int> used(m + 1), ans(n + 1);
    bool found = false;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> like[i][j];
        }
    }

    auto dfs = [&](auto&& self, int x) -> void {
        if(found) return;
        if(x > n){
            found = true;
            return;
        }
        for(int j = 1; j <= m; j++){ // 枚举第 i 个人拿了哪本书
            if(!like[x][j]) continue;
            if(used[j]) continue;

            used[j] = 1;
            ans[x] = j;
            self(self, x + 1);
            used[j] = 0;

            if(found) return;
        }
    };

    dfs(dfs, 1);

    if(found){
        cout << '(';
        for(int i = 1; i <= n; i++){
            if(i > 1) cout << ", ";
            cout << ans[i];
        }
        cout << ')';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

7-10 被n整除的n位数

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

void solve(){
    int n;
    ll a, b;
    cin >> n >> a >> b;

    vector<ll> ans;
    auto dfs = [&](auto&& self, int pos, ll val) -> void {
        if(pos > n){
            ans.push_back(val);
            return;
        }
        int lo = (pos == 1 ? 1 : 0);
        for(int d = lo; d <= 9; d++){
            ll nv = val * 10 + d;
            if(nv % pos == 0){
                self(self, pos + 1, nv);
            }
        }
    };
    dfs(dfs, 1, 0);

    sort(ans.begin(), ans.end());
    bool ok = false;
    for(ll x : ans){
        if(x >= a && x <= b){
            cout << x << '\n';
            ok = true;
        }
    }
    if(!ok) cout << "No Solution" << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while(t--) solve();
    return 0;
}