Cydiater

嗡嘛呢叭弥叭弥买买哞


  • 首页

  • 关于

  • 标签

  • 归档

  • 笔记

  • 伙伴

  • 搜索

「JSOI2018 RoundII」「BZOJ5314 - 5319」题解

发表于 2018-05-20 | 阅读次数:

BZOJ5314 潜入行动

看到这道题就很容易想到一个裸的$O(nk^2)$的 DP,但是时间复杂度上似乎不是很能承受,但是实际上这个题的时间复杂度是 $O(nk)$的。分三类情况讨论,一种是两个子树大小都大于 $k$的,这个时候合并复杂度为$k^2$,但是这样的情况最多出现 $\frac{n}{k}$次。第二种是一个大于 $k$,一个小于等于 $k$,这个时候对于小于等于 $k$ 的节点的子树,每个点贡献一个 $k$ 的复杂度,同时可以发现每个点最多贡献一次,因为小于 $k$ 的向上合并一次就必定大于等于 $k$ 了。最后是两个点都小于等于 $k$ 的,复杂度可以均摊到每个节点上,这样复杂度也是 $O(nk)$ 的。

具体实现的时候可能需要一些寻址的常数优化。

时间复杂度 $O(nk)$。

#include <bits/stdc++.h>

using namespace std;

#define ll      long long
#define db      double
#define up(i,j,n)   for (int i = j; i <= n; i++)
#define down(i,j,n) for (int i = j; i >= n; i--)
#define cadd(a,b)   a = add(a, b)
#define cpop(a,b)   a = pop(a, b)
#define cmul(a,b)   a = mul(a, b)
#define pr      pair<int, int>
#define fi      first
#define se      second
#define bin(i)      (1 << (i))
#define SZ(x)       (int)x.size()
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & a, T b) { return b > a ? a = b, true : false; }
template<typename T> inline bool cmin(T & a, T b) { return b < a ? a = b, true : false; }

const int MAXN = 1e5 + 5;
const int MAXK = 105;
const int oo = 0x3f3f3f3f;
const int mod = 1e9 + 7;

inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return (ll)a * b % mod;}

int N, K;

struct edge {
    int y, next;
}e[MAXN << 1];

int LINK[MAXN], len = 0, f[MAXN][MAXK][2][2], siz[MAXN], g[MAXK][2][2];

inline void ins(int x, int y){
    e[++len].next = LINK[x]; LINK[x] = len;
    e[len].y = y;
}

inline void Ins(int x, int y){
    ins(x, y);
    ins(y, x);
}

void DFS(int node, int fa){
    f[node][0][0][0] = f[node][1][0][1] = 1; siz[node] = 1;
    Auto (i, node) if (e[i].y != fa) {
        DFS(e[i].y, node);
        siz[node] += siz[e[i].y];
    }
    if (!fa) return;
    int n = min(K, siz[node]);
    up (i, 0, n) {
        int m = min(K - i, siz[fa]);
        up (j, 0, m) {
            int *ss[2], *tt[2];
            up (k, 0, 1) {
                ss[k] = f[node][i][k];
                tt[k] = f[fa][j][k];
            }
            if (ss[0][0]) {
                cadd(g[i + j][0][1], mul(ss[0][0], tt[0][1]));
                cadd(g[i + j][1][1], mul(ss[0][0], tt[1][1]));
            }
            if (ss[0][1]) {
                cadd(g[i + j][1][1], mul(ss[0][1], tt[0][1]));
                cadd(g[i + j][1][1], mul(ss[0][1], tt[1][1]));
            }
            if (ss[1][0]) {
                cadd(g[i + j][0][0], mul(ss[1][0], tt[0][0]));
                cadd(g[i + j][0][1], mul(ss[1][0], tt[0][1]));
                cadd(g[i + j][1][0], mul(ss[1][0], tt[1][0]));
                cadd(g[i + j][1][1], mul(ss[1][0], tt[1][1]));
            }
            if (ss[1][1]) {
                cadd(g[i + j][1][0], mul(ss[1][1], tt[0][0]));
                cadd(g[i + j][1][0], mul(ss[1][1], tt[1][0]));
                cadd(g[i + j][1][1], mul(ss[1][1], tt[0][1]));
                cadd(g[i + j][1][1], mul(ss[1][1], tt[1][1]));
            }
        }
    }
    n = min(K, siz[fa] + siz[node]);
    up (i, 0, n) {
        memcpy(f[fa][i], g[i], sizeof(g[i]));
        memset(g[i], 0, sizeof(g[i]));
    }
}

