2019牛客多校第七场

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

荣膺全场罚时最高，为什么今天和昨天都是6题，今天的我却没有了昨天的快乐呢。。。

A. String

solve at 00:28

给你一个$01$字符串$s$，你要将它分割成数量尽可能少的若干个串，使得每个串都是它的所有循环同构串中字典序最小的$(1<=T<=300, 1<=|s|<=200)$ 看上去就感觉贪心是对的，就是每次尽可能选最长的符合条件的串，然后套一个最小表示法就过了

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

int T, n;
char s[210];
vector<pair<int, int>> ans;

bool min_represent(int l, int r) {
	static char ss[210];
	for(int i = l; i <= r; ++i) {
		ss[i - l] = s[i];
	}
	int i = 0, j = 1, k = 0, len = r - l + 1;
	while(i < len && j < len && k < len) {
		int t = ss[(i+k) % len] - ss[(j+k) % len];
		if(t == 0)
			++k;
		else {
			if(t > 0)
				i += k + 1;
			else
				j += k + 1;
			if(i == j)
				++j;
			k = 0;
		}
	}
	return min(i, j) == 0;
}

void judge() {
	int l = 0, r;
	while(l < n) {
		for(r = n - 1; r >= l; --r) {
			if(min_represent(l, r)) {
				ans.push_back({l, r});
				break;
			}
		}
		l = r + 1;
	}
}

int main() {
	scanf("%d", &T);
	while(T--) {
		ans.clear();
		scanf("%s", s);
		n = strlen(s);
		judge();
		for(int i = 0; i < ans.size(); ++i) {
			for(int j = ans[i].first; j <= ans[i].second; ++j)
				putchar(s[j]);
			putchar(" \n"[i + 1 == ans.size()]);
		}
	}
	return 0;
}

B. Irreducible Polynomial

solved at 04:50(+38)

是的，这就是我们荣获罚时冠军的原因

题意是给你一个多项式，询问这个多项式能否在实数域内因式分解

然后我就口胡了一个假算法，即判断这个函数有没有零点（这是不对的，x^4+2x2+1$没有实数域上的零点，然而显然可以因式分解）

于是我们就写了模拟退火求最小值，牛顿迭代求零点等方法，调了无数次的参。。。

正解是这样的：

首先$n$次方程在复数域上有$n$个根，若$f(\omega)=0$，则$f(\overline \omega)=0$, 即原函数可以提取出$(x-\omega)(x-\overline \omega)$，而这两个东西乘起来就没有虚数部分了，因此三次及以上的多项式在实数域上一定可以因式分解

零次和一次显然不可以，二次看判别式。。。

C. Governing sand

solved at 02:51(+7)

有$n$种树，每种树有高度，数量以及砍伐代价，你要砍掉一些树使得最高的树的数量超过一半，求最小代价$(1<=n<=1e5)$

和杭电多校第三场的1007几乎一样，从小到大枚举高度线段树维护数量和代价就好了

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

const int N = 1e5 + 10;

struct GKP {
	int h, c, p, cc;
}a[N];
int n, b[N], m;
long long sum[N];

long long cost[N << 2], cnt[N << 2];

void build(int rt, int l, int r) {
	cost[rt] = cnt[rt] = 0;
	if(l == r) return;
	int mid = l + r >> 1;
	build(rt << 1, l, mid);
	build(rt << 1 | 1, mid + 1, r);
}

void update(int rt, int l, int r, int pos, int val, int num) {
	if(l == r) {
		cnt[rt] += num;
		cost[rt] += 1LL * val * num;
		return;
	}
	int mid = l + r >> 1;
	if(pos <= mid) update(rt << 1, l, mid, pos, val, num);
	else update(rt << 1 | 1, mid + 1, r, pos, val, num);
	cost[rt] = cost[rt << 1] + cost[rt << 1 | 1];
	cnt[rt] = cnt[rt << 1] + cnt[rt << 1 | 1];
}

long long query(int rt, int l, int r, long long num) {
	if(num <= 0) return 0;
	if(l == r) 
		return cost[rt] / cnt[rt] * num;
	int mid = l + r >> 1;
	if(cnt[rt << 1] < num) return cost[rt << 1] + query(rt << 1 | 1, mid + 1, r, num - cnt[rt << 1]);
	else return query(rt << 1, l, mid, num);
}

