头像

MILLOPE

jzyz


访客:17514

离线:8个月前


活动打卡代码 AcWing 373. 車的放置

MILLOPE
8个月前
#include <bits/stdc++.h> 

using namespace std; 

const int N = 250; 
const int M = N * N; 

template <typename T> inline void read(T &s) {
    s = 0; T w = 1, ch = getchar(); 
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); } 
    while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); } 
    s *= w; 
}

int n, m, t; 
int match[N]; 
int a[N][N]; 
bool vis[N]; 

bool dfs(int x) {
    for (int i = 1; i <= m; ++i) {
        if (a[x][i]) continue; 
        if (!vis[i]) {
            vis[i] = true; 
            if (!match[i] || dfs(match[i])) {
                match[i] = x; 
                return true; 
            } 
        }
    }
    return false; 
}

int main() {
    read(n), read(m), read(t); 
    int x, y; 
    for (int i = 1; i <= t; ++i) {
        read(x), read(y); 
        a[x][y] = 1; 
    }
    int ans = 0; 
    for (int i = 1; i <= n; ++i) {
        memset(vis, false, sizeof(vis)); 
        if (dfs(i)) ++ans; 
    }
    printf("%d\n", ans); 
    return 0; 
}


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

MILLOPE
8个月前
#include <bits/stdc++.h> 

using namespace std; 

const int N = 120; 
const int M = N * N; 
const int dx[5] = { 0, 0, 1, -1 }; 
const int dy[5] = { 1, -1, 0, 0 }; 

template <typename T> inline void read(T &s) {
    s = 0; T w = 1, ch = getchar(); 
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
    while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); } 
    s *= w; 
}

int n, t, tot; 
int pa[M], pb[M], lin[M], match[M]; 
bool vis[M]; 
vector<int> e[M]; 

inline int get(int x, int y) { return ((x-1)*n + y); }

bool dfs(int x) {
    for (int i = 0; i < e[x].size(); ++i) {
        int y = e[x][i]; 
        if (!vis[y]) {
            vis[y] = true; 
            if (!match[y] || dfs(match[y])) {
                match[y] = x; 
                match[x] = y; 
                return true; 
            }
        }
    }
    return false; 
}

int main() {
    read(n), read(t); 
    int x, y, tmp; 
    memset(vis, false, sizeof(vis)); 
    for (int i = 1; i <= t; ++i) {
        read(x), read(y); 
        vis[get(x, y)] = true; 
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int tmp = get(i, j); 
            if (vis[tmp]) continue; 
            if ((i+j) & 1) pa[++pa[0]] = tmp; 
            else pb[++pb[0]] = tmp; 
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int tmp = get(i, j); 
            if (vis[tmp]) continue; 
            for (int k = 0; k < 4; ++k) {
                int x = i + dx[k], y = j + dy[k]; 
                int cur = get(x, y); 
                if (x < 1 || x > n || y < 1 || y > n || vis[cur]) continue; 
                e[cur].push_back(tmp); 
                e[tmp].push_back(cur); 
            }
        } 
    }
    int ans = 0; 
    for (int i = 1; i <= pa[0]; ++i) {
        memset(vis, false, sizeof(vis)); 
        if (dfs(pa[i])) ++ans; 
    }
    printf("%d\n", ans); 
    return 0; 
}


活动打卡代码 AcWing 138. 兔子与兔子

MILLOPE
8个月前
#include <bits/stdc++.h> 

using namespace std; 

typedef unsigned long long ULL; 
const int N = 1e6 + 100; 

int n, q; 
char s[N]; 
ULL h[N], p[N]; 

int main() {
    scanf("%s", s + 1); n = strlen(s + 1); 
    p[0] = 1; 
    for (int i = 1; i <= n; ++i) {
        h[i] = h[i-1] * 131 + (s[i] - 'a' + 1); 
        p[i] = p[i-1] * 131; 
    }
    scanf("%d", &q); 
    for (int i = 1; i <= q; ++i) {
        int l1, r1, l2, r2; 
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2); 
        if (h[r1] - h[l1-1] * p[r1-l1+1] == h[r2] - h[l2-1] * p[r2-l2+1]) puts("Yes"); 
        else puts("No"); 
    }
    return 0; 
}


活动打卡代码 AcWing 364. 网络

MILLOPE
8个月前
#include <bits/stdc++.h> 

using namespace std; 

template <class T> inline void read(T &s) {
    s = 0; T w = 1, ch = getchar(); 
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
    while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
    s *= w; 
}

const int N = 1e5 + 100; 
const int M = 4e5 + 100; 
const int Z = 21; 

