头像

YimingLi

浙江大学 $\href{https://github.com/upupming}{My\ GitHub}$




离线:45分钟前


活动打卡代码 AcWing 186. 巴士

/*
样例的 3 等差数列:
13: 0-13-26-39-52
12: 3-15-27-39-51
8:  5-13-21-29-37-45-53
目标:找到 3 个起始点,3 个公差

算法:先预处理出所有合法路线
首项:a
公差:d
那么一定有 a - d < 0,也就是 d >= a + 1
等差数列至少有两个数,所有要求 a + d < 60

最少选择多少条(k)路线,可以将所有公交车(n)覆盖
组合问题
剪枝:
1. dfs 时需要传入一个枚举的起点
2. 优先枚举点较多的路线
3. 如果当前路线上的点数 * 剩余可以选择的路线数量 + 现在已经覆盖的公交车数量 < 总公交车数,直接回溯
*/
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
// 从 60 个时间点中选择两个点就可以确定一个等差数列,所以总的方案数不超过 C_60^2 < 2000
const int N = 2000, M = 60;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
vector<PIII> routes;

int n, t, bus[M], e;

bool check(int a, int d) {
    for (int i = a; i < 60; i += d) {
        // 如果某个时刻没有公交车
        if (!bus[i]) return false;
    }
    return true;
}

// dep: 已经选择的路线数量
// sum: 当前所有线路已经容纳的公交车数量
// start: 当前可以选的路线的开始下标
bool dfs(int dep, int sum, int start) {
    if (dep == e) return sum == n;

    // 枚举选哪个路线
    for (int i = start; i < routes.size(); i++) {
        auto r = routes[i];
        int a = r.second.first, d = r.second.second;
        // 后续不管怎么选,都不可能超出 n,剪枝 3
        if (r.first * (e - dep) + sum < n) continue;
        if (!check(a, d)) continue;
        for (int j = a; j < 60; j += d) bus[j]--;
        if (dfs(dep + 1, sum + r.first, i)) return true;
        // 还原现场
        for (int j = a; j < 60; j += d) bus[j]++;
    }

    return false;
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> t;
        bus[t]++;
    }
    // 枚举所有的首项
    for (int a = 0; a < 60; a++) {
        // 枚举所有公差
        for (int d = a + 1; a + d < 60; d++) {
            if (check(a, d)) {
                routes.push_back({// 路线上的公交车数量
                                  (59 - a) / d + 1,
                                  {a, d}});
            }
        }
    }
    // 按照「路线上的公交车数量」对所有路线从大到小排序,用于优先选择数量多的路线(剪枝2)
    sort(routes.begin(), routes.end(), greater<PIII>());

    e = 1;
    while (!dfs(0, 0, 0)) e++;
    cout << e << endl;
    return 0;
}


活动打卡代码 AcWing 1227. 分巧克力

/*
二分查找最大的正方形边长即可
*/
#include <iostream>
using namespace std;
const int N = 1e5 + 10;

int n, k, h[N], w[N];
bool valid(int a) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        cnt += (h[i] / a) * (w[i] / a);
    }
    return cnt >= k;
}
int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> h[i] >> w[i];
    int l = 0, r = 1e5;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (valid(mid))
            l = mid;
        else
            r = mid - 1;
    }
    cout << l << endl;
    return 0;
}


活动打卡代码 AcWing 680. 剪绳子

/*
实数二分
*/
#include <iostream>
using namespace std;
const int N = 1e5 + 10;

int n, m, a[N];
bool valid(double len) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        cnt += int(a[i] / len);
    }
    return cnt >= m;
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    double l = 0, r = 1e9;
    while (abs(l - r) > 1e-4) {
        double mid = (l + r) / 2;
        if (valid(mid))
            l = mid;
        else
            r = mid;
    }
    printf("%.2lf\n", l);
}


活动打卡代码 AcWing 1346. 回文平方

#include <iostream>
#include <algorithm>
using namespace std;