int main(){
    scanf("%d%d", &N, &K);
    up (i, 2, N) {
        int x, y; scanf("%d%d", &x, &y);
        Ins(x, y);
    }
    DFS(1, 0);
    printf("%d\n", add(f[1][K][1][0], f[1][K][1][1]));
    return 0;
}
阅读全文 »

NOI2017 题目分析

发表于 2018-05-12 | 阅读次数:

NOI2017 D1T1 整数

大体上来看是一道 NOIP 难度的题目,很容易发现题目要求快速维护高精度二进制加减。而我们每次加入或者删去一个数最多只会带来一次高精度的进位或者退位,而一次进退位就是区间赋值为 $0/1$,所以我们拿线段树维护即可。

同时考虑到数据范围很大,而且我们线段树维护的只有 $0/1$,可以一次性压到一个 unsigned int 里来维护,判断同时维护一个区间 or 和区间 and,结合这两个的值即可判定一段内是否全为$0/1$。去年码力实在是不太行,这样一个签到题愣是写了三个多小时,导致后两题,尤其是第二题没有拿到一点分。

时间复杂度 $O(n \log n)$。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define uint         unsigned int
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        ((uint)1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int MAXN = 2e6 + 5;
const int L = 30;
uint all = bin(30) - 1;
const int oo = 0x3f3f3f3f;

inline int read(){
    char ch = getchar(); int x = 0, f = 1;
    while (ch > '9' || ch < '0') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
} 

struct tree {
    uint sor, sand;
    int cov;
}t[MAXN << 2];

inline bool isall1(int k) { return t[k].sor == t[k].sand && t[k].sor == all; }
inline bool isall0(int k) { return t[k].sor == t[k].sand && t[k].sor == 0; }

inline void rel(int k){
    t[k].sor = t[k << 1].sor | t[k << 1 | 1].sor;
    t[k].sand = t[k << 1].sand & t[k << 1 | 1].sand;
}

inline void cg(int k, uint v){
    t[k].cov = v == 0 ? -1 : 1;
    t[k].sor = t[k].sand = v;
}

inline void Pushdown(int k){
    if (t[k].cov == 0) return;
    uint x = t[k].cov == -1 ? 0 : all;
    cg(k << 1, x); cg(k << 1 | 1, x);
    t[k].cov = 0;
}

uint get(int le, int ri, int k, int o){
    if (le != ri) Pushdown(k);
    if (le == ri) return t[k].sor;
    int mi = (le + ri) >> 1;
    o <= mi ? get(le, mi, k << 1, o) : get(mi + 1, ri, k << 1 | 1, o);
}

void cg(int le, int ri, int k, int o, uint v){
    if (le != ri) Pushdown(k);
    if (le == ri) return (void)(t[k].sor = t[k].sand = v);
    int mi = (le + ri) >> 1;
    o <= mi ? cg(le, mi, k << 1, o, v) : cg(mi + 1, ri, k << 1 | 1, o, v);
    rel(k);
}

struct ROOT {
    int le, ri, k;
    inline ROOT (int le = 0, int ri = 0, int k = 0) : le(le), ri(ri), k(k) {}
}rts[MAXN];

int siz;

void get(int le, int ri, int k, int L, int R){
    if (le != ri)        Pushdown(k);
    if (L <= le && ri <= R)    return (void)(rts[++siz] = ROOT(le, ri, k));
    int mi = (le + ri) >> 1;
    if (L <= mi)    get(le, mi, k << 1, L, R);
    if (mi + 1 <= R)    get(mi + 1, ri, k << 1 | 1, L, R);
}

int get0(int le, int ri, int k){
    if (le != ri) Pushdown(k);
    if (le == ri) return le;
    int mi = (le + ri) >> 1, x;
    if (isall1(k << 1)) {
        cg(k << 1, 0);
        x = get0(mi + 1, ri, k << 1 | 1);
    }else x = get0(le, mi, k << 1);
    rel(k);
    return x;
}

int get1(int le, int ri, int k){
    if (le != ri) Pushdown(k);
    if (le == ri) return le;
    int mi = (le + ri) >> 1, x;
    if (isall0(k << 1)) {
        cg(k << 1, all);
        x = get1(mi + 1, ri, k << 1 | 1);
    }else x = get1(le, mi, k << 1);
    rel(k);
    return x;
}

void Rel(int k){ while (k >>= 1) rel(k); }

int Q, n;

void add(int o, uint v){
    uint x = get(0, n, 1, o);
    cg(0, n, 1, o, (x += v) & all);
    if (x != (x & all)) {
        get(siz = 0, n, 1, o + 1, n);
        up (i, 1, siz) {
            int le = rts[i].le, ri = rts[i].ri, k = rts[i].k;
            if (isall1(k)) {
                cg(k, 0);
                Rel(k);
            }else {
                int w = get0(le, ri, k);
                uint x = get(0, n, 1, w);
                Rel(k);
                cg(0, n, 1, w, ++x);
                break;
            }
        }
    }
}

void pop(int o, uint v){
    uint x = get(0, n, 1, o);
    cg(0, n, 1, o, (x -= v) & all);
    if (x != (x & all)) {
        get(siz = 0, n, 1, o + 1, n);
        up (i, 1, siz) {
            int le = rts[i].le, ri = rts[i].ri, k = rts[i].k;
            if (isall0(k)) {
                cg(k, all);
                Rel(k);
            }else {
                int w = get1(le, ri, k); 
                uint x = get(0, n, 1, w);
                Rel(k);
                cg(0, n, 1, w, --x);
                break;
            }
        }
    }
}

int main(){
    Q = read(); n = Q + 15;
    int t1 = read(), t2 = read(), t3 = read();
    while (Q--) {
        int o = read(), x, v;
        if (o == 1) {
            v = read(); x = read();
            int vv = abs(v), w = x - x / L * L;
            v > 0 ? add(x / L, (vv << w) & all) : pop(x / L, (vv << w) & all);
            w = L - w;
            v > 0 ? add(x / L + 1, vv >> w) : pop(x / L + 1, vv >> w);
        }else {
            x = read();
            uint w = get(0, n, 1, x / L);
            puts(((w >> (x - (x / L * L))) & 1) ? "1" : "0");
        }
    }
    return 0;
}

NOI2017 D1T2 蚯蚓排队

主要考察选手的心态以及读题能力,看懂题后我们拿链表维护一下 Link Cut,每次操作暴力维护 hash 值即可。

时间复杂度 $O((n + m)k)$。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define ull            unsigned long long
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int mod = 998244353;
const int MOD = 10002333;

const ull step = 17171717;

const int MAXN = 2e5 + 5;
const int MAXM = 1e7 + 5;

inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return 1LL * a * b % mod;}