int main() {
	while(~scanf("%d", &n)) {
		for(int i = 1; i <= n; ++i) {
			scanf("%d%d%d", &a[i].h, &a[i].c, &a[i].p);
			b[i] = a[i].c;
		}
		sort(a + 1, a + n + 1, [&](GKP &i, GKP &j){return i.h < j.h;});
		sum[n + 1] = 0;
		for(int i = n; i; --i) {
			sum[i] = sum[i + 1] + 1LL * a[i].c * a[i].p;
		}
		long long ans = 1e18, cnt = 0, tot = 0;
		sort(b + 1, b + n + 1);
		m = unique(b + 1, b + n + 1) - b - 1;
		stack<GKP> s;
		for(int i = 1; i <= n; ++i)
			a[i].cc = lower_bound(b + 1, b + m + 1, a[i].c) - b;
		build(1, 1, m);
		for(int i = 1; i <= n; ++i) {
			tot += a[i].p;
			if(a[i].h == a[i - 1].h) {
				cnt += a[i].p;
				s.push(a[i]);
			}
			else {
				while(!s.empty()) {
					GKP u = s.top(); s.pop();
					update(1, 1, m, u.cc, u.c, u.p);
				}
				s.push(a[i]);
				cnt = a[i].p;
			}
			ans = min(ans, query(1, 1, m, tot - 2 * cnt + 1) + sum[i + 1]);
		}
		cout << ans << endl;
	}
	return 0;
}

D. Number

solved at 00:11

给你一个$n$和一个$p$，你要输出一个$n$位数，且是$p$的倍数

如果$n$小于$p$的位数则无解，否则直接输出$p$，后面补上足够的$0$即可

E. Find the median

upsolved

你有一个初始为空的数列，$n(1<=n<=4e5)$次操作，每次给定一个区间$L, R$，你将区间里所有数加入到数列中，然后求数列的中位数（偶数个取较小值）

将$R[i]$全部自增1后离散化，会得到至多$2n$个点，实际上每个点代表一个区间，代表的是大于等于当前这个点且小于后一个点的区间，对这些点建线段树，维护区间里数的总数以及区间被更新了多少次（非叶子节点的这个值只用于延迟更新，只有叶子节点的参与最终计算），然后支持查询第$k$大的数就好了

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

const int N = 4e5 + 10;

int x[N], y[N], A[3], B[3], C[3], M[3], L[N], R[N];
int num[N << 1], tot, n;
long long pre[N << 1], now;

int lazy[N << 3], cnt[N << 3];
long long sum[N << 3];

