2021-team4-template

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

= 路径压缩trie =

#include <bits/stdc++.h>
using namespace std;
int n, id[100005];
string s[100005];
int tot, par[200000], pos[100005], mx[200000], g[200000];
bool vis[200000];
void pro(int x, int l, int r, int d) {
    int cnt = 0;
    for (; l <= r && s[id[l]].size() == d; l ++) {
        pos[id[l]] = x;
        cnt = 1;
    }
    cnt += l <= r;
    cnt += l <= r && s[id[l]][d] != s[id[r]][d];
    for (int i = l, j; i <= r; i = j + 1) {
        j = i;
        while (j < r && s[id[i]][d] == s[id[j + 1]][d])
            j ++;
        if (cnt == 1)
            pro(x, i, j, d + 1), vis[x] = 1;
        else {
            char v = s[id[i]][d];
            int c = islower(v) ? v - 'a' : isupper(v) ? 26 + v - 'A' : isdigit(v) ? 52 + v - '0' : v == '.' ? 62 : 63;
            int y = ++ tot;
            par[y] = x;
            pro(y, i, j, d + 1);
        }
    }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("a.in", "r", stdin);
#endif
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> s[i];
    for (int i = 1; i <= n; i ++)
        id[i] = i;
    sort(id + 1, id + n + 1, [&](int i, int j) {
        return s[i] < s[j];
    });
    tot = 1, pro(1, 1, n, 0);
    assert(tot == 2 * n - 1);
    for (int i = 1; i <= n; i ++) {
        for (int x = pos[i]; x; x = par[x])
            mx[x] = i;
    }
    for (int i = 1; i <= n; i ++) {
        int x = pos[i];
        while (par[x] > (vis[1] ? 0 : 1) && mx[par[x]] == i)
            x = par[x];
        int tmp = 1 - g[x];
        for (int y = x; y; y = par[y])
            g[y] += tmp;
        printf("%d\n", g[1]);
    }
    return 0;
}

= hungary =

#include <bits/stdc++.h>
using namespace std;
int n, m, f[105][105], K, cons[1005][3], lk[1005], used[1005];
vector<int> g[1005];
int hungary(int i) {
    for (int j : g[i])
        if (!used[j]) {
            used[j] = 1;
            if (lk[j] == 0 || hungary(lk[j])) {
                lk[j] = i;
                return 1;
            }
        }
    return 0;
}
int main() {
    // freopen("b.in", "r", stdin);
    scanf("%d%d%d", &n, &m, &K);
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
            f[i][j] = (i != j) * 1e8;
    for (int i = 1; i <= m; i ++) {
        int x, y, d;
        scanf("%d%d%d", &x, &y, &d);
        f[x][y] = min(f[x][y], d);
    }
    for (int k = 1; k <= n; k ++)
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
    for (int i = 1; i <= K; i ++)
        scanf("%d%d%d", cons[i], cons[i] + 1, cons[i] + 2);
    for (int i = 1; i <= K; i ++)
        for (int j = 1; j <= K; j ++)
            if (i != j && cons[i][2] + f[cons[i][0]][cons[i][1]] + f[cons[i][1]][cons[j][0]] <= cons[j][2])
                g[i].push_back(j);
    int ans = K;
    for (int i = 1; i <= K; i ++) {
        memset(used, 0, sizeof used);
        ans -= hungary(i);
    }
    printf("%d\n", ans);
    return 0;
}




= 求直线外一点与凸包切点 =
//8.13    2021NowcoderTraining_816_J 
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int INF = 1e9;
struct Point {
    int x, y;
    Point(): x(0), y(0) {}
    Point(int x, int y): x(x), y(y) {}
    int det(const Point &u) { return x * u.y - y * u.x; }
};
bool operator<(const Point &u, const Point &v) { return u.x == v.x ? u.y < v.y : u.x < v.x; }
bool operator>(const Point &u, const Point &v) { return u.x == v.x ? u.y > v.y : u.x > v.x; }
Point operator-(const Point &u, const Point &v) { return Point(u.x - v.x, u.y - v.y); }

