|
|
今天簡(jiǎn)單看了下并查集,關(guān)于優(yōu)化什么的還沒(méi)有看。做了兩個(gè)簡(jiǎn)單的題,先熟悉一下~ 并查集用來(lái)表示若干互不相交的集合,是一種樹(shù)狀的結(jié)構(gòu)。 并查集有三個(gè)操作:初始化,合并,查詢(xún)。 其中在合并的時(shí)候,由于可能集合是一個(gè)偏的很厲害的樹(shù),如果不加分類(lèi)直接合并的話(huà),每次查詢(xún)會(huì)相當(dāng)浪費(fèi)時(shí)間,所以 需要每次合并的時(shí)候?qū)⒁?guī)模小的集合并到規(guī)模大的集合,并且隨時(shí)更新集合內(nèi)元素的個(gè)數(shù)。 簡(jiǎn)單的不優(yōu)化的Union函數(shù)如下:
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 }
優(yōu)化后的Union函數(shù)如下:
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 ; //只有當(dāng)兩個(gè)根節(jié)點(diǎn)的祖先不同才合并 7 if(t1!=t2){ 8 if(a[t1].v<a[t2].v){ //將規(guī)模小的集合并到規(guī)模大的集合,同時(shí)集合元素個(gè)數(shù)增加 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 }
先看一下最簡(jiǎn)單的并查集的模板:
1 #include<stdio.h> 2 #define MAX 10002 3 int m,n; 4 struct type 5 { 6 int father,v; //father 表示根節(jié)點(diǎn),v表示集合內(nèi)元素個(gè)數(shù) 7 }a[MAX]; 8 void initial(int n) 9 { 10 int i; 11 for(i=0;i<n;i++){ 12 a[i].father=i; //初始化將集合節(jié)點(diǎn)標(biāo)記為自己,元素個(gè)數(shù)為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); //此處也可以寫(xiě)為 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 ; //只有當(dāng)兩個(gè)根節(jié)點(diǎn)的祖先不同才合并 28 if(t1!=t2){ 29 if(a[t1].v<a[t2].v){ //將規(guī)模小的集合并到規(guī)模大的集合,同時(shí)集合元素個(gè)數(shù)增加 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 {}
運(yùn)用上邊的模板,就可以將TOJ 3499 AC掉了 題意大概是N個(gè)數(shù),從0到N-1,有M個(gè)關(guān)系,最后問(wèn)P和Q之間是否是關(guān)系。 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 }
簡(jiǎn)單的DP,很好想。但是我第一次又給做成了貪心···相當(dāng)無(wú)奈,不知道什么時(shí)候才能分清貪心和DP的區(qū)別。
初始化很重要,讓我WA了N次。
dp[i][j]表示第 i天在 city j 所能得到的最大income。
所以有轉(zhuǎn)移方程:
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]單獨(dú)初始化)
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是上一位的進(jìn)位,其中a[i-1][j]+10*k是i-1的數(shù)
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'標(biāo)記為-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
別人的思路,有點(diǎn)遞歸的意思。程序本身超時(shí),但可以利用它來(lái)打表。
這個(gè)題目其實(shí)就是要求前k次踢掉的都是壞人,假設(shè)第i次踢掉的人是i,則i>k。根據(jù)題意,可以得到如下關(guān)系: 設(shè) ai 是第i次踢掉的人在第i-1次踢掉后剩下的人中是第幾個(gè)。那么
a(n) = [a(n-1)+m-1]mod(2k-n+1) 要求a(n) > k;n = 1,2,3,...,k 其中2k-n+1是第i-1次踢人后剩下的人數(shù)
1 bool Joseph(int k, int m) // 這個(gè)算法確定對(duì)于給定的k,m是否滿(mǎn)足上面的要求
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> 2 using namespace std; 3 bool 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 } 15 int 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做,我是參考了一個(gè)人的思路寫(xiě)的代碼AC的。
大意是從后往前推,因?yàn)閺那巴笫遣荒艿玫饺肿顑?yōu)解的,而從后就可以。
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
先說(shuō)一個(gè)定理:
若正整數(shù)n可分解為p1^a1*p1^a2*...*pk^ak 其中pi為兩兩不同的素?cái)?shù),ai為對(duì)應(yīng)指數(shù) n的約數(shù)個(gè)數(shù)為(1+a1)*(1+a2)*....*(1+ak) 如180=2*2*3*3*5=2^2*3^2*5 180的約數(shù)個(gè)數(shù)為(1+2)*(1+2)*(1+1)=18個(gè)。
若求A/B的約數(shù)個(gè)數(shù),A可分解為p1^a1*p2^a2*...*pk^ak,B可分解為q1^b1*q1^b2*...*qk^bk,則A/B的約數(shù)個(gè)數(shù) 為(a1-b1+1)*(a2-b2+1)*(a3-b3+1)...*(ak-bk+1).
然后說(shuō)N的階乘:
例如:20! 1.先求出20以?xún)?nèi)的素?cái)?shù),(2,3,5,7,11,13,17,19) 2.再求各個(gè)素?cái)?shù)的階數(shù) 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
解釋?zhuān)?br>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的階乘質(zhì)數(shù)因數(shù)個(gè)數(shù)時(shí),從最小的質(zhì)數(shù)開(kāi)始,
1 int cal(int n, int p) {
2 if(n < p) return 0;
3 else return n / p + cal(n / p, p);
4 }
其中P是質(zhì)數(shù),則該函數(shù)返回的就是N的階乘中可以表達(dá)成質(zhì)數(shù)P的指數(shù)的最大值。原理如上。 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個(gè)素?cái)?shù) 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的階乘含質(zhì)因數(shù)M的次數(shù) 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 }
是個(gè)關(guān)于拓展歐幾里得的問(wèn)題,但是很難想到。這題也是看了結(jié)題報(bào)告的~~
關(guān)于拓展歐幾里得的算法http://mj-zhang.blogbus.com/tag/拓展歐幾里得/
大意是給N個(gè)瓶子,每個(gè)瓶子有個(gè)容量C,給定一個(gè)容量W,每次只能(1)灌滿(mǎn)一個(gè),(2)倒空一個(gè),(3)把一個(gè)的水倒給另一個(gè),直到一個(gè)滿(mǎn)了或者一個(gè)空了。通過(guò)三種操作,有沒(méi)有可能最后達(dá)到某個(gè)瓶子里有W的水??梢赃@樣考慮:
1)當(dāng)所有C都小于W,肯定不行;
2)如果有N個(gè)瓶子,N個(gè)瓶子的容量C1, C2, C3 ... Cn必然有個(gè)最大公約數(shù)P。
證明:假設(shè)n個(gè)水壺的容量分別為C1,C2,C3…..Cn. 必要性:不管執(zhí)行三種操作的那一種,壺中所含的水一定是P的整數(shù)倍. 充分性:由歐幾里德算法擴(kuò)展可知,必然存在整數(shù)A1,A2,A3…..An,使得 A1*C1+A2*C2+A3*C3+…+An*Cn=W. 如果Ai是正數(shù),我們就用第i個(gè)壺從水源中取Ai次水;如果Ai為負(fù)數(shù),我們就把第i個(gè)壺倒空Ai次,這樣最后必會(huì)剩下W升水
今天比較郁悶,什么都不說(shuō)了。期中的高數(shù),本來(lái)及格就很困難,加上這學(xué)期的狀態(tài)。。。。哎,整個(gè)兩個(gè)小時(shí)簡(jiǎn)直就是煎熬啊。從下星期開(kāi)始還是學(xué)學(xué)課程吧。。
|