海亮 DAY5 -- 解题报告

发表于 | 阅读次数:
字数统计: 2,099 字

今天按照计划的安排，如期进行了动态规划有关内容的测试。

分数： 80

前言

其实动态规划这天我是挺慌的，因为当初学动归的时候没有任何的基础，其实讲的时候好多基础题都是没思路的，不过还好，有一个系统的学习的机会，把几个基本的动归问题听懂之后，就慢慢的开始有了思路。这算是正式入门了吧。

T1

今天的T1其实… 怎么说，是一道很不像DP的一道题。题目是关于排列数的， 其实昨天有讲过这种DP的写法， 但是我感觉好像并找不到什么思路， 于是我就先打了一个暴力试了试， 就是生成了所有的排列， 然后将满足条件的记一下数， 其实就是先打一个表， 结果发现答案都很有规律， 可以推出一个公式即 2 ^ (n - 1) % p . 发现公式的我欣喜若狂， 于是这就成了一个考快速幂板子的题了。 需要注意的是在快速幂中的相乘取模需要用到快速乘。 于是就可以AC了

标程：

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
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 5e5 + 10;
const int mod = 1e9+7;

int T;

long long n, p;

inline ll Mul(ll a, ll b) { // 快速乘
	ll ans = 0;
	while(b) {
		if(b&1) ans += a, ans %= p;
		a <<= 1, a %= p;
		b >>= 1;
	}
	return ans;
}

inline ll Pow(ll b) {  // 快速幂
	if(p == 1) return 0ll;
	ll ans = 1, a = 2ll;
	while(b) {
		if(b&1) ans = Mul(ans, a), ans %= p;
		a = Mul(a, a);
		b >>= 1;
	}
	return ans;
}

int main() {
//	freopen("jian.in", "r", stdin);
//	freopen("jian.out", "w", stdout); 
	scanf("%d", &T);
	while(T--) {
		cin >> n >> p;
		cout << Pow(n-1) << endl;  // 直接带公式
	}
	return 0;
}

可以看到老师的代码缩进很好看， 而且有一点是， 老师对于常量的使用没有使用 #define， 而是使用 const 定义，ll 的缩写也没有使用 #define, 而是使用了 typedef 来定义 ll 的缩写， 这些代码风格都可以借鉴与学习。

突然发现自己的程序好像比老师的程序快了几秒， 貌似就是读入优化的问题？貌似可以显著的提高读入的速度，可以避免被卡常数吧.. 表示测的3遍， 两遍因为卡常被卡掉了最后一组数据， 简化代码和尽量减少无用的操作是优化常数的一个很好的方法。

T2

这道题是一道树形DP， 其实我的思路应该是暴力思路， 拿 60 分的那种， 但是在打 DP 求树的直径的时候打炸掉了， 应该得到的暴力分没有拿到，（其实听说好像不用DP求直径， DFS就可以处理出树的直径）

正解思路：
先预处理出一条直径(𝑎,𝑏)，如果边不在直径上，那么这次答案就是直径了。

如果枚举的是直径上的边，我们考虑对于a和b为根分别dp出𝑓1_𝑥,𝑓2_𝑥表示以a/b为根，x子树直径大小是多少。（这可以用树形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
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 2e5 + 10;
const int mod = 1e9+7;

int n;
int head[M], nxt[M], to[M], w[M], tot;
inline void add(int a, int b, int _w) {
	++tot; nxt[tot] = head[a]; head[a] = tot; to[tot] = b; w[tot] = _w;
}
inline void adde(int a, int b, int _w) {
	add(a, b, _w);
	add(b, a, _w);
}

int mx, re;
inline void dfs(int x, int fa, int v) {
	if(v > mx) mx = v, re = x;
	for (int i=head[x]; i; i=nxt[i]) if(to[i] != fa) dfs(to[i], x, v + w[i]);
} 

struct par {
	int fi, se, rfi, rse;
	par() {}
	par(int fi, int se, int rfi, int rse) : fi(fi), se(se), rfi(rfi), rse(rse) {}
}dp[2][M];
int G[2][M];

inline par comb(par a, par b, int c, int d) {
	par ret;
	if(a.fi == -1 && a.se == -1) a.fi = c;
	else if(a.se == -1) a.fi += c;
	else if(a.fi != -1 && a.se != -1) a.fi += c, a.se += c;
	ret = b;
	if(a.fi > ret.fi) {
		ret.se = ret.fi; ret.rse = ret.rfi;
		ret.fi = a.fi; ret.rfi = d;
	} else {
		if(a.fi > ret.se) ret.se = a.fi, ret.rse = d;
		else if(a.se > ret.se) ret.se = a.se, ret.rse = d;
	}
	return ret;
}

par *f;
int *g;

