2019 牛客多校第九场

发表于 2019-08-15 分类于算法阅读次数： 70 本文字数： 8k 阅读时长 ≈ 7 分钟

A. The power of Fibonacci

upsolved

求斐波那契数列的 $m$ 次方的前 $n$ 项的和模 1e9 的值 $(1 <= n <= 1 e 9, 1 <= m <= 1000)$

首先要知道斐波那契数列模意义下是有循环节的，它的循环节也必定是它的 $m$ 次方的循环节

然后把 $1 e 9$ 拆成 $2^{9} * 5^{9}$ , 对 $2^{9}$ 和 $5^{9}$ 这两个模数分别找循环节， $2^{9}$ 的循环节是 768, $5^{9}$ 的循环节是 7812500

这两个分别求出了然后拼起来就可以得到答案了

ps: 为什么快速幂的时候每次把模数 ( $2^{9}$ 或 $5^{9}$ ) 传进去的时间是直接把模数钉死为 1e9 的三倍啊...

#include <bits/stdc++.h>
using namespace std;

const int N = 8e6 + 10;
const int mod[2] = {512, 125 * 125 * 125};

int f[N];
int ans[2];
int n, m;

int qp(int a, int n, int mod = 1000000000) {
	int res = 1;
	while(n) {
		if(n & 1)
			res = 1LL * res * a % mod;
		a = 1LL * a * a % mod;
		n >>= 1;
	}
	return res;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int k = 0; k < 2; ++k) {
		f[0] = 0; f[1] = 1;
		int j = 2;
		for(; ; ++j) {
			f[j] = f[j - 1] + f[j - 2];
			if(f[j] >= mod[k]) f[j] -= mod[k];
			if(f[j] == 0 && f[j - 1] == 1) break;
		}
		for(int i = 0; i < j; ++i) {
			int cnt = n / j + (n % j >= i);
			ans[k] = (ans[k] + 1LL * cnt * qp(f[i], m)) % mod[k];
		}
	}
	while(ans[1] % mod[0] != ans[0]) ans[1] += mod[1];
	printf("%d\n", ans[1]);
	return 0;
}

B. Quadratic equation

solved at 00:53

队友做的，二次剩余，不会

D. Knapsack Cryptosystem

solved at 00:20

$n$ 个物品，每个物品有重量，你要找到一个子集使得物品的重量和恰好为 $s$ $(1 <= n <= 36)$ 输入保证有唯一解

折半搜索，先把考虑前一半，二进制状压把它们能组成的所有情况全部丢到 $m a p$ 里去，然后考虑后一半，每次二进制状压然后去 $m a p$ 里寻找解

#include <bits/stdc++.h>
using namespace std;

int n, p, q;
long long s, a[40];
int to[(1 << 18) + 10];

map<long long, int> pp;

void init() {
	int msk = 2;
	to[1] = 0;
	for(int i = 1; i <= 17; ++i) {
		to[msk] = i;
		msk *= 2;
	}
}

void print(int maskp, int maskq) {
	for(int i = 0; i < p; ++i) 
		printf("%d", 1 & (maskp >> i));
	for(int i = 0; i < q; ++i)
		printf("%d", 1 & (maskq >> i));
	puts("");
}

int main() {
	init();
	cin >> n >> s;
	for(int i = 0; i < n; ++i)
		cin >> a[i];
	p = n / 2;
	q = n - p;
	for(int i = 0; i < (1 << p); ++i) {
		long long tmp = 0;
		for(int j = i; j; j -= j & -j)
			tmp += a[to[j & -j]];
		pp[tmp] = i;
	}
	for(int i = 0; i < (1 << q); ++i) {
		long long tmp = 0;
		for(int j = i; j; j -= j & -j) 
			tmp += a[to[j & -j] + p];
		auto it = pp.lower_bound(s - tmp);
		if(it->first + tmp == s) {
			print(it->second, i);
			return 0;
		}
	}
	puts("-1");
	return 0;
}

E. All men are brothers

solved at 00:49

$n$ 个人，一开始互相都不认识， $m$ 次操作，每次会让两个人互相认识，这种认识关系具有传递性和对称性，每次操作后要求输出选择 $4$ 个人互相都不认识的方案数

并查集维护连通块大小即可

考虑合并两个连通块，那么答案会比上一次的答案减少一些，减少的是这两个连通块各选一个，再从外面选不在同一个连通块里的两个的方案数，具体就不写了，看代码 (sz 指所有连通块大小的平方和)

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, m, x, y;
int fa[N], size[N];
long long sz;
unsigned long long ans;