int n, m, tot, tim, q, dcc, totc, T; 
int lin[N], dfn[N], low[N], c[N], linc[N], fa[N]; 
int f[N][Z], d[N]; 
bool bridge[M]; 
struct edge {
    int next, to; 
} e[M], ec[M]; 

inline void clean() {
    tot = 1, tim = 0, dcc = 0, totc = 1; 
    for (int i = 1; i <= n; ++i) 
        c[i] = lin[i] = linc[i] = dfn[i] = low[i] = 0; 
    memset(bridge, false, sizeof(bridge)); 
}

inline void add(int from, int to) {
    e[++tot].to = to; 
    e[tot].next = lin[from]; 
    lin[from] = tot; 
}

void tarjan(int u, int in_edge) {
    dfn[u] = low[u] = ++tim; 
    for (int i = lin[u]; i; i = e[i].next) {
        int v = e[i].to; 
        if (!dfn[v]) {
            tarjan(v, i); 
            low[u] = min(low[u], low[v]); 
            if (low[v] > dfn[u]) 
                bridge[i] = bridge[i ^ 1] = true; 
        }
        else if (i != (in_edge ^ 1)) 
            low[u] = min(low[u], dfn[v]); 
    }
}

void dfs(int u) {
    c[u] = dcc; 
    for (int i = lin[u]; i; i = e[i].next) {
        int v = e[i].to; 
        if (bridge[i] || c[v]) continue; 
        dfs(v); 
    }
}

inline void addc(int from, int to) {
    ec[++totc].to = to; 
    ec[totc].next = linc[from]; 
    linc[from] = totc; 
}

void bfs() {
    memset(d, 0, sizeof(d)); 
    memset(f, 0, sizeof(f)); 
    queue<int> q; 
    q.push(1); d[1] = 1; 
    while (!q.empty()) {
        int u = q.front(); q.pop(); 
        for (int i = linc[u]; i; i = ec[i].next) {
            int v = ec[i].to; 
            if (d[v]) continue; 
            d[v] = d[u] + 1; 
            f[v][0] = u; 
            for (int j = 1; j < 20; ++j) 
                f[v][j] = f[f[v][j - 1]][j - 1]; 
            q.push(v); 
        }
    }
}

int lca(int x, int y) {
    if (d[x] < d[y]) swap(x, y); 
    for (int i = 19; i >= 0; --i) {
        if (d[f[x][i]] >= d[y]) x = f[x][i]; 
    }
    if (x == y) return x; 
    for (int i = 19; i >= 0; --i) {
        if (f[x][i] != f[y][i]) 
            x = f[x][i], y = f[y][i]; 
    }
    return f[x][0]; 
}

inline int get(int x) {
    return fa[x] == x ? x : fa[x] = get(fa[x]); 
}

int main() {
//  freopen("1.in", "r", stdin); 

    while (true) {
        read(n), read(m); 
        if (!n || !m) break; 
        clean(); 
        for (int i = 1; i <= m; ++i) {
            int x, y; read(x), read(y); 
            add(x, y); add(y, x); 
        }
        for (int i = 1; i <= n; ++i) {
            if (!dfn[i]) tarjan(i, 0); 
        }
        for (int i = 1; i <= n; ++i) {
            if (!c[i]) {
                ++dcc, dfs(i); 
            }
        }
        for (int i = 2; i <= tot; ++i) {
            int x = e[i].to, y = e[i ^ 1].to; 
            if (c[x] == c[y]) continue; 
            addc(c[x], c[y]); 
        }
        bfs(); 
        for (int i = 1; i <= dcc; ++i) fa[i] = i; 
        int ans = dcc - 1; 
        read(q); 
        printf("Case %d:\n", ++T); 
        while (q--) {
            int x, y; read(x), read(y); 
            x = c[x], y = c[y]; 
            int p = lca(x, y); 
            x = get(x); 
            while (d[x] > d[p]) {
                fa[x] = f[x][0]; 
                ans--; 
                x = get(x); 
            }
            y = get(y); 
            while (d[y] > d[p]) {
                fa[y] = f[y][0]; 
                ans--; 
                y = get(y); 
            }
            printf("%d\n", ans); 
        }
        puts(""); 
    }
    return 0; 
}



MILLOPE
8个月前
#include <bits/stdc++.h> 

using namespace std; 

const int N = 150; 
const int INF = 0x3f3f3f3f; 

int n, m; 
int a[N][N]; 

