欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #670 (Div. 2) C D

程序员文章站 2022-05-30 19:35:24
...

C. Link Cut Centroids

C. Link Cut Centroids
题意:给定一棵n个节点的树,假设n个节点中,如果去掉其中一个节点k(包括节点所含的所有边)后,各个联通块中所含的最大点的数量最小,那么节点k就是这个树的质心。
现在有两个操作

  1. 选择两个节点 a 1 , a 2 a_1,a_2 a1a2并删去这两者间的边
  2. 选择两个节点 a 1 , a 2 a_1,a_2 a1,a2并将两点相连
    要求在两次操作后,使得这颗树的质心惟一。

思路:
仔细观察题目里面给定的有两个质心的图:
Codeforces Round #670 (Div. 2) C D

再连续手造几个图,可以发现

  1. 最多只有俩质心
  2. 如果存在2个质心,那么这棵树肯定存在对称现象
  3. 如果存在2个质心,他们中间必然不能有其他点(因为是对称的。如果中间有了奇数个点,那么最中间的就是质心;如果中间有了偶数个点,那推到最中间的相邻点才是质心)
    那么代码总体就比较简单了
  • 以1号节点为root,dfs遍历树,把每个点(包含自己)的儿子个数统计出来,记录在 s o n [ ] son[] son[]数组中,同时记录父亲节点 f [ ] f[] f[](在过后的计数中用到两种判断)
  • 遍历所有的n个节点,假设把第 i i i个节点去掉了,然后向每个相邻节点查找他们所在连通块的节点个数:
    • 父亲节点= n − s o n [ i ] n-son[i] nson[i]
    • 儿子节点 k k k= s o n [ k ] son[k] son[k]
  • 取个最大值就可以了,然后搞个结构体 c u n [ ] cun[] cun[]记录他的去掉后连通块中最大的节点个数 n u m num num和当前自己的节点下标 i d id id s o r t sort sort

最后就是看最大和次大节点的 n u m num num是否相同

  • 相同:有两个质心,去掉中间连线,把其中一个的儿子匀给对方
  • 不相同:只有一个质心,随便找条边去了再加上^^
int f[maxn], son[maxn], co, n, t;
vector<int> G[maxn];
struct node {
	int num, id;
}cun[maxn];
bool cmp(node a, node b) {
	return a.num < b.num;
};
int dfs(int fa, int nw) {
	f[nw] = fa;
	int sum = 1;
	for (int i = 0; i < G[nw].size(); i++) {
		if (G[nw][i] == fa)continue;
		sum += dfs(nw, G[nw][i]);
	}
	return son[nw] = sum;
}
int main()
{
	cin >> t;
	int u, v;
	while (t--)
	{
		cin >> n;
		for (int i = 1; i <= n; i++)G[i].clear();
		co = 0;
		for (int i = 1; i < n; i++) {
			cin >> u >> v;
			G[u].push_back(v);
			G[v].push_back(u);
		}
		dfs(0, 1);
		int maxx;
		for (int i = 1; i <= n; i++) {
			maxx = 0;
			for (int j = 0; j < G[i].size(); j++) {
				if (G[i][j] == f[i]) {
					maxx = max(maxx, n - son[i]);
				}
				else {
					maxx = max(maxx, son[G[i][j]]);
				}
			}
			cun[++co].id = i;
			cun[co].num = maxx;
		}
		sort(cun + 1, cun + 1 + n, cmp);
		int ans;
		if (cun[1].num == cun[2].num) {
			for (int i = 0; i < G[cun[1].id].size(); i++) {
				ans = G[cun[1].id][i];
				if (G[cun[1].id][i] != cun[2].id)break;
			}
			cout << cun[1].id << " " << ans << endl;
			cout << ans << " " << cun[2].id << endl;
		}
		else {
			ans = G[cun[1].id][0];
			cout << cun[1].id << " " << ans << endl;
			cout << cun[1].id << " " << ans << endl;
		}
	}
	return 0;
}

D. Three Sequences

D. Three Sequences
题意:给定一个长度为 n n n的序列 a [ ] a[] a[],要求把他分成两个序列 b [ ] , c [ ] b[],c[] b[],c[]

  1. a [ i ] = b [ i ] + c [ i ] a[i]=b[i]+c[i] a[i]=b[i]+c[i]
  2. b [ ] b[] b[]是一个非递减序列
  3. c [ ] c[] c[]是一个非递增序列
  4. m a x ( b i , c i ) max(b_i,c_i) max(bi,ci)尽可能小

之后有 q ( 1 e 5 ) q(1e5) q(1e5)次对于 a [ ] a[] a[]的修改,给定 l , r , x l,r,x l,r,x:对 [ l , r ] [l,r] [l,r]范围内的 a i a_i ai都增加 x x x
要求给出整个序列中的 m a x ( m a x ( b i , c i ) ) max(max(b_i,c_i)) max(max(bi,ci))

