(仅作个人备忘)

其实很早就想着更了,但是因为前段时间封校导致没法更新,现在趁着上网课就更新吧。

PS: KaTeX\textbf{ \KaTeX}终于弄好了!!!

基本结构

1
2
3
4
5
6
#include <bits/stdc++.h>
using namespace std;
int main(){
//代码
return 0;
}

排序

STLsort

最香的当然是STL sort,采用快排堆排插排混合,时间复杂度O(nlogn)O(n log_{n} )O(n2)O(n^2)

1
2
sort(arr,arr+n,cmp);
//其中cmp可以不加,默认从小到大

至于cmp的写法,只需要写两项的比较规则,比如从小到大写成:

1
2
3
int cmp(int a,int b){
return a<b;
}

从大到小:

1
2
3
int cmp(int a,int b){
return a>b;
}

利用cmp就能实现sort的结构体排序和题目的特殊要求,举个例子:

例子

FZQOJ#84. 近似排序

读入正整数x和y,将这两个数之间(包括这两个数本身)的所有数按下述特别规则排序后输出。

该特别规则是:按两数倒过来的值进行比较决定其大小,如30倒过来为3,29倒过来为92,则29大于30

【输入】
一行两个整数x和y,用一个空格隔开,1xy10000000001\le x\le y\le 1000000000,yx100y-x\le 100

【输出】
包括yx+1y-x+1行,每行一个正整数,按两数倒过来的值进行比较决定其大小,然后由小到大输出

【样例】
样例输入1

1
22 39

样例输出1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
30
31
22
32
23
33
24
34
25
35
26
36
27
37
28
38
29
39

使用sort:

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
32
#include <bits/stdc++.h>
using namespace std;
int cmp(int a,int b){
int a2=0;
while(a!=0)
{
a2*=10;
a2+=a%10;
a/=10;
}
int b2=0;
while(b!=0)
{
b2*=10;
b2+=b%10;
b/=10;
}
return a2<b2;
}
int main(){
int x,y,l[114];
cin>>x>>y;
int n=y-x+1;
for(int i=1;i<=n;i++){
l[i]=i+x-1;
}
sort(l+1,l+n+1,cmp);
for(int i=1;i<=n;i++){
cout<<l[i]<<endl;
}
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
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
int cmp(int a,int b){
int a2=0;
while(a!=0)
{
a2*=10;
a2+=a%10;
a/=10;
}
int b2=0;
while(b!=0)
{
b2*=10;
b2+=b%10;
b/=10;
}
return a2<b2;
}
int main(){
int x,y,l[114];
cin>>x>>y;
int n=y-x+1;
for(int i=1;i<=n;i++){
l[i]=i+x-1;
}
for(int i=2;i<=n;i++){
for(int j=2;j<=n;j++){
if(cmp(l[j],l[j-1])){
int tmp=l[j];
l[j]=l[j-1];
l[j-1]=tmp;
}
}
}
for(int i=1;i<=n;i++){
cout<<l[i]<<endl;
}
return 0;
}

都是AC代码,但是显然前者速度更快且更简单,可以节省你在比赛时的时间以及突然忘记模板的风险。

选择排序

时间复杂度:固定时间复杂度O(n2)O(n^2),不稳定

我使用的是打擂台一个一个找放到第二个数组中,这样子可以简单一点,当然空间复杂度双倍快乐

实测选排比冒泡快,因为冒泡要交换

从大到小:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int arr[114514],arr2[191981],n,max,maxi,k=1;
//freopen("random.in","r",stdin);
//freopen("random.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&arr[i]);
}
//n为数组长度
for(int i=1;i<=n;i++){
max=0x7FFFFFFF;
for(int j=1;j<=n;j++){
if(arr[j]>max){
max=arr[j];
maxi=j;
}
}
arr[maxi]=0x7FFFFFFF;
arr2[k]=max;
k++;
}
for(int i=1;i<=n;i++){
printf("%d ",arr2[i]);
} //输出

从小到大:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int arr[114514],arr2[191981],n,min,mini,k=1;
//freopen("random.in","r",stdin);
//freopen("random.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&arr[i]);
}
//n为数组长度
for(int i=1;i<=n;i++){
min=0x7FFFFFFF;
for(int j=1;j<=n;j++){
if(arr[j]<min){
min=arr[j];
mini=j;
}
}
arr[mini]=0x7FFFFFFF;
arr2[k]=min;
k++;
}
for(int i=1;i<=n;i++){
printf("%d ",arr2[i]);
} //输出

