Codeforces Round #670 (Div. 2) C D
C. Link Cut Centroids
C. Link Cut Centroids
题意:给定一棵n个节点的树,假设n个节点中,如果去掉其中一个节点k(包括节点所含的所有边)后,各个联通块中所含的最大点的数量最小,那么节点k就是这个树的质心。
现在有两个操作
- 选择两个节点 a 1 , a 2 a_1,a_2 a1,a2并删去这两者间的边
- 选择两个节点
a
1
,
a
2
a_1,a_2
a1,a2并将两点相连
要求在两次操作后,使得这颗树的质心惟一。
思路:
仔细观察题目里面给定的有两个质心的图:
再连续手造几个图,可以发现
- 最多只有俩质心
- 如果存在2个质心,那么这棵树肯定存在对称现象
-
如果存在2个质心,他们中间必然不能有其他点(因为是对称的。如果中间有了奇数个点,那么最中间的就是质心;如果中间有了偶数个点,那推到最中间的相邻点才是质心)
那么代码总体就比较简单了
- 以1号节点为root,dfs遍历树,把每个点(包含自己)的儿子个数统计出来,记录在 s o n [ ] son[] son[]数组中,同时记录父亲节点 f [ ] f[] f[](在过后的计数中用到两种判断)
- 遍历所有的n个节点,假设把第
i
i
i个节点去掉了,然后向每个相邻节点查找他们所在连通块的节点个数:
- 父亲节点= n − s o n [ i ] n-son[i] n−son[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[]
- a [ i ] = b [ i ] + c [ i ] a[i]=b[i]+c[i] a[i]=b[i]+c[i]
- b [ ] b[] b[]是一个非递减序列
- c [ ] c[] c[]是一个非递增序列
- 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(在这里我设bi为x)的函数(雾?)。那么现在我只要合理分配初始值,就能使得 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=a1−x是一个已知值。我要求的就是 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)=a1−x,在下面的代码中我把 ∑ 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;
}
推荐阅读
-
Codeforces Round #595 (Div. 3)D1D2 贪心 STL
-
Codeforces Round #655 (Div. 2) A. Omkar and Completion
-
Codeforces Round #656 (Div. 3)D. a-Good String(递归+dfs)
-
Codeforces Round #487 (Div. 2)
-
Codeforces Round #649 (Div. 2)-B. Most socially-distanced subsequence(思维)
-
Codeforces Round #649 (Div. 2) C-Ehab and Prefix MEXs
-
Educational Codeforces Round 71 (Rated for Div. 2)E. XOR Guessing
-
Codeforces Round #659 (Div. 2) A. Common Prefixes(字符串,思维)
-
Codeforces Round #610 (Div. 2)
-
Codeforces Round #670 (Div. 2)