思路:看见 q q q次修改,想到差分序列,但是这题在想到用差分时候还是差了一点,手推一下感觉好像还要处理每次之前的最大值,用线段树或者树状数组记录修改。其实不仅仅对于数列 a [ ] a[] a[]需要进行差分,还要对于 b [ ] 、 c [ ] b[]、c[] b[]c[]进行差分分析

  • 由于 b [ ] b[] b[]是一个非递减序列。 c [ ] c[] c[]是一个非递增序列,那么对于 b [ ] b[] b[]的差分数列而言,每个都大于0;对于 c [ ] c[] c[]的每个差分数列而言,每个都小于0。
  • 由递增以及递减关系,可以把题目所求答案的 m a x ( m a x ( b i , c i ) ) max(max(b_i,c_i)) max(max(bi,ci))变成 m a x ( b n , c 1 ) max(b_n,c_1) max(bn,c1)
  • 问题就转换成了把 a [ ] 的 差 分 数 列 d a [ ] a[]的差分数列da[] a[]da[]拆分成一个正数(或0)和一个负数(或0),下面就是需要拆分的策略了。
  • 对于题里面给定的样例推理一下就可以发现:
    • 如果目前的 d a i da_i dai为正数,就直接全给 b i b_i bi,而 c i c_i ci则加上 0 0 0 因为如果变成一个正数 K K K和负数 k k k,那么 K > d a i K>da_i K>dai一定成立,这就会造成 b n b_n bn的增大。
    • 同理,如果目前的 d a i da_i dai为负数,就直接全给 c i c_i ci,而 b i b_i bi则加上 0 0 0 因为如果变成一个正数 K K K和负数 k k k,那么 k < d a i k<da_i k<dai一定成立,这就会造成 c 1 c_1 c1的增大。
  • 经过上述的两个操作我已经能够保证 b [ ] , c [ ] b[],c[] b[],c[]的增减性了。现在就相当于已经知道了初值分别是 b 1 , c 1 ( 在 这 里 我 设 b i 为 x ) b_1,c_1(在这里我设b_i为x) b1,c1(bix)的函数(雾?)。那么现在我只要合理分配初始值,就能使得 m a x ( b n , c 1 ) max(b_n,c_1) max(bn,c1)最小化。因为这里的 c 1 = a 1 − x c_1=a_1-x c1=a1x是一个已知值。我要求的就是 b n = x + ∑ i = 2 n m a x ( 0 , d a i ) b_n=x+\sum_{i=2}^n max(0,da_i) bn=x+i=2nmax(0,dai)
  • 这里把他们均分当然就是最小的时候,即 x + ∑ i = 2 n m a x ( 0 , d a i ) = a 1 − x x+\sum_{i=2}^n max(0,da_i)=a_1-x x+i=2nmax(0,dai)=a1x,在下面的代码中我把 ∑ i = 2 n m a x ( 0 , d a i ) \sum_{i=2}^n max(0,da_i) i=2nmax(0,dai) m a x x maxx maxx表示

接下来留给我的就是对于差分序列的维护,因为其实每次只修改了 a l , a r + 1 a_l,a_{r+1} al,ar+1两个值,所以只要修改前判断是否大于0,减去大于0的,修改后判断是否大于零再加上就好了。
尤其注意1和n的位置!!!这里的差分序列不作数^^(wa4)

LL a[maxn], da[maxn];//差分序列,L-R +1 a[l]+1,a[r+1]-1
LL n, q, xx, ans;
int main()
{
	cin >> n;
	LL maxx = 0;
	da[1] = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (i != 1)da[i] = a[i] - a[i - 1];
		if (da[i] > 0) {
			maxx += da[i];
		}
	}
	xx = (a[1] - maxx) / 2;
	ans = max(a[1] - xx, xx + maxx);
	cout << ans << endl;
	cin >> q;
	LL l, r, x;
	for (int i = 1; i <= q; i++) {
		cin >> l >> r >> x;
		if (l != 1 && da[l] > 0)maxx -= da[l];
		if (r != n && da[r + 1] > 0)maxx -= da[r + 1];

		if (l != 1)da[l] += x;
		if (l == 1)a[1] += x;
		if (r != n)da[r + 1] -= x;

		if (l != 1 && da[l] > 0)maxx += da[l];
		if (r != n && da[r + 1] > 0)maxx += da[r + 1];
		xx = (a[1] - maxx) / 2;
		ans = max(a[1] - xx, xx + maxx);
		cout << ans << endl;
	}
	return 0;
}
相关标签: 垃圾分类