头像

Protein

OIer




离线:4小时前


新鲜事 原文

Protein
4天前
骚断腿
图片 图片



Protein
7天前

Blog

题目

Luogu
LOJ
Acwing

思路

001.png 002.png

代码

貌似在 $Acwing$ 上要吸臭氧

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
const int N = 100010;
set<int> G[N];
int T, fa[N], id[N], sz[N], cnt, now;
bool cmp(int a, int b) { return sz[a] < sz[b]; }
inline bool check(int a, int b, int c, int d) {
    int n = b - a + 1, m = d - c + 1;
    if (n > m) return false;
    for (int i = 0; i < m; i++) {
        int x = a + i % n, y = c + i;
        if (G[y].find(x) == G[y].end()) return false;
        else now++;
    }
    return true;
}
int main() {
    cin >> T;
    for (int n, m; T--; ) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) G[i].clear();
        memset(fa, 0, sizeof fa), memset(sz, 0, sizeof sz);
        cnt = 0, now = 0;
        bool flag = true;
        for (int a, b; m--; ) {
            scanf("%d%d", &a, &b);
            if (a > b) swap(a, b);
            if (a == b || G[b].find(a) != G[b].end()) flag = false;
            else G[b].insert(a), cnt++; // 这里反着连边
        }
        for (int i = 1; i < n && flag; i++) {
            if (G[i].empty()) flag = false;
            else fa[i] = *G[i].rbegin();
        }
        for (int i = 0; i < n; i++) sz[i] = 1;
        for (int i = n - 1; i >= 1; i--) sz[fa[i]] += sz[i];
        for (int i = 0; i < n; i++) id[i] = i;
        sort(id, id + n, cmp);
        for (int i = 0; i < n - 1 && flag; i++) {
            int u = fa[id[i]], v = id[i];
            if (!check(u, v - 1, v, v + sz[v] - 1)) flag = false;
        }
        if (flag && cnt == now) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}



Protein
7天前

Blog

题目

Luogu
LOJ
Acwing

思路

001.png
002.png
003.png

代码

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int N = 3010, p = 2333;
int T, n, m;
short c[N][N], f[N][N];
int Lucas(int a, int b) {
    if (a < p && b < p) return c[a][b];
    return Lucas(a / p, b / p) * c[a % p][b % p] % p;
}
int C(int a, int b) { return Lucas(a, b); }
int F(int n, int k) {
    if (n < p && k < p) return f[n][k];
    return (F(n % p, p - 1) * F(n / p, (k / p) - 1) % p + 
            C(n / p, k / p) * F(n % p, k % p) % p) % p;
}
signed main() {
    scanf("%d", &T);
    for (int i = 0; i <= 3000; i++)
        for (int j = 0; j <= i; j++)
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % p;
    for (int i = 0; i <= 3000; i++)
        for (int j = 0; j <= 3000; j++)
            if (!j) f[i][j] = 1;
            else f[i][j] = (f[i][j - 1] + c[i][j]) % p;
    while (T-- && scanf("%lld%lld", &n, &m)) printf("%d\n", F(n, m));
    return 0;
}



Protein
7天前

Blog

题目

Luogu
LOJ
Acwing

思路

001.png 002.png 003.png

代码

#include <iostream>
#include <cstring>
#define int long long
using namespace std;
const int N = 3010;
int n, m, f[N][N], s[N], q[N];
int K(int a, int b, int j) { 
    int y1 = f[a][j - 1] + s[a] * s[a], x1 = s[a];
    int y2 = f[b][j - 1] + s[b] * s[b], x2 = s[b];
    return (y1 - y2) / (x1 - x2);
}
signed main() {
    cin >> n >> m;
    for (int i = 1, t; i <= n; i++)
        cin >> t, s[i] = s[i - 1] + t;
    for (int i = 1; i <= n; i++) f[i][1] = s[i] * s[i];
    for (int j = 2; j <= m; j++) {
        int hh = 0, tt = -1;
        for (int i = 1; i <= n; i++) {
            while (hh + 1 <= tt && K(q[hh], q[hh + 1], j) < 2 * s[i]) hh++;
            f[i][j] = f[q[hh]][j - 1] + (s[i] - s[q[hh]]) * (s[i] - s[q[hh]]);
            while (hh + 1 <= tt && K(q[tt - 1], q[tt], j) > K(q[tt], i, j)) tt--;
            q[++tt] = i;
        }
    }
    cout << f[n][m] * m - s[n] * s[n] << endl;
    return 0;
}



Protein
13天前

Blog

题目

Luogu
LOJ
Acwing