struct H {
    struct edge {
        int next, v;
        ull q;
    }e[MOD + MOD];
    int LINK[MOD], len;
    inline void ins(int p, ull q, int v){
        e[++len].next = LINK[p]; LINK[p] = len;
        e[len].q = q; e[len].v = v;
    }
    int get(ull x){
        int p = x % MOD;
        Auto (i, p) if (e[i].q == x) return e[i].v;
        return 0;
    }
    void cg(ull x, int v){
        int p = x % MOD;
        Auto (i, p) if (e[i].q == x) return (void) (e[i].v += v);
        ins(p, x, v);
    }
}S;

ull bin[MAXN];

int N, Q;

struct LK {
    int pre, nxt, v;
}a[MAXN];

int pre[MAXN], suf[MAXN];

char s[MAXM];

int main(){
    scanf("%d%d", &N, &Q);
    up (i, 1, N) {
        scanf("%d", &a[i].v);
        S.cg(a[i].v, 1);
    }
    bin[0] = 1;
    up (i, 1, N) bin[i] = bin[i - 1] * step;
    while (Q--) {
        int o, x, y;
        scanf("%d", &o);
        if (o == 1) {
            scanf("%d%d", &x, &y);
            int p = 0, q = 0;
            a[x].nxt = y; a[y].pre = x;
            for (int i = x; i && p < 50; i = a[i].pre) pre[++p] = a[i].v;
            for (int i = y; i && q < 50; i = a[i].nxt) suf[++q] = a[i].v;
            up (i, 1, p) {
                int n = min(q, 50 - i);
                ull cur = 0;
                down (j, i, 1) cur = cur * step + pre[j];
                up (j, 1, n) {
                    cur = cur * step + suf[j];
                    S.cg(cur, 1);
                }
            }
        } 
        if (o == 2) {
            scanf("%d", &x); y = a[x].nxt;
            int p = 0, q = 0;
            for (int i = x; i && p < 50; i = a[i].pre) pre[++p] = a[i].v;
            for (int i = y; i && q < 50; i = a[i].nxt) suf[++q] = a[i].v;
            up (i, 1, p) {
                int n = min(q, 50 - i);
                ull cur = 0;
                down (j, i, 1) cur = cur * step + pre[j];
                up (j, 1, n) {
                    cur = cur * step + suf[j];
                    S.cg(cur, -1);
                }
            }
            a[x].nxt = 0; a[y].pre = 0;
        }
        if (o == 3) {
            scanf("%s%d", s + 1, &x); int len = strlen(s + 1);
            ull cur = 0;
            up (i, 1, x - 1) cur = cur * step + (s[i] - '0');
            int ans = 1;
            up (i, x, len) {
                cur = cur * step + (s[i] - '0');
                if (i > x) cur -= bin[x] * (s[i - x] - '0');
                cmul(ans, S.get(cur));
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}
阅读全文 »

JSOI2018 Round II 酱油记

发表于 2018-05-05 | 阅读次数:

因为不是正式选手所以就叫酱油记啦~

阅读全文 »

「HAOI 2018」「BZOJ 5302 - 5306」题解

发表于 2018-05-02 | 阅读次数:

出题人的题解

BZOJ 5302 奇怪的背包

容易发现,在模 $P$ 意义下,一个数 $x$ 实际的贡献是 $(x, P)$,同时对于多个数来说,其贡献为这些数的 gcd。那么题目转化成给你 $n$ 个 $P$ 的约数,每次询问有多少种选择数的方案使得方案里所有数的 gcd 为某个数的约数。

这个时候就转化成了经典的容斥问题,利用莫比乌斯函数可以方便的在 $n^2$ 的时间内计算出来。同时我们发现,$P$ 的约数数量级在 $\frac{\sqrt P}{ \log P}$ 以内,所以不同的数是远小于 $n$ 这个级别的。因此我们可以在 $\frac{P}{\log ^2 P}$的时间内处理出答案,同时在这个时间内预处理出所有询问,即可做到 $O(1)$ 回答每个询问。

时间复杂度 $O(n + Q + \frac{P}{ \log ^2 P})$

#include <bits/stdc++.h>

using namespace std;

#define ll          long long
#define db          double
#define up(i,j,n)   for (int i = j; i <= n; i++)
#define down(i,j,n) for (int i = j; i >= n; i--)
#define cadd(a,b)   a = add(a, b)
#define cpop(a,b)   a = pop(a, b)
#define cmul(a,b)   a = mul(a, b)
#define pr          pair<int, int>
#define fi          first
#define se          second
#define bin(i)      (1 << (i))
#define SZ(x)       (int)x.size()
#define Auto(i,node) for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & a, T b) { return b > a ? a = b, true : false; }
template<typename T> inline bool cmin(T & a, T b) { return b < a ? a = b, true : false; }

const int mod = 1e9 + 7;
const int MAXN = 2e6 + 5;

inline int read(){
    char ch = getchar(); int x = 0, f = 1;
    while (ch > '9' || ch < '0') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}

inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return 1LL * a * b % mod;}

int qpow(int a, int b){
    int c = 1;
    while (b) {
        if (b & 1) cmul(c, a);
        cmul(a, a); b >>= 1;
    }
    return c;
}

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

int N, Q, P, num[MAXN], cnt = 0, f[MAXN], g[MAXN], mu[MAXN];

map<int, int> ID;

int main(){
    N = read(); Q = read(); P = read();
    int m = sqrt(P);
    up (i, 1, m) if (P % i == 0) {
        num[++cnt] = i;
        if (i * i != P) num[++cnt] = P / i;
    }
    sort(num + 1, num + cnt + 1);
    up (i, 1, cnt) ID[num[i]] = i;
    up (i, 1, cnt) {
        mu[i] = 1;
        down (j, i - 1, 1) if (num[i] % num[j] == 0) {
            int x = num[i] / num[j];
            if (num[j] % x == 0) mu[i] = 0;
            else mu[i] = pop(0, mu[j]);
            break;
        }
    }
    while (N--) {
        int x = read();
        cadd(g[ID[gcd(P, x)]], 1);
    }
    up (i, 1, cnt) { 
        int sum = 0;
        up (j, i, cnt) if (num[j] % num[i] == 0) cadd(sum, g[j]);   
        g[i] = sum;
    }
    up (i, 1, cnt) g[i] = pop(qpow(2, g[i]), 1);
    up (i, 1, cnt) up (j, i, cnt) if (num[j] % num[i] == 0) {
        int x = ID[num[j] / num[i]];
        cadd(f[i], mul(g[j], mu[x]));
    }
    up (i, 1, cnt) {
        g[i] = f[i];
        f[i] = 0;
    }
    up (i, 1, cnt) up (j, i, cnt) if (num[j] % num[i] == 0) cadd(f[j], g[i]);
    up (i, 1, Q) {
        int x = read(); x = gcd(x, P);
        printf("%d\n", f[ID[x]]);
    }
    return 0;
}

BZOJ 5303 反色游戏

首先很显然,我们把每条边看做一个长度为 $n$ 的$0/1$ 向量,在其连接的两个点的位置上为 $1$ ,其余地方为 $0$。那么任意一个方案即为这些 $0/1$向量的异或和。我们用线性基维护,判定给出的方案是否合法即可,我们令线性基的大小为 $w$,那么如果合法,答案为 $2^{m - w} - 1$,否则为 $0$。

但是这样复杂度显然是无法接受的。我们可以发现,我们这个向量集合是可能满足某些特殊性质的,经过冷静分析或者打表找规律,可以发现,对于任意一张大小为 $n$联通图来说,其线性基的大小一定为$n - 1$。感性理解一下就是,假设我们首先找到这个联通图的一个生成树,生成树上任意一条边一定是线性无关的,所以一定都在线性基中,同时对于任意一条非树边来说,其一定可以表示成路径上所有边的异或和。

同时我们还可以发现,对于任意一种方案,其合法当且仅当所有极大联通子图的黑点数量都为偶数。因为如果我们将所有黑点两两配对,一定可以在生成树上构造出一种合法的方案,即对于所有配对的路径上的边取反。

这个时候我们就可以在 $O(n+ m)$ 的时间内快速得到第一问的答案啦。接着考虑删掉一个点的情况,利用一些图论的基础知识可以发现这些也是可以快速维护的,这里不再赘述。

时间复杂度 $O(n + m)$

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

inline int read(){
    char ch = getchar(); int x = 0, f = 1;
    while (ch > '9' || ch < '0') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}

const int mod = 1e9 + 7;
const int MAXN = 1e5 + 5;
const int oo = 0x3f3f3f3f;

inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return (ll)a * b % mod;}

int N, M;

struct edge {
    int y, next;
}e[MAXN << 1];

int LINK[MAXN], len = 0, dfn[MAXN], low[MAXN], siz[MAXN], oth[MAXN], key[MAXN], ord, cnt, ban;
int cut[MAXN], deg[MAXN], vaild[MAXN], pw2[MAXN], rt[MAXN];
char s[MAXN];

inline void ins(int x, int y){
    e[++len].next = LINK[x]; LINK[x] = len;
    e[len].y = y; deg[x]++;
}

inline void Ins(int x, int y){
    ins(x, y);
    ins(y, x);
}

void DFS(int node, int fa){
    dfn[node] = low[node] = ++ord;
    siz[node] = key[node]; vaild[node] = 1; 
    rt[node] = fa ? rt[fa] : node; 
    Auto (i, node) if (e[i].y != fa) {
        if (!dfn[e[i].y]) {
            DFS(e[i].y, node);
            siz[node] += siz[e[i].y];
            cmin(low[node], low[e[i].y]);
            if (low[e[i].y] >= dfn[node]) {
                cut[node]++; vaild[node] &= (siz[e[i].y] % 2 == 0); 
                oth[node] += siz[e[i].y];
            }
        }else cmin(low[node], dfn[e[i].y]);
    }
    if (!fa) {
        cut[node]--;
        ban += siz[node] & 1;
        cnt++;
    }
}

int main(){
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &N, &M);
        pw2[0] = 1;
        up (i, 1, M) pw2[i] = add(pw2[i - 1], pw2[i - 1]);
        up (i, 1, M) {
            int x, y; scanf("%d%d", &x, &y);
            Ins(x, y);
        }
        scanf("%s", s + 1);
        up (i, 1, N) key[i] = s[i] == '1';
        up (i, 1, N) if (!dfn[i]) DFS(i, 0);
        printf("%d ", ban ? 0 : pw2[M - N + cnt]);
        up (i, 1, N) if (vaild[i] && ban - (siz[rt[i]] & 1) == 0 && (siz[rt[i]] - oth[i] - key[i]) % 2 == 0) 
            printf("%d ", pw2[M - deg[i] - (N - 1) + cnt + cut[i]]);
            else printf("0 ");
        puts("");
        up (i, 1, N) LINK[i] = key[i] = oth[i] = deg[i] = low[i] = dfn[i] = siz[i] = cut[i] = 0;
        ban = ord = cnt = len = 0;
    }
    return 0;
}
阅读全文 »

