P4884 多少个1？

也是BSGS。

注意到 t = 111...111 的特殊性质 9t + 1 = 10^N。

我们将同余式两边同乘 9 +1。

没代码。

P2894 [USACO08FEB]Hotel G

很像最大子段和。

维护最长空房前缀，最长空房后缀，区间最长空房长度。

查找时分治即可。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 5e4 + 5;

class SegmentTree {
#define MID int mid = (l + r) >> 1
#define lson l, mid, x << 1
#define rson mid + 1, r, x << 1 | 1
public :
    static const int N = ::N;
    struct Node {
        int lmx, rmx, mx, l, r, lzy;
    } node[N << 4];

    void build(int l, int r, int x) {
        node[x].l = l, node[x].r = r; node[x].lzy = -1;
        if(l == r) {
            node[x].lmx = node[x].rmx = node[x].mx = 1;
            return ;
        }
        MID;
        build(lson); build(rson);
        push_up(x);
    }

    void push_up(int x) {
        const int ls = (x << 1), rs = (x << 1 | 1);
        node[x].lmx = (node[ls].mx == node[ls].r - node[ls].l + 1 ? node[ls].mx + node[rs].lmx : node[ls].lmx);
        node[x].rmx = (node[rs].mx == node[rs].r - node[rs].l + 1 ? node[rs].mx + node[ls].rmx : node[rs].rmx);
        node[x].mx = max(max(node[ls].mx, node[rs].mx), node[ls].rmx + node[rs].lmx);
    }

    void push_down(int l, int r, int x) {
        if(node[x].lzy == -1) return ;
        const int ls = x << 1, rs = x << 1 | 1;
        if(node[x].lzy == 0) {
            node[ls].lmx = node[ls].rmx = node[ls].mx = node[ls].r - node[ls].l + 1;
            node[rs].lmx = node[rs].rmx = node[rs].mx = node[rs].r - node[rs].l + 1;
        } else if(node[x].lzy == 1) {
            node[ls].lmx = node[ls].rmx = node[ls].mx = 0;
            node[rs].lmx = node[rs].rmx = node[rs].mx = 0;
        }
        node[ls].lzy = node[x].lzy; node[rs].lzy = node[x].lzy;
        node[x].lzy = -1;
    }

    int query(int l, int r, int x, int p) {
        const int ls = x << 1, rs = x << 1 | 1; push_down(l, r, x);
        MID;
        if(node[ls].mx >= p) return query(lson, p);
        if(node[ls].rmx + node[rs].lmx >= p) return node[ls].r - node[ls].rmx + 1;
        if(node[rs].mx >= p) return query(rson, p);
    }

    void modify_assign(int l, int r, int x, int p, int q, int v) {
        if(p <= l && r <= q) {
            if(v == 0) node[x].lmx = node[x].rmx = node[x].mx = r - l + 1;
            else if(v == 1) node[x].lmx = node[x].rmx = node[x].mx = 0;
            node[x].lzy = v;
            return ;
        }
        MID; push_down(l, r, x);
        if(p <= mid) modify_assign(lson, p, q, v);
        if(q > mid) modify_assign(rson, p, q, v);
        push_up(x);
    }

} st;

signed main() {
#ifdef LOCAL
    file();
#endif
    int n = rd(), m = rd();
    st.build(1, n, 1);
    for(int i = 1; i <= m; i++) {
        int opt = rd();
        if(opt == 1) {
            int x = rd();
            if(st.node[1].mx < x) puts("0");
            else {
                int s = st.query(1, n, 1, x);
                printf("%d\n", s);
                st.modify_assign(1, n, 1, s, s + x - 1, 1);
            }
        } else if(opt == 2) {
            int x = rd(), y = rd();
            st.modify_assign(1, n, 1, x, x + y - 1, 0);
        }
    }
    return 0;
}

CF1481D. AB Graph

ps. 第一次 fst 祭。C题 nm 大小不一样，非常阴险。

ps. 地图用 grid 做变量名不错。

值得一记。构造。

如果 (u, v) 和 (v, u) 相等，则反复横跳一定是回文路径。

如果 m 是奇数，那么对于任意的 (u, v)(u \neq v) u \rightarrow v \rightarrow u \rightarrow ... \rightarrow v \rightarrow u 一定是回文路径。

如果 m 是偶数，可以证明，对于 n >= 3 一定能构造出 (i, j) = (j, k)。若 m 能被 4 整除，回文路径为 abbaabba...abba 式。若被 4 除余 2，则可以构造出 aa bbaa bbaa ... bbaa 式。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 1e3 + 6;
vector<string> a;
int to[N][2];

