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

【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;
}