C++博客-暑假训练之记录

TOJ 2553 Japan

gong — Mon, 27 Jul 2009 08:00:00 GMT

1 /*
2  * File:   H.cpp
3  * Author: GongZhi
4  * Problem:
5  * Created on 2009年7月27日, 上午9:41
6  */
7
8 #include <stdlib.h>
9 #include <string.h>
10 #include <iostream>
11 #include <string>
12 #include <vector>
13 #include <map>
14 #include <queue>
15 #include <algorithm>
16 using namespace std;
17 const int MAX=1100;
18 struct node{
19     int x,y;
20 }data[MAX*MAX];
21 int n,m;
22 long long seg[MAX];
23 bool cmp(node a, node b)
24 {
25     return a.x<b.x||a.x==b.x&&a.y<b.y;
26 }
27 /*
28  *
29  */
30 int lowbit(int x)
31 {
32     return x^(x&(x-1));
33 }
34
35 int add(int x,int d)
36 {
37     while(x<=m)
38     {
39         seg[x]+=d;
40         x+=lowbit(x);
41     }
42     return 0;
43 }
44
45 long long sum(int x)
46 {
47     long long ans=0;
48     while(x>0)
49     {
50         ans+=seg[x];
51         x-=lowbit(x);
52     }
53     return ans;
54 }
55
56 int main() {
57     int kase;
58     int k,l;
59     scanf("%d",&kase);
60     for(k=1;k<=kase;k++){
61         scanf("%d%d%d",&n,&m,&l);
62         for(int i=0;i<l;++i)
63             scanf("%d%d",&data[i].x,&data[i].y);
64         sort(data,data+l,cmp);
65         memset(seg,0,sizeof(seg));
66         long long ans=0;
67         for(int i=0;i<l;++i)
68         {
69             add(data[i].y,1);
70             ans+=sum(m)-sum(data[i].y);
71         }
72         printf("Test case %d: %lld\n",k,ans);
73     }
74     return 0;
75 }
76

gong 2009-07-27 16:00 发表评论

TOJ 2551 Stargates

gong — Mon, 27 Jul 2009 07:58:00 GMT

1 /*
2  * File:   F.cpp
3  * Author: GongZhi
4  *
5  * Created on 2009年7月27日, 下午12:19
6  */
7
8 #include <stdlib.h>
9 #include <string.h>
10 #include <stdio.h>
11 /*
12  *
13  */
14 const int MAX = 6100000;
15 int uset[MAX];
16 int n;
17 int root(int k) {
18     int t = k;
19     while (uset[t] != t)
20         t = uset[t];
21     while (uset[k] != k) {
22         int p = uset[k];
23         uset[k] = t;
24         k = p;
25     }
26     return uset[k];
27 }
28
29 int init(int n) {
30     for (int i = 0; i <= n; ++i)
31         uset[i] = i;
32     return 0;
33 }
34
35 int query(int src, int dst, int ss, int ds, int nnn) {
36     int ans=0;
37     for (int i = 0; src<=n && dst<=n && i < nnn; ++i) {
38         int a = root(src);
39         int b = root(dst);
40         if (a == b)
41             ++ans;
42         src += ss;
43         dst += ds;
44     }
45     printf("%d - %d\n", ans, nnn - ans);
46     return 0;
47 }
48
49 int join(int src, int dst, int ss, int ds, int nnn) {
50     int ans = 0;
51     for (int i = 0; src<=n && dst<=n && i < nnn; ++i) {
52         int a = src;//root(src);
53         int b = root(dst);
54         uset[b] = a;
55         src += ss;
56         dst += ds;
57     }
58     return 0;
59 }
60
61 int get(char* s)
62 {
63     int i=0;
64     char c;
65     while(true)
66     {
67         c=getchar();
68         if(c==-1)return -1;
69         if(c=='\n')break;
70         s[i]=c;
71         ++i;
72     }
73     s[i]=0;
74     return 1;
75 }
76
77 int main(int argc, char** argv) {
78     char line[1024];
79     //freopen("in.txt","r",stdin);
80     while (gets(line)!=NULL) {
81         int src = 0, dst = 0;
82         int nnn = 1, ss = 0, ds = 1;
83         char tmp[100];
84         if (line[0] == 'D' || line[0] == 'd') {
85             sscanf(line, "%s%d", tmp, &n);
86             init(n);
87         } else {
88             int i;
89             sscanf(line,"%s%d%d%d%d%d",tmp,&src,&dst,&nnn,&ds,&ss);
90             if (line[0] == 'Q' || line[0] == 'q')
91                 query(src, dst, ss, ds, nnn);
92             else
93                 join(src, dst, ss, ds, nnn);
94         }
95     }
96     return (EXIT_SUCCESS);
97 }
98