void solve() {
    int n, m; cin >> n >> m; a.clear();
    for(int i = 0; i < n; i++) to[i][0] = to[i][1] = -1;

    for(int i = 1; i <= n; i++) {
        string tmp; cin >> tmp;
        a.push_back(tmp);
    }

    if(m % 2) {
        puts("YES");
        int u = 1;
        for(int t = 0; t <= m; t++) {
            printf("%d ", u);
            u = 3 - u;
        }
        puts("");
        return ;
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(i == j) continue;
            to[i][a[i][j] - 'a'] = j;
            if(a[i][j] == a[j][i]) {
                puts("YES");
                for(int t = 0; t <= m; t++) {
                    cout << ((t & 1) ? i + 1 : j + 1) << " ";
                }
                puts("");
                return ;
            }
        }
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(i == j) continue;
            if(to[j][a[i][j] - 'a'] == -1) continue; 
            puts("YES");
            int k = to[j][a[i][j] - 'a'];
            if(m % 4 == 0) {
                cout << j + 1 << " ";
                for(int t = 1; t <= m; t += 4) {
                    cout << k + 1 << " " << j + 1 << " " << i + 1 << " " << j + 1 << " ";
                }
                cout << endl;
            } else {
                cout << i + 1 << " " << j + 1 << " " << k + 1 << " ";
                for(int t = 3; t <= m; t += 4) {
                    cout << j + 1 << " " << i + 1 << " " << j + 1 << " " << k + 1 << " ";
                }
                cout << endl;
            }
            return ;
        }
    }
    puts("NO");
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int T = rd();
    while(T--) solve();
    return 0;
}

P1494 [国家集训队]小Z的袜子

莫队。

核心思想是通过离线，并应用某种排序方式，使得 [l_1, r_1] 的答案能够快速向 [l_2, r_2] 转移。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
#define int long long
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 1e5 + 5;
int a[N], buc[N], ans[N], ans_fm[N], u, al = 1, ar = 1;

struct Ask {
    int id, lb, l, r;
    bool operator<(const Ask& b) {
        if(lb == b.lb)  
            return r < b.r;
        return lb < b.lb;
    }
} q[N];

int gcd(int a, int b) {
    return !b ? a : gcd(b, a % b);
}

void insert(int x) {
    // cerr << "insert " << x << endl;
    u += 2 * buc[x] + 1;
    buc[x]++;
}

void remove(int x) {
    // cerr << "remove " << x << endl;
    u -= 2 * buc[x] - 1;
    buc[x]--;
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int n = rd(), m = rd(); int sz = sqrt(n) + 1;
    for(int i = 1; i <= n; i++) a[i] = rd();
    for(int i = 1; i <= m; i++) {
        q[i].l = rd(), q[i].r = rd();
        q[i].lb = q[i].l / sz; if(q[i].l % sz) ++q[i].lb;
        q[i].id = i;
    }

    sort(q + 1, q + m + 1);
    insert(a[1]);
    for(int i = 1; i <= m; i++) {
        // d(q[i].l); d(q[i].r); d(q[i].id);
        if(q[i].l == q[i].r) {
            ans[q[i].id] = 0;
            ans_fm[q[i].id] = 1;
            continue;
        }

        while(ar > q[i].r) remove(a[ar--]);
        while(ar < q[i].r) insert(a[++ar]);
        while(al < q[i].l) remove(a[al++]);
        while(al > q[i].l) insert(a[--al]);
        int len = q[i].r - q[i].l + 1;
        ans_fm[q[i].id] = len * (len - 1);
        ans[q[i].id] = u - len;
    }

    for(int i = 1; i <= m; i++) {
        int fz = ans[i], fm = ans_fm[i];
        int gcdv = gcd(fz, fm);
        printf("%lld/%lld\n", fz / gcdv, fm / gcdv);
    }

    return 0;
}

P3376 【模板】网络最大流

神奇的 Dinic。 神奇的当前弧优化。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
#define int long long
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 250, M = 1e5 + 5;

struct Edge { 
    int to, nxt, wei;
} Edge[M << 1];

int head[N], dep[N], cur[N], cnt = 1, n, m, s, t;

void addEdge(int u, int v, int w) {
    Edge[++cnt].to = v;
    Edge[cnt].wei = w;
    Edge[cnt].nxt = head[u];
    head[u] = cnt;
}

queue<int> Q;

int bfs() {
    ms(dep);
    for(int i = 1; i <= n; i++) cur[i] = head[i];
    while(!Q.empty()) Q.pop();
    Q.push(s); dep[s] = 1;
    while(!Q.empty()) {
        int u = Q.front(); Q.pop();
        for(int i = head[u]; i; i = Edge[i].nxt) {
            const int v = Edge[i].to;
            if(Edge[i].wei && !dep[v]) {
                dep[v] = dep[u] + 1;
                Q.push(v);
            }
        }
    }
    return dep[t];
}

int dfs(int u, int provide) {
    if(u == t) return provide;
    int out = 0;
    for(int i = cur[u]; i && provide; i = Edge[i].nxt) {
        cur[u] = i;
        const int v = Edge[i].to;
        if(Edge[i].wei && dep[v] == dep[u] + 1) {
            int res = dfs(v, min(provide, Edge[i].wei));
            Edge[i].wei -= res;
            Edge[i ^ 1].wei += res;
            provide -= res;
            out += res;
        }
    }
    if(out == 0) dep[u] = 0;
    return out;
}

signed main() {
#ifdef LOCAL
    file();
#endif
    n = rd(), m = rd(), s = rd(), t = rd();
    for(int i = 1; i <= m; i++) {
        int u = rd(), v = rd(), w = rd();
        addEdge(u, v, w);
        addEdge(v, u, 0);
    }
    int ans = 0;
    while(bfs()) ans += dfs(s, 1e18);
    cout << ans << endl;
    return 0;
}
最后修改：2021 年 02 月 08 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