20230211 - 模拟赛 | Final Fantasy = xixike = 人间忽晚，山河已秋

考裂开了。

结论，线段树，树上期望 dp，恶心题

# A. 签到题（qiandao）

nt 结论题。

一个点度数模 $c$ 不为 0 有 1 的代价，否则没有代价。

	#include <bits/stdc++.h>

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
	}

	template <typename T> inline void write(T x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 1e6 + 10;
	int n, m, k, c;
	int deg[N];

	signed main(){
	// freopen("qiandao.in", "r", stdin);
	// freopen("qiandao.out", "w", stdout);
	n = read(), m = read(), k = read(), c = read();
	for(int i = 1; i <= k; ++i){
	int u = read(), v = read();
	deg[u]++, deg[v + n]++;
	}
	int ans = 0;
	for(int i = 1; i <= n + m; ++i)
	ans += (deg[i] % c != 0);
	write(ans), puts("");
	return 0;
	}

# B. M 弟娃（magic）

线段树裸题。

判一下祖先关系什么的，然后线段树上区间加。

	#include <bits/stdc++.h>
	#define pb push_back

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
	}

	template <typename T> inline void write(T x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 3e5 + 10;
	int n, m;
	vector <int> G[N];
	int fa[N][20], dfn[N], tim, dep[N], siz[N];

	inline void dfs(int x, int f){
	fa[x][0] = f, dep[x] = dep[f] + 1, dfn[x] = ++tim, siz[x] = 1;
	for(int i = 1; i <= 19; ++i) fa[x][i] = fa[fa[x][i - 1]][i - 1];
	for(auto y : G[x]){
	if(y == f) continue;
	dfs(y, x), siz[x] += siz[y];
	}
	}

	inline int jump(int x, int p){
	for(int i = 19; i >= 0; --i)
	if(dfn[fa[x][i]] > dfn[p]) x = fa[x][i];
	return x;
	}


	#define ls rt << 1
	#define rs rt << 1 \| 1
	#define mid ((l + r) >> 1)

	int tag[N << 2], mx[N << 2];

	inline void pushup(int rt){
	mx[rt] = max(mx[ls], mx[rs]);
	}

	inline void pushdown(int rt){
	if(tag[rt]){
	mx[ls] += tag[rt], mx[rs] += tag[rt];
	tag[ls] += tag[rt], tag[rs] += tag[rt];
	tag[rt] = 0;
	}
	}

	inline void upd(int L, int R, int l = 1, int r = n, int rt = 1){
	if(L > R \|\| L > r \|\| R < l) return;
	if(L <= l && r <= R) return tag[rt]++, mx[rt]++, void();
	pushdown(rt);
	upd(L, R, l, mid, ls), upd(L, R, mid + 1, r, rs);
	pushup(rt);
	}

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	n = read(), m = read();
	for(int i = 1; i < n; ++i){
	int u = read(), v = read();
	G[u].pb(v), G[v].pb(u);
	}
	dfs(1, 0);
	for(int i = 1; i <= m; ++i){
	int x = read(), y = read();
	if(dfn[x] > dfn[y]) swap(x, y);
	if(x == y){
	upd(1, n);
	}else if(dfn[y] <= dfn[x] + siz[x] - 1){
	x = jump(y, x);
	upd(dfn[y], dfn[y] + siz[y] - 1), upd(1, dfn[x] - 1);
	upd(dfn[x] + siz[x], n);
	}else{
	upd(dfn[x], dfn[x] + siz[x] - 1);
	upd(dfn[y], dfn[y] + siz[y] - 1);
	}
	write(mx[1]), puts("");
	}
	return 0;
	}

# C. 变异大老鼠（arrest）

由于题目里说了 $1 \sim i$ 的最短路只有 1 条，所以建出来就是一颗树。

然后就是裸的树上背包。

设 $f_{x, i}$ 表示 $x$ 子树内放了 $i$ 个警察抓到的期望。

转移就背包转移，注意还要给 $x$ 节点上放警察单独转移。

	#include <bits/stdc++.h>
	#define fi first
	#define se second
	#define pb push_back

	using namespace std;

	const int N = 310;
	const int M = 3e4 + 10;
	int n, m, k;
	struct node{
	int v, w, nxt;
	}edge[M << 1];
	int head[N], tot;

	inline void add(int x, int y, int z){
	edge[++tot] = (node){y, z, head[x]};
	head[x] = tot;
	}

	typedef pair<int, int> P;
	int dis[N], vis[N], fr[N];

	inline void dij(){
	priority_queue <P, vector<P>, greater<P> > q;
	memset(dis, 0x3f, sizeof(dis));
	q.push(P(0, 1)), dis[1] = 0;
	while(!q.empty()){
	int x = q.top().se; q.pop();
	if(vis[x]) continue; vis[x] = 1;
	for(int i = head[x]; i; i = edge[i].nxt){
	int y = edge[i].v;
	if(dis[y] > dis[x] + edge[i].w){
	dis[y] = dis[x] + edge[i].w, fr[y] = x;
	q.push(P(dis[y], y));
	}
	}
	}
	}

	vector <int> G[N];
	double f[N][N], p[N][N];

	inline void dfs(int x){
	for(auto y : G[x]){
	dfs(y);
	for(int i = k; i >= 0; --i)
	for(int j = 1; j <= i; ++j)
	f[x][i] = max(f[x][i], f[x][i - j] + f[y][j] * (1.0 / G[x].size()));
	}
	for(int i = k; i >= 0; --i)
	for(int j = 1; j <= i; ++j)
	f[x][i] = max(f[x][i], f[x][i - j] * (1.0 - p[x][j]) + p[x][j]);
	}

	signed main(){
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= m; ++i){
	int u, v, w; scanf("%d%d%d", &u, &v, &w);
	add(u, v, w), add(v, u, w);
	}
	for(int i = 1; i <= n; ++i)
	for(int j = 1; j <= k; ++j) scanf("%lf", &p[i][j]);
	dij();
	for(int i = 2; i <= n; ++i) G[fr[i]].pb(i);
	dfs(1);
	printf("%.10lf\n", f[1][k]);
	return 0;
	}

