簡單的樹形動態規劃
貼代碼
1 /*
2 * SOUR:sgu 134
3 * ALGO:tree dp
4 * DATE: 2009年 12月 09日 星期三 16:28:16 CST
5 * COMM:3
6 * */
7 #include<iostream>
8 #include<cstdio>
9 #include<cstdlib>
10 #include<cstring>
11 #include<algorithm>
12 #include<vector>
13 using namespace std;
14 typedef long long LL;
15 const int maxint = 0x7fffffff;
16 const long long max64 = 0x7fffffffffffffffll;
17 const int N = 16100;
18 #define pb(x) push_back(x)
19 vector<int> g[N];
20 int vis[N];
21 int n,res = maxint,out[N],top;
22 void ckmax(int &a,int b) { if(a < b) a = b;}
23 int dfs(int u)
24 {
25 //printf("dfs = %d\n",u);
26 vis[u] = true;
27 int sum = 0,val = 0,tmp;
28 for(int i = 0;i < g[u].size();i++) {
29 int v = g[u][i];
30 if(!vis[v]) {
31 tmp = dfs(v);
32 sum += tmp;
33 ckmax(val,tmp);
34 }
35 }
36 tmp = n - 1 - sum;
37 ckmax(val,tmp);
38 if (res > val) {
39 res = val,top = 1,out[0] = u;
40 }else if(val == res) {
41 out[top++] = u;
42 }
43 return sum + 1;
44 }
45
46 int main()
47 {
48 int i,j,k,a=-1,b;
49 scanf("%d",&n);
50 for(i = 1;i < n;i++) {
51 scanf("%d%d",&a,&b);
52 g[a].pb(b);
53 g[b].pb(a);
54 }
55 if(a != -1) {
56 dfs(a);
57 printf("%d %d\n",res,top);
58 sort(out,out + top);
59 if(top > 0) printf("%d",out[0]);
60 for(i = 1;i < top;i++) {
61 printf(" %d",out[i]);
62 }
63 putchar(10);
64 }else {
65 printf("0 0\n");
66 }
67 return 0;
68 }
69
70
sgu133 排序，看你幾分鐘能想出來
1 scanf("%d",&n);
2 for(i = 0;i < n;i++) {
3 scanf("%d%d",&a[i].l,&a[i].r);
4 }
5 sort(a,a + n,cmp);
6 int res = 0,pre = -1;
7 for(i = 0;i < n;i++) {
8 if(a[i].r < pre) {
9 res ++;
10 }
11 pre = max(pre,a[i].r);
12 }
13 printf("%d\n",res);
14
sgu181 算一個遞推式的第k項，很容易錯
1 /*
2 * SOUR:sgu181
3 * ALGO:math
4 * DATE: 2009年 12月 11日 星期五 21:50:18 CST
5 * COMM:3
6 * 注意k可能出現在循環節開始之前
7 * */
8 #include<iostream>
9 #include<cstdio>
10 #include<cstdlib>
11 #include<cstring>
12 #include<algorithm>
13 using namespace std;
14 typedef long long LL;
15 const int maxint = 0x7fffffff;
16 const long long max64 = 0x7fffffffffffffffll;
17
18 LL A,alpha,beta,gamma,M,k;
19 const int N = 20010;
20 LL vis[N];
21 LL val[N];
22 int main()
23 {
24 LL i;
25 /*
26 1) x0 = A;
27 2) xi = (alpha * x(i-1)^2 + beta * x(i-1) + gamma) mod M, for i >= 1.
28 * */
29 //A (1 <= A <= 10000), alpha (0 <= alpha <= 100), beta (0 <= beta <= 100), gamma
30 //(0 <= gamma <= 100), M (1 <= M <= 1000), k (0 <= k <= 10^9)
31
32 fill(vis,vis + N,-1);
33 cin >> A >> alpha >> beta >> gamma >> M >> k;
34 LL xi = A,step = 0,cycle,before;
35 while(1) {
36 if(vis[xi] >= 0) {
37 cycle = step - vis[xi];
38 before = vis[xi];
39 break;
40 }
41 val[step] = xi;
42 vis[xi] = step ++;
43
44 xi = (alpha * xi*xi + beta * xi + gamma) % M;
45 }
46 if(k < step ) {
47 cout << val[k] << endl;
48 }else {
49 LL idx = (k-before)%cycle + before;
50 cout << val[idx] << endl;
51 }
52
53 return 0;
54 }
55
56