牛客挑战赛78-题解

A

题意是：要求切割金条，使得能够用分散的金条组成 之间的所有数字。

注意到，面临的问题是：

  • 长度为 的金条无法获得，所以需要切割一刀获得长度为 的金条
  • 此时长度为 的金条无法获得，所以需要切割一刀获得长度为 的金条
  • 此时利用 发现长度为 的金条无法获得，所以需要切割一刀获得长度为 的金条
  • 此时利用 发现长度为 的金条无法获得，所以需要切割一刀获得长度为 的金条
  • ......

知道某个时刻，发现长度为 的金条可以获得，那么答案自然就确定了。

还需要注意一个点，那就是如果剩余金条长度不比需要切割到的金条长度长，那么最后一刀是可以省略的。

时间复杂度：

B

预处理，记 ，那么总共有 个矩形需要计算。

相邻矩形之间的交集很大，需要修改的只有 个位置，那么对整个数组进行“弓”形遍历（或者蛇形数组遍历）（二维滑动窗口），需要的计算次数大致为：，这个函数在 取 附近时取得最大值，可以通过 的数据。

时间复杂度：

C

利用处理区间元素种类的想法，离线处理所有的询问。

从左往右扫描每一个元素（在扫描的过程中维护一个树状数组），并记录到现在位置（记现在位置为 ）为止前缀中每种元素出现的个数，那么对于出现次数达到 的元素，我们对其在树状数组中进行处理。

  • 假设待处理颜色为 ，其从 位置向前数第 次出现位置为 （即区间 中出现了 次颜色 ），第 次出现的位置为 。
  • 那么在树状数组中对 位置执行 操作，对 位置执行 操作。

当操作完成后，对所有以 为结尾的查询区间进行回答即可，答案即是树状数组上对应区间的和。

时间复杂度：

D

利用前后两个栈即可模拟光标，光标前方的数用栈维护，光标后方的数用后方的栈维护。

记 为此时的数字总个数，由于栈只有一端会变化，那么维护前方栈中的前缀大数值（记 为 的前缀大数取模后的值），维护后方栈中的后缀大数值（记 为 的后缀大数取模后的值）是 的。

每一次询问会对应两个栈中各一段的求解，这一步可以利用字符串 hash 的想法，预处理出 用其代表 ，再预处理出 用其代表 。

  • 前方栈中区间 的大数取模值：，其中
  • 后方栈中区间 的大数取模值：，其中
  • 最终的答案即为：，其中

时间复杂度：

E

注意到消耗指令只会减少资源，而查询指令只会增加资源，于是发现每个消耗指令都只会提升对查询指令的要求。

所以可以逐步加入消耗指令，然后求出此时对查询指令的最小要求，即：缺少的最多资源数量、最靠左的缺少资源位置、最靠右的缺少资源位置。也就是：最少需要补充多少个资源，哪段区间需要补充资源。而上面这个区间只会向左右扩大而不会缩小，同样的，最少需要补充的资源数也是单调的。

上述做法可以利用线段树实现：区间减法、最靠左的小于 的位置、最靠右的小于 的位置。

预处理出所有的 个限制区间后，对于每个询问，只需要在这 个区间中进行二分查找即可。

时间复杂度：

F

对于一个查询，最后得到的结果必然是一些选或不选的段，实际上被选取的段不会很多：

  • 假设最终被选取的结果区间是：。
  • 那么没有被选取的区间是：。
  • 根据题意贪心，对于任意的 都有：
  • 根据上述式子，可以发现每一段的极小值（第一个数）是成倍增长的：
    • 设
    • 那么有：
    • 那么有：
    • 根据上面的贪心式有：
    • 同样的，可以发现：
    • 那么对于任意的 都有： 成立
    • 由于 数组的取值不超过 ，故被选取的区间数量最多只会有 60 个左右

由于被选取的区间不会很多，所以下一步就是需要快速确定每一个区间的左右端点即可得解，假设当前还需要 个物品确定区间的方式可以二分：

  • 首先二分最小的 使得 ，此时的 即是最后一个区间的右边界
  • 以 为起点，向前二分一个最大的 （），使得
  • 那么最后一个区间可以被确定为
  • 重复上述操作，直到 ，根据上面的证明，这里的重复次数最多会在 60 次左右

时间复杂度： 其中 取

G

对图上结点进行分类，连边数不小于 的记为“大结点”，其它的结点记为“小结点”，那么图中最多有 个大结点。