冒泡排序

时间复杂度:固定O(n2)O(n^2),具有稳定性。

一个板子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int arr[114514],n;
//freopen("random.in","r",stdin);
//freopen("random.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&arr[i]);
}
for(int i=2;i<=n;i++){
for(int j=2;j<=n;j++){
if(arr[j]>arr[j-1]){ //从小到大则把符号改为<
int tmp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=tmp;
}
}
}
for(int i=1;i<=n;i++){
printf("%d ",arr[i]);
} //输出

桶排序

较为简单,不稳定,时间复杂度O(n)O(n),空间复杂度较高,不适用于结构体和小数。

PS:这个桶排序指标记桶,并不是说分治的那个桶排序

2022.11.16更新

发现标记范围bug,已修正,然而本地能过(试过n=10000的数据规模也没有tle)但是过不了板子题qwq

1668570918842.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int arr[114514],bucket[114514],arr2[114514],n,k=1;
//freopen("random.in","r",stdin);
//freopen("random.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&arr[i]);
}
//arr指待排序数组,n为长度
for(int i=0;i<114514;i++){
bucket[i]=0;
}
for(int i=1;i<=n;i++){
bucket[arr[i]]++;
}
for(int i=0;i<114514;i++){ //从大到小改为for(int i=114513;i>=0;i--)
for(int j=1;j<=bucket[i];j++){
arr2[k]=i; //也可以直接输出,写成:cout<<i<<" ";
k++;
}
}
for(int i=1;i<=n;i++){
cout<<arr2[i]<<" ";
} //输出

就是在有序数组中做标记,和稳定完全搭不上边耶欸欸欸。

简单数论

斐波那契数列

求第nn

数组

1
2
3
4
5
6
int n,l[114]={0,1};
cin>>n;
for(int i=2;i<=n;i++){
l[i]=l[i-1]+l[i-2];
}
cout<<l[n];

递归

PS:时间复杂度O(n2)O(n^2),不建议使用

1
2
3
4
5
6
7
8
9
int fibnacci(int n) {
if(n < 1) {
return 0;
}else if(n == 1 || n == 2) {
return 1;
}

return f1(n-1) + f1(n-2);
}

递推(空间复杂度O(1)O(1)

1
2
3
4
5
6
7
8
int k,n=1,a=1,b=1;
cin>>k;
for(int i=3;i<=k;i++){
n=a+b;
a=b;
b=n;
}
cout<<n;

质数

咕咕咕。。。

拆数

1
2
3
4
5
6
7
int a=n,l=1,arr[114];
while(a!=0){
arr[l]=a%10;
a/=10;
l++;
}
l--;

快读快写

这些在一堆数据动不动就TLE的题中很好用,比scanf,printf,cin,cout快

快读板子:

1
2
3
4
5
6
7
8
9
10
11
12
13
inline void read(int &n){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
n=x*f;
}

快写板子:

1
2
3
4
5
6
7
8
inline void print(int n){
if(n<0){
putchar('-');
n*=-1;
}
if(n>9) print(n/10);
putchar(n % 10 + '0');
}

原理就是getchar,然后int和char互转

当然如果要用lld或者int128的话改一下也行的啦

求最大公约数

穷举

穷举么?雀食可以,不过

搜索

搜索虽然我背得模板但是用的不太熟悉qwq,依然是穷举贪心tle,然后助我退役

1668133472932.png

1668133599340.png

1668133671028.png

1668133741932.png

笑死。

二分

姑且也算搜索放进来吧。

原理就是根据大小不断分段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binarySearch(int arr[],int p,int q,int t) {
int mid=0;
if(p>q) {
return -1;
}
mid=p+(q-p)/2;
if(t==arr[mid]) {
return mid;
}
if(t<arr[mid]) { //降序改为>
return binarySearch(arr,p,mid-1,t);
}
else{
return binarySearch(arr,mid+1,q,t);
}
}

DFS

DFS比BFS貌似好理解点,因为是递归,一个费stack一个费queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int dfs(int t)
{
if(满足返回条件)
{
return 解;
}
else
{
for(int i=1;i<=尝试方法数;i++)
if(满足进一步搜索条件)
{
为进一步搜索所需要的状态打上标记;
dfs(t+1);
回溯一步;
}
}
}

BFS

这个真不会算了…

DP

no,我不会ヾ(´・ ・`。)ノ"

数据结构

链表

明天再写未完待续…

(PS:这篇文章充分体现了我OI的垃圾)