思路

001.png

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
const int N = 410, M = 200010, INF = 1e18;
int n, m, S, T, A[N], B[N], C[N];
int h[N], val[M], ptr[M], f[M], w[M], idx;
void add(int a, int b, int c, int d) { val[idx] = b, f[idx] = c, w[idx] = d, ptr[idx] = h[a], h[a] = idx++; }
void add(int a, int b, int c, int d, int e) { add(a, b, c, e), add(b, a, d, -e); }
bool check(int x, int y) {
    if (x < y) swap(x, y);
    if (x % y != 0 || x == y) return false;
    int t = x / y;
    for (int i = 2; i <= t / i; i++)
        if (t % i == 0) return false;
    return true;
}
int q[N], d[N], pre[M], incf[N], st[N];
// 最大费用最大流
bool SPFA() {
    int hh = 0, tt = 0;
    memset(d, -0x3f, sizeof d), memset(incf, 0, sizeof incf);
    q[tt++] = S, incf[S] = INF, d[S] = 0, st[S] = true;
    while (hh != tt) {
        int t = q[hh++];
        if (hh == N - 1) hh = 0;
        st[t] = false;
        for (int i = h[t], v = val[i]; i != -1; i = ptr[i], v = val[i]) {
            if (f[i] && d[v] < d[t] + w[i]) {
                d[v] = d[t] + w[i], pre[v] = i;
                incf[v] = min(incf[t], f[i]);
                if (st[v]) continue;
                q[tt++] = v, st[v] = true;
                if (tt == N - 1) tt = 0;
            }
        }
    } 
    return incf[T] > 0;
}
int EK() {
    int flow = 0, cost = 0;
    while (SPFA()) {
        int t = incf[T];
        if (cost + d[T] * t < 0) {
            flow += (cost / (-d[T]));
            return flow;
        } else cost += d[T] * t, flow += t;
        for (int i = T; i != S; i = val[pre[i] ^ 1]) 
            f[pre[i]] -= t, f[pre[i] ^ 1] += t;
    }
    return flow;
}
signed main() {
    cin >> n;
    memset(h, -1, sizeof h);
    S = 2 * n + 1, T = n * 2 + 2;
    for (int i = 1; i <= n; i++) cin >> A[i];
    for (int i = 1; i <= n; i++) cin >> B[i];
    for (int i = 1; i <= n; i++) cin >> C[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (check(A[i], A[j])) 
                add(i, j + n, INF, 0, C[i] * C[j]);

    for (int i = 1; i <= n; i++) add(S, i, B[i], 0, 0);
    for (int i = 1; i <= n; i++) add(n + i, T, B[i], 0, 0);

    cout << EK() / 2 << endl;
    return 0;
}



Protein
14天前

Blog

题目

Luogu
LOJ
Acwing

思路

001.png 002.png

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 65;
int f[N][2][2][2], g[N][2][2][2], T;
signed main() {
    cin >> T;
    for (int n, m, k, p; T-- && cin >> n >> m >> k >> p; ) {
        memset(f, 0, sizeof f), memset(g, 0, sizeof g), g[61][1][1][1] = 1;
        for (int i = 60; i >= 0; i--) {
            int q = (n >> i) & 1, w = (m >> i) & 1, e = (k >> i) & 1;
            for (int a = 0; a < 2; a++) 
                for (int b = 0; b < 2; b++)
                    for (int c = 0; c < 2; c++)
                        if (f[i + 1][a][b][c] || g[i + 1][a][b][c])
                            for (int x = 0; x < 2; x++) 
                                for (int y = 0; y < 2; y++) {
                                    int z = x ^ y;
                                    if ((a && x > q) || (b && y > w) || (c && z < e)) continue;
                                    int s = (a && x == q), u = (b && y == w), v = (c && z == e);
                                    g[i][s][u][v] = (g[i][s][u][v] + g[i + 1][a][b][c]) % p;
                                    f[i][s][u][v] = (f[i][s][u][v] + f[i + 1][a][b][c] + 
                                                     (z - e + p) % p * 
                                                     ((1ll << i) % p) % p * 
                                                     g[i + 1][a][b][c] % p) % p;
                                }
        }
        cout << f[0][0][0][0] << endl;
    }
    return 0;
}



Protein
14天前

Blog

题目

Luogu
LOJ
Acwing

思路

001.png
002.png
003.png
004.png
005.png
006.png

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int N = 110, mod = 1e9 + 7;
int n, m, k, T[N], C[N][N], X[N][N], g[N];
int u[N], r[N];
int qmi(int a, int b) {
    int res = 1 % mod;
    for (; b; b >>= 1, a = a * a % mod)
        if (b & 1) res = res * a % mod;
    return res;
}
int inv(int x) { return qmi(x, mod - 2); }
signed main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) cin >> u[i];
    for (int i = 1; i <= m; i++) cin >> r[i];
    for (int i = 0; i <= 100; i++) 
        for (int j = 0; j <= i; j++)
            if (!j) C[i][j] = 1;
            else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            int s = 0;
            for (int t = 0; t <= j - 1; t++) 
                s = (s + C[j + 1][t] * X[i][t] % mod) % mod;
            X[i][j] = ((qmi(u[i] + 1, j + 1) - 1 - s) % mod + mod) % mod *
                       inv(j + 1) % mod;
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int t = 0; t <= r[i] - 1; t++) {
            T[i] = (T[i] + qmi(-1, t) * C[r[i] - 1][t] % mod * 
                    qmi(u[i], r[i] - t - 1) % mod * 
                    X[i][n - r[i] + t] % mod);
        }
    }
    for (int k = 1; k <= n; k++) {
        g[k] = C[n - 1][k];
        for (int i = 1; i <= m; i++) {
            g[k] = g[k] * C[n - 1 - k][n - r[i] - k] % mod * T[i] % mod;
        }
    }
    int res = 0;
    for (int i = k; i <= n; i++)
        res = (res + qmi(-1, i - k) * C[i][k] % mod * g[i] % mod) % mod;
    cout << (res + mod) % mod << endl;
    return 0;
}


