暑假集训刷题记录

　　　　向上跳，再向上跳，也许再努力一点我就能够着菊苣们的膝盖了。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　——题记

7.23

　　　　CodeForces 559C 组合数 + DP

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <map>
 5 #define MP make_pair
 6 #define F first
 7 #define S second
 8 using namespace std;
 9 
10 typedef long long LL;
11 typedef pair<LL, LL> Point;
12 
13 const int maxn = 22000 + 10;
14 const LL MOD = 1000000007LL;
15 
16 inline LL mul_mod(LL a, LL b)
17 {
18     a %= MOD; b %= MOD;
19     return (a * b) % MOD;
20 }
21 
22 inline LL sub_mod(LL a, LL b)
23 {
24     return (((a - b) % MOD) + MOD) % MOD;
25 }
26 
27 LL pow_mod(LL a, LL n)
28 {
29     LL ans = 1;
30     while(n)
31     {
32         if(n & 1) ans = mul_mod(ans, a);
33         a = mul_mod(a, a);
34         n >>= 1;
35     }
36     return ans;
37 }
38 
39 LL Inverse(LL a)
40 { return pow_mod(a, MOD - 2); }
41 
42 const int maxh = 200000 + 10;
43 
44 LL fac[maxh], invfac[maxh];
45 
46 void init()
47 {
48     fac[0] = fac[1] = 1;
49     for(int i = 2; i < maxh; i++) fac[i] = mul_mod(fac[i-1], i);
50     invfac[maxh-1] = Inverse(fac[maxh-1]);
51     for(int i = maxh-2; i >= 0; i--) invfac[i] = mul_mod(invfac[i+1], i+1);
52 }
53 
54 LL C(LL n, LL m)
55 {
56     if(m > n) { puts("shakalaka"); return 0; }
57     return mul_mod(mul_mod(fac[n], invfac[m]), invfac[n-m]);
58 }
59 
60 int h, w, n;
61 
62 Point a[maxn];
63 
64 LL methods(int i, int j)
65 {
66     LL x = a[j].first - a[i].first;
67     LL y = a[j].second - a[i].second;
68     return C(x + y, x);
69 }
70 
71 LL dp[maxn];
72 
73 int main()
74 {
75     //freopen("in.txt", "r", stdin);
76 
77     init();
78     scanf("%d%d%d", &h, &w, &n);
79     for(int i = 1; i <= n; i++)
80     {
81         LL x, y; scanf("%I64d%I64d", &x, &y);
82         a[i] = MP(x, y);
83     }
84     sort(a + 1, a + n + 1);
85     a[0] = MP(1, 1);
86     a[n+1] = MP(h, w);
87     dp[1] = methods(0, 1);
88 
89     for(int i = 2; i <= n + 1; i++)
90     {
91         dp[i] = methods(0, i);
92         for(int j = 1; j < i; j++) if(a[j].F <= a[i].F && a[j].S <= a[i].S)
93             dp[i] = sub_mod(dp[i], mul_mod(methods(j, i), dp[j]));
94     }
95 
96     printf("%I64d
", dp[n + 1]);
97 
98     return 0;
99 }
代码君

　　　　

　　　　CodeForces 219D 树形DP

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <vector>
 5 using namespace std;
 6 
 7 const int maxn = 200000 + 10;
 8 int n;
 9 
10 vector<int> G[maxn];
11 vector<bool> f[maxn];
12 
13 int L[maxn];
14 int fa[maxn];
15 int up[maxn];
16 int rev[maxn];
17 int totup;
18 
19 void dfs(int u, int father, int d)
20 {
21     L[u] = d;
22     fa[u] = father;
23     for(int i = 0; i < G[u].size(); i++)
24     {
25         int v = G[u][i];
26         if(v == father) continue;
27         if(!f[u][i]) { totup++; up[v] = up[u] + 1; }
28         else up[v] = up[u];
29         dfs(v, u, d + 1);
30     }
31 }
32 
33 int main()
34 {
35     //freopen("in.txt", "r", stdin);
36     scanf("%d", &n);
37     for(int i = 0; i < n-1; i++)
38     {
39         int u, v; scanf("%d%d", &u, &v);
40         G[u].push_back(v); f[u].push_back(true);
41         G[v].push_back(u); f[v].push_back(false);
42     }
43 
44     dfs(1, 0, 0);
45 
46     for(int v = 1; v <= n; v++)
47         rev[v] = totup - up[v] + L[v] - up[v];
48 
49     int ans = n - 1;
50     for(int i = 1; i <= n; i++) ans = min(ans, rev[i]);
51 
52     printf("%d
", ans);
53 
54     vector<int> hehe;
55     for(int i = 1; i <= n; i++) if(rev[i] == ans) hehe.push_back(i);
56 
57     printf("%d", hehe[0]);
58     for(int i = 1; i < hehe.size(); i++) printf(" %d", hehe[i]);
59     puts("");
60 
61     return 0;
62 }
代码君

7.24　　补多校

7.25

　　　　CodeForces 445B Tire树上的博弈

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 const int maxn = 100000 + 10;
 6 const int sigma_size = 26;
 7 
 8 int sz;
 9 int ch[maxn][sigma_size];
10 char str[maxn];
11 
12 void insert(char* s)
13 {
14     int u = 0;
15     for(int i = 0; s[i]; i++)
16     {
17         int c = s[i] - 'a';
18         if(!ch[u][c]) ch[u][c] = sz++;
19         u = ch[u][c];
20     }
21 }
22 
23 bool win[maxn], lose[maxn];
24 
25 void dfs(int u)
26 {
27     bool isleaf = true;
28     for(int c = 0; c < 26; c++) if(ch[u][c])
29     {
30         isleaf = false;
31         int v = ch[u][c];
32         dfs(v);
33         win[u] |= !win[v];
34         lose[u] |= !lose[v];
35     }
36     if(isleaf) win[u] = false, lose[u] = true;
37 }
38 
39 int main()
40 {
41     int n, k; scanf("%d%d", &n, &k);
42 
43     sz = 1;
44     for(int i = 0; i < n; i++)
45     {
46         scanf("%s", str);
47         insert(str);
48     }
49     dfs(0);
50 
51     if(!win[0]) puts("Second");
52     else if(lose[0]) puts("First");
53     else if(k & 1) puts("First");
54     else puts("Second");
55 
56     return 0;
57 }
代码君

 　　　　HDU 3996 网络流 最大权闭合图

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <queue>
  6 using namespace std;
  7 
  8 typedef long long LL;
  9 
 10 const int maxn = 3000;
 11 const LL INF = 10000000000;
 12 
 13 struct Edge
 14 {
 15     int from, to;
 16     LL cap, flow;
 17     Edge(int u, int v, LL c, LL f):from(u), to(v), cap(c), flow(f) {}
 18 };
 19 
 20 struct Dinic
 21 {
 22     int n, m, s, t;
 23     vector<Edge> edges;
 24     vector<int> G[maxn];
 25     int d[maxn], cur[maxn];
 26     bool vis[maxn];
 27 
 28     void init() { for(int i = 0; i < n; i++) G[i].clear(); edges.clear(); }
 29 
 30     void AddEdge(int u, int v, LL c)
 31     {
 32         edges.push_back(Edge(u, v, c, 0));
 33         edges.push_back(Edge(v, u, 0, 0));
 34         m = edges.size();
 35         G[u].push_back(m - 2);
 36         G[v].push_back(m - 1);
 37     }
 38 
 39     bool BFS()
 40     {
 41         memset(vis, false, sizeof(vis));
 42         queue<int> Q;
 43         Q.push(s);
 44         vis[s] = true;
 45         d[s] = 0;
 46 
 47         while(!Q.empty())
 48         {
 49             int u = Q.front(); Q.pop();
 50             for(int i = 0; i < G[u].size(); i++)
 51             {
 52                 Edge& e = edges[G[u][i]];
 53                 int v = e.to;
 54                 if(!vis[v] && e.cap > e.flow)
 55                 {
 56                     vis[v] = true;
 57                     d[v] = d[u] + 1;
 58                     Q.push(v);
 59                 }
 60             }
 61         }
 62 
 63         return vis[t];
 64     }
 65 
 66     LL DFS(int u, LL a)
 67     {
 68         if(u == t || a == 0) return a;
 69         LL flow = 0, f;
 70         for(int& i = cur[u]; i < G[u].size(); i++)
 71         {
 72             Edge& e = edges[G[u][i]];
 73             int v = e.to;
 74             if(d[v] == d[u] + 1 && (f = DFS(v, min(a, e.cap-e.flow))) > 0)
 75             {
 76                 flow += f;
 77                 e.flow += f;
 78                 a -= f;
 79                 edges[G[u][i]^1].flow -= f;
 80                 if(a == 0) break;
 81             }
 82         }
 83         return flow;
 84     }
 85 
 86     LL MaxFlow()
 87     {
 88         LL flow = 0;
 89         while(BFS())
 90         {
 91             memset(cur, 0, sizeof(cur));
 92             flow += DFS(s, INF);
 93         }
 94         return flow;
 95     }
 96 }g;
 97 
 98 int main()
 99 {
100     int T; scanf("%d", &T);
101     for(int kase = 1; kase <= T; kase++)
102     {
103         int n; scanf("%d", &n);
104         g.n = n * 25 + 2;
105         g.init();
106         g.s = 0; g.t = g.n - 1;
107 
108         LL sum = 0;
109         for(int i = 0; i < n; i++)
110         {
111             int num; scanf("%d", &num);
112             for(int j = 1; j <= num; j++)
113             {
114                 int x = i * 25 + j;
115                 LL cost, value;
116                 int rela;
117                 scanf("%I64d%I64d%d", &cost, &value, &rela);
118 
119                 value -= cost;
120                 if(value > 0) { g.AddEdge(0, x, value); sum += value; }
121                 else g.AddEdge(x, g.t, -value);
122 
123                 while(rela--)
124                 {
125                     int a, b; scanf("%d%d", &a, &b); a--;
126                     int y = a * 25 + b;
127                     g.AddEdge(x, y, INF);
128                 }
129             }
130         }
131 
132         printf("Case #%d: %I64d
", kase, sum - g.MaxFlow());
133     }
134 
135     return 0;
136 }
代码君

 　　　　HDU 3472 网络流 混合图的欧拉路径

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <queue>
  7 using namespace std;
  8 
  9 const int maxn = 30;
 10 const int INF = 1000000000;
 11 
 12 struct Edge
 13 {
 14     int from, to, cap, flow;
 15     Edge(int u, int v, int c, int f):from(u), to(v), cap(c), flow(f) {}
 16 };
 17 
 18 struct Dinic
 19 {
 20     int n, m, s, t;
 21     vector<Edge> edges;
 22     vector<int> G[maxn];
 23     int d[maxn], cur[maxn];
 24     bool vis[maxn];
 25 
 26     void init() { m = 0; for(int i = 0; i < n; i++) G[i].clear(); edges.clear(); }
 27 
 28     void AddEdge(int u, int v, int c)
 29     {
 30         edges.push_back(Edge(u, v, c, 0));
 31         edges.push_back(Edge(v, u, 0, 0));
 32         m = edges.size();
 33         G[u].push_back(m - 2);
 34         G[v].push_back(m - 1);
 35     }
 36 
 37     bool BFS()
 38     {
 39         memset(vis, false, sizeof(vis));
 40         queue<int> Q;
 41         Q.push(s);
 42         d[s] = 0;
 43         vis[s] = true;
 44 
 45         while(!Q.empty())
 46         {
 47             int u = Q.front(); Q.pop();
 48             for(int i = 0; i < G[u].size(); i++)
 49             {
 50                 Edge& e = edges[G[u][i]];
 51                 int v = e.to;
 52                 if(!vis[v] && e.cap > e.flow)
 53                 {
 54                     vis[v] = true;
 55                     d[v] = d[u] + 1;
 56                     Q.push(v);
 57                 }
 58             }
 59         }
 60 
 61         return vis[t];
 62     }
 63 
 64     int DFS(int u, int a)
 65     {
 66         if(u == t || a == 0) return a;
 67         int flow = 0, f;
 68         for(int& i = cur[u]; i < G[u].size(); i++)
 69         {
 70             Edge& e = edges[G[u][i]];
 71             int v = e.to;
 72             if(d[v] == d[u] + 1 && (f = DFS(v, min(a, e.cap-e.flow))) > 0)
 73             {
 74                 flow += f;
 75                 e.flow += f;
 76                 a -= f;
 77                 edges[G[u][i]^1].flow -= f;
 78                 if(a == 0) break;
 79             }
 80         }
 81         return flow;
 82     }
 83 
 84     int MaxFlow()
 85     {
 86         int flow = 0;
 87         while(BFS())
 88         {
 89             memset(cur, 0, sizeof(cur));
 90             flow += DFS(s, INF);
 91         }
 92         return flow;
 93     }
 94 }g;
 95 
 96 const int maxm = 1000 + 10;
 97 int n;
 98 char word[30];
 99 
100 int deg[maxn];
101 
102 bool occur[maxn];
103 
104 int pa[maxn];
105 int findset(int x) { return x == pa[x] ? x : pa[x] = findset(pa[x]); }
106 void Union(int x, int y)
107 {
108     int px = findset(x), py = findset(y);
109     if(px != py) pa[px] = py;
110 }
111 
112 int u[maxm], v[maxm], directed[maxm];
113 int id[maxm];
114 
115 int main()
116 {
117     //freopen("in.txt", "r", stdin);
118 
119     int T; scanf("%d", &T);
120     for(int kase = 1; kase <= T; kase++)
121     {
122         printf("Case %d: ", kase);
123 
124         g.n = 28;
125         g.s = 26, g.t = 27;
126         g.init();
127         int n; scanf("%d", &n);
128 
129         for(int i = 0; i < 26; i++) pa[i] = i;
130         memset(id, 0, sizeof(id));
131         memset(occur, false, sizeof(occur));
132         memset(deg, 0, sizeof(deg));
133         memset(directed, 0, sizeof(directed));
134         for(int i = 0; i < n; i++)
135         {
136             scanf("%s%d", word, directed + i);
137             int l = strlen(word);
138             u[i] = word[0] - 'a';
139             v[i] = word[l - 1] - 'a';
140             occur[u[i]] = occur[v[i]] = true;
141             Union(u[i], v[i]);
142             deg[u[i]]++; deg[v[i]]--;
143             if(directed[i])
144             {
145                 id[i] = g.m;
146                 g.AddEdge(u[i], v[i], 1);
147             }
148         }
149 
150         //Judge the graph is connected
151         int root;
152         bool ok = true;
153         for(int i = 0; i < 26; i++) if(occur[i]) { root = findset(i); break; }
154         for(int i = 0; i < 26; i++) if(occur[i] && findset(i) != root)  { ok = false; break; }
155         int cnt = 0;
156         for(int i = 0; i < 26; i++) if(deg[i] & 1) cnt++;
157         if((cnt != 0) && cnt != 2) ok = false;
158         if(!ok) { puts("Poor boy!"); continue; }
159 
160         for(int i = 0; i < 26; i++) if(deg[i])
161         {
162             if(deg[i] > 0) g.AddEdge(g.s, i, deg[i] / 2);
163             else if(deg[i] < 0) g.AddEdge(i, g.t, -deg[i] / 2);
164         }
165         g.MaxFlow();
166 
167         for(int i = 0; i < n; i++) if(directed[i])
168         {
169             int x = id[i];
170             if(g.edges[x].flow == 1)
171                 { deg[u[i]] -= 2; deg[v[i]] += 2; }
172         }
173 
174         int a1 = 0, a2 = 0;
175         for(int i = 0; i < 26; i++) if(deg[i])
176         {
177             if(deg[i] == 1) a1++;
178             else if(deg[i] == -1) a2++;
179         }
180         if((a1 == 0 && a2 == 0) || (a1 == 1 || a2 == 1)) puts("Well done!");
181         else puts("Poor boy!");
182     }
183 
184     return 0;
185 }
代码君

　　　　HDU 4183 网络流 每个点只能走一次的回路

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <queue>
  7 #include <cmath>
  8 using namespace std;
  9 
 10 const int maxn = 1000;
 11 const int INF = 1000000000;
 12 int n;
 13 
 14 struct Edge
 15 {
 16     int from, to, cap, flow;
 17     Edge(int u, int v, int c, int f):from(u), to(v), cap(c), flow(f) {}
 18 };
 19 
 20 struct Dinic
 21 {
 22     int n, m, s, t;
 23     vector<Edge> edges;
 24     vector<int> G[maxn];
 25     int d[maxn], cur[maxn];
 26     bool vis[maxn];
 27 
 28     void init() { m = 0; edges.clear(); for(int i = 0; i < n; i++) G[i].clear(); }
 29 
 30     void AddEdge(int u, int v, int c)
 31     {
 32         edges.push_back(Edge(u, v, c, 0));
 33         edges.push_back(Edge(v, u, 0, 0));
 34         m = edges.size();
 35         G[u].push_back(m - 2);
 36         G[v].push_back(m - 1);
 37     }
 38 
 39     bool BFS()
 40     {
 41         memset(vis, false, sizeof(vis));
 42         queue<int> Q;
 43         Q.push(s);
 44         vis[s] = true;
 45         d[s] = 0;
 46 
 47         while(!Q.empty())
 48         {
 49             int u = Q.front(); Q.pop();
 50             for(int i = 0; i < G[u].size(); i++)
 51             {
 52                 Edge& e = edges[G[u][i]];
 53                 int v = e.to;
 54                 if(!vis[v] && e.cap > e.flow)
 55                 {
 56                     vis[v] = true;
 57                     d[v] = d[u] + 1;
 58                     Q.push(v);
 59                 }
 60             }
 61         }
 62 
 63         return vis[t];
 64     }
 65 
 66     int DFS(int u, int a)
 67     {
 68         if(u == t || a == 0) return a;
 69         int flow = 0, f;
 70         for(int& i = cur[u]; i < G[u].size(); i++)
 71         {
 72             Edge& e = edges[G[u][i]];
 73             int v = e.to;
 74             if(d[v] == d[u] + 1 && (f = DFS(v, min(a, e.cap-e.flow))) > 0)
 75             {
 76                 flow += f;
 77                 e.flow += f;
 78                 a -= f;
 79                 edges[G[u][i]^1].flow -= f;
 80                 if(a == 0) break;
 81             }
 82         }
 83         return flow;
 84     }
 85 
 86     int MaxFlow()
 87     {
 88         int flow = 0;
 89         while(BFS())
 90         {
 91             memset(cur, 0, sizeof(cur));
 92             flow += DFS(s, INF);
 93         }
 94         return flow;
 95     }
 96 }g;
 97 
 98 const double eps = 1e-6;
 99 
100 int dcmp(double x)
101 {
102     if(fabs(x) < eps) return 0;
103     return x < 0 ? -1 : 1;
104 }
105 
106 struct Pad
107 {
108     double freq, x, y, r;
109     bool operator < (const Pad& rhs) const
110     { return freq > rhs.freq; }
111 }a[maxn];
112 
113 bool Intersect(int i, int j)
114 {
115     double d = sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x) + (a[i].y-a[j].y)*(a[i].y-a[j].y));
116     return dcmp(a[i].r + a[j].r - d) > 0;
117 }
118 
119 int main()
120 {
121     //freopen("in.txt", "r", stdin);
122 
123     int T; scanf("%d", &T);
124     while(T--)
125     {
126         scanf("%d", &n);
127         g.n = n * 2 - 1;
128         g.init();
129         g.s = 0, g.t = n-1;
130         for(int i = 0; i < n; i++)
131         {
132             scanf("%lf%lf%lf%lf", &a[i].freq, &a[i].x, &a[i].y, &a[i].r);
133         }
134         sort(a, a + n);
135 
136         if(Intersect(0, n-1)) { puts("Game is VALID"); continue; }
137 
138         g.AddEdge(0, n, 2);
139         for(int i = 1; i < n - 1; i++) g.AddEdge(i, i + n, 1);
140         for(int i = 0; i < n; i++)
141             for(int j = i + 1; j < n; j++)
142                 if(dcmp(a[i].freq - a[j].freq) > 0 && Intersect(i, j))
143                     g.AddEdge(i + n, j, INF);
144 
145         if(g.MaxFlow() == 2) puts("Game is VALID");
146         else puts("Game is NOT VALID");
147     }
148 
149     return 0;
150 }
代码君

 　　　　CodeForces 461B 树形DP 跪舔题解

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <vector>
 5 using namespace std;
 6 
 7 typedef long long LL;
 8 
 9 const int maxn = 100000 + 100;
10 const LL MOD = 1000000000 + 7;
11 int n;
12 int color[maxn];
13 vector<int> G[maxn];
14 
15 LL dp[maxn][2];
16 
17 void dfs(int u, int fa)
18 {
19     dp[u][color[u]] = 1;
20     for(int i = 0; i < G[u].size(); i++)
21     {
22         int v = G[u][i];
23         if(v == fa) continue;
24         dfs(v, u);
25         dp[u][1] = ((dp[u][1] * (dp[v][0] + dp[v][1])) % MOD + (dp[u][0]*dp[v][1])%MOD)%MOD;
26         dp[u][0] = (dp[u][0] * ((dp[v][0] + dp[v][1])%MOD))%MOD;
27     }
28 }
29 
30 int main()
31 {
32     scanf("%d", &n);
33     for(int u = 1; u < n; u++)
34     {
35         int v; scanf("%d", &v);
36         G[u].push_back(v);
37         G[v].push_back(u);
38     }
39     for(int i = 0; i < n; i++) scanf("%d", color + i);
40     dfs(0, -1);
41     printf("%I64d", dp[0][1]);
42 
43     return 0;
44 }
代码君

7.26

　　　　CodeForces 455C 给出一个森林，可以合并两棵树。合并以后得到的新树的最小直径为。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <vector>
 5 using namespace std;
 6 
 7 const int maxn = 300000 + 10;
 8 int n, m, Q;
 9 
10 int diameter[maxn];
11 
12 bool vis[maxn];
13 int pa[maxn];
14 int findset(int x) { return x == pa[x] ? x : pa[x] = findset(pa[x]); }
15 void Union(int x, int y)
16 {
17     int px = findset(x), py = findset(y);
18     if(px != py) pa[px] = py;
19 }
20 
21 vector<int> G[maxn];
22 
23 int len, id;
24 
25 void dfs(int u, int fa, int d)
26 {
27     if(d > len) { len = d; id = u; }
28     for(int i = 0; i < G[u].size(); i++)
29     {
30         int v = G[u][i];
31         if(v != fa) dfs(v, u, d + 1);
32     }
33 }
34 
35 int longest(int v)
36 {
37     len = -1;
38     dfs(v, -1, 0);
39     len = -1;
40     dfs(id, -1, 0);
41     return len;
42 }
43 
44 int main()
45 {
46     scanf("%d%d%d", &n, &m, &Q);
47 
48     for(int i = 1; i <= n; i++)  pa[i] = i;
49     while(m--)
50     {
51         int u, v; scanf("%d%d", &u, &v);
52         G[u].push_back(v);
53         G[v].push_back(u);
54         Union(u, v);
55     }
56 
57     for(int i = 1; i <= n; i++)
58     {
59         int p = findset(i);
60         if(!vis[p])
61         {
62             vis[p] = true;
63             diameter[p] = longest(p);
64         }
65     }
66 
67     while(Q--)
68     {
69         int op, x, y;
70         scanf("%d%d", &op, &x);
71         if(op == 1)
72         {
73             printf("%d
", diameter[findset(x)]);
74         }
75         else
76         {
77             scanf("%d", &y);
78             int px = findset(x), py = findset(y);
79             if(px == py) continue;
80             pa[px] = py;
81             int t = (diameter[px] + 1) / 2 + (diameter[py] + 1) / 2 + 1;
82             diameter[py] = max(diameter[px], max(diameter[py], t));
83         }
84     }
85 
86     return 0;
87 }
代码君

　　　　CodeForces 274B 树形DP

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 
10 const int maxn = 100000 + 10;
11 
12 int n;
13 
14 vector<int> G[maxn];
15 LL val[maxn];
16 LL add[maxn], sub[maxn];
17 
18 void dfs(int u, int fa)
19 {
20     for(int i = 0; i < G[u].size(); i++)
21     {
22         int v = G[u][i];
23         if(v != fa)
24         {
25             dfs(v, u);
26             add[u] = max(add[u], add[v]);
27             sub[u] = max(sub[u], sub[v]);
28         }
29     }
30     val[u] += add[u] - sub[u];
31     if(val[u] > 0) sub[u] += val[u];
32     else if(val[u] < 0) add[u] += -val[u];
33 }
34 
35 int main()
36 {
37     scanf("%d", &n);
38     for(int i = 1; i < n; i++)
39     {
40         int u, v; scanf("%d%d", &u, &v);
41         G[u].push_back(v);
42         G[v].push_back(u);
43     }
44     for(int i = 1; i <= n; i++) scanf("%I64d", val + i);
45 
46     dfs(1, -1);
47     printf("%I64d
", add[1] + sub[1]);
48 
49     return 0;
50 }
代码君

　　　　CodeForces 337D

　　　　题意：给出一棵n个节点的树，和m个特定的点。求这棵树中距所有这m个点的距离不超过d的点的个数。

　　　　题解本来是给的DP的做法，评论下面有个给出了一种更好的方法：用类似求树的直径办法求出这m个点中相距最远的两个点a、b，然后算出所有点到a、b的距离。最终答案所统计的点就是距a、b不超过d的点的个数。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 using namespace std;
 7 
 8 const int maxn = 100000 + 10;
 9 
10 vector<int> G[maxn];
11 
12 int n, m, d;
13 
14 int p[maxn];
15 bool mark[maxn];
16 
17 int a, b;
18 
19 int len, id;
20 
21 void dfs1(int u, int fa, int d)
22 {
23     if(mark[u] && d > len) { len = d; id = u; }
24     for(int i = 0; i < G[u].size(); i++)
25     {
26         int v = G[u][i];
27         if(v == fa) continue;
28         dfs1(v, u, d + 1);
29     }
30 }
31 
32 int La[maxn], Lb[maxn];
33 
34 void dfs2(int u, int fa, int d, int* L)
35 {
36     L[u] = d;
37     for(int i = 0; i < G[u].size(); i++)
38     {
39         int v = G[u][i];
40         if(v == fa) continue;
41         dfs2(v, u, d + 1, L);
42     }
43 }
44 
45 int main()
46 {
47     //freopen("in.txt", "r", stdin);
48 
49     scanf("%d%d%d", &n, &m, &d);
50     for(int i = 0; i < m; i++)
51     {
52         scanf("%d", p + i);
53         mark[p[i]] = true;
54     }
55     for(int i = 1; i < n; i++)
56     {
57         int u, v; scanf("%d%d", &u, &v);
58         G[u].push_back(v); G[v].push_back(u);
59     }
60 
61     len = -1;
62     dfs1(p[0], 0, 0);
63     a = id;
64     len = -1;
65     dfs1(a, 0, 0);
66     b = id;
67 
68     dfs2(a, 0, 0, La);
69     dfs2(b, 0, 0, Lb);
70 
71     int ans = 0;
72     for(int i = 1; i <= n; i++) if(La[i] <= d && Lb[i] <= d) ans++;
73     printf("%d
", ans);
74 
75     return 0;
76 }
代码君

　　　　CodeForces 486D 树形DP 枚举集合中值最小的点(如果点一样的话就枚举取编号最小的那个)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <vector>
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 
10 const int maxn = 2000 + 10;
11 const LL MOD = 1000000007;
12 
13 int d, n, root;
14 int a[maxn];
15 vector<int> G[maxn];
16 
17 LL dfs(int u, int fa)
18 {
19     LL ans = 1;
20     for(int i = 0; i < G[u].size(); i++)
21     {
22         int v = G[u][i];
23         if(v == fa) continue;
24         if(a[v] < a[root] || a[v] > a[root] + d) continue;
25         if(a[v] == a[root] && v < root) continue;
26         ans = (ans * (dfs(v, u) + 1)) % MOD;
27     }
28     return ans;
29 }
30 
31 int main()
32 {
33     scanf("%d%d", &d, &n);
34     for(int i = 1; i <= n; i++) scanf("%d", a + i);
35     for(int i = 1; i < n; i++)
36     {
37         int u, v; scanf("%d%d", &u, &v);
38         G[u].push_back(v); G[v].push_back(u);
39     }
40 
41     LL ans = 0;
42     for(int i = 1; i <= n; i++)
43     {
44         root = i;
45         ans = (ans + dfs(i, 0)) % MOD;
46     }
47 
48     printf("%I64d
", ans);
49 
50     return 0;
51 }
代码君

　　　　POJ 3744 概率DP + 矩阵快速幂优化

　　　　先不考虑地雷，设f(x)表示走到位置x的概率。则有递推关系。所以在一段没有地雷的区间，可以快速计算走x步的概率。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 typedef double Mat[2][2];
 8 
 9 const int maxn = 12;
10 int n;
11 double p;
12 int pos[maxn];
13 
14 Mat A, E;
15 
16 void mul(Mat A, Mat B, Mat ans)
17 {
18     Mat C;
19     memset(C, 0, sizeof(C));
20     for(int i = 0; i < 2; i++)
21         for(int j = 0; j < 2; j++)
22             for(int k = 0; k < 2; k++)
23                 C[i][j] += A[i][k] * B[k][j];
24     memcpy(ans, C, sizeof(C));
25 }
26 
27 void pow(Mat A, int n, Mat ans)
28 {
29     Mat a, r;
30     memcpy(a, A, sizeof(a));
31     memset(r, 0, sizeof(r));
32     r[0][0] = r[1][1] = 1;
33     while(n)
34     {
35         if(n & 1) mul(r, a, r);
36         mul(a, a, a);
37         n >>= 1;
38     }
39 
40     memcpy(ans, r, sizeof(r));
41 }
42 
43 int main()
44 {
45     //freopen("in.txt", "r", stdin);
46 
47     while(scanf("%d", &n) == 1 && n)
48     {
49         scanf("%lf", &p);
50         for(int i = 0; i < n; i++) scanf("%d", pos + i);
51         sort(pos, pos + n);
52         n = unique(pos, pos + n) - pos;
53 
54         if(pos[0] == 1) { puts("0.0000000"); continue; }
55         bool flag = false;
56         for(int i = 0; i + 1 < n; i++) if(pos[i] + 1 == pos[i+1]) { flag = true; break; }
57         if(flag) { puts("0.0000000"); continue; }
58 
59         Mat x, t;
60         x[0][0] = 0; x[0][1] = 1; x[1][0] = 1- p; x[1][1] = p;
61         pow(x, pos[0] - 2, t);
62         double ans = t[1][1];
63 
64         for(int i = 1; i < n; i++)
65         {
66             ans *= 1.0 - p;
67             pow(x, pos[i]-pos[i-1]-2, t);
68             ans *= t[1][1];
69         }
70 
71         printf("%.7f
", ans * (1.0 - p));
72     }
73 
74     return 0;
75 }
代码君

7.27

　　　　POJ 2096 Collecting Bugs 概率DP

　　　　d(i, j)表示已经发现i种BUG且属于j个子系统，距离目标的期望天数。然后逆推

 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 const int maxn = 1000 + 10;
 7 
 8 double d[maxn][maxn];
 9 
10 int n, s;
11 
12 int main()
13 {
14     while(scanf("%d%d", &n, &s) == 2)
15     {
16         d[n][s] = 0;
17         double ns = n * 1.0 * s;
18         for(int i = n; i >= 0; i--)
19             for(int j = s; j >= 0; j--)
20             {
21                 if(i == n && j == s) continue;
22                 double p1 = (double)(i*j)/ns;
23                 double p2 = (double)((n-i)*j)/ns;
24                 double p3 = (double)(i*(s-j))/ns;
25                 double p4 = (double)(n-i)*(s-j)/ns;
26                 d[i][j] = (p2*d[i+1][j] + p3*d[i][j+1] + p4*d[i+1][j+1] + 1.0) / (1.0 - p1);
27             }
28 
29         printf("%.4f
", d[0][0]);
30     }
31 
32     return 0;
33 }
代码君

　　　　CodeForces 148D Bag of mice 概率DP

 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 const int maxn = 1000 + 10;
 7 
 8 int w, b;
 9 
10 bool vis[maxn][maxn];
11 
12 double d[maxn][maxn];
13 
14 double DP(int w, int b)
15 {
16     if(w <= 0) return 0;
17     if(b <= 0) return 1;
18     if(vis[w][b]) return d[w][b];
19     vis[w][b] = true;
20 
21     double& ans = d[w][b];
22     ans = w * 1.0 / (w + b);
23 
24     double t = b * 1.0 / ( w + b);
25     b--;
26     t *= b * 1.0 / ( w + b);
27     b--;
28 
29     if(t > 1e-13)
30     {
31         double ta = (w * 1.0 / (w + b)) * DP(w-1, b);
32         double tb = (b * 1.0 / (w + b)) * DP(w, b-1);
33         ans += t * (ta + tb);
34     }
35 
36     return ans;
37 }
38 
39 int main()
40 {
41     scanf("%d%d", &w, &b);
42     printf("%.9f
", DP(w, b));
43 
44     return 0;
45 }
代码君

　　　　ZOJ 3329 One Person Game 概率DP

　　　　这是个有换的概率DP，需要神奇地将式子变形一下。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 int n;
 7 int k1, k2, k3;
 8 int a, b, c;
 9 
10 const int maxn = 500 + 20;
11 
12 double A[maxn], B[maxn];
13 
14 double pro[20];
15 
16 int main()
17 {
18     int T; scanf("%d", &T);
19     while(T--)
20     {
21         scanf("%d%d%d%d%d%d%d", &n, &k1, &k2, &k3, &a, &b, &c);
22         int tot = k1 + k2 + k3;
23 
24         memset(pro, 0, sizeof(pro));
25         double t = 1.0 / (1.0 * k1 * k2 * k3);
26         for(int i = 1; i <= k1; i++)
27             for(int j = 1; j <= k2; j++)
28                 for(int k = 1; k <= k3; k++)
29                     if(i != a || j != b || k != c)
30                         pro[i+j+k] += t;
31 
32         memset(A, 0, sizeof(A));
33         memset(B, 0, sizeof(B));
34         for(int i = n; i >= 0; i--)
35         {
36             A[i] = t; B[i] = 1.0;
37             for(int j = 3; j <= tot; j++)
38             {
39                 A[i] += pro[j] * A[i + j];
40                 B[i] += pro[j] * B[i + j];
41             }
42         }
43 
44         printf("%.15f
", B[0] / (1.0 - A[0]));
45     }
46 
47     return 0;
48 }
代码君

　　　　HDU 4405 Aeroplane chess 概率DP

　　　　一维的概率DP直接递推就行了，设d(i)表示在第i个格子，还需走的次数的期望。如果x能直接走到y，则d(x) = d(y)。

　　　　否则。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 int n, m;
 7 
 8 const int maxn = 100000 + 10;
 9 const int maxm = 1000 + 10;
10 const double p0 = 1.0 / 6.0;
11 int p[maxn];
12 double d[maxn];
13 
14 int main()
15 {
16     while(scanf("%d%d", &n, &m) == 2 && n)
17     {
18         memset(p, 0, sizeof(p));
19         while(m--)
20         {
21             int x, y; scanf("%d%d", &x, &y);
22             p[x] = y;
23         }
24         memset(d, 0, sizeof(d));
25 
26         for(int i = n-1; i >= 0; i--)
27         {
28             if(p[i]) d[i] = d[p[i]];
29             else
30             {
31                 d[i] = 1;
32                 for(int j = 1; j <= 6; j++)
33                     d[i] += p0 * d[i + j];
34             }
35         }
36 
37         printf("%.4f
", d[0]);
38     }
39 
40     return 0;
41 }
代码君

　　　　HDU 4089 && UVa 1498 Activation 带环的概率DP

7.28

　　　　HDU 4035 Maze 树上的概率DP

　　　　这题好难，简直要把人难哭了。题解戳这

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <vector>
 6 using namespace std;
 7 
 8 const int maxn = 10000 + 10;
 9 const double eps = 1e-10;
10 
11 int n;
12 double A[maxn], B[maxn], C[maxn];
13 double e[maxn], k[maxn];
14 
15 vector<int> G[maxn];
16 
17 bool dfs(int u, int fa)
18 {
19     int m = G[u].size();
20 
21     if(m == 1 && fa)
22     {
23         A[u] = k[u];
24         B[u] = C[u] = 1.0 - k[u] - e[u];
25         return true;
26     }
27 
28     double sigA = 0, sigB = 0, sigC = 0;
29     for(int i = 0; i < G[u].size(); i++)
30     {
31         int v = G[u][i];
32         if(v == fa) continue;
33         if(!dfs(v, u)) return false;
34         sigA += A[v];
35         sigB += B[v];
36         sigC += C[v];
37     }
38 
39     double tt = (1 - k[u] - e[u]) / m;
40     double t = 1.0 - tt * sigB;
41     if(fabs(t) < eps) return false;
42 
43     A[u] = (k[u] + tt * sigA) / t;
44     B[u] = tt / t;
45     C[u] = (tt * sigC + 1.0 - k[u] - e[u]) / t;
46 
47     return true;
48 }
49 
50 int main()
51 {
52     //freopen("in.txt", "r", stdin);
53 
54     int T; scanf("%d", &T);
55     for(int kase = 1; kase <= T; kase++)
56     {
57         printf("Case %d: ", kase);
58 
59         scanf("%d", &n);
60         for(int i = 1; i <= n; i++) G[i].clear();
61         for(int i = 1; i < n; i++)
62         {
63             int u, v; scanf("%d%d", &u, &v);
64             G[u].push_back(v); G[v].push_back(u);
65         }
66 
67         for(int i = 1; i <= n; i++)
68         {
69             scanf("%lf%lf", k + i, e + i);
70             k[i] /= 100.0; e[i] /= 100.0;
71         }
72 
73         if(!dfs(1, 0) || fabs(A[1] - 1.0) < eps) puts("impossible");
74         else printf("%.6f
", C[1] / (1.0 - A[1]));
75     }
76 
77     return 0;
78 }
代码君

　　　　HDU 3853 概率DP

　　　　递推方程式很容易就写出来了。但是有一个坑点就是，当某个格子的P1 = 1时，妹子就会困死在原地，根据方程式来看答案不就变成无穷大了吗，而题目中说了最终答案小于1e6。AC的做法应该是直接把这种情况的期望变为0，=_-||

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 using namespace std;
 6 
 7 const int maxn = 1000 + 10;
 8 
 9 const double eps = 1e-8;
10 
11 int n, m;
12 
13 double p[maxn][maxn][3];
14 double E[maxn][maxn];
15 
16 int main()
17 {
18     while(scanf("%d%d", &n, &m) == 2 && n)
19     {
20         for(int i = 1; i <= n; i++)
21             for(int j = 1; j <= m; j++)
22                 for(int k = 0; k < 3; k++)  scanf("%lf", &p[i][j][k]);
23         memset(E, 0, sizeof(E));
24 
25         for(int i = n; i >= 1; i--)
26             for(int j = m; j >= 1; j--)
27             {
28                 if(i == n && j == m) continue;
29                 if(fabs(1.0 - p[i][j][0]) < eps) continue;
30                 double t = 1.0 - p[i][j][0];
31                 double p2 = p[i][j][1], p3 = p[i][j][2];
32                 E[i][j] = p2 / t * E[i][j+1] + p3 / t * E[i+1][j] + 2.0 / t;
33             }
34 
35         printf("%.3f
", E[1][1]);
36     }
37 
38     return 0;
39 }
代码君

7.29

　　　　补多校题目。

　　　　POJ 2151 概率DP

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 int n, m, cham;
 8 
 9 const int maxn = 35;
10 const int maxm = 1000 + 10;
11 
12 double p[maxm][maxn];
13 double d[maxm][maxn][maxn];
14 
15 int main()
16 {
17     while(scanf("%d%d%d", &m, &n, &cham) == 3)
18     {
19         if(n == 0 && m == 0 && cham == 0) break;
20         for(int i = 1; i <= n; i++)
21             for(int j = 1; j <= m; j++) scanf("%lf", &p[i][j]);
22 
23         for(int i = 1; i <= n; i++) { d[i][1][1] = p[i][1]; d[i][1][0] = 1.0 - p[i][1]; }
24 
25         for(int i = 1; i <= n; i++)
26             for(int j = 2; j <= m; j++)
27                 for(int k = 0; k <= j; k++)
28                 {
29                     if(k == 0) d[i][j][k] = d[i][j-1][k] * (1.0 - p[i][j]);
30                     else d[i][j][k] = p[i][j]*d[i][j-1][k-1] + (1.0-p[i][j])*d[i][j-1][k];
31                 }
32 
33         double ans1 = 1, ans2 = 1;
34         for(int i = 1; i <= n; i++)
35         {
36             double p1 = 0, p2 = 0;
37             for(int j = 1; j <= m; j++)
38             {
39                 p1 += d[i][m][j];
40                 if(j < cham) p2 += d[i][m][j];
41             }
42             ans1 *= p1;
43             ans2 *= p2;
44         }
45 
46         printf("%.3f
", ans1 - ans2);
47     }
48 
49     return 0;
50 }
代码君

　　　　POJ 3071 概率DP 又到了神奇的位运算出场的时候了

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 double p[150][150];
 8 double d[10][150];
 9 
10 int main()
11 {
12     //freopen("in.txt", "r", stdin);
13 
14     int n;
15     while(scanf("%d", &n) == 1 && n + 1)
16     {
17         for(int i = 0; i < (1<<n); i++)
18             for(int j = 0; j < (1<<n); j++) scanf("%lf", &p[i][j]);
19         memset(d, 0, sizeof(d));
20         for(int i = 0; i < (1 << n); i++) d[0][i] = 1.0;
21         for(int i = 1; i <= n; i++)
22             for(int j = 0; j < (1 << n); j++)
23                 for(int k = 0; k < (1 << n); k++)
24                     if(((k >> (i-1)) ^ 1) == (j >> (i-1)))
25                         d[i][j] += d[i-1][j] * d[i-1][k] * p[j][k];
26 
27         double M = 0.0;
28         int id;
29         for(int i = 0; i < (1 << n); i++) if(d[n][i] > M) { M = d[n][i]; id = i; }
30         printf("%d
", id + 1);
31     }
32 
33     return 0;
34 }
代码君

7.30

　　　　ZOJ 3380 概率DP 看了网上好多题解，「感觉」有点不靠谱。因为既然把状态定义为

dp[i][j]表示当前已经放了j个位置，用到了第i种颜色

　　　　既然用到了第i种颜色，那为什么代码中k还是从0开始循环呢？

　　　　我觉得从0开始循环应该表示考虑过第i种颜色，可以出现可以不出现。所以不符合要求的方案应该就是d[n][m]，而不是sum{d[1~n][m]}

　　　　但是为什么他们能AC我就想不通了，智商余额不足。。

 1 import java.util.*;
 2 import java.io.*;
 3 import java.math.*;
 4 
 5 public class Main
 6 {
 7     static BigInteger[][] dp = new BigInteger[110][110];
 8     static BigInteger[][] C = new BigInteger[110][110];
 9 
10     public static void main(String arg[])
11     {
12         Scanner cin = new Scanner(new BufferedInputStream(System.in));
13         for(int i = 0; i < 105; i++)
14         {
15             C[i][0] = C[i][i] = BigInteger.ONE;
16             for(int j = 1; j < i; j++)
17                 C[i][j] = C[i-1][j].add(C[i-1][j-1]);
18         }
19 
20         int n, m, l;
21         while(cin.hasNext())
22         {
23             m = cin.nextInt();
24             n = cin.nextInt();
25             l = cin.nextInt();
26             BigInteger tot = BigInteger.valueOf(n).pow(m);
27             
28             if(l > m)
29             {
30                 System.out.println("mukyu~");
31                 continue;
32             }
33 
34             if(l > m / 2)
35             {
36                 BigInteger ans = BigInteger.ZERO;
37                 for(int i = l; i <= m; i++)
38                     ans = ans.add(C[m][i].multiply(BigInteger.valueOf(n-1).pow(m-i)));
39                 ans = ans.multiply(BigInteger.valueOf(n));
40                 BigInteger g = ans.gcd(tot);
41                 System.out.println(ans.divide(g) + "/" + tot.divide(g));
42                 continue;
43             }
44 
45             for(int i = 0; i <= n; i++)
46                 for(int j = 0; j <= m; j++) dp[i][j] = BigInteger.ZERO;
47             dp[0][0] = BigInteger.ONE;
48 
49             for(int i = 1; i <= n; i++)
50                 for(int j = 0; j <= m; j++)
51                     for(int k = 0; k <= j && k < l; k++)
52                         dp[i][j] = dp[i][j].add(dp[i-1][j-k].multiply(C[j][k]));
53             BigInteger ans = tot.subtract(dp[n][m]);
54             BigInteger g = ans.gcd(tot);
55             System.out.println(ans.divide(g) + "/" + tot.divide(g));
56         }
57     }
58 }
代码君

　　　　ZOJ 3640 概率DP

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int maxn = 20000 + 10;
 9 const double hehe = (1.0 + sqrt(5)) / 2.0;
10 int n, f;
11 double d[maxn];
12 int t[maxn];
13 int c[maxn];
14 
15 double E(int f)
16 {
17     if(d[f]) return d[f];
18     d[f] = 0;
19     for(int i = 0; i < n; i++)
20     {
21         if(f > c[i]) d[f] += t[i];
22         else d[f] += E(f + c[i]) + 1;
23     }
24     d[f] /= n;
25     return d[f];
26 }
27 
28 int main()
29 {
30     while(scanf("%d%d", &n, &f) == 2)
31     {
32         for(int i = 0; i < n; i++)
33         {
34             scanf("%d", c + i);
35             t[i] = hehe * c[i] * c[i];
36         }
37 
38         memset(d, 0, sizeof(d));
39         printf("%.3f
", E(f));
40     }
41 
42     return 0;
43 }
代码君

　　　　HDU 4336 概率DP 状压

　　　　SGU 495 概率DP

　　　　HDU 1054 树形DP

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <vector>
 6 using namespace std;
 7 
 8 const int maxn = 2000;
 9 int d[2][maxn];
10 int n;
11 vector<int> G[maxn];
12 
13 void dfs(int u, int fa)
14 {
15     d[0][u] = 0;
16     d[1][u] = 1;
17     for(int i = 0; i < G[u].size(); i++)
18     {
19         int v = G[u][i];
20         if(v == fa) continue;
21         dfs(v, u);
22         d[0][u] += d[1][v];
23         d[1][u] += min(d[0][v], d[1][v]);
24     }
25 }
26 
27 int main()
28 {
29     while(scanf("%d", &n) == 1 && n)
30     {
31         for(int i = 0; i < n; i++) G[i].clear();
32         for(int i = 0; i < n; i++)
33         {
34             int u, t, v;
35             scanf("%d:(%d)", &u, &t);
36             for(int j = 0; j < t; j++)
37             {
38                 scanf("%d", &v);
39                 G[u].push_back(v);
40                 G[v].push_back(u);
41             }
42         }
43         dfs(0, -1);
44         printf("%d
", min(d[0][0], d[1][0]));
45     }
46 
47     return 0;
48 }
代码君

　　　　HDU 2376 树形DP

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 using namespace std;
 7 
 8 const int maxn = 10000 + 10;
 9 
10 int n;
11 int fa[maxn], d[maxn];
12 int u[maxn], v[maxn], w[maxn];
13 vector<int> G[maxn];
14 
15 void dfs(int u, int father)
16 {
17     d[u] = 1;
18     fa[u] = father;
19     for(int i = 0; i < G[u].size(); i++)
20     {
21         int v = G[u][i];
22         if(v == father) continue;
23         dfs(v, u);
24         d[u] += d[v];
25     }
26 }
27 
28 int main()
29 {
30     int T; scanf("%d", &T);
31     while(T--)
32     {
33         scanf("%d", &n);
34         for(int i = 0; i < n; i++) G[i].clear();
35         for(int i = 1; i < n; i++)
36         {
37             scanf("%d%d%d", u + i, v + i, w + i);
38             G[u[i]].push_back(v[i]);
39             G[v[i]].push_back(u[i]);
40         }
41 
42         dfs(0, 0);
43 
44         double sum = 0;
45         for(int i = 1; i < n; i++)
46         {
47             int x = u[i], y = v[i];
48             if(fa[x] == y) swap(x, y);
49             int ta = d[y], tb = n - d[y];
50             sum += (double)ta * tb * w[i];
51         }
52         double mu = n * 1.0 * (n-1) / 2;
53         printf("%.9f
", sum / mu);
54     }
55 
56     return 0;
57 }
代码君

　　　　POJ 1986 LCA模板题 开始几发WA原来是因为数组开小了

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 using namespace std;
 7 
 8 const int maxn = 100000 + 10;
 9 
10 vector<int> G[maxn], c[maxn];
11 
12 int n, m;
13 
14 int dis[maxn];
15 int fa[maxn];
16 int L[maxn];
17 int anc[maxn][15];
18 
19 void dfs(int u, int father, int d)
20 {
21     fa[u] = father;
22     L[u] = d;
23     for(int i = 0; i < G[u].size(); i++)
24     {
25         int v = G[u][i];
26         if(v == father) continue;
27         dis[v] = dis[u] + c[u][i];
28         dfs(v, u, d + 1);
29     }
30 }
31 
32 int LCA(int p, int q)
33 {
34     if(L[p] < L[q]) swap(p, q);
35     int log;
36     for(log = 1; (1 << log) <= L[p]; log++); log--;
37     for(int i = log; i >= 0; i--)
38         if(L[p] - (1 << i) >= L[q]) p = anc[p][i];
39     if(p == q) return q;
40     for(int i = log; i >= 0; i--)
41         if(anc[p][i] && anc[p][i] != anc[q][i])
42             p = anc[p][i], q = anc[q][i];
43     return fa[p];
44 }
45 
46 int main()
47 {
48     //freopen("in.txt", "r", stdin);
49 
50     scanf("%d%d", &n, &m);
51     for(int i = 0; i < m; i++)
52     {
53         int u, v, d;
54         scanf("%d%d%d", &u, &v, &d);
55         G[u].push_back(v); c[u].push_back(d);
56         G[v].push_back(u); c[v].push_back(d);
57         getchar(); getchar();
58     }
59 
60     dfs(1, 0, 0);
61 
62     for(int i = 1; i <= n; i++)
63     {
64         anc[i][0] = fa[i];
65         for(int j = 1; (1 << j) < n; j++) anc[i][j] = 0;
66     }
67 
68     for(int j = 1; (1 << j) < n; j++)
69         for(int i = 1; i <= n; i++) if(anc[i][j-1])
70             anc[i][j] = anc[anc[i][j-1]][j-1];
71 
72     int Q; scanf("%d", &Q);
73     while(Q--)
74     {
75         int u, v;
76         scanf("%d%d", &u, &v);
77         int lca = LCA(u, v);
78         printf("%d
", dis[u] + dis[v] - dis[lca] * 2);
79     }
80 
81     return 0;
82 }
代码君

　　　　POJ 1655 树形DP

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 using namespace std;
 7 
 8 const int maxn = 20000 + 10;
 9 
10 int n;
11 int d[maxn], b[maxn];
12 
13 vector<int> G[maxn];
14 
15 void dfs(int u, int fa)
16 {
17     d[u] = 1;
18     b[u] = 0;
19     for(int i = 0; i < G[u].size(); i++)
20     {
21         int v = G[u][i];
22         if(v == fa) continue;
23         dfs(v, u);
24         d[u] += d[v];
25         b[u] = max(b[u], d[v]);
26     }
27     b[u] = max(b[u], n - d[u]);
28 }
29 
30 int main()
31 {
32     int T; scanf("%d", &T);
33     while(T--)
34     {
35         scanf("%d", &n);
36         for(int i = 1; i <= n; i++) G[i].clear();
37         for(int i = 1; i < n; i++)
38         {
39             int u, v; scanf("%d%d", &u, &v);
40             G[u].push_back(v);
41             G[v].push_back(u);
42         }
43 
44         dfs(1, 0);
45 
46         int ans = b[1], id = 1;
47         for(int i = 2; i <= n; i++)
48             if(b[i] < ans || (b[i] == ans && i < id)) { ans = b[i]; id = i; }
49 
50         printf("%d %d
", id, ans);
51     }
52 
53     return 0;
54 }
代码君

　　　　POJ 1935 树形DP 5W个点要开10W的数组，Why?

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int maxn = 100000 + 10;
 7 
 8 struct Edge
 9 {
10     int v, w, nxt;
11 }edges[maxn];
12 int sz;
13 int head[maxn];
14 bool vis[maxn];
15 int dis[maxn];
16 int n, m, root;
17 
18 void Insert(int u, int v, int w)
19 {
20     edges[sz].v = v;
21     edges[sz].w = w;
22     edges[sz].nxt = head[u];
23     head[u] = sz++;
24 }
25 
26 int tot;
27 int haha[maxn];
28 
29 void dfs(int u, int fa)
30 {
31     for(int i = head[u]; i != -1; i = edges[i].nxt)
32     {
33         int v = edges[i].v, w = edges[i].w;
34         if(v == fa) continue;
35         dis[v] = dis[u] + w;
36         dfs(v, u);
37         if(vis[v]) { tot += w * 2; vis[u] = true; }
38     }
39 }
40 
41 int main()
42 {
43     while(scanf("%d%d", &n, &root) == 2)
44     {
45         sz = 0;
46         memset(head, -1, sizeof(head));
47         for(int i = 1; i < n; i++)
48         {
49             int u, v, w; scanf("%d%d%d", &u, &v, &w);
50             Insert(u, v, w);
51             Insert(v, u, w);
52         }
53 
54         memset(vis, false, sizeof(vis));
55         scanf("%d", &m);
56         for(int i = 0; i < m; i++) { scanf("%d", haha + i); vis[haha[i]] = true; }
57 
58         tot = 0;
59         dis[root] = 0;
60         dfs(root,  -1);
61 
62         int hehe = 0;
63         for(int i = 0; i < m; i++) hehe = max(hehe, dis[haha[i]]);
64         printf("%d
", tot - hehe);
65     }
66 
67     return 0;
68 }
代码君

　　　　SGU 149 Computer Network 树形DP

　　　　POJ 1849 树的直径

7.31

HDU 4003

 

POJ 2486 树形背包DP Apple Tree

 

HDU 3507 斜率优化 DP Print Article

 

HDU 2829 斜率优化DP Lawrence

 

8.1(又过了一个月，sigh~)

HDU 3045 DP 斜率优化 Picnic Cows

 

HDU 3480 DP 斜率优化 Division

 

8.2

CodeForces 484B 数学 Maximum Value

 

HDU 3516 DP 四边形不等式优化 Tree Construction

 

HDU 3506 DP 四边形不等式优化 Monkey Party

 

LightOJ 1422 区间DP Halloween Costumes

 

POJ 2955 区间DP Brackets

 

UVa 11987 并查集 Almost Union-Find

 

CodeForces 149D 区间DP Coloring Brackets

 

POJ 1651 区间DP Multiplication Puzzle

 

8.3

ZOJ 3469 区间DP Food Delivery

 

HDU 4283 区间DP You Are the One

 

HDU 2476 区间DP String painter

 

LA 4256 DP Salesmen

 

UVa 10534 DP LIS Wavio Sequence

 

UVa 11552 DP Fewest Flops

 

8.4

UVa 1407 树形背包 Caves

 

UVa 12235 状压DP Help Bubu

 

8.5

UVa 1354 枚举子集 Mobile Computing

 

UVa 12299 线段树 单点更新 RMQ with Shifts

 

8.6

SPOJ 375 树链剖分 QTREE - Query on a tree

 

HDU 3966 RE 树链剖分 Aragorn's Story

 

POJ 2763 树链剖分 线段树 Housewife Wind

 

8.10

UVa 11795 状压DP Mega Man's Mission

 

UVa 1452 递推 Jump

 

UVa 1366 DP Martian Mining

 

HDU 1827 强连通 缩点 Summer Holiday

 

HDU 3072 SCC Intelligence System

 

HDU 3639 SCC Hawk-and-Chicken

 

8.11

CodeForces 109C 树形DP Lucky Tree

 

CodeForces 489F DP Special Matrices

 

CodeForces 519E 树形DP A and B and Lecture Rooms

 

HDU 2242 双连通分量 考研路茫茫——空调教室

 

8.12

HDU 4738 双连通分量 Caocao's Bridges

 

HDU 3394 双连通分量 桥 Railway

 

UVa 12167 & HDU 2767 强连通分量 Proving Equivalences

 

8.13

UVa 10564 DP Paths through the Hourglass

 

8.14

HDU 5379 树形DP Mahjong tree

 

HDU 5378 树上的概率DP Leader in Tree Land

 

CodeForces 348B Apple Tree

 

CodeForces 14D 树的直径 Two Paths

 

8.15

CodeForces 570D DFS序 树状数组 Tree Requests

 

HDU 5371 Manacher Hotaru's problem

 

8.17

CodeForces 379F 树的直径 New Year Tree

 

8.18

CodeForces 567F DP Mausoleum

 

8.19

HDU 5399 数学 Too Simple

 

HDU 5402 模拟 构造 Travelling Salesman Problem

 

HDU 5396 区间DP 数学 Expression

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/AOQNRMGYXLMV/p/4671534.html