Visits: 305

【LGR-066】洛谷 1 月月赛 Div.2

Hello, 2020!

模拟。

const int M = 1e6 + 7;
int n, m, p, k, x, c[M];

int main() {
    rd(n), rd(m), rd(p);
    for (int i = 1; i <= n; i++) {
        rd(k);
        while (k--) rd(x), ++c[x];
    }
    vi ans;
    for (int i = 1; i <= m; i++)
        if (c[i] == p) ans.pb(i);
    print(ans.size());
    for (auto x : ans) print(x, ' ');
    prints("");
    return 0;
}

Ringed Genesis

简单数论。

const int M = 1e6 + 7;
int n, m, k, v[M];

int main() {
    rd(n), rd(m), rd(k);
    int d = __gcd(k, n), p = n / d, x, c = 0;
    for (int i = 1; i <= m; i++) rd(x), v[x%d] = 1;
    for (int i = 0; i < d; i++) c += !v[i];
    print(c * p);
    return 0;
}

传球游戏

组合计数 dp。

const int N = 5e4 + 7;
int n, m, k, t;
map< int, int > p;
int h[N<<1], e[N], nxt[N], tot;
modint f[2][N<<1], g[2][N<<1], w, s, o;

inline void add(int x, int y) {
    e[++tot] = y;
    nxt[tot] = h[x];
    h[x] = tot;
}

int main() {
    rd(n), rd(m), rd(k), p[1] = t = 1;
    for (int i = 1, x, y; i <= k; i++) {
        rd(x), rd(y);
        if (x == y) continue;
        if (!p[x]) p[x] = ++t;
        if (!p[y]) p[y] = ++t;
        add(p[x], p[y]);
    }
    g[0][1] = 1;
    for (int i = 0; i < m; i++) {
        int x = i & 1, y = x ^ 1;
        s = w * (n - p.size());
        for (int j = 1; j <= t; j++)
            f[y][j] = g[y][j] = 0, s += g[x][j];
        w = s - w;
        for (int j = 1; j <= t; j++)
            for (int z = h[j]; z; z = nxt[z]) f[y][e[z]] += g[x][j];
        for (int j = 1; j <= t; j++)
            g[y][j] = s - g[x][j] - f[y][j];
    }
    print(g[m&1][1]);
    return 0;
}

跳树

显而易见的线段树。

每个线段树的节点维护两个信息：

1. 最多向上走的层数。
2. 走到最上之后，若最上面的点为 $1$ 号点，则会走到几号点。

显然这个信息可以 $\mathcal O(1)$ 合并，分类讨论一下即可。

时间复杂度 $\mathcal O((m + q\log m)n)$，常数较小。

const int N = 5e5 + 7;
int n, m, q, x, p[37];
struct T {
    int l, r;
    pi x;
} t[N<<2];

inline int get(int x) {
    if (!x) return 0;
    int y;
    while (x) y = x, x -= x & -x;
    return p[y%37];
}

inline pi operator + (pi a, pi b) {
    int o = get(a.se);
    if (b.fi <= o) {
        o = get(b.se);
        return mp(a.fi, ((a.se >>= b.fi) ? a.se : 1) << o | (b.se ^ (1 << o)));
    }
    return mp(a.fi + b.fi - o, b.se);
}

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r)
        return rd(x), t[p].x = x == 3 ? mp(1, 1) : mp(0, x + 1), void();
    build(ls, l, md), build(rs, md + 1, r);
    t[p].x = t[ls].x + t[rs].x; 
}

pi ask(int p, int l, int r) {
    if (t[p].l >= l && t[p].r <= r) return t[p].x;
    pi o = mp(0, 1);
    if (l <= md) o = o + ask(ls, l, r);
    if (r > md) o = o + ask(rs, l, r);
    return o;
}

void chg(int p, int x, int y) {
    if (t[p].l == t[p].r)
        return t[p].x = y == 3 ? mp(1, 1) : mp(0, y + 1), void();
    chg(x <= md ? ls : rs, x, y);
    t[p].x = t[ls].x + t[rs].x;
}

int main() {
    rd(n), rd(m), rd(q);
    for (int i = 0, j = 1; i <= n; i++, j <<= 1) p[j%37] = i;
    build(1, 1, m);
    while (q--) {
        int o;
        rd(o);
        if (o == 1) {
            int s, l, r;
            rd(s), rd(l), rd(r), print((mp(0, s) + ask(1, l, r)).se);
        } else {
            int x, y;
            rd(x), rd(y), chg(1, x, y);
        }
    }
    return 0;
}