新鲜事 原文

Protein
19天前
这几天高考放假, 感觉很爽, 适合刷题 立下flag: 今天刷五道题: Acwing2972「JLOI / SHOI2016」成绩比较 Acwing2793「SHOI2016」黑暗前的幻想乡 Acwing2794「SHOI2016」随机序列 Acwing2569「SDOI2016」储能表 Acwing2570「SDOI2016」数字配对



Protein
21天前

Blog

题目

Luogu
LOJ
Acwing

思路

001.png
002.png
003.png

代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1000010, M = 2010, S = 1e6 + 7, mod = 1e8 + 7;
int n, m, k;
// Begin Hash
int h[S], ptr[M], idx;
struct NODE { int x, y; } val[M], p[M];
inline bool find(int x, int y) {
    int t = (1ll * x * 101 + y) % S;
    for (int i = h[t]; i != -1; i = ptr[i])
        if (val[i].x == x && val[i].y == y) return true;
    return false;
}
inline void insert(int a, int b) { 
    int x = (1ll * a * 101 + b) % S;
    val[idx] = (NODE) { a, b }, ptr[idx] = h[x], h[x] = idx++;
}
// End Hash
// Begin inv
inline int qmi(int a, int b) {
    int res = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod)
        if (b & 1) res = 1ll * res * a % mod;
    return res;
}
inline int inv(int x) { return qmi(x, mod - 2); }
// End inv
// Begin calculate
inline int calc_f0() {
    int res = 0;
    for (int i = 1; i <= min(n, m); i++)
        res = (res + 1ll * (n - i + 1) * (m - i + 1) % mod * i % mod) % mod;
    return res;
}
inline int calc(int l, int r, int h) {
    int t = min(l + r, h);
    if (!t) return 0;
    int res = 1ll * t * (t + 3) % mod * inv(2) % mod;
    if (t > l) res -= 1ll * (t - l) * (t - l + 1) % mod * inv(2) % mod;
    if (t > r) res -= 1ll * (t - r) * (t - r + 1) % mod * inv(2) % mod;
    return (res % mod + mod) % mod;
}
inline int calc_f1(NODE t) {
    int a = n - t.x, b = m - t.y, c = t.x, d = t.y;
    int res = (calc(a, c, b) + calc(a, c, d) + calc(b, d, a) + calc(b, d, c)) % mod;
    res -= (min(a, b) + min(b, c) + min(c, d) + min(a, d)) % mod;
    return (res % mod + mod) % mod;
}
NODE rotate(NODE a) { return { a.y, -a.x }; }
NODE operator+(NODE a, NODE b) { return { a.x + b.x, a.y + b.y }; }
NODE operator-(NODE a, NODE b) { return { a.x - b.x, a.y - b.y }; }
NODE operator/(NODE a, int b) { return { a.x / b, a.y / b }; }
inline bool inside(NODE a) { return a.x >= 0 && a.x <= n && a.y >= 0 && a.y <= m; }
inline bool check(NODE a, NODE b) { return inside(a) && inside(b); }
// 如果除以二之后都是整数, 说明在格点上
inline bool on_point(NODE a) { return ((!(a.x & 1)) && (!(a.y & 1))); }
inline int find(NODE x) { return find(x.x, x.y); }
inline int calc_f2(NODE a, NODE b) {
    NODE t = rotate(a - b);
    // a, b 连线作为边长的情况
    int res = check(a + t, b + t) + check(a - t, b - t);
    // a, b 连线作为对角线的情况
    // 真正的另外两个点是 ta / 2, tb / 2
    NODE mid = a + b, ta = mid + t, tb = mid - t;
    if (on_point(ta) && on_point(tb) && check(ta / 2, tb / 2)) res++;
    return res;
}
inline int calc_f3(NODE a, NODE b) {
    NODE t = rotate(a - b);
    int res = 0;
    if (check(a + t, b + t)) res += find(a + t) + find(b + t);
    if (check(a - t, b - t)) res += find(a - t) + find(b - t);
    NODE mid = a + b, ta = mid + t, tb = mid - t;
    if (on_point(ta) && on_point(tb) && check(ta / 2, tb / 2)) 
        res += find(ta / 2) + find(tb / 2);
    return res;
}
inline int calc_f4(NODE a, NODE b) {
    NODE t = rotate(a - b);
    int res = 0;
    if (check(a + t, b + t)) res += (find(a + t) && find(b + t));
    if (check(a - t, b - t)) res += (find(a - t) && find(b - t));
    NODE mid = a + b, ta = mid + t, tb = mid - t;
    if (on_point(ta) && on_point(tb) && check(ta / 2, tb / 2)) 
        res += (find(ta / 2) && find(tb / 2));
    return res;
}
// End calculate
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;
    memset(h, -1, sizeof h);
    // if (n > m) swap(n, m);
    for (int i = 1; i <= k; i++) 
        cin >> p[i].x >> p[i].y, insert(p[i].x, p[i].y);
    int f0 = calc_f0(), f1 = 0, f2 = 0, f3 = 0, f4 = 0;
    for (int i = 1; i <= k; i++) 
        f1 = (f1 + calc_f1(p[i])) % mod;
    for (int i = 1; i <= k; i++) {
        for (int j = i + 1; j <= k; j++) {
            f2 = (f2 + calc_f2(p[i], p[j])) % mod;
            f3 = (f3 + calc_f3(p[i], p[j])) % mod;
            f4 = (f4 + calc_f4(p[i], p[j])) % mod;
        }
    }
    f3 = 1ll * f3 * inv(3) % mod, f4 = 1ll * f4 * inv(6) % mod;
    int res = ((f0 - f1 + f2 - f3 + f4) % mod + mod) % mod;
    cout << res << endl;
    return 0;
}



