2009年7月27日
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
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
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
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
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
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
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
2009年7月25日
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
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
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 }