gong 2009-07-27 15:58 发表评论

TOJ 2549 Sherlock Holmes

gong — Mon, 27 Jul 2009 07:54:00 GMT

1 /*
2  * File:   D.cpp
3  * Author: GongZhi
4  * Problem:
5  * Created on 2009年7月27日, 上午10:00
6  */
7
8 #include <stdlib.h>
9 #include <string.h>
10 #include <iostream>
11 #include <string>
12 #include <vector>
13 #include <map>
14 #include <queue>
15 using namespace std;
16
17 /*
18  *
19  */
20 int data[2][11000];
21
22 int main() {
23     srand(time(NULL));
24     int n, m, i, f, k, p, j;
25     int t0, t1;
26     int t, sumt;
27     int sum0, sum1;
28     double ans;
29     while (scanf("%d%d", &n, &m) != EOF) {
30         sum0 = 0;
31         sum1 = 0;
32         for (i = 0; i < n; i++) {
33             scanf("%d%d", &data[0][i], &data[1][i]);
34             sum0 += data[0][i];
35             sum1 += data[1][i];
36         }
37         if (sum0 > sum1)f = 0;
38         else f = 1;
39         p = n / 2;
40         sum0 = 0;
41         sum1 = 0;
42         for (i = 0; i < p; i++)sum0 += data[f][i];
43         for (i = p; i < n; i++)sum1 += data[f][i];
44         sumt = sum0 - sum1;
45         if (sumt < 0)sumt = -sumt;
46         //    printf("%d %d %d\n",sum0,sum1,sumt);
47         for (k = 0; k <= 1000000; k++) {
48             i = rand() % p;
49             j = rand() % p + p;
50             t0 = sum0 - data[f][i] + data[f][j];
51             t1 = sum1 + data[f][i] - data[f][j];
52             t = t0 - t1;
53             if (t < 0)t = -t;
54             sumt = sum0 - sum1;
55             if (sumt < 0)sumt = -sumt;
56             if (t < sumt) {
57                 sumt = t;
58                 sum0 = t0;
59                 sum1 = t1;
60                 t = data[f][i];
61                 data[f][i] = data[f][j];
62                 data[f][j] = t;
63             }
64         }
65         if (sum0 < sum1)sumt = sum0;
66         else sumt = sum1;
67         //    printf("%d\n",sumt);
68         if (2 * sumt <= p * m)printf("No solution\n");
69         else {
70             if (!f)printf("W ");
71             else printf("B ");
72             ans = ((double) (sumt * 100.0)) / (p * m);
73             printf("%.2f\n", ans);
74         }
75     }
76     return 0;
77 }
78
79
80

gong 2009-07-27 15:54 发表评论

TOJ 2547 Subsequence

gong — Mon, 27 Jul 2009 07:52:00 GMT

1 /*
2  * File:   B.cpp
3  * Author: GongZhi
4  * Problem:
5  * Created on 2009年7月27日, 上午9:07
6  */
7
8 #include <stdlib.h>
9 #include <string.h>
10 #include <iostream>
11 #include <string>
12 #include <vector>
13 #include <map>
14 #include <queue>
15 using namespace std;
16
17 /*
18  *
19  */
20 int a[110000];
21
22 int main() {
23     int i, j,t,ans;
24     int n, s;
25     int kase;
26     scanf("%d",&kase);
27     while (kase--) {
28         scanf("%d%d", &n, &s);
29         ans=n+1;
30         for (i = 0; i < n; i++)scanf("%d", &a[i]);
31         i=0;j=0;t=0;
32         while(j<n){
33             t+=a[j++];
34             while(i<=j && t-a[i]>=s){
35                 t-=a[i];
36                 i++;
37             }
38             if(t>=s && j-i<ans)ans=j-i;
39         }
40         if(ans==n+1)printf("0\n");
41         else printf("%d\n",ans);
42     }
43     return 0;
44 }
45

