好公式

将变量设为0

1
memset(变量名,0,sizeof(变量名))

刷题ing

【模板】快速排序

其实就是 STL 的 sort

题目链接

动态演示

QuickSort.gif

代码实现

使用 C++ STL sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
 int n=0;
 cin>>n;
 int num[n+2]={0};
 for(int i=0;i<n;i++){
  cin>>num[i];
 } 
 sort(num,num+n);
 for(int i=0;i<n;i++){
  cout<<num[i]<<" ";
 } 
 return 0;
}

手写快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
using namespace std;
void QuickSort(int* num,int l,int r){
    int mid=num[(l+r)/2];
    int i=l,j=r;
    do{
        while(num[i]<mid) i++;
        while(num[j]>mid) j--;
        if(i<=j)
        {
            swap(num[i],num[j]);
            i++;
            j--;
        }
    }while(i<=j);
 if(l<j) QuickSort(num,l,j);
 if(i<r) QuickSort(num,i,r);
}
int main(){
 int n=0;
 cin>>n;
 int num[n+2]={0};
 for(int i=1;i<=n;i++){
  cin>>num[i];
 }
 QuickSort(num,1,n);
 for(int i=1;i<=n;i++){
  cout<<num[i]<<" ";
 }
 return 0;
}

【模板】程序优化

题目链接

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<algorithm>
using namespace std;
//快读
inline int read(){
    char ch=getchar();
 int x=0,f=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    } 
 while('0'<=ch&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    } return x*f;
}
int main(){
 int n,k;
 n=read();
 k=read();
 int num[n+2]={0}; 
 for(int i=0;i<n;i++){ 
  num[i]=read();
 }
 nth_element(num,num+k,num+n);
 cout<<num[k];
 return 0;
}

【算法】深度优先探索

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
using namespace std;
int dfs(int n,int step=1){
 static int ans[11],book[11],sum=0;
 if(step==n){
  sum++;
  for(int i=1;i<=n;i++){
   cout<<ans[i];
  }
  cout<<endl;
  return sum;
 }
 for(int i=1;i<=n;i++){
  if(book[i]==0){
   ans[step]=i;
   book[i]=1;
   dfs(n,step+1);
   book[i]=0;
  }
 }
 return sum;
}
int main(){
 int n=0;
 cin>>n;
 cout<<dfs(n)<<endl;
 return 0;
}