「BZOJ 2673」「WF 2011」Chips Challenge

发表于 2018-04-20 | 阅读次数:

要求构造一个 $n \times n$ 的 $0/1$ 矩阵,满足下列限制的前提下 $1$ 的总数最多:

  • 对于某些位置,要求这些位置为 $1$。

  • 对于某些位置,要求这些位置必须为 $0$。

  • 第 $i$ 行与第$i$列中 $1$ 的个数相等。

  • 任意行列中$1$的个数不能超过总共 $1$ 个数的 $\frac{A}{B}$。

阅读全文 »

「BZOJ 4775」网管

发表于 2018-04-13 | 阅读次数:

给定一棵大小为 $n$ 的树,每个点有一个黑或白的颜色,给定初始颜色,要求支持:

  • 以 $P$ 的概率翻转某个点的颜色。
  • 求某个点到所有黑点的距离和的平方的期望值。
阅读全文 »

「BZOJ 5259」「CERC 2017 I」区间

发表于 2018-04-13 | 阅读次数:

给定一个$1$到$n$的排列${ a }$,对于一个区间$[l, r]$,我们称该区间是连续的,如果将$a_l, . . . , a_r$排列之后得到的是一列连续的数。(换句话说,如果$x,y$都在该区间中,那么所有介于$x,y$之间的数也在该区间中)现在有$m$个询问,每个询问给出一个区间$[x_i, y_i]$,你需要找到一个长度最短的连续区间$[l_i,r_i]$,使得$[x_i,y_i]$属于 $[l_i, r_i]$。

阅读全文 »

「BZOJ 3328」PYXFIB

发表于 2018-03-06 | 阅读次数:

给定 $n,k,p$ ,求 $\sum\limits_{i = 0}^n [k|i] C_n^i f_i \pmod p$,同时保证$p \equiv 1 \pmod k$。

阅读全文 »

LOJ #6052. 「雅礼集训 2017 Day11」DIV

发表于 2018-03-04 | 阅读次数:

定义复数 $ a + bi$ 为整数 $k$ 的约数,当且仅当 $a$ 和 $b$ 为整数且存在整数 $c$ 和 $d$ 满足 $ (a + bi)(c + di) = k $,给定 $n $,求出 $1$ 到 $n$ 的所有满足 $a > 0 $ 的约数 $ a + bi $ 的 $a$ 的和。答案模 $ 1004535809 $ 输出。

阅读全文 »

CSA #70 Solution

发表于 2018-02-23 | 阅读次数:

两道垃圾套路题没写出来。

我好菜啊

阅读全文 »
123…5
Cydiater

Cydiater

Blog

47 日志
88 标签
© 2017 — 2020 Cydiater
由 Hexo 强力驱动 v3.7.1
|
主题 — NexT.Gemini v6.3.0