2017北京网络赛补

D.Agent Communication

题意:给你一棵树,你需要加一条边,使得所有点对的距离的最大值最小.
分析:加的边一定在直径上,先处理出所有点到直径的距离,然后仿照hdu5699即可

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//created by missever
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int mod = 1e9 + 7;
const int maxn = 1005;
vector<int> g[maxn],f;
int d[maxn],w[maxn];
bool inl[maxn];
int dfs(int u,int fa) {
int x,k = u;
for(auto v:g[u]) {
if(v == fa || inl[v]) continue;
d[v] = d[u] + 1;
x = dfs(v,u);
if(d[x] > d[k]) k = x;
}
return k;
}
bool dfs(int u,int fa,int w) {
f.push_back(u);
inl[u] = 1;
if(u == w) return true;
for(auto v:g[u]) {
if(v == fa) continue;
if(dfs(v,u,w)) return true;
}
f.pop_back();
inl[u] = 0;
return false;
}
bool check(int k,int m) {
int i,j,u,l1,l2,r1,r2;
l1 = l2 = -mod;
r1 = r2 = mod;
for(i = 0;i < m; i++) {
for(j = i + 1;j < m; j++) {
if(j - i + w[i] +w[j] <= k) continue;
u = k - 1 - w[i] - w[j];
l1 = max(l1,i + j - u);
l2 = max(l2,j - i - u);
r1 = min(r1,i + j + u);
r2 = min(r2,j - i + u);
}
}
if(l1 <= r1 && l2 <= r2) {
if(l1 == r1 && l2 == r2) {
if((l1 + l2) & 1) return false;
else return true;
} else return true;
} else return false;
}
void solve() {
int n,m,u,v,i,l,r,mid;
scanf("%d",&n);
for(i = 1;i <= n; i++) g[i].clear();
memset(inl,0,sizeof(inl));
for(i = 1;i < n; i++) {
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
d[1] = 1;
u = dfs(1,0);
d[u] = 1;
v = dfs(u,0);
f.clear();
dfs(u,0,v);
m = f.size();
for(i = 0;i < m; i++) {
d[f[i]] = 0;
w[i] = d[dfs(f[i],0)];
}
l = 0;
r = 1005;
while(l < r) {
mid = (l + r) >> 1;
if(check(mid,m)) r = mid;
else l = mid + 1;
}
printf("%d\n",r);
}
int main() {
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int t;
scanf("%d",&t);
while(t--) solve();
return 0;
}

F.Cake

题意:有三个人在做$n$个蛋糕,每个蛋糕分三步,每人负责一步,只能做完上一步才能做下一步.每个人做的顺序必须一致,问最小总时间.
分析:对于两个蛋糕A和B,定义$A < B$,当且仅当AB相邻时AB比BA要优。然后排序完跑一遍就行了

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
//created by missever
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
struct node {
int a,b,c;
} f[maxn];
bool cmp(const node &x,const node &y) {
int u = max(x.a + x.b,x.a + y.a);
u = max(u + y.b,x.a + x.b + x.c) + y.c;
int v = max(y.a + y.b,y.a + x.a);
v = max(v + x.b,y.a + y.b + y.c) + x.c;
return u < v;
}
int main() {
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int n,i;
LL da,db,dc;
while(~scanf("%d",&n) && n) {
for(i = 0;i < n; i++) scanf("%d%d%d",&f[i].a,&f[i].b,&f[i].c);
sort(f,f + n,cmp);
da = db = dc = 0;
for(i = 0;i < n; i++) {
da += f[i].a;
db = max(db,da);
db += f[i].b;
dc = max(dc,db);
dc += f[i].c;
}
printf("%lld\n",dc);
}
return 0;
}

H.Polynomial Product

题意:给你两个多项式,定义卷积后的系数$c_{i}= max(a_{j}+b_{i-j})$,问哪些系数大于了$w$
分析:排序之后,可以线性处理出对于$a_{i}$有哪些$b_{j}$会使得它们的和大于$w$,然后用$bitset$取一遍或,即可.

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//created by missever
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
vector<P> fa,fb;
bitset<1005> v1,ans1;
bitset<maxn> v2,ans2;
void solve(int t) {
int n,m,w,x,i,j;
scanf("%d%d%d",&n,&m,&w);
fa.clear();
fb.clear();
for(i = 0; i < n; i++) {
scanf("%d",&x);
if(x == 0) continue;
if(x == 1) x = 0;
fa.push_back(P(x,i));
}
for(i = 0; i < m; i++) {
scanf("%d",&x);
if(x == 0) continue;
if(x == 1) x = 0;
fb.push_back(P(x,i));
}
x = n + m - 1;
sort(fa.begin(),fa.end());
sort(fb.begin(),fb.end());
n = fa.size();
m = fb.size();
if(n > m) {
swap(n,m);
swap(fa,fb);
}
if(t < 4) {
v2.reset();
ans2.reset();
for(i = 0,j = m - 1; i < n; i++) {
while(j >= 0 && (LL)fb[j].first + fa[i].first > w) v2[fb[j--].second] = 1;
ans2 |= v2 << fa[i].second;
}
for(i = 0; i < x; i++) putchar(ans2[i] ? 'Y' : 'N');
puts("");
} else {
v1.reset();
ans1.reset();
for(i = 0,j = m - 1; i < n; i++) {
while(j >= 0 && (LL)fb[j].first + fa[i].first > w) v1[fb[j--].second] = 1;
ans1 |= v1 << fa[i].second;
}
for(i = 0; i < x; i++) putchar(ans1[i] ? 'Y' : 'N');
puts("");
}
}
int main() {
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int t;
scanf("%d",&t);
while(t--) solve(t);
return 0;
}