剩余定理，讀題廢了好長時間，看完題，又看了一遍算法段輪的31.5
1
#include<stdio.h>
2#define N 21252
3typedef struct node{
4 int d;
5 int x;
6 int y;
7void operator=(node b)
8{
9 d=b.d;
10 x=b.x;
11 y=b.y;
12}}NODE;
13NODE EXTENDED_EUCLID(int a,int b)
14{
15 NODE first,sec;
16 if(b==0){
17 sec.d=a;
18 sec.x=1;
19 sec.y=0;
20 return sec;
21 }
22 first=EXTENDED_EUCLID(b,a%b);
23 sec.d=first.d;
24 sec.x=first.y;
25 sec.y=first.x-(a/b)*first.y;
26 return sec;
27}
28int main()
29{
30 int a,c1,c2,c3,j=1;
31 int p,e,i,d;
32 NODE m1,m2,m3;
33 m1= EXTENDED_EUCLID(28*33,23);
34 m2= EXTENDED_EUCLID(23*33,28);
35 m3= EXTENDED_EUCLID(23*28,33);
36 c1=28*33*m1.x;
37 c2=23*33*(m2.x+28);
38 c3=23*28*m3.x;
39 while(scanf("%d%d%d%d",&p,&e,&i,&d)){
40 if(p==-1&&e==-1&&i==-1&&d==-1)break;
41 a=(p*c1+e*c2+i*c3-d+N)%N;
42 if(!a)a=N;
43 printf("Case %d: the next triple peak occurs in %d days.\n",j++,a);
44 }
45 return 0;
46}
前27行都是用來求c1,c2,c3的，真正這道題的數據處理只是在main函數的while循環
posted @
2008-02-23 11:20 zoyi 閱讀(562) |
評論 (0) |
編輯 收藏
在我還有一口氣的時候他終于過了........
1#include<iostream>
2#define MaxN 50000
3typedef struct {
4 int parent;
5 int rank;
6 int food;//指向食物類
7 int enemy;//指向天敵類
8}NODE;
9NODE animal[MaxN+1];
10void init(int n)
11{
12 int i;
13 for(i=1;i<=n;i++){
14 animal[i].parent=i;
15 animal[i].rank=0;
16 animal[i].food=-1;
17 animal[i].enemy=-1;
18 }
19}
20int find_set(int x)
21{
22 if(x==-1)return -1;//有些food，enemy指向-1
23 if(animal[x].parent!=x)
24 animal[x].parent=find_set(animal[x].parent);
25 return animal[x].parent;
26}
27int union_set(int x,int y)
28{
29 if(x==-1)return y;
30 if(y==-1)return x;
31 if(animal[x].rank>animal[y].rank){
32 animal[y].parent=x;
33 return x;}
34 else {
35 animal[x].parent=y;
36 if(animal[x].rank==animal[y].rank)animal[y].rank++;
37 return y;}
38}
39void make(int x,int y,int fx,int fy,int ex,int ey)//創建x吃y的關系
40{
41 int t,v,w;
42 t=union_set(fx,y);//首先將y與x的food合并
43 v=union_set(x,ey);
44 w=union_set(ex,fy);
45 animal[v].enemy=w;
46 animal[v].food=t;
47 animal[t].enemy=v;
48 animal[t].food=w;
49 if(w!=-1){
50 animal[w].food=v;
51 animal[w].enemy=t;}
52}
53int main()
54{
55 int N,K,i,wn=0,x,y,fx,fy,ex,ey,oper;
56 int t,u,v;
57 scanf("%d%d",&N,&K);
58 init(N);
59 for(i=1;i<=K;i++){
60 scanf("%d%d%d",&oper,&x,&y);//oper為1的時候表示x和y是同類，oper為2的時候表示x吃y
61 if(x>N||y>N){wn++;continue;}
62 x=find_set(x);
63 y=find_set(y);
64 fx=find_set(animal[x].food);//fx可能是-1
65 fy=find_set(animal[y].food);//fy也可能是-1
66 ex=find_set(animal[x].enemy);
67 ey=find_set(animal[y].enemy);
68 if(x==y){if(oper==2)wn++;continue;}//1.x,y同類
69 if(fy==x){wn++;continue;}//3.y吃x
70 if(fx==y){if(oper==1)wn++;continue;}//2.x吃y
71 if(oper==2)make(x,y,fx,fy,ex,ey);//4..x和y尚未產生聯系,創建聯系，首先是x吃y，其次y的food類吃x
72 if(oper==1){//4..x和y尚未產生聯系,創建聯系
73 t=union_set(x,y);
74 u=union_set(fx,fy);
75 v=union_set(ex,ey);
76 animal[t].food=u;
77 animal[t].enemy=v;
78 if(u!=-1){
79 animal[u].enemy=t;
80 animal[u].food=v;}
81 if(v!=-1){
82 animal[v].food=t;
83 animal[v].enemy=u;}}
84 }
85 printf("%d\n",wn);
86 return 0;
87}
if(u!=-1)if(v!=-1)這里折騰了我兩天
posted @
2008-01-31 20:39 zoyi 閱讀(1517) |
評論 (5) |
編輯 收藏
螞蟻..........
posted @
2008-01-27 23:42 zoyi 閱讀(100) |
評論 (0) |
編輯 收藏 1#include<iostream>
2#define MaxN 30000
3typedef struct node{
4 int count;
5 int parent;
6 int d;
7}NODE;
8NODE S[MaxN+1];
9void init()
10{
11 for(int i=1;i<=MaxN;i++){
12 S[i].count=1;
13 S[i].d=0;
14 S[i].parent=i;}
15}
16int find_set(int x)
17{
18 int t=S[x].parent;
19 if(S[x].parent!=x){
20 S[x].parent=find_set(S[x].parent);
21 S[x].d+=S[t].d;
22 }
23 return S[x].parent;
24}
25void union_set(int x,int y)
26{
27 x=find_set(x);
28 y=find_set(y);
29 S[y].parent=x;
30 S[y].d=S[x].count;
31 S[x].count+=S[y].count;
32}
33int main()
34{
35 int P,x,y;
36 char c;
37 init();
38 scanf("%d",&P);
39 getchar();
40 while(P>0){
41 P--;
42 c=getchar();
43 if(c=='M'){
44 scanf("%d%d",&x,&y);
45 union_set(x,y);
46 }
47 else {
48 scanf("%d",&x);
49 y=find_set(x);
50 printf("%d\n",S[y].count-S[x].d-1);
51 }
52 getchar();
53 }
54 return 0;
55}
http://acm.pku.edu.cn/JudgeOnline/problem?id=1988
posted @
2008-01-27 22:48 zoyi 閱讀(377) |
評論 (0) |
編輯 收藏
摘要: 其實很不好意思的說，這道題我的方法肯定不大好，非常的慢，需400多ms但是再怎么說也是好不容易寫出來的這道題的轉換方法很巧妙要不是上網搜出來的，我肯定不敢相信這是用并查集做主要是把區間化為單個數的想法來做這一點的處理我是用cube stacking同樣的想法來做的還有一點，離散化，這是基本上資料對這題的所要求的一點，這一點我不大懂這一題確實有個很大的特點，10億的數據，只有5000個操作離散化，還...
閱讀全文
posted @
2008-01-27 22:26 zoyi 閱讀(257) |
評論 (0) |
編輯 收藏
1 //并查集
2 #include<iostream>
3 #define MaxN 100000
4 typedef struct{
5 int fparent;
6 int frank;
7 int others;
8 }NODE;
9 NODE S[MaxN+1];
10 void init(int n)
11 {
12 for(int i=1;i<=n;i++){
13 S[i].fparent=i;
14 S[i].frank=0;
15 S[i].others=-1;
16 }
17 }
18 int find_set(int x)
19 {
20 if(x==-1)return -1;
21 if(S[x].fparent!=x)
22 S[x].fparent=find_set(S[x].fparent);
23 return S[x].fparent;
24 }
25 int union_set(int x,int y)
26 {
27 if(x==-1)return y;
28 if(y==-1)return x;
29 if(S[x].frank>S[y].frank)
30 {
31 S[y].fparent=x;
32 return x;
33 }
34 else {
35 S[x].fparent=y;
36 if(S[x].frank==S[y].frank)
37 S[y].frank++;
38 return y;
39 }
40 }
41 void make(int x,int y)//x is the enemy of y
42 {
43 int tx,ty;
44 x=find_set(x);
45 y=find_set(y);
46 tx=union_set(S[x].others,y);//這是x敵人團伙的合并，也是y朋友團伙的合并，對于ｙ來說x的敵人也是y的朋友
47 //tx是x敵人團伙合并后新的頭,y朋友團伙合并后新的頭
48 ty=union_set(x,S[y].others);//這是y敵人團伙的合并，也是x朋友團伙的合并,對于x來說y的敵人也是x的朋友
49 //ty是y敵人團伙合并后新的頭,x朋友團伙合并后新的頭
50 S[tx].others=ty;//注意union_set返回的永遠是頭
51 S[ty].others=tx;
52 }
53 int main()
54 {
55 int T,N,M,i,p,q;
56 char X;
57 scanf("%d",&T);
58 while(T>0){
59 T--;
60 scanf("%d%d",&N,&M);
61 getchar();
62 init(N);
63 for(i=0;i<M;i++){
64 scanf("%c %d %d",&X,&p,&q);
65 getchar();
66 if(X=='A'){
67 p=find_set(p);
68 q=find_set(q);
69 if(p==q)printf("In the same gang.\n");
70 else if(p==S[q].others)printf("In different gangs.\n");
71 else printf("Not sure yet.\n");}
72 else if(X=='D')
73 make(p,q);
74 }
75 }
76 return 0;
77 }
http://acm.pku.edu.cn/JudgeOnline/problem?id=1703
posted @
2008-01-27 15:55 zoyi 閱讀(465) |
評論 (0) |
編輯 收藏