526互联

22.2 杂题

发布时间 2023-05-08 10:52:36作者: ZCR7

1623D [4]

首先找到循环节，假设长度为 \(L\)，然后设答案为 \(E\)，中间有 \(k\) 个位置可以搞到。有 \(E=(1-(1-p)^k)(E+L)+\sum (i-1)p(1-p)^{q-1}\)。后面那一坨就代表在中间停下的期望。然后解方程模拟即可。

/*
Time : 2022/01/02 11:09 
Author : Gemini7X
Problem : https://codeforces.com/contest/1623/problem/D
*/
#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
using namespace std;
const int maxn = 200005, mod = 1e9 + 7;
int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
int dec(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
int mul(int a, int b) { return 1ll * a * b % mod; }
int ksm(int a, int b = mod - 2) { int ret = 1; for (; b; b >>= 1, a = mul(a, a)) if (b & 1) ret = mul(ret, a); return ret; }
int n, m, rb, cb, rd, cd, p;
pii stk[maxn << 2];
int top;
void run(int &x, int &y, int dx, int dy) {
	x += dx; y += dy;
}
void work(int x, int y, int &dx, int &dy) {
	if (x == 1 && dx == -1) dx = -dx;
	if (x == n && dx == 1) dx = -dx;
	if (y == 1 && dy == -1) dy = -dy;
	if (y == m && dy == 1) dy = -dy;
}
void solve() {
	cin >> n >> m >> rb >> cb >> rd >> cd >> p;
	p = mul(p, ksm(100));
	int x = rb, y = cb, dx = 1, dy = 1; top = 0;
	work(x, y, dx, dy);
	int ux = dx, uy = dy;
	while (1) {
		stk[++top] = mp(x, y);
		run(x, y, dx, dy);
		work(x, y, dx, dy);
		if (x == rb && y == cb && dx == ux && dy == uy) break;
	}
	int k = 0, ans = 0;
	for (int i = 1; i <= top; i++) {
		x = stk[i].F, y = stk[i].S;
		if (x == rd || y == cd) {
			ans = add(ans, mul(mul(p, i - 1), ksm(dec(1, p), k)));
			k++;
		}
	}
	ans = add(ans, mul(top, ksm(dec(1, p), k)));
	printf("%d\n", mul(ans, ksm(dec(1, ksm(dec(1, p), k)))));
}
int main() {
	int T; cin >> T; while (T--) solve();
	return 0;
}

1623E [5]

一开始有个误区就是要按a,b,c,...的顺序扩，其实不用。先处理出double了之后会更优的节点，这个可以通过处理 in-order 来解决。然后考虑一个贪心，还是按照 in-order 来 dfs，在每个节点记录一个 cost 代表 double 了之后有一个没有 double 的祖先要被处理。如果 cost 大于 k 了也就不需要管了，否则先遍历左儿子，假设左儿子被 double 了，那么这个点也一定要被 double。否则假设这个点是 good 的，那么就可以 double 它。然后是一步很关键的点，只有当这个点被 double 了才可以取遍历其右儿子，否则如果右子树内有点被 double，那么这个点也要被 double，而这个点之前没有被 double 一定是因为它不优，那么这样最后的答案也就不优了。所以在遍历右儿子的时候已经可以把 cost 设成 1，从新开始遍历一棵树了。

/*
Time : 2022/01/02 12:50
Author : Gemini7X
Problem : https://codeforces.com/contest/1623/problem/E
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
int n, k;
char s[maxn];
int ls[maxn], rs[maxn];
int stk[maxn], top;
bool good[maxn], mark[maxn];
void dfs(int u) {
	if (ls[u]) dfs(ls[u]);
	stk[++top] = u;
	if (rs[u]) dfs(rs[u]); 
}
void get_ans(int u, int cost) {
	if (cost > k) return;
	if (ls[u]) get_ans(ls[u], cost + 1);
	if (mark[ls[u]]) mark[u] = 1;
	else if (good[u]) mark[u] = 1, k -= cost;
	if (rs[u] && mark[u]) get_ans(rs[u], 1);
}
int main() {
	scanf("%d%d", &n, &k);
	scanf("%s", s + 1);
	for (int i = 1; i <= n; i++) scanf("%d%d", ls + i, rs + i);
	dfs(1);
	int lst = s[stk[n]];
	for (int i = n - 1; i >= 1; i--) {
		if (s[stk[i]] != lst) {
			if (s[stk[i]] < lst) good[stk[i]] = 1;
			lst = s[stk[i]];
		} else good[stk[i]] = good[stk[i + 1]];
	}
	get_ans(1, 1);
	for (int i = 1; i <= n; i++) {
		putchar(s[stk[i]]);
		if (mark[stk[i]]) putchar(s[stk[i]]);
	}
	return 0;
}

1622E [3]

也就是一个比较骚的操作，绝对值看起来不好处理，拆掉！然后 \(2^n\) 枚举正负，然后就是个排序不等式。

#include <bits/stdc++.h>
using namespace std;
template <typename T>
void read(T &num) {
	T flg = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') flg = -1;
	for (num = 0; isdigit(ch); ch = getchar()) num = num * 10 + ch - '0';
	num *= flg;
}
int n, m, x[15], a[10005], ans;
int p[10005], rk[10005];
char s[15][10005];
bool cmp(int i, int j) {
	return a[i] < a[j];
}
void solve() {
	read(n); read(m);
	for (int i = 1; i <= n; i++) read(x[i]);
	for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
	ans = -1; 
	for (int msk = 0; msk < (1 << n); msk++) {
		int now = 0; 
		for (int j = 1; j <= m; j++) a[j] = 0, rk[j] = j;
		for (int j = 1; j <= n; j++) {
			if ((msk >> (j - 1)) & 1) {
				now += x[j];
				for (int k = 1; k <= m; k++) if (s[j][k] == '1') a[k]--;
			} else {
				now -= x[j];
				for (int k = 1; k <= m; k++) if (s[j][k] == '1') a[k]++;
			}
		}
		sort(rk + 1, rk + 1 + m, cmp);
		for (int j = 1; j <= m; j++) now += j * a[rk[j]];
		if (now > ans) {
			ans = now;
			for (int j = 1; j <= m; j++) p[rk[j]] = j;
		}
	}
	for (int i = 1; i <= m; i++) printf("%d ", p[i]);
	puts("");
}
int main() {
	int T; read(T); while (T--) solve();
	return 0;
}

1622F [5]

实属诈骗了。手玩或推导发现答案至少是 \(n-3\)。考虑把相邻的配对即可。接下来考虑用 xor 来哈希，给每个质数随机一个 \([0,2^64]\) 范围内的值。然后将每个数替换成这些质数随机的值的 xor。显然对于一个完全平方数这样异或出来的值是 \(0\)。于是问题就变成了能否找到一个位置等于全部的异或和，或两个位置异或起来等于全部的异或和，这个随便 map 搞一个下就好了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1000005;
mt19937 rnd(20060413);
template <typename T>
void read(T &num) {
	T flg = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') flg = -1;
	for (num = 0; isdigit(ch); ch = getchar()) num = num * 10 + ch - '0';
	num *= flg;
}
int n;
int prime[maxn], cnt;
bool mark[maxn];
ull H[maxn], HH[maxn], val[maxn];
int mn[maxn];
map<ull, int> mp;
void solve() {
	read(n);
	for (int i = 2; i <= n; i++) {
		if (!mark[i]) {
			prime[++cnt] = i;
			mn[i] = i;
		}
		for (int j = 1; j <= cnt && prime[j] * i <= n; j++) {
			mark[i * prime[j]] = 1;
			mn[i * prime[j]] = prime[j];
			if (i % prime[j] == 0) break;
		}
	}
	for (int i = 1; i <= cnt; i++) {
		val[i] = ((ull)rnd() << 32) | rnd();
		for (ll now = prime[i]; now <= n; now *= prime[i]) {
			for (ll j = now; j <= n; j += now) {
				H[j] ^= val[i];
			}
		}
	}
	for (int i = 2; i <= n; i++) HH[i] = HH[i - 1] ^ H[i];
	ull s = 0;
	for (int i = 2; i <= n; i++) s ^= HH[i];
	if (s == 0) {
		printf("%d\n", n);
		for (int i = 1; i <= n; i++) printf("%d ", i);
		puts("");
	} else {
		for (int i = 2; i <= n; i++) {
			if ((HH[i] ^ s) == 0) {
				printf("%d\n", n - 1);
				for (int j = 1; j <= n; j++) {
					if (j == i) continue;
					printf("%d ", j);
				} puts("");
				return;
			}
		}
		for (int i = 2; i <= n; i++) {
			if (mp.find(HH[i]) != mp.end()) {
				printf("%d\n", n - 2);
				for (int j = 1; j <= n; j++) {
					if (j == i || j == mp[HH[i]]) continue;
					printf("%d ", j);
				} puts("");
				return;
			}
			mp[HH[i] ^ s] = i;
		}
		int k = n / 2;
		printf("%d\n", n - 3);
		for (int i = 1; i <= n; i++) {
			if (i == 2 || i == k || i == n) continue;
			printf("%d ", i);
		} puts("");
		return;
	}
}
int main() {
	int T = 1; while (T--) solve();
	return 0;
}

CF 1634F

一个非常妙的转换。考虑 \(C_i=A_i-B_i\)，然后只用在 \(C\) 上做操作。然后这个区间加考虑差分，这里差分的姿势奇怪一点 \(D_1=C_1,D_i=C_i-C_{i-1}-C_{i-2}\)。这样发现区间加 \(F\) 即变为单点加，于是就做完了。

code

ABC217H

被称作经典题。。。

先考虑一个dp，设 \(f_{i,p}\) 代表在时刻 \(T_i\) 时处在 \(p\) 位置的最小伤害，以 \(d=0\) 为例，\(d=1\) 反过来即可。记 \(m_i=T_i-T{i-1}\)。有转移 \(f_{i,p}=\min_{p-m_i\le q\le <p+m_i}f_{i-1,q}+\max(x_i-p,0)\)。如果 \(x_i\) 比 \(T_i\) 还大可以考虑将 \(x_i\) 变成 \(T_i\)，于是可以只考虑到 \(T_i\) 即可。然后我们发现这个dp是一个下凸壳，于是可以用一个大根堆（维护斜率小于 0），一个 ans（维护斜率等于 0）以及一个小根堆（维护斜率大于 0）的部分。

转移的第一步相当于把斜率小于 \(0\) 的部分像左平移 \(m_i\) 个单位，大于 \(0\) 部分同理向右平移。然后再加上一段斜率 \(-1\) 的射线，到 \(x_i\) 为止。那么这个时候分类讨论一下，是否会撞到右半边第一个点，不会的话就直接放进左边增加一段。会的话，右边一部分就会变成平的，而平的部分会变成左边的斜率小于 \(0\) 的部分。

关于偏移量，其实当前 \(T_i\) 就是偏移量。注意我们这些操作其实都有可能有中间插入，所以得用堆。

code

loj3563 BalticOI2021

设 \(f[u,0/1,0/1]\) 代表以 \(u\) 为根的子树，\(u\) 是否翻了，以及 \(u\) 是 \(0\) 还是 \(1\)。然后使得子树内所有点是 \(0\) 的最小次数。

转移就做卷积即可。此题关键在于想到 \(f[u,0/1]\) 的 dp 后发现需要再加一维状态。

code