int find(int x) {
	return fa[x] == x ? x : find(fa[x]);
}

void unite(int x, int y) {
	int fx = find(x), fy = find(y);
	if(fx != fy) {
		if(size[fx] < size[fy])
			swap(fx, fy);
		fa[fy] = fx;
		size[fx] += size[fy];
	}
}

int main() {
	scanf("%d%d", &n, &m);
	if(n <= 3) {
		for(int i = 0; i <= m; ++i)
			puts("0");
		return 0;
	}
	for(int i = 1; i <= n; ++i) {
		fa[i] = i;
		size[i] = 1;
	}
	ans = 1ULL * n * (n - 1) / 2 * (n - 2) / 3 * (n - 3) / 4;
	printf("%llu\n", ans);
	sz = n;
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d", &x, &y);
		if(find(x) == find(y)) {
			printf("%llu\n", ans);
			continue;
		}
		int sx = size[find(x)], sy = size[find(y)];
		ans -= 1ULL * sx * sy * (1ULL * (n - sx - sy) * (n - sx - sy) - (sz - 1LL * sx * sx - 1LL * sy * sy)) / 2;
		sz -= 1LL * sx * sx;
		sz -= 1LL * sy * sy;
		sz += 1LL * (sx + sy) * (sx + sy);
		printf("%llu\n", ans);
		unite(find(x), find(y));
	}
	return 0;
}

H. Cutting Bamboos

solved at 03:11(+2)

有 $n$ 株竹子，每株有高度， $q$ 次询问，每次询问一个区间 $l, r$ ，给定 $x, y$

，指的是水平方向切了 $y$ 刀并且每一刀切下来的竹子总量相同且最后一刀高度为 $0$ , 求第 $x$ 刀的高度

首先每一刀切下来的总量相同，那么可以求出第 $x$ 刀到第 $y$ 到切下的总量，然后二分答案，查询当前高度下的竹子总量（小于等于刀的高度的就是竹子本身高度，大于的是刀的高度），那么相当于求区间小于 $k$ 的数的个数以及它们的和，可以用主席树实现，总复杂度 $O (q \log (n) (\log (h) + 50))$ (50 是浮点数二分次数，可能不需要这么多)

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

struct node {
	int l, r, cnt;
	long long sum;
}Tree[N * 20];
int root[N];

int cnt;

void init() {
	cnt = 0;
	root[0] = 0;
	Tree[0].l = Tree[0].r = Tree[0].cnt = Tree[0].sum = 0;
}

void update(int &rt, int l, int r, int num) {
	Tree[++cnt] = Tree[rt];
	rt = cnt;
	Tree[rt].cnt++;
	Tree[rt].sum += num;
	if(l == r)
		return;
	int mid = l + r >> 1;
	if(num <= mid)
		update(Tree[rt].l, l, mid, num);
	else
		update(Tree[rt].r, mid + 1, r, num);
}

pair<int, long long> query(int i, int j, int num, int l, int r) {
	if(l == r)
		return make_pair(Tree[j].cnt - Tree[i].cnt, Tree[j].sum - Tree[i].sum);
	int mid = l + r >> 1;
	if(num <= mid) 
		return query(Tree[i].l, Tree[j].l, num, l, mid);
	pair<int, long long> tmp = query(Tree[i].r, Tree[j].r, num, mid + 1, r);
	return make_pair(Tree[Tree[j].l].cnt - Tree[Tree[i].l].cnt + tmp.first, Tree[Tree[j].l].sum - Tree[Tree[i].l].sum + tmp.second);
}

int n, q, l, r, x, y;
int h[N];
long long sumh[N];

double check(double height) {
	if(height < 1) 
		return (r - l + 1) * height;
	int c; long long s;
	tie(c, s) = query(root[l - 1], root[r], (int)height, 1, 100000);
	return s + (r - l + 1 - c) * height;
}

int main() {
	init();
	scanf("%d%d", &n, &q);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &h[i]);
		root[i] = root[i - 1];
		update(root[i], 1, 100000, h[i]);
		sumh[i] = sumh[i - 1] + h[i];
	}
	while(q--) {
		scanf("%d%d%d%d", &l, &r, &x, &y);
		int ll = 0, rr = 1e5, ans;
		double tar = (1.0 * y - x) / y * (sumh[r] - sumh[l - 1]);
		while(ll <= rr) {
			int mid = ll + rr >> 1;
			if(check(mid) <= tar) {
				ans = mid;
				ll = mid + 1;
			}
			else {
				rr = mid - 1;
			}
		}
		double o, lll = ans, rrr = ans + 1;
		for(int _ = 0; _ <= 50; ++_) {
			o = (lll + rrr) / 2;
			if(check(o) <= tar) 
				lll = o;
			else
				rrr = o;
		}
		printf("%.15f\n", o);
	}
	return 0;
}