gong 2009-07-27 15:52 发表评论

uva :: Programming Challenges :: Chapter 2

gong — Sun, 26 Jul 2009 17:17:00 GMT

1 /*
2  * File:   10038.cpp
3  * Author: GongZhi
4  * Problem: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=30&page=show_problem&problem=979
5  * Created on 2009年7月27日, 上午1:10
6  */
7
8 #include <stdlib.h>
9 #include <string.h>
10 #include <iostream>
11 #include <string>
12 #include <vector>
13 #include <map>
14 #include <queue>
15 using namespace std;
16
17 /*
18  *
19  */
20 int a[4000];
21 char mark[4000];
22
23 int main() {
24     int n, i, t, f;
25     while (scanf("%d", &n) != EOF) {
26         f = 1;
27         for (i = 0; i < n; i++)scanf("%d", &a[i]);
28         memset(mark, 0, sizeof (mark));
29         for (i = 1; i < n; i++) {
30             t = a[i] - a[i - 1];
31             if (t < 0)t = -t;
32             if (t >= n)f = 0;
33             if (!f)break;
34             if(mark[t])f=0;
35             mark[t]=1;
36             if (!f)break;
37         }
38         if(f)printf("Jolly\n");
39         else printf("Not jolly\n");
40     }
41     return 0;
42 }
43
44

gong 2009-07-27 01:17 发表评论

PKU 1160 Post Office

gong — Sun, 26 Jul 2009 16:56:00 GMT

1/*
2 * File:   1160.cpp
3 * Author: GongZhi
4 * Problem: 动态规划四边形优化
5 * Created on 2009年7月27日, 上午12:00
6 */
7
8#include <stdlib.h>
9#include <string.h>
10#include <iostream>
11#include <string>
12#include <vector>
13#include <map>
14#include <queue>
15using namespace std;
16
17/*
18 *
19 */
20#define MAXN 2000
21int a[MAXN], sum[MAXN], f[MAXN][MAXN], w[MAXN][MAXN], p[MAXN][MAXN];
22
23int main() {
24    int n, m, i, j, t, k;
25    scanf("%d%d", &n, &m);
26    for (i = 1; i <= n; i++)scanf("%d", &a[i]);
27    sum[0] = 0;
28    for (i = 1; i <= n; i++)sum[i] = sum[i - 1] + a[i];
29    for (i = 1; i <= n; i++)
30        for (j = 1; j <= n; j++) {
31            t = (i + j) / 2;
32            w[i][j] = (t - i + 1) * a[t]-(sum[t] - sum[i - 1]) +(sum[j] - sum[t - 1])-(j - t + 1) * a[t];
33        }
34    for (i = 1; i <= n; i++) {
35        f[1][i] = w[1][i];
36        p[1][i] = 1;
37    }
38    for (i = 2; i <= m; i++) {
39        j = n;
40        f[i][j] = 1000000000;
41        for (k = p[i - 1][j]; k <= j - 1; k++)
42            if (f[i - 1][k] + w[k + 1][j] < f[i][j]) {
43                f[i][j] = f[i - 1][k] + w[k + 1][j];
44                p[i][j] = k;
45            }
46        for (j = n - 1; j >= 1; j--) {
47            f[i][j] = 1000000000;
48            for (k = p[i - 1][j]; k <= p[i][j+1]; k++)
49                if (f[i - 1][k] + w[k + 1][j] < f[i][j]) {
50                    f[i][j] = f[i - 1][k] + w[k + 1][j];
51                    p[i][j] = k;
52                }
53        }
54    }
55    printf("%d\n",f[m][n]);
56    return 0;
57}
58
59
60

gong 2009-07-27 00:56 发表评论

Toj Lawrence of Arabia 四边形不等式优化

gong — Sun, 26 Jul 2009 16:44:00 GMT