对大结点创建 条链表，用来存储大结点每个相邻结点的编号（放在对应颜色链表上），对小结点存储一个链表，用来记录每个相邻结点编号。

接下来依次进行每个操作并处理，如果处理时遇到某两个结点颜色相同，那就用并查集合并这两个结点，并对新的结点分为大或小结点进行处理，这个合并的过程涉及相邻结点编号的合并，采用启发式合并即可，这一步的总时间复杂度为 。

如果当前操作的是大结点：

  • 根据大结点变成的新颜色，暴力的将对应颜色的相邻结点都进行合并即可，这一步的总时间复杂度为：
  • 暴力扫描周围所有的大结点，修改这个大结点中对应记录的颜色链表

如果当前操作的是小结点：

  • 暴力扫描周围的所有结点，如果颜色相同就合并，这一步的总时间复杂度为：
  • 暴力扫描周围所有结点，如果这个结点是大结点，那就修改这个结点对应记录的颜色链表

时间复杂度：

空间复杂度：

综合时间和空间， 取 400 左右即可通过本题。

参考代码

A

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

void solved() {
	int n, m;	cin >> n >> m;
	int ans = 0, gt = 0;
	while(gt < m) {
		gt += 1 << ans;
		ans ++;
		if(n - gt <= gt + 1) gt = n;
	}
	cout << ans << endl;
}
int main() {
	int ttx;	cin >> ttx;	while(ttx --)
	solved();
	return 0;
}

B

#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = a, IM = b; i <= IM; i ++)
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

const int N = 709, M = 1000009;

int a[N][N], cnt[M], ans[N][N];
int sum;

void add(int x) {
	if(cnt[x] ++ == 1) sum ++;
}
void del(int x) {
	if(cnt[x] -- == 2) sum --;
}
void solved() {
	int n, m, k;	cin >> n >> m >> k;
	_for(i, 1, n) _for(j, 1, n) cin >> a[i][j];
	int x = 1, y = 1;
	_for(i, 1, k) _for(j, 1, k) add(a[i][j]);
	ans[x][y] = sum;
	while(x <= n - k + 1) {	// 弓形遍历
		while(y <= n - k) {	y ++;	// 朝右
			_for(i, x, x + k - 1) del(a[i][y - 1]), add(a[i][y + k - 1]);
			ans[x][y] = sum;
		}
		if(x > n - k) break;	x ++;	// 朝下
		_for(j, y, y + k - 1) del(a[x - 1][j]), add(a[x + k - 1][j]);
		ans[x][y] = sum;
		while(y >= 2) {	y --;		// 朝左
			_for(i, x, x + k - 1) add(a[i][y]), del(a[i][y + k]);
			ans[x][y] = sum;
		}
		if(x > n - k) break;	x ++;	// 朝下
		_for(j, y, y + k - 1) del(a[x - 1][j]), add(a[x + k - 1][j]);
		ans[x][y] = sum;
	}
	while(m --) {
		int x, y;	cin >> x >> y;
		cout << ans[x][y] << endl;
	}
	return ;
}
int main() {
	IOS
	solved();
	return 0;
}

C

#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = a, IM = b; i <= IM; i ++)
#define _rep(i, a, b) for(int i = a, IM = b; i >= IM; i --)
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using ll = long long;

const int M = 1000009;

int n, m, k;
int a[M];
int l[M], r[M], c[M];
ll ans[M];
int d[M], now[M];

ll sum[M];
void add(int x, int tp) {
	while(x <= n) {
		sum[x] += tp;
		x += x & -x;
	}
}
ll ask(int x) {
	ll ans = 0;
	while(x) {
		ans += sum[x];
		x -= x & -x;
	}
	return ans;
}
ll qur(int l, int r) {
	return ask(r) - ask(l - 1);
}
void init() {
	_for(i, 1, m) c[i] = i;
	sort(c + 1, c + 1 + m, [&](int x, int y) -> bool {
		return r[x] < r[y];
	});
	_for(i, 1, n) d[i] = i;
	sort(d + 1, d + 1 + n, [&](int x, int y) -> bool {
		if(a[x] != a[y]) return a[x] < a[y];
		return x < y;
	});
	_rep(i, n, 1) now[a[d[i]]] = i;
}
void modify(int col) {
	int y = now[col] - k, x = y - 1, z = y + 1;
	if(x > 0 && a[d[x]] == col) add(d[x], col);
	if(y > 0 && a[d[y]] == col) add(d[y], -2 * col);
	if(z > 0 && a[d[z]] == col) add(d[z], col);
	now[col] ++;
}
void solved() {
	cin >> n >> m >> k;
	_for(i, 1, n) cin >> a[i];
	_for(i, 1, m) cin >> l[i] >> r[i];
	init();
	int tp = 1;
	_for(i, 1, n) {
		modify(a[i]);
		while(tp <= m && r[c[tp]] == i) {
			ans[c[tp]] = qur(l[c[tp]], r[c[tp]]);
			tp ++;
		}
	}
	_for(i, 1, m) cout << ans[i] << endl;
	return ;
}
int main() {
	IOS
	solved();
	return 0;
}