I. KM and M

upsolved

给你 $N, M (1 <= N <= 1 e 18, 1 <= M <= 1 e 11)$ ，求 $\sum_{k = 1}^{N} ((k M) & M) m o d (1 e 9 + 7)$

按二进制位每一位考虑，考虑第 $i$ 位，那么一个数 $x$ 的贡献就是 $(2^{i}) & x$ , 考虑 $x$ 的第 $i$ 位是否为 $1$ ，显然可以用 $\frac{x}{2^{i}} - 2 * \frac{x}{2^{i + 1}}$ 表示

那么对于 $N$ 个数，第 $i$ 位为 $1$ 的就是 $\sum_{i = 1}^{N} \frac{M * i}{2^{i}} - 2 * \sum_{i = 1}^{N} \frac{M * i}{2^{i + 1}}$

这两个求和都是求等差数列除以一个数的和，可以用类欧几里得算法求解

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int mod = 1e9 + 7, inv2 = (mod + 1) / 2;

LL n, m, ans;

LL calc(LL a, LL b, LL c, LL n) {
	if(!a) return 0;
	if(a >= c || b >= c) {
		LL tmp = calc(a % c, b % c, c, n);
		return (tmp + ((n % mod) * ((n + 1) % mod) % mod * inv2 % mod) * ((a / c) % mod) % mod + ((n + 1) % mod) * ((b / c) % mod) % mod) % mod;
	}
	LL f = ((__int128)a * n + b) / c;
	return (((n % mod) * (f % mod) % mod - calc(c, c - b - 1, a, f - 1)) % mod + mod) % mod;
}

int main() {
	cin >> n >> m;
	for(int i = 0; i < 40; ++i) if(m >> i & 1) {
		LL res = ((calc(m, 0, 1LL << i, n) - 2 * calc(m, 0, 2LL << i, n)) % mod + mod) % mod;
		ans = (ans + (1LL << i) % mod * res % mod) % mod;
	}
	printf("%lld\n", ans);
	return 0;
}

J. Symmetrical Painting

solved at 01:38(+4)

为什么 map 一直 MLE 啊.....

二维平面上有 n 个矩形，每个矩形左下角是 $(i - 1, L_{i})$ , 右上角是 $(i, R_{i})$ ，矩形一开始全是黑色，平面不被矩形覆盖的地方是白色，你要把某些黑色区域涂白（一个矩形可以内部颜色不一样），使得黑色区域是一个轴对称图形并且对称轴平行于 x 轴，求最大黑色区域面积

首先取得答案时的对称轴纵坐标要么是整数要么是 $x .5$ ，枚举对称轴，维护两个集合，一个代表当前枚举的对称轴在矩形下半部分，一个表示上半部分，每次对称轴往上移动 0.5, 第一个集合里每一个元素都会给答案贡献 1, 第二个集合贡献 - 1, 然后可能会有第一个集合的矩形跳到第二个集合（到达中线），也可能有矩形进入第一个集合（到达下底），也可能有矩形从第二个集合出去（到达上底）

实际上你并不需要真的维护集合，只需要知道集合的大小就可以了

#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 10;

int n, L[N], R[N], md[N], m;
long long tmp, ans;
int b[N * 3];
int in[N * 3], change[N * 3], out[N * 3];

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d%d", &L[i], &R[i]);
		L[i] = 2 * L[i] - 1;
		R[i] = 2 * R[i] - 1;
		md[i] = (0LL + L[i] + R[i]) / 2;
		b[3 * i - 2] = L[i];
		b[3 * i - 1] = R[i];
		b[3 * i] = md[i];
	}
	tmp = ans = 0;
	sort(b + 1, b + 3 * n + 1);
	m = unique(b + 1, b + 3 * n + 1) - b - 1;
	for(int i = 1; i <= n; ++i) {
		in[lower_bound(b + 1, b + m + 1, L[i]) - b]++;
		change[lower_bound(b + 1, b + m + 1, md[i]) - b]++;
		out[lower_bound(b + 1, b + m + 1, R[i]) - b]++;
	}
	int down = 0, up = 0;
	down += in[1];
	for(int i = 2; i <= m; ++i) {
		tmp += 1LL * (down - up) * (b[i] - b[i - 1]);
		ans = max(ans, tmp);
		down += in[i];
		down -= change[i];
		up += change[i];
		up -= out[i];
	}
	printf("%lld\n", ans);
	return 0;
}