头像

greg666


访客:21171

离线:9小时前



greg666
12天前

可以用浮点数作为map/unordered_map中的key吗?比如想用斜率作key。会不会不精确



新鲜事 原文

greg666
20天前
已认怂。难题自己肯定做不出来。能做的只有把已做过的题背好。


新鲜事 原文

greg666
2个月前
Hello, world.



greg666
2个月前

看完闫老师的视频写的。
向量方法确实简便。

const double eps = 1e-9;
vector<vector<double>> getCenters(vector<int> p1, vector<int> p2, int r) {
    double x1 = p1[0], y1 = p1[1];
    double x2 = p2[0], y2 = p2[1];
    double xc = (x1 + x2) / 2;
    double yc = (y1 + y2) / 2;
    double d = sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
    if (d / 2 >  r + eps) {
        return {};
    }

    vector<double> v = {(x2 - x1) / d, (y2 - y1) / d};
    /*
        cos, -sin  --> 0, -1  -->  0, 1 
        sin,  cos      1,  0      -1, 0

        (x, y) -> (y, -x) and (-y, x)
    */
    double h = sqrt(r * r - (d / 2) * (d / 2));

    vector<vector<double>> res;
    res.push_back({xc + v[1] * h, yc - v[0] * h});
    res.push_back({xc - v[1] * h, yc + v[0] * h});
    return res;
}

int numPoints(vector<vector<int>>& points, int r) {
    int n = points.size();
    int res = 1;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            vector<vector<double>> centers = getCenters(points[i], points[j], r);
            for (auto center : centers) {
                int cnt = 0;
                double cx = center[0];
                double cy = center[1];
                for (int k = 0; k < n; k++) {
                    double x = points[k][0];
                    double y = points[k][1];
                    if ((cx - x) * (cx - x) + (cy - y) * (cy - y) < r * r + eps) {
                        cnt++;
                    }
                }
                res = max(res, cnt);
            }
        }
    }
    return res;
}


活动打卡代码 AcWing 379. 捉迷藏

greg666
5个月前
// 捉迷藏
const int N = 200, M = 30000;
bool d[N + 1][N + 1];
bool st[N + 1];
int match[N + 1];

bool find(int u, int n) {
    for (int v = 1; v <= n; v++) {
        if (!d[u][v]) {
            continue;
        }

        if (st[v]) {
            continue;
        }
        st[v] = true;

        int t = match[v];
        if (t == 0 || find(t, n)) {
            match[v] = u;
            return true;
        }
    }

    return false;
}

int solve(int n) {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                d[i][j] |= d[i][k] & d[k][j];
            }
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i++) {
        memset(st, 0, sizeof st);
        if (find(i, n)) {
            res++;
        }
    }

    return n - res;
}


活动打卡代码 AcWing 378. 骑士放置

greg666
5个月前
// 骑士放置
const int N = 100;
PII match[N + 1][N + 1];
bool g[N + 1][N + 1];  // 1-based, 1 is bad block
bool st[N + 1][N + 1];

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

bool find(int x, int y, int m, int n, int k) {
    for (int i = 0; i < 8; i++) {
        int a = x + dx[i];
        int b = y + dy[i];
        if (a < 1 || a > m || b < 1 || b > n) {
            continue;
        }
        if (g[a][b]) {
            continue;
        }

        if (st[a][b]) {
            continue;
        }
        st[a][b] = true;

        PII t = match[a][b];
        if (t.x == 0 || find(t.x, t.y, m, n, k)) {
            match[a][b] = {x, y};
            return true;
        }
    }

    return false;
}

int solve(int m, int n, int k) {
    int res = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (g[i][j] || (i + j) % 2) {
                continue;
            }
            memset(st, 0, sizeof st);
            if (find(i, j, m, n, k)) {
                res++;
            }
        }
    }

    return m * n - k - res;
}


活动打卡代码 AcWing 376. 机器任务

greg666
5个月前
// 机器任务
const int N = 100, M = 100;
bool g[N][M];  // [0, n - 1], [0, m - 1], but skip 0
int st[M];
int match[M];

bool find(int u, int m) {
    for (int v = 0; v < m; v++) {
        if (!g[u][v]) {
            continue;
        }

        if (st[v]) {
            continue;
        }
        st[v] = true;

        if (match[v] == -1 || find(match[v], m)) {
            match[v] = u;
            return true;
        }
    }

    return false;
}

int solve(int n, int m) {
    int res = 0;
    for (int i = 0; i < n; i++) {
        memset(st, 0, sizeof st);
        if (find(i, m)) {
            res++;
        }
    }
    return res;
}


活动打卡代码 AcWing 372. 棋盘覆盖

greg666
5个月前
// 棋盘覆盖
const int N = 100;
PII match[N + 1][N + 1];  // 1-based
bool g[N + 1][N + 1];  // bad point true
bool st[N + 1][N + 1];

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

bool find(int x, int y, int n) {
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 1 || nx > n || ny < 1 || ny > n) {
            continue;
        }
        if (g[nx][ny]) {
            continue;
        }
        if (st[nx][ny]) {
            continue;
        }
        st[nx][ny] = true;
        PII t = match[nx][ny];
        if (t.x == -1 || find(t.x, t.y, n)) {
            match[nx][ny] = {x, y};
            return true;
        }
    }

    return false;
}

int solve(int n) {
    memset(match, -1, sizeof match);

    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if ((i + j) % 2 && !g[i][j]) {
                memset(st, 0, sizeof st);
                if (find(i, j, n)) {
                    res++;
                }
            }
        }
    }

    return res;
}


活动打卡代码 AcWing 257. 关押罪犯

greg666
5个月前
// 关押罪犯
const int N = 2e4, M = 2e5;

int h[N + 1];
int e[M], w[M], ne[M], idx;
int color[N + 1];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool dfs(int u, int c, int x) {
    color[u] = c;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (w[i] <= x) {  // ignore small edges
            continue;
        }
        if (color[v]) {
            if (color[v] == c) {
                return false;
            }
        } else if (!dfs(v, 3 - c, x)) {
            return false;
        }
    }

    return true;
}

bool check(int n, int x) {
    memset(color, 0, sizeof color);
    for (int i = 1; i <= n; i++) {
        if (!color[i]) {
            if (!dfs(i, 1, x)) {
                return false;
            }
        }
    }
    return true;
}

int solve(int n) {
    int l = 0, r = 1e9;
    int res = r;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(n, mid)) {
            res = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    return res;

    // while (l < r) {
    //     int mid = l + r >> 1;
    //     if (check(mid)) {
    //         r = mid;
    //     } else {
    //         l = mid + 1;
    //     }
    // }
    // return r;
}


活动打卡代码 AcWing 1185. 单词游戏

greg666
5个月前
// 单词游戏
const int N = 26 + 1;
int din[N], dout[N];
int p[N];
bool st[N];

int find(int x) {
    if (p[x] != x) {
        p[x] = find(p[x]);
    }
    return p[x];
}

bool solve() {
    int start = 0, end = 0;
    for (int i = 0; i < 26; i++) {
        if (din[i] != dout[i]) {
            if (din[i] == dout[i] + 1) {
                end++;
            } else if (din[i] + 1 == dout[i]) {
                start++;
            } else {
                return false;
            }
        }
    }

    if (!(!start && !end || start == 1 && end == 1)) {
        return false;
    }

    int root = -1;
    for (int i = 0; i < 26; i++) {
        if (st[i]) {
            if (root == -1) {
                root = find(i);
            } else if (root != find(i)) {
                return false;
            }
        }
    }

    return true;
}