inline void dfs2(int x, int fa) {
	f[x] = par(-1, -1, -1, -1); g[x] = 0;
	for (int i=head[x]; i; i=nxt[i]) {
		if(to[i] == fa) continue;
		dfs2(to[i], x);
		f[x] = comb(f[to[i]], f[x], w[i], to[i]);
		g[x] = max(g[x], g[to[i]]);
	}
	if(f[x].rfi != -1 && f[x].rse == -1) g[x] = max(g[x], f[x].fi); 
	else if(f[x].rfi != -1 && f[x].rse != -1) g[x] = max(g[x], f[x].fi + f[x].se);
}

int fr[M], w2[M];
bool gg;
inline void dfs3(int x, int fa, int dest) {
	if(gg) return ;
	for (int i=head[x]; i; i=nxt[i]) {
		if(gg) return ;
		if(to[i] == fa) continue;
		if(to[i] == dest) {
			fr[x] = to[i]; w2[x] = w[i];
			gg = 1;
			return ;
		}
		fr[x] = to[i]; w2[x] = w[i];
		dfs3(to[i], x, dest);
	}
}

void Main() {
	tot = 0; 
	scanf("%d", &n); for (int i=1; i<=n; ++i) head[i] = nxt[i] = fr[i] = w2[i] = 0;
	for (int i=1, u, v, _w; i<n; ++i) {
		scanf("%d%d%d", &u, &v, &_w);
		adde(u, v, _w);
	}
	int pa, pb;
	mx = -1, re = 0;
	dfs(1, 0, 0); pa = re;
	mx = -1, re = 0;
	dfs(pa, 0, 0); pb = re;
	gg = 0; dfs3(pa, 0, pb);
	int r = 0, cnt = 0;
	for (int i=pa; i!=pb; i=fr[i]) r += w2[i], ++cnt;
	f = dp[0]; g = G[0]; dfs2(pa, 0);
	f = dp[1]; g = G[1]; dfs2(pb, 0);
	long long ans = 1ll * (n-1 - cnt) * r;
	for (int i=pa, j, fp1, fp2; i!=pb; i=fr[i]) {
		j = fr[i];
//		printf("%d %d %d %d\n", i, j, G[0][j], G[1][i]);
		ans += max(G[0][j], G[1][i]);
	}
	cout << ans << endl;
}

int main() {
	freopen("dan.in", "r", stdin);
	freopen("dan.out", "w", stdout);
	int T; scanf("%d", &T);
	while(T--) Main();
	return 0;
}

老师的程序里出现了关于指针的使用， 在日常打题的时候要避免使用指针。

T3

直接贴题解了， 概率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
# include <math.h>
# include <vector> 
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm> 

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 50 + 10;
const int INF = 1e9;

namespace work {
    bool f[M][M][M*M]; 
    int n, a[M], b[M], len[M], m, X; 
    void main() {
        memset(f, 0, sizeof f); 
        int pre = 0;
        cin >> n; m = 0;
        for (int i=1; i<=n; ++i) {
        	scanf("%d", &a[i]);
            m += (a[i] == 0); 
        }
        for (int i=1; i<=n; ++i) scanf("%d", &b[i]);
        cin >> X;
        sort(a+1, a+n+1);
        sort(b+1, b+n+1);
        for (int i=1; i<n; ++i) len[i] = b[i+1] - b[i] - 1;
        len[n] = X - b[n];
        for (int i=1; i<=n; ++i) {
            if(a[i] == 0) continue;
            int tem = 0;
            for (int j=1; j<=n; ++j)
                if(a[i] > b[j]) ++tem;
            if(tem) len[tem] --;
            pre += tem;
        }
        for (int j=0; j<=m; ++j) f[0][j][pre] = 1; 
        for (int i=1; i<=n; ++i)  
            for (int j=0; j<=m; ++j)
                for (int k=0; k<=n*n; ++k) 
                    for (int cur=0, to = min(j, len[i]); cur<=to; ++cur) 
                        if(k-i*cur >= 0) f[i][j][k] |= f[i-1][j-cur][k-i*cur];
        double ans = 1e9, E = (double)n*n, id;            
    	for (int i=0; i<=n*n; ++i) {
        	if(f[n][m][i]) {
                if(fabs(2*i-E) < ans) {
                    ans = fabs(2*i-E); 
                    id = i;
                }
            }
        }
        printf("%.10lf\n", id/n/n);
    }
}

int main() {
	freopen("ti.in", "r", stdin);
	freopen("ti.out", "w", stdout);
	work :: main();
	return 0;
}

总结

别人的故事， 已经听了许多， 终于要自己把握机会， 尝试一下了吧。 如果这次错过， 输掉的将不止一场比赛， 失去的将会更多！ 加油！