2009年7月27日

TOJ 2553 Japan

 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 

posted @ 2009-07-27 16:00 gong 阅读(1044) | 评论 (1)编辑 收藏

TOJ 2551 Stargates

 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<=&& dst<=&& 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<=&& dst<=&& 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 

posted @ 2009-07-27 15:58 gong 阅读(837) | 评论 (1)编辑 收藏

TOJ 2549 Sherlock Holmes

 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("");
71             else printf("");
72             ans = ((double) (sumt * 100.0)) / (p * m);
73             printf("%.2f\n", ans);
74         }
75     }
76     return 0;
77 }
78 
79 
80 

posted @ 2009-07-27 15:54 gong 阅读(903) | 评论 (0)编辑 收藏

TOJ 2547 Subsequence

 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<=&& t-a[i]>=s){
35                 t-=a[i];
36                 i++;
37             }
38             if(t>=&& 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 

posted @ 2009-07-27 15:52 gong 阅读(882) | 评论 (1)编辑 收藏

uva :: Programming Challenges :: Chapter 2

 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, 0sizeof (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 

posted @ 2009-07-27 01:17 gong 阅读(1001) | 评论 (0)编辑 收藏

PKU 1160 Post Office

 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

posted @ 2009-07-27 00:56 gong 阅读(1143) | 评论 (1)编辑 收藏

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

 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 

posted @ 2009-07-27 00:44 gong 阅读(1434) | 评论 (4)编辑 收藏

2009年7月25日

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

  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     {1110111},
 24     {0010010},
 25     {1011101},
 26     {1011011},
 27     {0111010},
 28     {1101011},
 29     {1101111},
 30     {1010010},
 31     {1111111},
 32     {1111011}
 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 

posted @ 2009-07-25 22:35 gong 阅读(803) | 评论 (0)编辑 收藏

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

 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 

posted @ 2009-07-25 21:57 gong 阅读(1092) | 评论 (0)编辑 收藏

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

 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     {01},
23     {0-1},
24     {10},
25     {-10},
26     {1-1},
27     {11},
28     {-11},
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 }

posted @ 2009-07-25 21:55 gong 阅读(828) | 评论 (1)编辑 收藏

仅列出标题  下一页
<2019年7月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

导航

统计

常用链接

留言簿(6)

随笔档案

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