Protein
22天前

Blog

题目

Luogu
LOJ
Acwing

思路

001.png
002.png
003.png
004.png

代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 500010, M = 22;
int n, m, d, w[N], st[N];
int h[N], val[N << 1], ptr[N << 1], idx;
int f[N][M], g[N][M];
void add(int a, int b) { val[idx] = b, ptr[idx] = h[a], h[a] = idx++; }
void DFS(int u, int fa) {
    if (st[u]) f[u][0] = g[u][0] = w[u];
    else f[u][0] = g[u][0] = 0;
    for (int i = 1; i <= d; i++) f[u][i] = w[u];
    f[u][d + 1] = 0x3f3f3f3f;
    for (int i = h[u], v = val[i]; i != -1; i = ptr[i], v = val[i]) {
        if (v == fa) continue;
        DFS(v, u);
        // 这里当 j == d 的时候, f[u][j + 1] 即 f[u][d + 1] = INF
        for (int j = d; j >= 0; j--)
            f[u][j] = min(f[u][j] + g[v][j], g[u][j + 1] + f[v][j + 1]);
        for (int j = d; j >= 0; j--) f[u][j] = min(f[u][j], f[u][j + 1]);
        g[u][0] = f[u][0];
        for (int j = 1; j <= d + 1; j++) g[u][j] += g[v][j - 1];
        for (int j = 1; j <= d + 1; j++) g[u][j] = min(g[u][j], g[u][j - 1]);
    }
}
int main() {
    cin >> n >> d;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++) cin >> w[i];
    cin >> m;
    for (int i = 1, t; i <= m; i++) 
        cin >> t, st[t] = true;
    for (int i = 1, a, b; i < n; i++)
         cin >> a >> b, add(a, b), add(b, a);
    DFS(1, 0);
    cout << f[1][0] << endl;
    return 0;
}