D

#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = a, IM = b; i <= IM; i ++)
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using ll = long long;

const int M = 1000009, mod = 998244353;

int a[M], ta, b[M], tb;
ll p[M], fp[M];

int pw(ll x, int y) {
	int ans = 1;
	while(y) {
		if(y & 1) ans = ans * x % mod;
		x = x * x % mod, y >>= 1;
	}
	return ans;
}
void solved() {
	int q, m;	cin >> q >> m;
	p[0] = 1, fp[0] = 1, fp[1] = pw(10, mod - 2);
	_for(i, 1, q) p[i] = p[i - 1] * 10 % mod;
	_for(i, 2, q) fp[i] = fp[i - 1] * fp[1] % mod;
	q += m;	
	while(q --) {
		char op;	cin >> op;
		if(op == 'Q') {
			int l, r;	cin >> l >> r;	r = l + r - 1;
			int ans = 0;
			if(l <= ta) {
				if(r <= ta) ans += (a[r] + mod - a[l - 1] * p[r - l + 1] % mod) % mod;
				else ans += (a[ta] + mod - a[l - 1] * p[ta - l + 1] % mod) % mod;
			}
			if(r > ta) {
				ans = ans * p[r - ta] % mod;	l = max(l, ta + 1);
				l = ta + tb - l + 1, r = ta + tb - r;
				ans += (b[l] + mod - b[r]) * fp[r] % mod;
			}
			cout << ans % mod << endl;
		} else if(op == 'I') {
			int x;	cin >> x;
			a[++ ta] = (a[ta] * 10ll + x) % mod;
		} else if(op == 'D') {
			ta --;
		} else if(op == 'F') {
			int x = (a[ta] + mod - a[ta - 1] * 10ll % mod) % mod;
			ta --;
			b[++ tb] = (x * p[tb] + b[tb]) % mod;
		} else {
			int x = (b[tb] + mod - b[tb - 1]) * fp[tb - 1] % mod;
			tb --;
			a[++ ta] = (a[ta] * 10ll + x) % mod;
		}
 	}
	return ;
}
int main() {
	IOS
	solved();
	return 0;
}

E

#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = a, IM = b; i <= IM; i ++)
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using ll = long long;

const int N = 200009, M = 1000009;

int a[M];
int ml[N], mr[N];
ll mc[N];

int m, n;

ll mn[M << 2], flag[M << 2];
void updata(int p) {
	int l = p << 1, r = l | 1;
	mn[p] = min(mn[l], mn[r]);
}
void push_down(int p) {
	int l = p << 1, r = l | 1;
	mn[l] += flag[p], mn[r] += flag[p];
	flag[l] += flag[p], flag[r] += flag[p];
	flag[p] = 0;
}
void build(int l = 1, int r = n, int p = 1) {
	if(l == r) {
		mn[p] = a[l];
		return ;
	}
	int mid = l + r >> 1;
	build(l, mid, p << 1);
	build(mid + 1, r, p << 1 | 1);
	updata(p);
}
void modify(int lx, int rx, int x, int l = 1, int r = n, int p = 1) {
	if(l >= lx && r <= rx) {
		mn[p] += x, flag[p] += x;
		return ;
	}
	push_down(p);
	int mid = l + r >> 1;
	if(lx <= mid) modify(lx, rx, x, l, mid, p << 1);
	if(rx > mid) modify(lx, rx, x, mid + 1, r, p << 1 | 1);
	updata(p);
}
int ask1(int l = 1, int r = n, int p = 1) {
	if(mn[p] > 0) return 0;
	if(l == r) return l;
	push_down(p);
	int mid = l + r >> 1;
	if(mn[p << 1 | 1] < 0) return ask1(mid + 1, r, p << 1 | 1);
	return ask1(l, mid, p << 1);
}
int ask2(int l = 1, int r = n, int p = 1) {
	if(mn[p] > 0) return n + 1;
	if(l == r) return l;
	push_down(p);
	int mid = l + r >> 1;
	if(mn[p << 1] < 0) return ask2(l, mid, p << 1);
	return ask2(mid + 1, r, p << 1 | 1);
}
void work() {
	int L, R, c;	cin >> L >> R >> c;
	int l = 1, r = m + 1;
	while(l < r) {
		int mid = l + r >> 1;
		if(ml[mid] >= L && mr[mid] <= R && mc[mid] + c >= 0) l = mid + 1;
		else r = mid;
	}
	if(l == m + 1) cout << -1 << endl;
	else cout << l << endl;
	return ;
}
void solved() {
	int q;	cin >> n >> m >> q;
	_for(i, 1, n) cin >> a[i];
	build();
	_for(i, 1, m) {
		int l, r, c;	cin >> l >> r >> c;
		modify(l, r, -c);
		ml[i] = ask2(), mr[i] = ask1(), mc[i] = mn[1];
	}
	while(q --) work();
	return ;
}
int main() {
	IOS
	solved();
	return 0;
}

