剩余定理，读题废了好长时间，看完题，又看了一遍算法段轮的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 阅读(541) |
评论 (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 阅读(1504) |
评论 (5) |
编辑 收藏
蚂蚁..........
posted @
2008-01-27 23:42 zoyi 阅读(95) |
评论 (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 阅读(372) |
评论 (0) |
编辑 收藏
摘要: 其实很不好意思的说，这道题我的方法肯定不大好，非常的慢，需400多ms但是再怎么说也是好不容易写出来的这道题的转换方法很巧妙要不是上网搜出来的，我肯定不敢相信这是用并查集做主要是把区间化为单个数的想法来做这一点的处理我是用cube stacking同样的想法来做的还有一点，离散化，这是基本上资料对这题的所要求的一点，这一点我不大懂这一题确实有个很大的特点，10亿的数据，只有5000个操作离散化，还...
阅读全文
posted @
2008-01-27 22:26 zoyi 阅读(255) |
评论 (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 阅读(461) |
评论 (0) |
编辑 收藏