# D. 朝鲜时蔬（vegetable）

神秘题。

读题分有 40，比较简单的部分分有 70.

但是这里都不讲了，要看题解去这里

	#include <bits/stdc++.h>
	#define int long long

	using namespace std;

	const int mod = 1e9 + 7;
	int n, m, k, tn;

	inline int qpow(int a, int b){
	int res = 1;
	while(b){
	if(b & 1) res = 1ll * res * a % mod;
	a = 1ll * a * a % mod, b >>= 1;
	}
	return res;
	}

	inline int inv(int x) {return qpow(x, mod - 2);}

	inline void calc21(){
	int res = 0;
	for(int l = 1, r; l <= tn; l = r + 1){
	r = tn / (tn / l);
	res = (res + (r - l + 1) * (tn / l - 1) % mod) % mod;
	}
	cout << res << '\n';
	}

	inline void calc32(){
	int res = 0, inv2 = inv(2);
	for(int l = 3, r; l <= tn; l = r + 1){
	r = tn / (tn / l);
	int len, c = 0, tl, tr;
	tl = l, tr = r;
	if(l % 2 == 0) tl++, c = (c + (l % mod * inv2 % mod - 1 + mod) % mod) % mod;
	if(r % 2 == 1) tr--, c = (c + ((r + 1) % mod * inv2 % mod - 1 + mod) % mod) % mod;
	tl %= mod, tr %= mod;
	len = (tr - tl + mod + 1) % mod * inv2 % mod;
	int a = ((tl + 1) * inv2 % mod - 1 + mod) % mod, b = (tr * inv2 % mod - 1 + mod) % mod;
	res = (res + (2 * (a + b) % mod * len % mod * inv2 % mod + c) % mod * (tn / l) % mod) % mod;
	}
	cout << res << '\n';
	}

	inline void calc42(){
	if(tn == 4) cout << 1 << '\n';
	else if(tn < 11){
	int ans = 0;
	for(int a = 1; a <= n; ++a)
	for(int b = a + 1; b <= n; ++b)
	for(int c = b + 1; c <= n; ++c)
	for(int d = c + 1; d <= n; ++d){
	int s = a + b + c + d, t = 0;
	t += (s % (a + b) == 0) + (s % (a + c) == 0) + (s % (a + d) == 0) + (s % (b + c) == 0) + (s % (b + d) == 0) + (s % (c + d) == 0);
	ans += (t == 3);
	}
	cout << ans << '\n';
	}else cout << (tn / 11 + tn / 29) % mod << '\n';
	}

	inline int S3(int n){
	int tn = n; n %= mod;
	int sum = n * (n + 1) % mod * (2 * n + 1) % mod * inv(6) % mod;
	sum = (sum - 6 * (n * (n + 1) % mod * inv(2) % mod) % mod + mod) % mod;
	sum = (sum + 5 * n) % mod;
	sum = (sum + 3 * (tn / 2) % mod + 4 * (tn / 3) % mod) % mod;
	return sum;
	}

	inline void calc43(){
	if(tn == 4) cout << "1\n";
	else if(tn == 5) cout << "5\n";
	else{
	int ans = 0;
	for(int l = 1, r; l <= tn; l = r + 1){
	r = tn / (tn / l);
	ans = (ans + (tn / l) % mod * (S3(r) - S3(l - 1) + mod) % mod) % mod;
	}
	cout << ans * inv(12) % mod << '\n';
	}
	}

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	cin >> n >> m >> k, tn = n;
	n %= mod;

	if(m == 1 && k == 1) return cout << n % mod << '\n', 0;
	if(m == 2 && k == 2) return cout << n * (n - 1) % mod * qpow(2, mod - 2) % mod << '\n', 0;
	if(m == 3 && k == 3) return cout << n * (n - 1) % mod * (n - 2) % mod * qpow(6, mod - 2) % mod << '\n', 0;
	if(m == 4 && k == 4) return cout << n * (n - 1) % mod * (n - 2) % mod * (n - 3) % mod * qpow(24, mod - 2) % mod << '\n', 0;

	if(m == 2 && k == 1) return calc21(), 0;
	if(m == 3 && k == 1) return cout << tn / 3 % mod << '\n', 0;
	if(m == 3 && k == 2) return calc32(), 0;

	if(m == 4 && k == 1) return cout << (tn <= 5 ? 1 : (tn / 6 + tn / 9 + tn / 10 + tn / 12 + tn / 15 + tn / 21) % mod) << '\n', 0;
	if(m == 4 && k == 2) return calc42(), 0;
	if(m == 4 && k == 3) return calc43(), 0;
	return 0;
	}

# A. 签到题（qiandao）

# B. M 弟娃（magic）

# C. 变异大老鼠（arrest）

# D. 朝鲜时蔬（vegetable）

Codeforces Round 845 (Div. 2) and ByteRace 2023

20230212