F

#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = a, IM = b; i <= IM; i ++)
#define _rep(i, a, b) for(int i = a, IM = b; i >= IM; i --)
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using ll = long long;

const int N = 300009, M = 1000009, mod = 998244353;
const ll inf = 2.01e18;

ll a[M], b[M];
int p[M];
ll sum[M];
int n;

void ask() {
	ll x;	cin >> x;
	ll ans = 0;
	while(x > 0) {
		int l = 1, r = n;
		while(l < r) {
			int mid = l + r >> 1;
			if(sum[mid] < x) l = mid + 1;
			else r = mid;
		}
		int R = l;
		l = 0, r = R - 1;
		while(l < r) {
			int mid = l + r + 1 >> 1;
			if(sum[R] - a[mid] >= x) l = mid;
			else r = mid - 1;
		}
		ans += mod + p[R] - p[l];
		x -= sum[R] - sum[l];
	}
	cout << ans % mod << endl;
	return ;
}
void solved() {
	int m;	cin >> n >> m;
	_for(i, 1, n) cin >> a[i];
	_for(i, 1, n) p[i] = (2 * p[i - 1] + 1) % mod;
	_for(i, 1, n) {
		sum[i] = sum[i - 1] + a[i];
		if(sum[i] > inf) {
			n = i;
			break;
		}
	}
	_for(i, 1, m) ask();
	return ;
}
int main() {
	IOS
	solved();
	return 0;
}

G

#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = a, IM = b; i <= IM; i ++)
#define _rep(i, a, b) for(int i = a, IM = b; i >= IM; i --)
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define _mp(a, b) make_pair(a, b)
using pii = pair<int, int>;

const int N = 100009, M = 400, mod = 998244353, inf = 1.01e9;

int vb[100000 / M + 9][N];	// 大点的 颜色链头
int nex[200000 * M], to[200000 * M], ft;
void add(int id, int c, int x) {	// 增加一个结点
	nex[++ ft] = vb[id][c];
	vb[id][c] = ft, to[ft] = x;
}

vector<int> va[N << 1];	// 大点邻边、图邻边
int a[N], b[N], ans;	// 颜色、并查集
int n;

int id[N], tot, sz[N];	// 大点映射、下标、结点数

