D

构造一个长度为2n的序列(1-n每个出现两次),$d_i$是两个相同元素i间的距离,使得$\sum_{i=1}^n (n-i)|d_i + i - n|$最小

构造
观察$|d_i + i - n|$,我们总可以使得$d_i = n - i$,而$i = n时,(n-i) = 0$,我们可以不考虑其怎么放
构造形式类似于
11
1122
131223
13312424

即奇数和偶数分开,分别构成回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;

int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=(n+1)/2;++i)
printf("%d ",2*i-1);
for(int i=n/2;i>=1;--i)
printf("%d ",2*i-1);
for(int i=1;i<=n/2;++i)
printf("%d ",2*i);
for(int i=(n-1)/2;i>=1;--i)
printf("%d ",2*i);
printf("%d ",n);
return 0;
}

E

有一棵树,每个叶子节点有一只蚂蚁,蚂蚁每次可以移动一个节点,除了根节点外,其余节点同时只能有一只蚂蚁。求所有蚂蚁到达根节点的最短时间。

贪心
我们发现若两个叶子节点的深度相等,则他们会在某点相遇,此时则为其中的一个深度+1,然后我们处理出每个根节点的每个子树的情况,dfs一遍将深度排序,扫描过程中维护最深的深度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 10;
vector<int> G[maxn];
vector<int> lst;
int dep[maxn],n;

void dfs(int u,int fa)
{
dep[u] = dep[fa] + 1;
if(G[u].size() == 1) lst.push_back(dep[u]);
for(int i=0;i<G[u].size();++i)
{
int v = G[u][i];
if(v != fa) dfs(v,u);
}
}

int main()
{
scanf("%d",&n);
for(int i=1;i<n;++i)
{
int u,v;
scanf("%d %d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
int ans = 0;
dep[1] = 0;
for(int i=0;i<G[1].size();++i)
{
int v = G[1][i];
lst.clear();
dfs(v,1);
sort(lst.begin(),lst.end());
int cur = 0;
for(int i=0;i<lst.size();++i)
if(cur >= lst[i]) ++cur;
else cur = lst[i];
ans = max(ans,cur);
}
printf("%d\n",ans);
return 0;
}