|
|
今天簡單看了下并查集，關于優化什么的還沒有看。做了兩個簡單的題，先熟悉一下~ 并查集用來表示若干互不相交的集合，是一種樹狀的結構。 并查集有三個操作：初始化，合并，查詢。 其中在合并的時候，由于可能集合是一個偏的很厲害的樹，如果不加分類直接合并的話，每次查詢會相當浪費時間，所以 需要每次合并的時候將規模小的集合并到規模大的集合，并且隨時更新集合內元素的個數。 簡單的不優化的Union函數如下：
1 Union(int root1,int root2)
2 {
3 int t1,t2;
4 t1=find(root1);
5 t2=find(root2);
6 if(t1!=t2)
7 t1.father=t2;
8 return ;
9 }
優化后的Union函數如下：
1 void Union(int root1,int root2)
2 {
3 int t1,t2;
4 t1=find(root1);
5 t2=find(root2);
6 if(t1==t2) return ; //只有當兩個根節點的祖先不同才合并
7 if(t1!=t2){
8 if(a[t1].v<a[t2].v){ //將規模小的集合并到規模大的集合，同時集合元素個數增加
9 a[t1].father=t2;
10 a[t2].v+=a[t1].v;
11 }
12 else{
13 a[t2].father=t1;
14 a[t1].v+=a[t2].v;
15 }
16
17 }
18 }
先看一下最簡單的并查集的模板：
1 #include<stdio.h>
2 #define MAX 10002
3 int m,n;
4 struct type
5 {
6 int father,v; //father 表示根節點，v表示集合內元素個數
7 }a[MAX];
8 void initial(int n)
9 {
10 int i;
11 for(i=0;i<n;i++){
12 a[i].father=i; //初始化將集合節點標記為自己，元素個數為1
13 a[i].v=1;
14 }
15 }
16 int find(int n)
17 {
18 if(a[n].father!=n)
19 return find(a[n].father); //此處也可以寫為 while(a[n].father!=n) n=a[n].father;
20 return n;
21 }
22 void Union(int root1,int root2)
23 {
24 int t1,t2;
25 t1=find(root1);
26 t2=find(root2);
27 if(t1==t2) return ; //只有當兩個根節點的祖先不同才合并
28 if(t1!=t2){
29 if(a[t1].v<a[t2].v){ //將規模小的集合并到規模大的集合，同時集合元素個數增加
30 a[t1].father=t2;
31 a[t2].v+=a[t1].v;
32 }
33 else{
34 a[t2].father=t1;
35 a[t1].v+=a[t2].v;
36 }
37 }
38 }
39 int main()
40 {}
運用上邊的模板，就可以將TOJ 3499 AC掉了 題意大概是N個數，從0到N-1，有M個關系，最后問P和Q之間是否是關系。 Code：
1 #include<stdio.h>
2 #define MAX 10002
3 int m,n;
4 struct type
5 {
6 int father,v;
7 }a[MAX];
8 void initial(int n)
9 {
10 int i;
11 for(i=0;i<n;i++){
12 a[i].father=i;
13 a[i].v=1;
14 }
15 }
16 int find(int n)
17 {
18 if(a[n].father!=n)
19 return find(a[n].father);
20 return n;
21 }
22 void Union(int root1,int root2)
23 {
24 int t1,t2;
25 t1=find(root1);
26 t2=find(root2);
27 if(t1==t2) return ;
28 if(t1!=t2){
29 if(a[t1].v<a[t2].v){
30 a[t1].father=t2;
31 a[t2].v+=a[t1].v;
32 }
33 else{
34 a[t2].father=t1;
35 a[t1].v+=a[t2].v;
36 }
37 }
38 }
39 int main()
40 {
41 int cas,i,j,k,p,q,N,M;
42 while(scanf("%d%d%d",&N,&M,&k)!=EOF){
43 initial(N);
44 for(i=0;i<M;i++){
45 scanf("%d%d",&p,&q);
46 Union(p,q);
47 }
48 for(i=1;i<=k;i++){
49 scanf("%d%d",&p,&q);
50 if(find(p)==find(q))
51 printf("YES\n");
52 else printf("NO\n");
53 }
54 }
55 }
簡單的DP,很好想。但是我第一次又給做成了貪心···相當無奈，不知道什么時候才能分清貪心和DP的區別。
初始化很重要，讓我WA了N次。
dp[i][j]表示第 i天在 city j 所能得到的最大income。
所以有轉移方程：
dp[i][j] = max{ dp[i-1][j]-pay[j][j]+income[i-1][j] ,dp[i-1][k]-pay[k][j]+income[i-1][j]};
其中1<k<=n (dp[1][i]單獨初始化)
Code:
1 #include<iostream>
2 #define MAX 120
3 using namespace std;
4 int m,n,dp[MAX][MAX];
5 int pay[MAX][MAX],income[MAX][MAX];
6 int main()
7 {
8 int i,j,k,temp,mm;
9 while(cin>>n>>m){
10 if(m==0&&n==0) break;
11 mm=-1000000;
12 for(i=1;i<=n;i++)
13 for(j=1;j<=n;j++)
14 cin>>pay[i][j];
15 for(i=1;i<=m;i++)
16 for(j=1;j<=n;j++)
17 cin>>income[i][j];
18 dp[0][1]=0;
19 for(i=1;i<=n;i++)
20 dp[1][i]=income[1][i]-pay[1][i];
21 for(i=2;i<=m;i++)
22 for(j=1;j<=n;j++){
23 temp=dp[i][j]=dp[i-1][j]-pay[j][j]+income[i][j];
24 for(k=1;k<=n;k++)
25 if(temp<dp[i-1][k]-pay[k][j]+income[i][j]){
26 dp[i][j]=dp[i-1][k]-pay[k][j]+income[i][j];
27 temp=dp[i][j];
28 }
29 }
30
31 for(i=1;i<=n;i++)
32 if(dp[m][i]>mm)
33 mm=dp[m][i];
34 cout<<mm<<endl;
35 }
36
37 }
高精度除法和加法。Code：
1 #include<iostream>
2 #include<cstring>
3 using namespace std;
4 int main()
5 {
6 int a[20][60];
7 int i,j,k,m,n;
8 for(i=0;i<60;i++)
9 a[0][i]=0;
10 a[0][0]=1; //初始化a[0]=1000000000000000000000
11 k=0;
12 for(i=1;i<20;i++)
13 for(j=0;j<60;j++)
14 {
15 a[i][j]=(a[i-1][j]+10*k)/8;
16 k=(a[i-1][j]+10*k)%8; //k是上一位的進位，其中a[i-1][j]+10*k是i-1的數
17 }
18 char p[20];
19 int len,key,di[20],re[60];
20 while(cin>>p)
21 {
22 if(strlen(p)==1&&p[0]=='0')
23 cout<<p<<" [8] = 0 [10]"<<endl;
24 else if(strlen(p)==1&&p[0]=='1')
25 cout<<p<<" [8] = 1 [10]"<<endl;
26 else{
27 memset(re,0,sizeof(re));
28 memset(di,0,sizeof(di));
29 len=strlen(p);
30 for(i=0;i<len;i++)
31 if(p[i]=='.')
32 {
33 key=i+1;
34 break;
35 }
36 j=1;
37 for(i=key;i<len;i++)
38 di[j++]=p[i]-'0';
39 for(i=1;i<j;i++)
40 {
41 for(k=0;k<60;k++)
42 re[k]+=di[i]*a[i][k];
43 }
44 for(i=59;i>=0;i--)
45 if(re[i]>=10)
46 {
47 re[i-1]+=(re[i]/10);
48 re[i]%=10;
49 }
50 cout<<p<<" [8] = "<<"0.";
51 for(i=59;i>0;i--)
52 if(re[i]!=0)
53 {
54 for(k=i+1;k<60;k++)
55 re[k]=-1;
56 break;
57 } //把末尾的'0'標記為-1
58 for(i=1;i<60;i++)
59 {
60 if(re[i]==-1) break;
61 cout<<re[i];
62 }
63 cout<<" [10]"<<endl;
64 }
65 }
66 }
67
別人的思路，有點遞歸的意思。程序本身超時，但可以利用它來打表。
這個題目其實就是要求前k次踢掉的都是壞人，假設第i次踢掉的人是i，則i>k。根據題意，可以得到如下關系：
設 ai 是第i次踢掉的人在第i-1次踢掉后剩下的人中是第幾個。那么
a(n) = [a(n-1)+m-1]mod(2k-n+1)
要求a(n) > k；n = 1,2,3,...,k
其中2k-n+1是第i-1次踢人后剩下的人數
1 bool Joseph(int k, int m) // 這個算法確定對于給定的k,m是否滿足上面的要求
2 {
3 int n=0,a=1;
4 for(n=1;n<=k;n++)
5 {
6 a = (a+m-1)%(k*2-n+1);
7 if(a == 0) a = k*2-n+1;
8 if(a<=k && a>=1) return false;
9 }
10 return true;
11 }
Code:
1 #include<iostream>
2using namespace std;
3bool judge(int k,int m)
4  {
5 int i,j=1;
6 for(i=1;i<=k;i++)
7  {
8 j=(j+m-1)%(k*2+1-i);
9 if(j==0) j=k*2+1-i;
10 if((j<=k)&&(j>=1))
11 return false;
12 }
13 return true;
14 }
15int main()
16{
17 int k,m,i,j,n;
18 while(cin>>k)
19 {
20 if(k==0) break;
21 for(m=k+1;;m++)
22 {
23 if(judge(k,m))
24 {
25 cout<<m<<endl;
26 break;
27 }
28 }
29 }
30}
1 #include<iostream>
2 using namespace std;
3 int main()
4 {
5 int i;
6 while(scanf("%d",&i)!=EOF)
7 {
8 int j,k,m,n,temp,begin_new,begin,end,max=-100000,sum=0;
9 bool judge=true;
10 if(i==0) break;
11 for(j=1;j<=i;j++)
12 {
13 scanf("%d",&k);
14 if(k>=0) judge=false;
15 sum+=k;
16 if(k>sum)
17 {
18 begin_new=k;
19 sum=k;
20 }
21 if(sum>max)
22 {
23 begin=begin_new;
24 max=sum;
25 end=k;
26 if(j==1){begin=k;begin_new=k;}
27 begin=begin_new;
28 }
29 }
30 if(judge)printf("%c %d %d\n",'0',begin,k);
31 else printf("%d %d %d\n",max,begin,end);
32 }
33 }
34
有人用遞歸做，有人用DP做，我是參考了一個人的思路寫的代碼AC的。
大意是從后往前推，因為從前往后是不能得到全局最優解的，而從后就可以。
Code：
1 #include<iostream>
2
3 using namespace std;
4
5 int a[102][102];
6
7 int main()
8
9 {
10
11 int i,j,k;
12
13 cin>>i;
14
15 for(j=1;j<=i;j++)
16
17 for(k=1;k<=j;k++)
18
19 cin>>a[j][k];
20
21 for(j=i-1;j>=1;j--)
22
23 for(k=1;k<=j;k++)
24
25 {
26
27 if(a[j+1][k]>a[j+1][k+1])
28
29 a[j][k]+=a[j+1][k];
30
31 else
32
33 a[j][k]+=a[j+1][k+1];
34
35 }
36
37 cout<<a[1][1]<<endl;
38
39 }
40
先說一個定理：
若正整數n可分解為p1^a1*p1^a2*...*pk^ak
其中pi為兩兩不同的素數,ai為對應指數
n的約數個數為(1+a1)*(1+a2)*....*(1+ak)
如180=2*2*3*3*5=2^2*3^2*5
180的約數個數為(1+2)*(1+2)*(1+1)=18個。
若求A/B的約數個數，A可分解為p1^a1*p2^a2*...*pk^ak，B可分解為q1^b1*q1^b2*...*qk^bk,則A/B的約數個數 為(a1-b1+1)*(a2-b2+1)*(a3-b3+1)...*(ak-bk+1).
然后說N的階乘：
例如:20!
1.先求出20以內的素數,(2,3,5,7,11,13,17,19)
2.再求各個素數的階數
e(2)=[20/2]+[20/4]+[20/8]+[20/16]=18;
e(3)=[20/3]+[20/9]=8;
e(5)=[20/5]=4;
...
e(19)=[20/19]=1;
所以
20!=2^18*3^8*5^4*...*19^1
解釋：
2、4、6、8、10、12、14、16、18、20能被2整除
4、8、12、16、20能被4整除（即被2除一次后還能被2整除）
8、16能被8整除（即被2除兩次后還能被2整除）
16能被16整除（即被2除三次后還能被2整除）
這樣就得到了2的階。其它可以依次遞推。
所以在求N的階乘質數因數個數時，從最小的質數開始，
1 int cal(int n, int p) {
2 if(n < p) return 0;
3 else return n / p + cal(n / p, p);
4 }
其中P是質數，則該函數返回的就是N的階乘中可以表達成質數P的指數的最大值。原理如上。
TOJ 2308的AC代碼：
1 #include<iostream>
2
3 #include<cmath>
4
5 #define N 90
6
7 #define M 450
8
9 using namespace std;
10
11 int p[M+2]={0};
12
13 int prime[N+2],l,q,t=1; //求前90個素數
14
15 void getprime(int n)
16
17 {
18
19 for(l=2;l<n;l++)
20
21 {
22
23 if(!p[l])
24
25 {
26
27 for(q=l+l;q<n;q+=l)
28
29 {
30
31 p[q]=1;
32
33 }
34
35 prime[t]=l;t++;
36
37 }
38
39 }
40
41 }
42
43 int cal(int n,int m) //求N的階乘含質因數M的次數
44
45 {
46 if(m>n)
47
48 return 0;
49
50 else
51
52 return n/m+cal(n/m,m);
53
54 }
55 int main()
56 {
57 int i,j,k,n;
58
59 long long m;
60
61 getprime(M);
62
63 while(cin>>n>>k)
64
65 {
66 if(2*k>n) k=n-k;
67
68 for(i=1,m=1;prime[i]<=n,i<t;i++)
69
70 m*=(cal(n,prime[i])-cal(k,prime[i])-cal(n-k,prime[i])+1);
71
72 cout<<m<<endl;
73
74 }
75 }
是個關于拓展歐幾里得的問題，但是很難想到。這題也是看了結題報告的~~
關于拓展歐幾里得的算法http://mj-zhang.blogbus.com/tag/拓展歐幾里得/
大意是給N個瓶子，每個瓶子有個容量C，給定一個容量W，每次只能（1）灌滿一個，（2）倒空一個，（3）把一個的水倒給另一個，直到一個滿了或者一個空了。通過三種操作，有沒有可能最后達到某個瓶子里有W的水。可以這樣考慮：
1）當所有C都小于W，肯定不行；
2）如果有N個瓶子，N個瓶子的容量C1, C2, C3 ... Cn必然有個最大公約數P。
證明：假設n個水壺的容量分別為C1,C2,C3…..Cn.
必要性：不管執行三種操作的那一種，壺中所含的水一定是Ｐ的整數倍．
充分性：由歐幾里德算法擴展可知，必然存在整數A1,A2,A3…..An,使得
A1*C1+A2*C2+A3*C3+…+An*Cn=W.
如果Ai是正數，我們就用第i個壺從水源中取Ai次水；如果Ai為負數，我們就把第i個壺倒空Ai次，這樣最后必會剩下Ｗ升水
今天比較郁悶，什么都不說了。期中的高數，本來及格就很困難，加上這學期的狀態。。。。哎，整個兩個小時簡直就是煎熬啊。從下星期開始還是學學課程吧。。
|