int main() {
    memset(a, 0x3f, sizeof(a)); 
    scanf("%d%d", &n, &m); 
    for (int i = 1; i <= m; ++i) {
        int x, y; scanf("%d%d", &x, &y); 
        a[x][y] = a[y][x] = 1; 
    }
    for (int i = 1; i <= n; ++i) a[i][i] = 0; 
    for (int k = 1; k <= n; ++k) 
        for (int i = 1; i <= n; ++i) 
            for (int j = 1; j <= n; ++j) 
                if (a[i][j] > a[i][k] + a[k][j]) 
                    a[i][j] = a[i][k] + a[k][j]; 
    int ans = -1; 
    for (int i = 1; i <= n; ++i) 
        for (int j = 1; j <= n; ++j) 
            if (a[i][j] != INF)
                ans = max(ans, a[i][j]); 
    printf("%d\n", ans); 
    return 0; 
}


活动打卡代码 AcWing 217. 绿豆蛙的归宿

MILLOPE
8个月前
#include <bits/stdc++.h> 
using namespace std; 
const int maxn = 1e5 + 100; 
typedef long long ll; 

int n, m, tot; 
int lin[maxn], deg[maxn], out[maxn]; 
double dis[maxn]; 
struct edge {
    int next, to, dis; 
} e[maxn << 1]; 

inline void add(int from, int to, int dis) {
    e[++tot].to = to; 
    e[tot].dis = dis; 
    e[tot].next = lin[from]; 
    lin[from] = tot; 
}

int main() {
    scanf("%d%d", &n, &m); 
    for (int i = 1; i <= m; ++i) {
        int x, y, z; scanf("%d%d%d", &x, &y, &z); 
        add(y, x, z); 
        deg[x]++, out[x]++; 
    }
    queue<int> q; 
    q.push(n); 
    while (!q.empty()) {
        int u = q.front(); q.pop(); 
        // cout << u << endl; 
        for (int i = lin[u]; i; i = e[i].next) {
            int v = e[i].to; 
            dis[v] += (dis[u] + e[i].dis) / deg[v]; 
            out[v]--; 
            if (!out[v]) q.push(v); 
        }
    }
    printf("%.2lf\n", dis[1]); 
    return 0; 
}


活动打卡代码 AcWing 216. Rainbow的信号

MILLOPE
8个月前
#include <bits/stdc++.h> 
using namespace std; 
const int maxn = 1e5 + 100; 

template <typename T> 
inline void read(T &s) {
    s = 0; T w = 1, ch = getchar(); 
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
    while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
    s *= w; 
}

int n;
double ansand, ansor, ansxor; 
int a[maxn]; 

void sol(int k) {
    int last[2] = { 0, 0 }, c1 = 0, c2 = 0; 
    double w = (double)(1 << k) / n / n; 
    for (int i = 1, b; i <= n; ++i) {
        // if (b[i]) swap(c1, c2); 
        b = ((a[i] >> k) & 1); 
        if (b) {
            ansand += w, ansxor += w, ansor += w; 
        }
        if (!b) {
            ansor += w * last[1] * 2; 
        }
        else {
            ansor += w * (i - 1) * 2; 
            ansand += w * ((i - 1) - (last[0] + 1) + 1) * 2; 
        }
        ansxor += w * (b ? c1 : c2) * 2; 
        c1++; 
        if (b) swap(c1, c2); 
        last[b] = i; 
    }
}

int main() {
    read(n); 
    for (int i = 1; i <= n; ++i) read(a[i]); 
    for (int i = 0; i < 31; ++i) sol(i); 
    printf("%.3lf %.3lf %.3lf\n", ansxor, ansand, ansor); 
    return 0; 
}


活动打卡代码 AcWing 354. 天天爱跑步

MILLOPE
8个月前
#include <bits/stdc++.h> 
using namespace std; 
const int maxn = 3e5 + 100; 

template <class T> 
inline void read(T &s) {
    s = 0; T w = 1, ch = getchar(); 
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
    while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
    s *= w; 
}

int n, m, tot; 
int lin[maxn], dep[maxn], w[maxn], f[maxn][20]; 
struct edge {
    int next, to; 
} e[maxn << 1]; 
int c1[maxn * 2], c2[maxn * 2], ans[maxn]; 
vector<int> a1[maxn], b1[maxn], a2[maxn], b2[maxn]; 
bool vis[maxn]; 

inline void add(int from, int to) {
    e[++tot].to = to; 
    e[tot].next = lin[from]; 
    lin[from] = tot; 
}

void bfs(int st) {
    queue<int> q; 
    q.push(st); dep[st] = 1; 
    while (!q.empty()) {
        int u = q.front(); q.pop(); 
        for (int i = lin[u]; i; i = e[i].next) {
            int v = e[i].to; 
            if (dep[v]) continue; 
            dep[v] = dep[u] + 1; 
            f[v][0] = u; 
            for (int j = 1; j < 20; ++j) 
                f[v][j] = f[f[v][j - 1]][j - 1]; 
            q.push(v); 
        }
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y); 
    for (int j = 19; j >= 0; --j) 
        if (dep[f[x][j]] >= dep[y])
            x = f[x][j]; 
    if (x == y) return x; 
    for (int j = 19; j >= 0; --j) 
        if (f[x][j] != f[y][j])
            x = f[x][j], y = f[y][j]; 
    return f[x][0]; 
}

