劉汝佳『アルゴリズムコンテスト入門経典』---総括
34304 ワード
：《 》
：
+ ；
；
、 ， ！
：
1.a/b a、b ， ； ： -8/5 -1 ；
2. %.3lf ； : - = / = ；
3. const int ( )； eclipse 10 ；
#define 10 ；
：
1. ， ， ；
2. ！ ， ， 。
：
for(a=1;a<=9;a++)
for(b=0;b<=9;b++)
if(aabb ) printf("%d",aabb); if() ， 。
， ， 。
3. ， ， ；
4. ， ， ；
5.scanf() ；
：
1.memset(f,0,siziof(f)); f 0；
2. ：
3 ： ， fgets() ；
； ： ， ，
！
char f[N];
fgets(f,sizeof(f),stdin);
：
！ 。
3.printf("%d %o %x
",a,b,c); // ， ， ；
4.strchr ： 。--------------( )
5. ， '\0' ！
：
1. ， return ， ；
2. ， ； ， ， 。
3. ， ， 。
4. ： ！
----------------------------------- -----------------------------------
：
1. 。 ， 。
2.typedef 。
。(75 )
3.qsort 。
4. ：
： 。(78 )
， 。
5.
6. ：
ABC ：
Sabc == Soab + Sobc + Soca ? 。 。
：(85 )
|X0 Y0 1|
2S= |X1 Y1 1|
|X2 Y2 1| 。 ， 。 。
7. ， 、 、 ， ： V-E+F=2 ： 、 、 。
//------------- 88 ， 。
：
1. ， 。 front rear， 。 while(front<rear) 。
2. ， 1 ； 。
3. ， 。
4. ： ， ， 。
5. ： ， 。 dfs、 bfs。
， ， dfs bfs ， 。
6. ： ！ +1， 。
7.dfs/bfs ， 。
： ： 、 、 、 、 。
1. ：
(1) 1-n ：
：
： 、 A， cur。
： ， A 。 cur ！ 。
(2) ：
ok， c1、c2， c1<c2 ；
， ， for ， ， if(!i || p[i]!=p[i-1]) ， ！
(3) ：
C++ !
， next_permutation(p,p+n); p 。( p ！)
： ！
2. ：( )
(1) ：
， 。 。
(2) ：
： ， ， A(if(cur==n) )。 。
A， ， ， ！！
：
B[cur]=1; // cur ！
Print(n,B,cur+1);
B[cur]=0; // ！ cur ！
Print(n,B,cur+1);
3. ： ( ) ！ ---------- ？
， ( )， ， ！！
: ！ ( )， ！
： ， ， ， 。
( ， ， ： ， ！ 。)
(1) ：
(2) ：
： next_permutation() 。---- ， ；
： ： ， ！ vis ， ， ： ，
！
(3) ：
。
、 ： ， ， ，
， 。
， ， ， i ， ！
(4) ：( )
， min 。
， min ， 。 ！
4. ：( + ； )
(1) ：
、 ： ( ！ )， n。
， ， ， 。
： 。 ， ：
， ， 。。
(2) ：
， 。 ， 。
， ， ， ！( ！)
： ， ： ， ！
(3) ：
！ ， ， ， ( ， )， ！
， 0。
，133 3 ： ； ； STL 。
：
、 + 、 ！
， ， ， 。
， ， ， 。
， d。
， ， 。
： ( ； ， ，
。)
、 ， ， ！ ， 。
1. ：
：O(n^3)； S[j]-S[i-1]， ：O(n^2)； ： - - ：O(n*log2n)。
( ， 141 。)
， ： ： m=x+(y-x)/2; m 。( 。) m=(x+y)/2 0 。
2.n 10000 ， n^2 ； n 10^6 ， n*log2n 。
：
3. ： n，( int *T)
： ！ ！
else ： cnt+=m-p; ！
4. ：
： k ： k ， ， ， ：
， q-p+1 k ， ， 。
， O(n)。
5. ：
： ， ， 。
： ！ ， A， v， ！
： ： n m ， ！
： x， y； x y ！
：
6. 、 、 ！
7. ！( x ， ！)
： x ！ ， 。
x ， ， while(y-x>1e-5){} 。
：( 7 )
3 ：
8. ：
9. ：
bi ， 。
10. ： [a,b]
ai ， a ， ， 。
----------------------------------- -----------------------------------
： ： 、 + 。
1. ：
： ， 。 ！
：
： ， ， ， 。
2.DAG :( )
(1) ： i ， ！( 。)
： d[i]=max(d[j]+1); (i,j)
(d[i] : i ！)
：( )
int dp(int i){
int &ans=d[i];
if(ans>0) return ans;// ， ！
ans=1;
for(int j=1;j<=n;j++)
if(G[i][j]) ans >?= dp(j)+1;//
return ans;
}
：
， 。
d[] ， d[i] i， ， i 。
void Print(int i){
printf("%d",i); // ， 。 ， if ！
for(int j=1;j<=n;j++){
if(G[i][j] && d[i]==d[j]+1){ // ！
Printf(j);
break;
}
}
}
(2) ： ！
：
d[i] ： i 0 ！ dp(S); // ？ ？
int dp(int S){
if(vis[S]) return d[S]; // 0 ， d[]==0 d[] ;
// ： memset(vis,0,sizeof(vis));
vis[S]=1;// ！
int &ans=d[S];
ans= -1<<30;
for(int j=1;j<=n;j++)
if(S>=V[i]) ans >?= dp(S-V[i])+1;// ！ v[i] ！
return ans;
}
：
min[0]=max[0]=0;
for(int i=1;i<=S;i++){min[i]=INF; max[i]=-INF;}
for(int i=1;i<=s;i++)
for(int j=1;j<=n;j++)
if(i>V[j]){
min[i] = min[i-V[j]]+1;
max[i] >?= max[i-V[j]]+1;
}
printf("%d %d
",max[S],min[S]);
：
void Print(int *d,int S){
for(int i=1;i<=n;i++) // ， i=1 ！
if(S>=v[i] && d[S]==d[S-v[i]]+1){ // ！
printf("%d ",i);
Print(d,S-v[i]);
break;// ！
}
}
3.0-1 ：
： 0-1
： f[i][j]=max(f[i-1][j],f[i-1][j-V[i]]+W[i]);
(f[i][j] i j ！ ： i ！)
for(int i=1;i<=n;i++)
for(int j=0;j<=C;j++){
f[i][j]=(i==1 ? 0 : f[i-1][j]);
if(j>V[i]) f[i][j] >?= f[i-1][j-V[i]]+W[i];
} // ， ；( V、W )
4. ：
(1) ：( + )
： ， ， 。
： " "， ：P Q, P Q ！( )
( ！)
： f[i][j]=max(f[i][k]+f[k][j]+Pi-1PkPj); k i-j ！
(f[i][j] ： Pi Pj 。) ： f[i][i]=0;
(2) ：
： f[i][j]=max(f[i][k]+f[k][j]+W(i,j,k)); f[i][j] i j 。
( ： ，j i ， k ：i+1,i+2...n,1,2...j-1) --- 。
(3) ：
： ， 。
( ， 。)
： i 。
： d[i]=max(1+ (d[j]), (d[j])); j i ， j i 。
！ ， ， 。
( ， ， 172 )
5. ：( ， )
： ！ ： ！ ！
，'=' ， 。
( ， ， ！ ！)
2014.3.11 ：
：
1. ；（DAG ）
2. --- ：( ！)
： --- ---> f(i,j)=max( )
3. ；
4. 。
： ， ， ！
： ：( 、 、 、 )
：( ) ， 。
( ， ， 。)
( ， ！ 。)
1. ：
2 ， ， X1*X3*X4*.../X2 ；
， ，X2 ！ X2 ！
------ ： 。
( 1， ！)
2. ：
： m p， p^2 ！
： ：179 ，π(x) ： x 。 π(x)= x/ln(x);
(10^6 8W ；)
3. ：( ！ ： 179 )
4. ：
(1)a,b n ： a-b ， ； a*b ！
： (a-b)%n=((a%n)-(b%n)+n)%n; a*b%n=(int)((long long)(a%n)*(b%n)%n);
(2) ：
： 。
(3) ：( ！)
：
5. ：
： 。
： a,b,n， (a+b)^n ？
(1) ； O(n^2)
(2) ： C(n)(k)=((n-k+1)/k)*C(n)(k-1), C(n)(0)=1 ， n 。 O(n)
C[0]=1;
for(int i=1;i<=n;i++) C[i]=C[i-1]*(n-i+1)/i; // C 。
6. ： 、 ！
7. ：
(1) ：---- ： ， ， ！
n ：
， ： (a1+1)(a2+1)...(ak+1);
， n ， 。
(2) n n 。(184 )
8. ：
9. ：(187 )
：
10. ：
： f[n]=f[n-1]+1+f[n-1]; f[n]=2^n-1;
： ， 。
11.Fibonacci ：
： n ： 1 ， 2 ， ?
： ， n-1 ； ， n-2 。 f[n]=f[n-1]+f[n-2]; ( fibonacci )
2 ： ： n ： ， 。
： f[n]=f[n-1]+f[n-2];
3 ：2*n ： ！ 。
12.Catalan ：
(191 ， ！)
：
：
1. ：( ， ， .)
， ， STL ， ！ vector
vector<int> G[max];
//
void tree(){
int u,v;
scanf("%d",&n);
for(int i=0;i1;i++){
scanf("%d %d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
}
// ， : i p[i];
( p[root]=-1; 。 dfs(root,-1) 。)
void dfs(int u,int fa){
int d=G[u].size();
for(int i=0;i){
int v=G[u][i];
if(v!=fa) dfs(v,p[v]=u);
}
}
2. ：(197 )
3. ： ：Prim Kruskal( Kruskal， ， 。)
： ；------ 。
： (u,v) ; ------ ！！
： 。--- 。
Code:
#define N 100010
int m,n;int p[N],r[N],w[N];int u[N],v[N];
int cmp(int i,int j){return w[i]// ！
int find(int x){return p[x]== x ? x:p[x]=find(p[x]);} // find， x 。
int Kruskal(){
int ans=0;
for(int i=0;i//
for(int i=0;i// ， ！ i r[i]
sort(r,r+m,cmp);//
for(int i=0;i){
int e=r[i];
int x=find(u[e]);int y=find(v[e]); // ！
if(x!=y){
ans += w[e]; p[x]=y; // ， ！ x y ， y
}
}
return ans; //ans ！
}
//依次输入边和对应权值。----如果村庄编号是从1-n,初始化并查集那里需要改成i<=n！！！
4. ：
(202 )
：
1. ， ： num=num*2%10000;
f[i]=(num-f[i-1])%10000;
f[i] ！！ 。
2.while(scanf("%d:%d %d:%d",&a,&b,&a1,&b1)!=EOF)
；
3. ， break ， ！
4. ， ， 1， 。
5. n m ， ， ( )
， 。
6. ， ， 。
7.hdu1058, ！ int i,in1=0,in2=0,in3=0,in4=0,M1,M2,M3,M4; ， ， 。
8. ， ， ， 。 。
hdu 2428， ： ， ， 。
9. ： ！
転載先:https://www.cnblogs.com/songacm/p/3537731.html