九尾妖狐

网络流的二元关系建图

~~有一种神奇的可以消除奇环的构图方法~~

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e7 + 10;
int head[N], rest[N], to[N], flow[N], tot = 1;
void sig(int u, int v, int w) {
    to[++ tot] = v, flow[tot] = w, rest[tot] = head[u], head[u] = tot;
}
void add(int u, int v, int w) {
    sig(u, v, w), sig(v, u, 0);
}
int n, m, cnt, dis[N], S, T; ll ans;
int bfs() {
    for(int i = 1 ; i <= cnt ; ++ i) dis[i] = -1;
    queue<int> q;
    q.push(S), dis[S] = 1;
    while(q.size()) {
        int u = q.front(); q.pop(); 
        for(int i = head[u] ; i ; i = rest[i]) {
            int v = to[i];
            if(dis[v] == -1 && flow[i]) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
    return dis[T] != -1;
}
int dfs(int u, int f) {
    if(u == T || !f) return f;
    int use = 0;
    for(int i = head[u] ; i ; i = rest[i]) {
        int v = to[i];
        if(flow[i] && dis[v] == dis[u] + 1) {
            int a = dfs(v, min(f - use, flow[i]));
            flow[i] -= a, flow[i ^ 1] += a;
            use += a;
            if(use == f) break;
        }
    }
    if(!use) dis[u] = -1;
    return use;
}
int main() {
    scanf("%d%d", &n, &m);
    S = ++ cnt, T = ++ cnt;
    for(int i = 1, a, b ; i <= n ; ++ i) {
        scanf("%d%d", &a, &b);
        int x = ++ cnt;
        add(S, x, a);
        add(x, T, b);
        ans += a + b;
    }
    for(int i = 1, u, v, a, b, c ; i <= m ; ++ i) {
        scanf("%d%d%d%d%d", &u, &v, &b, &a, &c);
        u += 2, v += 2;
        int x = ++ cnt, y = ++ cnt;
        add(S, x, a); add(x, u, a); add(x, v, a);
        add(u, y, b); add(v, y, b); add(y, T, b);
        add(u, v, c); add(v, u, c);
        ans += a + b;
    }
    while(bfs()) {
        ans -= dfs(S, 0x3f3f3f3f);
    }
    printf("%lld\n", ans);
}

皮城女警

~~数据范围这么小……怕是暴力好题……~~

首先如果有 $r$ 行是 $1$，$c$ 行是 $1$，那么实际的 $s$ 是 $r(m-c)+c(n-r)$

即 $s=rm+cn-2rc=rm+c(n-2r)$

可以这么理解：只有行列相反的会在交点处产生 $1$ 的贡献

由于数据范围只有 $10^5$，所以可以暴力枚举 $r$，然后可以计算出来 $c$

但这里有个分类讨论，就是 $n-2r$ 是否为 $0$

如果 $n-2r=0$，那么意味着列可以随便填，方案数就是把 $n$ 行搞成有 $r$ 行 $1$ 的方案数，这个组合数搞一搞就行了

否则 $c$ 就是唯一确定了，依然组合数搞一搞就行了

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

const ll mod = 1e9 + 7, T = 2e5, N = T + 10;

ll ans, n, m, R, C, S, fac[N], invfac[N];

ll pw(ll a, ll b) {
    ll r = 1;
    for(a %= mod ; b ; b >>= 1, a = a * a % mod)
        if(b & 1)
            r = r * a % mod;
    return r;    
}

ll calc(ll n, ll m) {
    return n < m ? 0 : fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}

ll poi(ll n, ll k) {
    return calc(n + k - 1, n - 1);
}

void sol(ll r, ll c) {
    ll res = calc(n, r) * calc(m, c) % mod;
    r = R - r, c = C - c;
    if(r % 2 || c % 2) return ;
    res = res * poi(n, r / 2) % mod * poi(m, c / 2) % mod;
    ans = (ans + res) % mod;
}

int main() {cin >> n >> m >> R >> C >> S;
    fac[0] = invfac[0] = 1;
    for(ll i = 1 ; i <= T ; ++ i) fac[i] = fac[i - 1] * i % mod;
    invfac[T] = pw(fac[T], mod - 2);
    for(ll i = T - 1 ; i ; -- i) invfac[i] = invfac[i + 1] * (i + 1) % mod;
    for(ll r = 0 ; r <= min(n, R) ; ++ r) {
        ll c = S - r * m;
        if(n - 2 * r == 0) {
            if(r * m == S) {
                ll res = calc(n, r);
                if((R - r) % 2) continue;
                res = res * poi(n, (R - r) / 2) % mod * poi(m, C) % mod;
                ans = (ans + res) % mod;
            }
        } else if(c % (n - 2 * r) == 0) {
            c /= n - 2 * r;
            if(0 <= c && c <= min(C, m)) {
                sol(r, c);
            }
        }
    }
    cout << (ans % mod + mod) % mod << endl;
}

不祥之刃

~~怕是这场比赛最水的题了~~

由于小学僧贡献的法强都是 $1$，所以可以直接用小根堆维护当前位置所有击杀的小学僧的金币

如果遇到盲僧，就一直弹堆顶直到堆的大小严格小于当前的权值

然后就做完了？？？

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;

ll ans;
int n, m;
priority_queue<int, vector<int>, greater<int> > pq;

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1, x ; i <= n ; ++ i) {
        char op[5]; scanf("%s%d", op, &x);
        if(op[0] == 'd') {
            pq.push(x);
        } else {
            while(pq.size() >= x) pq.pop();
        }
    }
    if(pq.size() >= m) {
        while(pq.size()) ans += pq.top(), pq.pop();
        printf("%lld\n", ans);
    } else puts("-1");
}