struct Convex {
    int n;
    vector<Point> a, upper, lower;
    void Init(int _n) {
        a.resize(_n);
        n = _n;
        int mn = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%lld%lld", &a[i].x, &a[i].y);
            if (a[i] < a[mn]) mn = i; 
        }
        rotate(a.begin(), a.begin() + mn, a.end());
        int ptr = 0;
        for (int i = 1; i < n; ++i) if (a[ptr] < a[i]) ptr = i;
        for (int i = 0; i <= ptr; ++i) lower.push_back(a[i]);
        for (int i = ptr; i < n; ++i) upper.push_back(a[i]);
        upper.push_back(a[0]);
    }
    int sign(int x) { return x < 0 ? -1 : x > 0; }
    void update_tangent(const Point &p, int id, int &i0, int &i1) {
        if ((a[i0] - p).det(a[id] - p) > 0) i0 = id;
        if ((a[i1] - p).det(a[id] - p) < 0) i1 = id;
    }
    void binary_search(int l, int r, Point p, int &i0, int &i1) {
        if (l == r) return;
        update_tangent(p, l % n, i0, i1);
        int sl = sign((a[l % n] - p).det(a[(l + 1) % n] - p));
        for (; l + 1 < r; ) {
            int mid = (l + r) / 2;
            int smid = sign((a[mid % n] - p).det(a[(mid + 1) % n] - p));
            if (smid == sl) l = mid; else r = mid;
        }
        update_tangent(p, r % n, i0, i1);
    }
    pii get_tangent(Point p) {
        int i0 = 0, i1 = 0;
        int id = lower_bound(lower.begin(), lower.end(), p) - lower.begin();
        binary_search(0, id, p, i0, i1);
        binary_search(id, (int)lower.size(), p, i0, i1);
        id = lower_bound(upper.begin(), upper.end(), p, greater<Point>()) - upper.begin();
        binary_search((int)lower.size() - 1, (int)lower.size() - 1 + id, p, i0, i1);
        binary_search((int)lower.size() - 1 + id, (int)lower.size() - 1 + (int)upper.size(), p, i0, i1);
        return pii(i0, i1);
    }
} con;
const int N = 2e5 + 10;
int n, m;
int f[N][20], d[N][20];
signed main() {
    scanf("%lld%lld", &n, &m);
    con.Init(n);
    for (int i = 1, x, y; i <= m; ++i) {
        scanf("%lld%lld", &x, &y);
        pii tmp = con.get_tangent(Point(x, y));
        if (tmp.second < tmp.first) tmp.second += n;
    }

}

路径压缩trie

#include

using namespace std;

int n, id[100005];

string s[100005];

int tot, par[200000], pos[100005], mx[200000], g[200000];

bool vis[200000];

void pro(int x, int l, int r, int d) {

int cnt = 0;

for (; l <= r && s[id[l]].size() == d; l ++) {

pos[id[l]] = x;

cnt = 1;

}

cnt += l <= r;

cnt += l <= r && s[id[l]][d] != s[id[r]][d];

for (int i = l, j; i <= r; i = j + 1) {

j = i;

while (j < r && s[id[i]][d] == s[id[j + 1]][d])

j ++;

if (cnt == 1)

pro(x, i, j, d + 1), vis[x] = 1;

else {

char v = s[id[i]][d];

int c = islower(v) ? v - 'a' : isupper(v) ? 26 + v - 'A' : isdigit(v) ? 52 + v - '0' : v == '.' ? 62 : 63;

int y = ++ tot;

par[y] = x;

pro(y, i, j, d + 1);

}

}

}

int main() {

#ifndef ONLINE_JUDGE

freopen("a.in", "r", stdin);

#endif

cin.tie(0)->sync_with_stdio(0);

cin >> n;

for (int i = 1; i <= n; i ++)

cin >> s[i];

for (int i = 1; i <= n; i ++)

id[i] = i;

sort(id + 1, id + n + 1, [&](int i, int j) {

return s[i] < s[j];

});

tot = 1, pro(1, 1, n, 0);

assert(tot == 2 * n - 1);

for (int i = 1; i <= n; i ++) {

for (int x = pos[i]; x; x = par[x])

mx[x] = i;

}

for (int i = 1; i <= n; i ++) {

int x = pos[i];

while (par[x] > (vis[1] ? 0 : 1) && mx[par[x]] == i)

x = par[x];

int tmp = 1 - g[x];

for (int y = x; y; y = par[y])

g[y] += tmp;

printf("%d\n", g[1]);

}

return 0;

}

hungary

#include

using namespace std;

int n, m, f[105][105], K, cons[1005][3], lk[1005], used[1005];

vector g[1005];

int hungary(int i) {

for (int j : g[i])

if (!used[j]) {

used[j] = 1;

if (lk[j] == 0 || hungary(lk[j])) {

lk[j] = i;

return 1;

}

}

return 0;

}