int finding(int x) {
	return b[x] == x ? x : b[x] = finding(b[x]);
}
int funq, vis[N];
void unq(vector<int> &ve) {	// 剔除重复结点、获取真实结点
	++ funq;
	int cnt = 0;
	for(int i = 0, p; i < ve.size(); i ++) {
		p = finding(ve[i]); if(vis[p] == funq) continue;
		vis[p] = funq;	ve[cnt ++] = p;
	}
	ve.resize(cnt);
}
void build(int x) {	// 建立一个新大点
	if(id[x] != 0 || va[x].size() < M) return ;
	id[x] = ++ tot;
	unq(va[x]);
	for(int c: va[x]) add(tot, a[c], c);
	sz[tot] = va[x].size();
	for(int c: va[x]) if(id[c] != 0) 
		va[x + n].emplace_back(c), va[c + n].emplace_back(x);
}
void clear(int x, int c) {	// 将颜色表中被更新过的结点剔除、获取真实结点位置
	int now = vb[x][c], pre = 0;
	for(int i = vb[x][c]; i; i = nex[i]) {
		int p = to[i];	p = finding(p);
		if(a[p] == c) to[now] = p, pre = now, now = nex[now];
	}
	if(pre == 0) vb[x][c] = 0;
	else nex[pre] = 0;
}
void work(int x, int y) {
	x = finding(x), y = finding(y);	if(x == y) return ;
	if(id[x] == id[y]) {	// 两个小点
		if(va[x].size() < va[y].size()) swap(x, y);
		for(int c: va[y]) va[x].emplace_back(c);	// 这里会有一些废边，即（自环）
		build(x);
	} else if(id[x] != 0 && id[y] != 0) {	// 两个大点
		if(sz[id[x]] < sz[id[y]]) swap(x, y);
		_for(i, 1, n) {
			clear(id[y], i);
			for(int j = vb[id[y]][i]; j; j = nex[j]) add(id[x], i, to[j]), sz[id[x]] ++;
		}
		for(int c: va[y + n]) va[x + n].emplace_back(c);
		unq(va[x + n]);
	} else {	// x 大 y 小
		if(id[x] == 0) swap(x, y);
		unq(va[y]);
		for(int c: va[y]) add(id[x], a[c], c);
		sz[id[x]] += va[y].size();
		for(int c: va[y]) if(id[c] != 0) va[x + n].emplace_back(c);
		unq(va[x + n]);
	}
	b[y] = x;	ans --;
}
void solved() {
	int m, q;	cin >> n >> m >> q;
	_for(i, 1, n) cin >> a[i];
	vector<pii> vc;	// 连接边
	_for(i, 1, m) {
		int x, y;	cin >> x >> y;
		va[x].emplace_back(y), va[y].emplace_back(x);
		if(a[x] == a[y]) vc.push_back(_mp(x, y));
	}
	_for(i, 1, n) b[i] = i;	ans = n;
	for(pii pi: vc) work(pi.first, pi.second);	vc.clear();
	while(q --) {
		int x, c;	cin >> x >> c;	x = finding(x);
		if(id[x] == 0) {
			unq(va[x]);
			for(int y: va[x]) if(c == a[y]) vc.push_back(_mp(x, y));	// 建立链接
			for(int y: va[x]) if(id[y] != 0) add(id[y], c, x);
		} else {
			clear(id[x], c);	// 清除表中无用结点
			for(int i = vb[id[x]][c]; i; i = nex[i]) vc.push_back(_mp(x, to[i]));
			vb[id[x]][c] = 0;
			unq(va[x + n]);
			for(int y: va[x + n]) {
				if(a[y] == c) vc.push_back(_mp(x, y));
				else add(id[y], c, x);
			}
		}
		a[x] = c;
		for(pii pi: vc) work(pi.first, pi.second);	vc.clear();
		cout << ans << endl;
	}
	return ;
}
int main() {
	IOS
	solved();
	return 0;
}
全部评论

相关推荐

今天 15:29
门头沟学院 Java
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-19 14:35
点赞 评论 收藏
分享
05-25 12:52
中国石油大学(华东)青岛校区 Java
点赞 评论 收藏
分享
05-05 21:45
已编辑
广州大学 Java
点赞 评论 收藏
分享
06-23 18:20
甘肃农业大学 市场
点赞 评论 收藏
分享
评论
点赞
1
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 第一份工作能做外包吗？ #
10123次浏览 101人参与
# 国企/银行/研究所公司爆料 #
137977次浏览 797人参与
# 为了找工作你花了哪些钱？ #
6134次浏览 53人参与
# 26届校招投递进展 #
774次浏览 28人参与
# 我的职场心眼子段位 #
21166次浏览 528人参与
# 如果不考虑收入，你最想做什么工作？ #
21877次浏览 133人参与
# 如何看待应届生身份？ #
118258次浏览 1144人参与
# 大学四年该怎么过，才不算浪费时间？ #
5730次浏览 57人参与
# 商战，最累的是我们 #
17267次浏览 77人参与
# 金融财会交流会 #
109060次浏览 377人参与
# 互联网公司爆料 #
124710次浏览 684人参与
# 计算机专业还有必要去大厂卷吗 #
24834次浏览 151人参与
# 你知道哪些职场黑话？ #
47070次浏览 391人参与
# 还记得你第一次面试吗？ #
198419次浏览 2934人参与
# 工作一周年分享 #
28157次浏览 151人参与
# 春招别灰心，我们一人来一句鼓励 #
113880次浏览 1307人参与
# 离家近房租贵VS离家远但房租低，怎么选 #
8228次浏览 117人参与
# 京东美团大战，你怎么看？ #
87316次浏览 482人参与
# 2022届毕业生现状 #
823003次浏览 7158人参与
# 生化医药面经大本营 #
111177次浏览 475人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务