void pushup(int rt) {
	sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

void pushdown(int rt, int l, int r) {
	int mid = l + r >> 1;
	if(lazy[rt]) {
		lazy[rt << 1] += lazy[rt];
		lazy[rt << 1 | 1] += lazy[rt];
		cnt[rt << 1] += lazy[rt];
		cnt[rt << 1 | 1] += lazy[rt];
		sum[rt << 1] += 1LL * (pre[mid] - pre[l - 1]) * lazy[rt];
		sum[rt << 1 | 1] += 1LL * (pre[r] - pre[mid]) * lazy[rt];
		lazy[rt] = 0;
	}
}

void update(int rt, int l, int r, int L, int R) {
	if(L <= l && r <= R) {
		lazy[rt]++; cnt[rt]++;
		sum[rt] += (pre[r] - pre[l - 1]);
		return;
	}
	pushdown(rt, l, r);
	int mid = l + r >> 1;
	if(L <= mid) 
		update(rt << 1, l, mid, L, R);
	if(R > mid)
		update(rt << 1 | 1, mid + 1, r, L, R);
	pushup(rt);
}

int query(int rt, int l, int r, long long k) {
	if(l == r) {
		return num[l] + (k - 1) / cnt[rt];
	}
	pushdown(rt, l, r);
	int mid = l + r >> 1;
	if(sum[rt << 1] < k) return query(rt << 1 | 1, mid + 1, r, k - sum[rt << 1]);
	return query(rt << 1, l, mid, k);
}

int main() {
	cin >> n;
	cin >> x[1] >> x[2] >> A[1] >> B[1] >> C[1] >> M[1];
	cin >> y[1] >> y[2] >> A[2] >> B[2] >> C[2] >> M[2];
	for(int i = 1; i <= n; ++i) {
		if(i >= 3) {
			x[i] = (1LL * A[1] * x[i - 1] + 1LL * B[1] * x[i - 2] + C[1]) % M[1];
			y[i] = (1LL * A[2] * y[i - 1] + 1LL * B[2] * y[i - 2] + C[2]) % M[2];
		}
		L[i] = min(x[i], y[i]) + 1;
		R[i] = max(x[i], y[i]) + 2;
		num[i * 2 - 1] = L[i];
		num[i * 2] = R[i];
	}
	sort(num + 1, num + 2 * n + 1);
	tot = unique(num + 1, num + 2 * n + 1) - num - 1;
	num[tot + 1] = num[tot];
	for(int i = 1; i <= tot; ++i) {
		pre[i] = pre[i - 1] + num[i + 1] - num[i];
	}
	for(int i = 1; i <= n; ++i) {
		L[i] = lower_bound(num + 1, num + tot + 1, L[i]) - num;
		R[i] = lower_bound(num + 1, num + tot + 1, R[i]) - num - 1;
		now += pre[R[i]] - pre[L[i] - 1];
		update(1, 1, tot, L[i], R[i]);
		printf("%d\n", query(1, 1, tot, (now + 1) / 2));
	}
	return 0;
}

H. Pair

solved at 04:18(+1)

给你三个数$A, B, C(1<=A,B,C<=1e9)$, 求满足$1<=i<=A\ \&\&\ 1<=j<=B\ \&\& (i\ and\ j>C\ ||\ i\ xor\ j<C)$的$(i,j)$对数量

正着不太好求，我们反过来求$i\ and\ j<=C \ \&\&\ i\ xor\ j >=C$的数量

考虑二进制数位$dp$，从高位往低位考虑，一共有五维

第一维表示已经填了几位，第二维表示当前已经填的位的$and$是比$C$大还是一样大，第三位表示已经填的位的$xor$是比$C$小还是一样大，第四五维表示已经填的数和$A,B$的关系（是一样大还是已经更小了）后四维都是为$0$表示相等

转移的时候枚举当前位这两个数分别填$0$还是$1$，不合法的情况就不转移

注意这样最后可能填的数是$0$，而题目要求大于等于$1$，考虑一下就好了

复杂度$O(T2^6\log {1e9})$

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

long long dp[31][2][2][2][2], ans;
int n, A, B, C, T, a[33], b[33], c[33];

int get_bit(int x, int aa[]) {
	for(int i = 0; i <= 29; ++i)
		aa[i] = (x >> i) & 1;
}

int main() {
	cin >> T;
	while(T--) {
		cin >> A >> B >> C;
		ans = 0;
		memset(dp, 0, sizeof(dp));
		get_bit(A, a);
		get_bit(B, b);
		get_bit(C, c);
		dp[30][0][0][0][0] = 1;
		for(int i = 30; i; --i) {
			for(int _a = 0; _a < 2; ++_a) {
				for(int _b = 0; _b < 2; ++_b) {
					for(int AandB = 0; AandB < 2; ++AandB) {
						for(int AxorB = 0; AxorB < 2; ++AxorB) {
							for(int AtmpA = 0; AtmpA < 2; ++AtmpA) {
								for(int BtmpB = 0; BtmpB < 2; ++BtmpB) {
									if(AtmpA == 0 && _a > a[i - 1]) continue;
									if(BtmpB == 0 && _b > b[i - 1]) continue;
									if(AandB == 0 && (_a & _b) > c[i - 1]) continue;
									if(AxorB == 0 && (_a ^ _b) < c[i - 1]) continue;
									int newAandB = AandB | ((_a & _b) < c[i - 1]);
									int newAxorB = AxorB | ((_a ^ _b) > c[i - 1]);
									int newAtmpA = AtmpA | (_a < a[i - 1]);
									int newBtmpB = BtmpB | (_b < b[i - 1]);
									dp[i - 1][newAandB][newAxorB][newAtmpA][newBtmpB] += dp[i][AandB][AxorB][AtmpA][BtmpB];
								}
							}
						}
					}		
				}
			}
		}
		ans = 1LL * A * B;
		for(int a = 0; a < 2; ++a)
			for(int b = 0; b < 2; ++b)
				for(int c = 0; c < 2; ++c) 
					for(int d = 0; d < 2; ++d)
						ans -= dp[0][a][b][c][d];
		ans += max(0, A - C + 1);
		ans += max(0, B - C + 1);
		cout << ans << endl;
	}
	return 0;
}

J. A+B problem

solve at 00:07

定义$f(x)$为把$x$各位数倒过来的数，给你$A, B$, 求$f(f(A) + f(B))$

牛客能交python好评