牛客练习赛99

A

直接找中间数字

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define inf 0x3f3f3f3f
const int N=2e5+5;
int n;
int a[N];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    cout<<n/2<<" "<<a[n/2]+1;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t=1;
//  cin>>t;
    while(t--) solve();
    return 0;
}

B

由于有一个a+b=c+d性质因此一定有一个先后顺序

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve(int ca) {
	ll a, b, c, d, v[5];
	scanf("%lld%lld%lld%lld%lld%lld%lld%lld", &a, &b, &c, &d, &v[1], &v[2], &v[3], &v[4]);
	ll res = 9e18;
	// a -> c
	{
		if(a >= c) {
			res = min(res, c * v[1] + (a - c) * v[2] + b * v[4]); // a->c, a->d, b->d
		} else if(a < c) {
			res = min(res, a * v[1] + (c - a) * v[3] + d * v[4]); // a->c, b->c, b->d
		}
	}
	
	// a -> d
	{
		if(a >= d) {
			res = min(res, d * v[2] + (a - d) * v[1] + b * v[3]); // a->d, a->c, b->d
		} else if(a < d) {
			res = min(res, a * v[2] + (d - a) * v[4] + c * v[3]); // a->d, b->d, b->c
		}
	} 
	
	// b -> c
	{
		if(b >= c) {
			res = min(res, c * v[3] + (b - c) * v[4] + a * v[2]); // b->c, b->d, a->d
		} else if(b < c) {
			res = min(res, b * v[3] + (c - b) * v[1] + d * v[2]); // b->c, a->c, a->d
		}
	}
	
	// b -> d
	{
		if(b >= d) {
			res = min(res, d * v[4] + (b - d) * v[3] + a * v[1]); // b->d, b->c, a->c 
		} else if(b < d) {
			res = min(res, b * v[4] + (d - b) * v[2] + c * v[1]); // b->d, a->d, a->c 
		}
	}

	
	printf("%lld\n", res);
}

int main()
{
	int T = 1;
	scanf("%d", &T);
	for(int i = 1; i <= T; ++i) solve(i);

	return 0;
}

C

打表加规律题？

模拟几个样例可以发现： 𝑛=2和𝑛=4时无解，𝑛=3时可以分为 1、2mul组3 从𝑛=5开始， 存在有：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
5
mul: 1 2 4

6
mul: 1 2 6

7
mul: 1 3 6

8
mul: 1 3 8

9
mul: 1 4 8

10
mul: 1 4 10

11 
mul: 1 5 10

12
mul: 1 5 12
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
#include <iostream>
#define int long long
using namespace std;
 
signed main(){
    int T,n;
    cin >> T;
    while(T--){
        cin >> n;
        if(n==2||n==4)
            cout << -1 << endl;
        else if(n==3) cout << 1 << '\n' << 3 << endl;
        else{
            cout << 3 << endl;
            cout << 1 << ' ' << (n-1)/2 << ' ' << (n%2?n-1:n) << endl;
        }
    }
    return 0;
}
// 2  -1
// 3   3  =  1 + 2
// 4  -1
// 5   1 * 2 * 4  =  3 + 5
// 6   1 * 2 * 6  =  3 + 4 + 5
// 7   1 * 3 * 6  =  2 + 4 + 5 + 7
// 8   1 * 3 * 8  =  2 + 4 + 5 + 6 + 7
// 9   1 4 8
// 10  1 4 10
// 11  1 5 10
// 12  1 5 12

D

感觉一眼换根dp啊

然后开始复制题解，进一步理解换根dp

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1000010;
const int M = N << 1;
int h[N], e[M], ne[M], idx;
int n, id;
ll sum, ans;
ll siz[N];

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs1(int u, int fa) {
	siz[u] = 1;
	for(int i = h[u]; i != -1; i = ne[i]) {
		int v = e[i];
		if(v != fa) {
			dfs1(v, u);
			sum += siz[u] * siz[v] * u;
			siz[u] += siz[v];
		}
	}
}

void dfs2(int u, int fa) {
	
	if(sum > ans) {
		ans = sum;
		id = u;
	}
	
	for(int i = h[u]; i != -1; i = ne[i]) {
		int v = e[i];
		if(v != fa) {
			ll temp = siz[v] * (n - siz[v]) * (u - v);
			sum -= temp;
			dfs2(v, u);
			sum += temp;
		}
	}
}

void solve(int ca) {
	scanf("%d", &n);
	memset(h, -1, (n + 1) * sizeof(int));
	idx = 0;
	
	for(int i = 1; i < n; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b);
		add(b, a);
	}
	
	dfs1(1, -1);
	ans = 0;
	dfs2(1, -1);
	
	printf("%d %lld\n", id, ans * 2 + 1ll * n * (n + 1) / 2);
}

int main()
{
	int T = 1;
//	scanf("%d", &T);
	for(int i = 1; i <= T; ++i) solve(i);

	return 0;
}