int n;
string toString(int x) {
    string ans;
    while (x) {
        int remainder = x % n;
        ans += remainder >= 10 ? remainder - 10 + 'A' : remainder + '0';
        x /= n;
    }
    return ans;
}
int main() {
    cin >> n;
    for (int x = 1; x <= 300; x++) {
        int y = x * x;
        string a = toString(y), b = a;
        reverse(b.begin(), b.end());
        if(a == b) {
            string c = toString(x), d = c;
            reverse(d.begin(), d.end());
            cout << d << " " << b << endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 185. 玛雅游戏

/*
每一步枚举操作哪一个格子(7 * 5),再枚举像哪个方向移动,最多只需要枚举 5 步(题目要求)
剪枝 1:如果某种颜色只有1个或2个小方块,则直接回溯
剪枝 2:枚举向左移动时,如果左边有方块,则直接回溯
    因为 (x, y, -1) 和 (x-1, y, 1) 是等价的移动,但是 (x-1, y, 1) 字典序更小
*/
#include <cstring>
#include <iostream>
using namespace std;

struct Path {
    int x, y, d;
} path[5];
int n, cnt[11], g[5][7], st[5][7];
void move(int a, int b, int c) {
    swap(g[a][b], g[c][b]);

    while (true) {
        // true 表示不再有连续 3 个可以消除的
        bool flag = true;
        // 处理悬空方格
        for (int x = 0; x < 5; x++) {
            int z = 0;
            for (int y = 0; y < 7; y++) {
                // 把原来的列上的所有方格(可能悬空)从下往上重新排到列上
                if (g[x][y])
                    g[x][z++] = g[x][y];
            }
            while (z < 7) g[x][z++] = 0;
        }

        // st[x][y] = true 表示这个地方可被消除
        memset(st, 0, sizeof st);
        // 遍历所有坐标,看是不是在 3 个一行或 3 个一列的区域,设置 st
        for (int x = 0; x < 5; x++) {
            for (int y = 0; y < 7; y++) {
                if (g[x][y]) {
                    // 向左、向右能够延伸到的最远区域
                    int l = x, r = x;
                    while (l - 1 >= 0 &&
                           g[l - 1][y] == g[x][y]) l--;
                    while (r + 1 < 5 &&
                           g[r + 1][y] == g[x][y]) r++;
                    if (r - l + 1 >= 3) {
                        st[x][y] = true;
                        flag = false;
                    } else {
                        l = r = y;
                        // 向上、向下能够延伸到的最远区域
                        while (l - 1 >= 0 &&
                               g[x][l - 1] == g[x][y]) l--;
                        while (r + 1 < 7 &&
                               g[x][r + 1] == g[x][y]) r++;
                        if (r - l + 1 >= 3) {
                            st[x][y] = true;
                            flag = false;
                        }
                    }
                }
            }
        }

        if (flag) break;
        for (int x = 0; x < 5; x++) {
            for (int y = 0; y < 7; y++) {
                if (st[x][y]) {
                    cnt[0]--;
                    cnt[g[x][y]]--;
                    g[x][y] = 0;
                }
            }
        }
    }
}
// u 表示之前已经移动过的步数
bool dfs(int u) {
    // n 步正好所有格子全部消失就返回 true
    if (u == n) return !cnt[0];
    for (int i = 0; i < 10; i++) {
        // 剪枝 1
        if (cnt[i] == 1 || cnt[i] == 2)
            return false;
    }
    int bg[5][7], bcnt[11];
    memcpy(bg, g, sizeof(g));
    memcpy(bcnt, cnt, sizeof(cnt));
    // 枚举所有列
    for (int x = 0; x < 5; x++) {
        // 枚举所有行
        for (int y = 0; y < 7; y++) {
            // 如果这个位置有方格,那么枚举所有方向
            if (g[x][y]) {
                // 向右移动
                int nx = x + 1;
                if (nx < 5) {
                    path[u] = {x, y, 1};
                    move(x, y, nx);
                    if (dfs(u + 1)) return true;
                    // 还原现场
                    memcpy(g, bg, sizeof(g));
                    memcpy(cnt, bcnt, sizeof(cnt));
                }

                // 向左移动
                nx = x - 1;
                // 剪枝 2
                if (nx >= 0 && !g[nx][y]) {
                    path[u] = {x, y, -1};
                    move(x, y, nx);
                    if (dfs(u + 1)) return true;
                    // 还原现场
                    memcpy(g, bg, sizeof(g));
                    memcpy(cnt, bcnt, sizeof(cnt));
                }
            }
        }
    }
    return false;
}
int main() {
    cin >> n;
    // 每一列
    for (int x = 0; x < 5; x++) {
        int t, y = 0;
        while (cin >> t && t) {
            // 所有颜色的格子的总个数
            cnt[0]++;
            // 颜色为 t 的格子的总个数
            cnt[t]++;
            g[x][y++] = t;
        }
    }
    if (dfs(0)) {
        for (int i = 0; i < n; i++) {
            cout << path[i].x << " " << path[i].y << " " << path[i].d << endl;
        }
    } else {
        puts("-1");
    }
    return 0;
}


活动打卡代码 AcWing 184. 虫食算

/*
按照等式从后往前搜,枚举所有满足情况的分配即可,dfs 的时候需要传一个进位给下一层
*/
#include <cstring>
#include <iostream>
using namespace std;
const int N = 26;

// n 表示进制,题目给定了式子长度也是 n
int ans[N], n, used[N], b[3][N];
string a[3];
// 这个优化非常重要,不然过不了
bool check(int k) {
    for (int bit_k = n - 1; bit_k >= k; bit_k--) {
        int x1 = b[0][bit_k], a1 = ans[x1];
        int x2 = b[1][bit_k], a2 = ans[x2];
        int x3 = b[2][bit_k], a3 = ans[x3];
        // 如果已经确定,提前剪枝
        if (a1 != -1 && a2 != -1 && a3 != -1 &&
            (a1 + a2) % n != a3 &&
            (a1 + a2 + 1) % n != a3) return false;
    }
    return true;
}
// 当前搜索到第 bit_k 位,来自第 k - 1 位的进位为 r
// g = 0, 1, 2 表示正在分配第 g 行
bool dfs(int bit_k, int r, int g) {
    if (bit_k == n) return true;

    int x = b[g][bit_k];
    if (!check(bit_k)) return false;

    int x1 = b[0][bit_k], a1 = ans[x1];
    int x2 = b[1][bit_k], a2 = ans[x2];
    int sum = ans[x1] + ans[x2] + r;

    // 如果之前 x 已经被更低的位确定了
    if (ans[x] != -1) {
        if (g == 2) {
            if (sum % n == ans[x]) {
                if (dfs(bit_k + 1, sum / n, 0)) return true;
            }
        } else {
            if (dfs(bit_k, r, g + 1)) return true;
        }
    }
    // 枚举所有的分配情况
    else {
        // 优化:当 g == 2 时,x 的选择只能是 sum % n
        if (g == 2) {
            int i = sum % n;
            if (!used[i]) {
                used[i] = true;
                ans[x] = i;

                if (dfs(bit_k + 1, sum / n, 0)) return true;

                ans[x] = -1;
                used[i] = false;
            }
        } else
            for (int i = n - 1; i >= 0; i--) {
                if (used[i]) continue;
                used[i] = true;
                ans[x] = i;

                if (dfs(bit_k, r, g + 1)) return true;

                ans[x] = -1;
                used[i] = false;
            }
    }

    return false;
}
int main() {
    cin >> n;
    cin >> a[0] >> a[1] >> a[2];
    for (int g = 0; g < 3; g++)
        for (int k = 0; k < n; k++) {
            b[g][k] = a[g][n - 1 - k] - 'A';
        }
    memset(ans, 0xff, sizeof(ans));
    dfs(0, 0, 0);
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " ";
    }
}


活动打卡代码 AcWing 1113. 红与黑

#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 30;
typedef pair<int, int> PII;

int w, h, ans, v[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
char s[N][N];
PII start;
bool valid(int x, int y) {
    return x >= 0 && x < h && y >= 0 && y < w && s[x][y] == '.';
}
int main() {
    while (cin >> w >> h && (w || h)) {
        memset(v, 0, sizeof(v)), ans = 0;
        for (int i = 0; i < h; i++) {
            cin >> s[i];
            for (int j = 0; j < w; j++) {
                if (s[i][j] == '@') start = {i, j};
            }
        }
        queue<PII> q;
        ans++;
        q.push(start);
        while (q.size()) {
            auto now = q.front();
            q.pop();
            for (int i = 0; i < 4; i++) {
                int x = now.first + dx[i];
                int y = now.second + dy[i];
                if (!valid(x, y) || v[x][y]) continue;
                v[x][y] = 1;
                ans++;
                q.push({x, y});
            }
        }
        cout << ans << endl;
    }
    return 0;
}



/*
跟 166 题数独完全一样
暴力搜索所有的解决方案,并计算分值即可,分值的计算可以用坐标到边界的最小距离+6即可
*/
#include <iostream>
using namespace std;
const int N = 9;

int row[N], col[N], cell[N][N], h[1 << N], cnt[1 << N], ans = -1;
int g[N][N];

inline void flip(int x, int y, int z) {
    row[x] ^= 1 << z;
    col[y] ^= 1 << z;
    cell[x / 3][y / 3] ^= 1 << z;
}
int getScore(int x, int y) {
    int dx = min(x, 8 - x), dy = min(y, 8 - y);
    return min(dx, dy) + 6;
}
// now: 剩余的没有填的位置数
// score: 到目前为止的得分总和
void dfs(int now, int score) {
    // 更新答案
    if (now == 0) {
        ans = max(ans, score);
        return;
    }
    // 找一个能填的合法数字最少的位置
    int minCh = 10, x, y;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (g[i][j] == 0) {
                auto choices = row[i] & col[j] & cell[i / 3][j / 3];
                int numCh = cnt[choices];
                if (numCh == 0) return;
                if (numCh < minCh) {
                    minCh = numCh;
                    x = i, y = j;
                }
            }
        }
    }

    // 枚举当前位置的所有的填充方法
    auto choices = row[x] & col[y] & cell[x / 3][y / 3];
    int s = getScore(x, y);
    for (int val = choices; val; val -= val & -val) {
        int num = h[val & -val];
        g[x][y] = num + 1;
        flip(x, y, num);
        dfs(now - 1, g[x][y] * s + score);
        flip(x, y, num);
        g[x][y] = 0;
    }
}
int main() {
    // log 计算
    for (int i = 0; i < N; i++)
        h[1 << i] = i;
    // 数中 1 的数量
    for (int i = 0; i < 1 << N; i++) {
        for (int j = i; j; j -= j & -j) {
            cnt[i]++;
        }
    }
    // 空白待填的个数
    int tot = 0, sum = 0;
    // 初始时,1~9 都可以填
    for (int i = 0; i < N; i++) {
        row[i] = col[i] = cell[i / 3][i % 3] = (1 << N) - 1;
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> g[i][j];
            if (g[i][j] != 0) {
                sum += getScore(i, j) * g[i][j];
                flip(i, j, g[i][j] - 1);
            } else {
                tot++;
            }
        }
    }
    dfs(tot, sum);
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 183. 靶形数独

/*
跟 166 题数独完全一样
暴力搜索所有的解决方案,并计算分值即可,分值的计算可以用坐标到边界的最小距离+6即可
*/
#include <iostream>
using namespace std;
const int N = 9;

int row[N], col[N], cell[N][N], h[1 << N], cnt[1 << N], ans = -1;
int g[N][N];

inline void flip(int x, int y, int z) {
    row[x] ^= 1 << z;
    col[y] ^= 1 << z;
    cell[x / 3][y / 3] ^= 1 << z;
}
int getScore(int x, int y) {
    int dx = min(x, 8 - x), dy = min(y, 8 - y);
    return min(dx, dy) + 6;
}
// now: 剩余的没有填的位置数
// score: 到目前为止的得分总和
void dfs(int now, int score) {
    // 更新答案
    if (now == 0) {
        ans = max(ans, score);
        return;
    }
    // 找一个能填的合法数字最少的位置
    int minCh = 10, x, y;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (g[i][j] == 0) {
                auto choices = row[i] & col[j] & cell[i / 3][j / 3];
                int numCh = cnt[choices];
                if (numCh == 0) return;
                if (numCh < minCh) {
                    minCh = numCh;
                    x = i, y = j;
                }
            }
        }
    }

    // 枚举当前位置的所有的填充方法
    auto choices = row[x] & col[y] & cell[x / 3][y / 3];
    int s = getScore(x, y);
    for (int val = choices; val; val -= val & -val) {
        int num = h[val & -val];
        g[x][y] = num + 1;
        flip(x, y, num);
        dfs(now - 1, g[x][y] * s + score);
        flip(x, y, num);
        g[x][y] = 0;
    }
}
int main() {
    // log 计算
    for (int i = 0; i < N; i++)
        h[1 << i] = i;
    // 数中 1 的数量
    for (int i = 0; i < 1 << N; i++) {
        for (int j = i; j; j -= j & -j) {
            cnt[i]++;
        }
    }
    // 空白待填的个数
    int tot = 0, sum = 0;
    // 初始时,1~9 都可以填
    for (int i = 0; i < N; i++) {
        row[i] = col[i] = cell[i / 3][i % 3] = (1 << N) - 1;
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> g[i][j];
            if (g[i][j] != 0) {
                sum += getScore(i, j) * g[i][j];
                flip(i, j, g[i][j] - 1);
            } else {
                tot++;
            }
        }
    }
    dfs(tot, sum);
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 756. 蛇形矩阵

#include <iostream>
using namespace std;
const int N = 110;

int n, m, a[N][N];
int d[4][2] = {
    {0, 1},
    {1, 0},
    {0, -1},
    {-1, 0}
};
int main() {
    cin >> n >> m;    
    int x = 0, y = 0, dx = 0, dy = 1;
    for (int i = 1; i <= n * m; i++) {
        a[x][y] = i;
        if (dy == 1 && (y == m - 1 || a[x][y+1] != 0)) dx = d[1][0], dy = d[1][1];
        if (dx == 1 && (x == n - 1 || a[x+1][y] != 0)) dx = d[2][0], dy = d[2][1];
        if (dy == -1 && (y == 0 || a[x][y-1] != 0)) dx = d[3][0], dy = d[3][1];
        if (dx == -1 && (x == 0 || a[x-1][y] != 0)) dx = d[0][0], dy = d[0][1];

        x += dx, y += dy;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
}