1 /*
2  * File:   Toj 3305.cpp
3  * Author: GongZhi
4  * Problem: 动态规划，四边形不等式优化
5  * Created on 2009年7月27日, 上午12:00
6  */
7
8 #include <stdlib.h>
9 #include <string.h>
10 #include <iostream>
11 #include <string>
12 #include <vector>
13 #include <map>
14 #include <queue>
15 using namespace std;
16
17 /*
18  *
19  */
20 #define MAXN 1100
21 long long a[MAXN], sum1[MAXN], sum2[MAXN], f[MAXN][MAXN], w[MAXN][MAXN], p[MAXN][MAXN];
22
23 int main() {
24     int n, m, i, j, t, k;
25     while (scanf("%d%d", &n, &m), n) {
26         m++;
27         for (i = 1; i <= n; i++)scanf("%d", &a[i]);
28         sum1[0] = 0;
29         sum2[0] = 0;
30         for (i = 1; i <= n; i++)sum1[i] = sum1[i - 1] + a[i];
31         for (i = 1; i <= n; i++)sum2[i] = sum2[i - 1] + a[i] * a[i];
32         for (i = 1; i <= n; i++)
33             for (j = 1; j <= n; j++)w[i][j] = ((sum1[j] - sum1[i - 1])*(sum1[j] - sum1[i - 1])-(sum2[j] - sum2[i - 1])) / 2;
34         for (i = 1; i <= n; i++) {
35             f[1][i] = w[1][i];
36             p[1][i] = 1;
37         }
38         for (i = 2; i <= m; i++) {
39             j = n;
40             f[i][j] = 100000000000000ll;
41             for (k = p[i - 1][j]; k <= j - 1; k++)
42                 if (f[i - 1][k] + w[k + 1][j] < f[i][j]) {
43                     f[i][j] = f[i - 1][k] + w[k + 1][j];
44                     p[i][j] = k;
45                 }
46             for (j = n - 1; j >= 1; j--) {
47                 f[i][j] = 100000000000000ll;
48                 for (k = p[i - 1][j]; k <= p[i][j + 1]; k++)
49                     if (f[i - 1][k] + w[k + 1][j] < f[i][j]) {
50                         f[i][j] = f[i - 1][k] + w[k + 1][j];
51                         p[i][j] = k;
52                     }
53             }
54         }
55         printf("%d\n", f[m][n]);
56     }
57     return 0;
58 }
59
60

gong 2009-07-27 00:44 发表评论

uva :: Programming Challenges :: Chapter 1 :: 706 - LCD Display

gong — Sat, 25 Jul 2009 14:35:00 GMT

  1 /*
  2  * File:   706.cpp
  3  * Author: GongZhi
  4  * Problem: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=29&page=show_problem&problem=647
  5  * Created on 2009年7月25日, 下午10:08
  6  */
  7
  8 #include <stdlib.h>
  9 #include <string.h>
10 #include <iostream>
11 #include <string>
12 #include <vector>
13 #include <map>
14 #include <queue>
15 using namespace std;
16
17 /*
18  *
19  */
20
21 //下面为0~9字符表示
22 int P[10][7] = {
23     {1, 1, 1, 0, 1, 1, 1},
24     {0, 0, 1, 0, 0, 1, 0},
25     {1, 0, 1, 1, 1, 0, 1},
26     {1, 0, 1, 1, 0, 1, 1},
27     {0, 1, 1, 1, 0, 1, 0},
28     {1, 1, 0, 1, 0, 1, 1},
29     {1, 1, 0, 1, 1, 1, 1},
30     {1, 0, 1, 0, 0, 1, 0},
31     {1, 1, 1, 1, 1, 1, 1},
32     {1, 1, 1, 1, 0, 1, 1}
33 };
34
35 int main() {
36     int s, i, j, l, k;
37     char n[100];
38     while (scanf("%d%s", &s, n), s) {
39         l = strlen(n);
40         for (i = 0; i < l; i++)n[i] -= '0';
41         //0
42         for (i = 0; i < l; i++) {
43             if (i != 0)printf(" ");
44             printf(" ");
45             for (j = 0; j < s; j++)
46                 if (P[n[i]][0])printf("-");
47                 else printf(" ");
48             printf(" ");
49         }
50         printf("\n");
51         //1&2
52         for (k = 0; k < s; k++) {
53             for (i = 0; i < l; i++) {
54                 if (i != 0)printf(" ");
55                 if (P[n[i]][1])printf("|");
56                 else printf(" ");
57                 for (j = 0; j < s; j++)printf(" ");
58                 if (P[n[i]][2])printf("|");
59                 else printf(" ");
60             }
61             printf("\n");
62         }
63         //3
64         for (i = 0; i < l; i++) {
65             if (i != 0)printf(" ");
66             printf(" ");
67             for (j = 0; j < s; j++)
68                 if (P[n[i]][3])printf("-");
69                 else printf(" ");
70             printf(" ");
71         }
72         printf("\n");
73         //4&5
74         for (k = 0; k < s; k++) {
75             for (i = 0; i < l; i++) {
76                 if (i != 0)printf(" ");
77                 if (P[n[i]][4])printf("|");
78                 else printf(" ");
79                 for (j = 0; j < s; j++)printf(" ");
80                 if (P[n[i]][5])printf("|");
81                 else printf(" ");
82             }
83             printf("\n");
84         }
85         //6
86         for (i = 0; i < l; i++) {
87             if (i != 0)printf(" ");
88             printf(" ");
89             for (j = 0; j < s; j++)
90                 if (P[n[i]][6])printf("-");
91                 else printf(" ");
92             printf(" ");
93         }
94         printf("\n");
95         //因为没加下面这个居然wa了一次
96         printf("\n");
97     }
98
99     return 0;
100 }
101
102