void dfs(int u) {
    vis[u] = true; 
    int val1 = c1[w[u] + dep[u]], val2 = c2[w[u] - dep[u] + n]; 
    for (int i = lin[u]; i; i = e[i].next) {
        int v = e[i].to; 
        if (vis[v]) continue; 
        dfs(v); 
    }
    for (int i = 0; i < a1[u].size(); ++i) c1[a1[u][i]]++; 
    for (int i = 0; i < b1[u].size(); ++i) c1[b1[u][i]]--; 
    for (int i = 0; i < a2[u].size(); ++i) c2[a2[u][i] + n]++; 
    for (int i = 0; i < b2[u].size(); ++i) c2[b2[u][i] + n]--; 
    ans[u] += c1[w[u] + dep[u]] - val1 + c2[w[u] - dep[u] + n] - val2; 
}

int main() {
    read(n), read(m); 
    for (int i = 1; i < n; ++i) {
        int x, y; read(x), read(y); 
        add(x, y), add(y, x); 
    }
    for (int i = 1; i <= n; ++i) read(w[i]); 
    bfs(1); 
    for (int i = 1; i <= m; ++i) {
        int x, y, z; read(x), read(y); 
        z = lca(x, y); 
        a1[x].push_back(dep[x]); 
        b1[f[z][0]].push_back(dep[x]); 
        a2[y].push_back(dep[x] - 2 * dep[z]); 
        b2[z].push_back(dep[x] - 2 * dep[z]); 
    }
    dfs(1); 
    for (int i = 1; i <= n; ++i) 
        printf("%d ", ans[i]); 
    return 0; 
}


活动打卡代码 AcWing 280. 陪审团

MILLOPE
8个月前
#include <bits/stdc++.h> 
using namespace std; 
const int maxn = 22; 
const int maxm = 850; 
const int maxz = 220; 

int n, m, suma, sumb; 
int a[maxz], b[maxz]; 
int f[maxn][maxm]; 
int p[maxz][maxn][maxm]; 
vector<int> c; 

void get_path(int i, int j, int k) {
    if (!j) return ; 
    int last = p[i][j][k]; 
    get_path(last - 1, j - 1, k - (a[last] - b[last])); 
    c.push_back(last); 
    suma += a[last]; 
    sumb += b[last]; 
}

int main() {
    int T = 0; 
    while (cin >> n >> m && n && m) {
        for (int i = 1; i <= n; ++i) 
            scanf("%d%d", &a[i], &b[i]); 

        memset(f, 0xcf, sizeof(f)); 
        f[0][400] = 0; 

        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) 
                for (int k = 0; k <= 800; ++k) 
                    p[i][j][k] = p[i - 1][j][k]; 
            for (int j = m; j; --j) {
                for (int k = 0; k <= 800; ++k) {
                    if (k - (a[i] - b[i]) < 0 || k - (a[i] - b[i]) > 800) continue; 
                    if (f[j][k] < f[j - 1][k - (a[i] - b[i])] + a[i] + b[i]) {
                        f[j][k] = f[j - 1][k - (a[i] - b[i])] + a[i] + b[i]; 
                        p[i][j][k] = i; 
                    }
                }
            }
        }
        int ans = 0; 
        for (int k = 0; k <= 400; ++k) {
            if (f[m][k + 400] >= 0 && f[m][k + 400] >= f[m][400 - k]) {
                ans = 400 + k; 
                break; 
            }
            if (f[m][400 - k] >= 0) {
                ans = 400 - k; 
                break; 
            }
        }
        c.clear(); 
        suma = 0; sumb = 0; 
        get_path(n, m, ans); 
        printf("Jury #%d\n", ++T); 
        printf("Best jury has value %d for prosecution and value %d for defence:\n", suma, sumb); 
        for (int i = 0; i < c.size(); ++i) 
            printf(" %d", c[i]); 
        puts("\n"); 
    }
    return 0; 
}


活动打卡代码 AcWing 279. 自然数拆分

MILLOPE
8个月前
#include <bits/stdc++.h> 
using namespace std; 
const int maxn = 4e3 + 100; 
const int mod = 2147483648u; 

int n; 
unsigned int f[maxn]; 

int main() {
    scanf("%d", &n); 
    f[0] = 1; 
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            f[j] = (f[j] + f[j - i]) % mod; 
        }
    }
    cout << (f[n] > 0 ? f[n] - 1 : 2147483647) << endl; 
    return 0; 
}