int main() {

// freopen("b.in", "r", stdin);

scanf("%d%d%d", &n, &m, &K);

for (int i = 1; i <= n; i ++)

for (int j = 1; j <= n; j ++)

f[i][j] = (i != j) * 1e8;

for (int i = 1; i <= m; i ++) {

int x, y, d;

scanf("%d%d%d", &x, &y, &d);

f[x][y] = min(f[x][y], d);

}

for (int k = 1; k <= n; k ++)

for (int i = 1; i <= n; i ++)

for (int j = 1; j <= n; j ++)

f[i][j] = min(f[i][j], f[i][k] + f[k][j]);

for (int i = 1; i <= K; i ++)

scanf("%d%d%d", cons[i], cons[i] + 1, cons[i] + 2);

for (int i = 1; i <= K; i ++)

for (int j = 1; j <= K; j ++)

if (i != j && cons[i][2] + f[cons[i][0]][cons[i][1]] + f[cons[i][1]][cons[j][0]] <= cons[j][2])

g[i].push_back(j);

int ans = K;

for (int i = 1; i <= K; i ++) {

memset(used, 0, sizeof used);

ans -= hungary(i);

}

printf("%d\n", ans);

return 0;

}

求直线外一点与凸包切点

//8.13 2021NowcoderTraining_816_J

#include

using namespace std;

#define int long long

typedef pair pii;

const int INF = 1e9;

struct Point {

int x, y;

Point(): x(0), y(0) {}

Point(int x, int y): x(x), y(y) {}

int det(const Point &u) { return x * u.y - y * u.x; }

};

bool operator<(const Point &u, const Point &v) { return u.x == v.x ? u.y < v.y : u.x < v.x; }

bool operator>(const Point &u, const Point &v) { return u.x == v.x ? u.y > v.y : u.x > v.x; }

Point operator-(const Point &u, const Point &v) { return Point(u.x - v.x, u.y - v.y); }

struct Convex {

int n;

vector a, upper, lower;

void Init(int _n) {

a.resize(_n);

n = _n;

int mn = 0;

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

scanf("%lld%lld", &a[i].x, &a[i].y);

if (a[i] < a[mn]) mn = i;

}

rotate(a.begin(), a.begin() + mn, a.end());

int ptr = 0;

for (int i = 1; i < n; ++i) if (a[ptr] < a[i]) ptr = i;

for (int i = 0; i <= ptr; ++i) lower.push_back(a[i]);

for (int i = ptr; i < n; ++i) upper.push_back(a[i]);

upper.push_back(a[0]);

}

int sign(int x) { return x < 0 ? -1 : x > 0; }

void update_tangent(const Point &p, int id, int &i0, int &i1) {

if ((a[i0] - p).det(a[id] - p) > 0) i0 = id;

if ((a[i1] - p).det(a[id] - p) < 0) i1 = id;

}

void binary_search(int l, int r, Point p, int &i0, int &i1) {

if (l == r) return;

update_tangent(p, l % n, i0, i1);

int sl = sign((a[l % n] - p).det(a[(l + 1) % n] - p));

for (; l + 1 < r; ) {

int mid = (l + r) / 2;

int smid = sign((a[mid % n] - p).det(a[(mid + 1) % n] - p));

if (smid == sl) l = mid; else r = mid;

}

update_tangent(p, r % n, i0, i1);

}

pii get_tangent(Point p) {

int i0 = 0, i1 = 0;

int id = lower_bound(lower.begin(), lower.end(), p) - lower.begin();

binary_search(0, id, p, i0, i1);

binary_search(id, (int)lower.size(), p, i0, i1);

id = lower_bound(upper.begin(), upper.end(), p, greater()) - upper.begin();

binary_search((int)lower.size() - 1, (int)lower.size() - 1 + id, p, i0, i1);

binary_search((int)lower.size() - 1 + id, (int)lower.size() - 1 + (int)upper.size(), p, i0, i1);

return pii(i0, i1);

}

} con;

const int N = 2e5 + 10;

int n, m;

int f[N][20], d[N][20];

signed main() {

scanf("%lld%lld", &n, &m);

con.Init(n);

for (int i = 1, x, y; i <= m; ++i) {

scanf("%lld%lld", &x, &y);

pii tmp = con.get_tangent(Point(x, y));

if (tmp.second < tmp.first) tmp.second += n;

}

}