gong 2009-07-25 22:35 发表评论

uva :: Programming Challenges :: Chapter 1-10137 - The Trip

gong — Sat, 25 Jul 2009 13:57:00 GMT

1 /*
2  * File:   10137.cpp
3  * Author: GongZhi
4  * Problem: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=29&page=show_problem&problem=1078
5  * Created on 2009年7月25日, 下午9:29
6  */
7
8 #include <stdlib.h>
9 #include <string.h>
10 #include <iostream>
11 #include <string>
12 #include <vector>
13 #include <map>
14 #include <queue>
15 using namespace std;
16
17 /*
18  *
19  */
20 double data[2000];
21 char temp[100];
22 int main() {
23     int n,i;
24     double t,ans1,ans2;
25     while(scanf("%d",&n),n){
26         t=0;
27         for(i=0;i<n;i++){
28             scanf("%lf",&data[i]);
29             t+=data[i];
30         }
31         t/=n;
32         sprintf(temp,"%.2f",t);
33         sscanf(temp,"%lf",&t);
34         ans1=0;ans2=0;
35         for(i=0;i<n;i++)
36             if(t>data[i])ans1=ans1+t-data[i];
37             else ans2=ans2-t+data[i];
38         if(ans1<ans2)printf("$%.2f\n",ans1);
39         else printf("$%.2f\n",ans2);
40     }
41     return 0;
42 }
43
44

gong 2009-07-25 21:57 发表评论

uva :: Programming Challenges :: Chapter 1-10189 - Minesweeper

gong — Sat, 25 Jul 2009 13:55:00 GMT

1 /*
2  * File:   10189.cpp
3  * Author: GongZhi
4  * Problem: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=29&page=show_problem&problem=1130
5  * Created on 2009年7月25日, 下午9:08
6  */
7
8 #include <stdlib.h>
9 #include <string.h>
10 #include <iostream>
11 #include <string>
12 #include <vector>
13 #include <map>
14 #include <queue>
15 using namespace std;
16
17 /*
18  *
19  */
20 char ans[200][200];
21 int P[8][2] = {
22     {0, 1},
23     {0, -1},
24     {1, 0},
25     {-1, 0},
26     {1, -1},
27     {1, 1},
28     {-1, 1},
29     {-1, -1}
30 };
31
32 int main() {
33     int n, m, i, j, k, t,kase=1;
34     while (scanf("%d%d", &n, &m), n) {
35         for (i = 0; i < n; i++)scanf("%s", ans[i]);
36         for (i = 0; i < n; i++)
37             for (j = 0; j < m; j++) {
38                 if (ans[i][j] == '*')continue;
39                 t = 0;
40                 for (k = 0; k < 8; k++)
41                     if (i + P[k][0] >= 0 && i + P[k][0] < n && j + P[k][1] >= 0 && j + P[k][1] < m && ans[i + P[k][0]][j + P[k][1]] == '*')t++;
42                 ans[i][j] = '0' + t;
43             }
44             if(kase!=1)printf("\n");
45             printf("Field #%d:\n",kase++);
46             for(i=0;i<n;i++)printf("%s\n",ans[i]);
47     }
48     return 0;
49 }

gong 2009-07-25 21:55 发表评论