网站主要参照洛谷 牛客 力扣 cf等
题单列表 - 洛谷
题单链接
今天的刷题内容如上
在进入专题学习之前
先看补充知识
数组能开多大
C/C++数组的大小最大能有多大？_c++数组大小_JoannaJuanCV的博客-CSDN博客
全局：int 2000*2000 6个0可
局部： int 5个0可 char 6个0可
需要申请较大的空间->动态申请（new、malloc）
快读
快读/快写
快读/快写：只能处理整数读入/输出，但是要比标准输入输出函数都快得多。
- 一般来讲，快读快写在针对数据量不是很大的输入输出的时候显得比较无力，但如果是多组数据或者输入量较多，就可以显著提升效率。
- 开不开inline差不多。
- 还有一种更快的fread()函数型快读，比一般的快读都要快，但是模板不太好理解。
inline int read(){int x=0,f=1;char c=getchar();//这里isdigit()也可以改为通过ASCII判断，isdigit=c>='0'&&c<='9'while(!isdigit(c))//#include<ctype>{if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;
}不过快读也有可能被卡，比如一个数据有很多很多空格
还没有见过如此毒瘤的数据
而实际上，甚至还有更快的读入方式：fread
这个函数的原理就是先把数 据流中的一整段都存下来，然后从这个数组里读取，直到数组读空了再重新从数据流中读取，由于是整段整段读取，所以自然比getchar()要快的多。
这两个东西在各种OJ上面还是适用的，因为OJ上就是文件读入输出的。
不过我们会发现，一旦用了这个读入优化。getchar，scanf都不能用了（存到buf里了），所有读入都必须自己写了。所以说数据流不是太大的时候（如1*10^6），可以考虑不用这个读入优化。
代码长这样↓
static char buf[1000000],*p1=buf,*p2=buf,obuf[1000000],*p3=obuf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;
}
scanf:
1.使用scanf的时候最容易犯的也是最常见的问题就是没打取地址符，这个问题是不会CE，只会RE，但是一定要注意！scanf输入字符串本来也没有取地址符！
2.少一个或者多一个%d也是很常见的问题，多一个%d会因为找不到地址RE，少一个%d你的变量就会少值
3.文本替代符写错类型也是一个常见问题，尤其是%lld和%d，一定要确定好读入类型再写文本替代符
读入优化：
1.读入优化最最最最最容易出现的问题就是类型，虽然只能是int或者ll，但是一定要看好读入的的变量将会是什么类型，这里千万不能写错，ll写成int你题就炸了，int写成ll可能连赋值都做不到
2.只能用于整数，如果有什么浮点数建议直接放弃
3.写的时候一定要注意好别写错了，比如少个getchar之类的，如果没了会直接TLE或者RE
fread：(建议了解下即可)
1.同读入优化
2.只能使用文件读入
快写
内容基本与快读一致，此处将给出代码但不予赘述，请读者自行理解
快速读入唯一的问题是不能输出0，这里需要自行特判
以及fwrite可以在终端输入的情况下使用，但是会直接输出为文件形式
原初の快速输出↓
inline int read()
{ 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*10+ch-'0',ch=getchar();return x*f;
}fwrite快速输出↓
static char buf[1000000],*p1=buf,*p2=buf,obuf[1000000],*p3=obuf;
#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
inline void write(int x){ if(x==0){putchar('0');return;}int len=0,k1=x,c[10005];if(k1<0)k1=-k1,putchar('-');while(k1)c[len++]=k1%10+'0',k1/=10;while(len--)putchar(c[len]);
}O2优化
我们不用管O2优化的原理，只需要记住这个优化能使得程序的效率大大提高
手动打开O2开关：
#pragma GCC optimize(2)
模拟
【算法1-1】模拟与高精度 - 题单 - 洛谷
[NOIP2003 普及组] 乒乓球
P1042 [NOIP2003 普及组] 乒乓球_哔哩哔哩_bilibili
#include<iostream>
using namespace std;
char a[2501*25+10];//每行至多25个字母，最多有2500行。void work(int n)
{int w=0,l=0;for(int i=0;a[i]!='E';i++){if(a[i]=='W') w++;else l++;if((w>=n&&w-l>=2)||(l>=n&&l-w>=2))//不要忽略题目中的每个信息{cout<<w<<":"<<l<<endl;w=l=0;}}cout<<w<<":"<<l<<endl;//不需要判断w!=0||l!=0
}
int main()
{int i=0;while(cin>>a[i]&&a[i]!='E'){i++;}work(11);cout<<endl;work(21);return 0;
}
P1067 [NOIP2009 普及组] 多项式输出
同判断三角形类型
高精度
加法
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int a[1000],b[1000];
int c[1000]={0};
void jiafa()
{int l1=s1.length();int l2=s2.length();for (int i=0;i<l1;i++)a[i]=s1[i]-'0';for(int i=0;i<l2;i++)b[i]=s2[i]-'0';int l=max(l1,l2);for(int i=0;i<l;i++){c[i]+=a[i]+b[i];//进位if(c[i]>=10){c[i+1]=c[i]/10;c[i]%=10;}}if(c[l]!=0) l++;for(int i=l-1;i>=0;i--)cout<<c[i];}
void fanzhuan(string s)
{int l=s1.length();for(int i=0,j=l-1;i<j;i++,j--){swap(s[i],s[j]);}
}
int main()
{cin>>s1>>s2;//空格 tab 换行都可下一个//cin.getline(s1);读一行//gets()太危险被禁用//fanzhuan(s1);reverse(s1.begin(),s1.end());reverse(s2.begin(),s2.end());jiafa();cout<<endl;
}题目：P1601 A+B Problem（高精）
减法
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int a[1000],b[1000];
int d[1000]={0};
void jian(string s1,string s2)
{memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(d,0,sizeof(d));
//八位一复制int l1=s1.length();int l2=s2.length();for(int i=0;i<l1;i++)a[i]=s1[i]-'0';for(int i=0;i<l2;i++)b[i]=s2[i]-'0';int l=max(l1,l2);for(int i=0;i<l;i++){d[i]+=a[i]-b[i];//借位问题if(d[i]<0){d[i]+=10;//借位d[i+1]-=1;}}while(d[l-1]==0&&l>=1)l--;//借位借没了
int flag=0;for(int i=l-1;i>=0;i--){cout<<d[i];flag=1;}if(flag==0)cout<<"0";
}
int judge(string s1,string s2)
{int l1=s1.length();int l2=s2.length();if(l1>l2) return 1;//长的数大if(l1<l2) return 0;for(int i=l1-1;i>=0;i--){if(s1[i]>s2[i]) return 1;//一位一位比较 大的大if(s1[i]<s2[i]) return 0;}return 1;
}
void fanzhuan(string s)
{int l=s1.length();for(int i=0,j=l-1;i<j;i++,j--){swap(s[i],s[j]);}
}
int main()
{cin>>s1>>s2;//空格 tab 换行都可下一个//cin.getline(s1);读一行//gets()太危险被禁用reverse(s1.begin(),s1.end());reverse(s2.begin(),s2.end());if(judge(s1,s2)==1) jian(s1,s2);else{cout<<"-";jian(s2,s1);}
}乘法
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int a[1000],b[1000];
int c[1000]={0};int cheng(string s1,string s2)
{memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(c,0,sizeof(c));int l1=s1.length();int l2=s2.length();for(int i=0;i<l1;i++)a[i]=s1[i]-'0';for(int i=0;i<l2;i++)b[i]=s2[i]-'0';int l=l1+l2-1;/for(int i=0;i<l1;i++)for(int j=0;j<l2;j++){c[i+j]+=a[i]*b[j];+}for(int i=0;i<l;i++){if(c[i]>=10){c[i+1]+=c[i]/10;//+c[i]%=10;}}while(c[l]>0)//这里l+1或者l都可以ac{l++;if(c[l]>=10){c[l+1]+=c[l]/10;+c[l]%=10;}}for(int i=l-1;i>=0;i--)cout<<c[i];}
int main()
{cin>>s1>>s2;reverse(s1.begin(),s1.end());reverse(s2.begin(),s2.end());cheng(s1,s2);
}
看着string里的reverse如此好用
我觉得去学一下STL中的string
string
于是去看了一篇博客
String用法详解_manonghouyiming的博客-CSDN博客
这里选取一部分内容放上
初始化
1) string s; // 生成一个空字符串s
2) string s(str) ; // 拷贝构造函数生成str的复制品
3) string s(str, stridx); // 将字符串str内"始于位置stridx"的部分当作字符串的初值
4) string s(str, stridx, strlen) ; // 将字符串str内"始于stridx且长度顶多strlen"的部分作为字符串的初值
5) string s(cstr) ; // 将C字符串（以NULL结束）作为s的初值
6) string s(chars, chars_len) ; // 将C字符串前chars_len个字符作为字符串s的初值。
7) string s(num, ‘c’) ; // 生成一个字符串，包含num个c字符
8) string s(“value”); string s=“value”; // 将s初始化为一个字符串字面值副本
9) string s(begin, end); // 以区间begin/end(不包含end)内的字符作为字符串s的初值
10) s.~string(); //销毁所有字符，释放内存 
string对象的操作
string s;
1) s.empty(); // s为空串 返回true
2) s.size(); // 返回s中字符个数 类型应为：string::size_type
3) s[n]; // 从0开始相当于下标访问
4) s1+s2; // 把s1和s2连接成新串 返回新串
5) s1=s2; // 把s1替换为s2的副本
6) v1==v2; // 比较，相等返回true
7) `!=, <, <=, >, >=` 惯有操作 任何一个大写字母都小于任意的小写字母
当进行string对象和字符串字面值混合连接操作时，+操作符的左右操作数必须至少有一个是string类型的：
string s1(“hello”);
string s3=s1+”world”; //合法操作
string s4=”hello”+”world”; //非法操作：两个字符串字面值相加
4、字符串操作函数
1、string类函数
1) =, s.assign() // 赋以新值
2) swap() // 交换两个字符串的内容
3) +=, s.append(), s.push_back() // 在尾部添加字符
4) s.insert() // 插入字符
5) s.erase() // 删除字符
6) s.clear() // 删除全部字符
7) s.replace() // 替换字符
8) + // 串联字符串
9) ==,!=,<,<=,>,>=,compare() // 比较字符串
10) size(),length() // 返回字符数量
11) max_size() // 返回字符的可能最大个数
12) s.empty() // 判断字符串是否为空
13) s.capacity() // 返回重新分配之前的字符容量
14) reserve() // 保留一定量内存以容纳一定数量的字符
15) [ ], at() // 存取单一字符
16) >>,getline() // 从stream读取某值
17) << // 将谋值写入stream
18) copy() // 将某值赋值为一个C_string
19) c_str() // 返回一个指向正规C字符串(C_string)的指针 内容与本string串相同 有’\0’
20) data() // 将内容以字符数组形式返回 无’\0’
21) s.substr() // 返回某个子字符串
22) begin() end() // 提供类似STL的迭代器支持
23) rbegin() rend() // 逆向迭代器
24) get_allocator() // 返回配置器2、函数说明
1、s.assign();
s.assign(str); // 不说
s.assign(str,1,3); // 如果str是"iamangel" 就是把"ama"赋给字符串
s.assign(str,2,string::npos); // 把字符串str从索引值2开始到结尾赋给s
s.assign("gaint"); // 不说
s.assign("nico",5); // 把’n’ ‘I’ ‘c’ ‘o’ ‘\0’赋给字符串
s.assign(5,'x'); // 把五个x赋给字符串排序
冒泡排序、选择排序、快速排序
//快速排序
#include<iostream>
using namespace std;int partition(int arr[], int low, int high) {int num = arr[low];while(low < high) {while(low < high && arr[high] > num) {high--;}arr[low] = arr[high];while(low < high && arr[low] <=num) {low++;//此处是<=num 并且 while不要忘记low<high}arr[high] = arr[low];}arr[low] = num;return low;//返回low
}void QuickSort(int arr[],int L,int R)
{if(L<R){int mid=partition(arr,L,R);QuickSort(arr,L,mid-1);QuickSort(arr,mid+1,R);}
}
void BubbleSort(int arr[],int n)
{for(int i=0;i<n-1;i++){for(int j=i+1;j<n;j++){if(arr[i]>arr[j]){int temp=arr[i];arr[i]=arr[j];arr[j]=temp;}}}
}
void ChooseSort(int arr[],int n)
{int minnum;for(int i=0;i<n-1;i++){minnum=i;for(int j=i+1;j<n;j++){if(arr[minnum]>arr[j])minnum=j;} int temp=arr[i];arr[i]=arr[minnum];arr[minnum]=temp;}}
void travel(int arr[],int n)
{for(int i=0;i<n;i++)cout<<arr[i]<<" ";cout<<endl;}
int main()
{int x;int a[100],b[100],c[100];int n=0;cin>>x;while(x!=0){a[n]=x;b[n]=x;c[n]=x;cin>>x;n++;}
// travel(a,n);BubbleSort(a,n);ChooseSort(b,n);QuickSort(c,0,n-1);travel(a,n);travel(b,n);travel(c,n);
}插入排序（O(n^2)）
void DirecInsSort(int* a, int n)//直接插入排序函数
{int i, j,temp;for (i = 1; i < n; i++) {//第一个数默认排序好了,而他的下标是0，所以从1开始if (a[i] < a[i - 1])//如果大于就直接加入，就是相当于排好了{temp = a[i];for (j = i - 1; j >= 0 && temp < a[j]; j--)//从已经排好的序列，从后往前检查{a[j + 1] = a[j];//往后移一个位置}a[j + 1] = temp;}}
}希尔排序
注意：数组最后一个数一定要为1
//希尔排序
//8 3 6 1 68 12 19 3 1 0
#include<iostream>
using namespace std;
void Shell(int a[],int n,int incr)
{int j;
for(int i=0;i+incr<n;i++)//i++哦
{int x=a[i+incr];for( j=i;j>=0;j-=incr){if(x<a[j]) //18<10{a[j+incr]=a[j];}else break;}a[j+incr]=x;
}
}
void ShellSort(int a[],int n,int d[])
{for(int i=0;i<3;i++){Shell(a,n,d[i]);for(int j=0;j<n;j++)cout<<a[j]<<" ";cout<<endl;}
}
int main()
{int a[100],n,i=0;while(cin>>a[i]&&a[i])//输入数据 i++; n=i;int d[10];//incrcin>>d[0]>>d[1]>>d[2];ShellSort(a,n,d);}
void Shell(int a[],int n,int incr)
{int j;for(int i=incr;i<n-incr;i++){if(a[i]<a[i-incr]){int temp=a[i];for(j=i-incr;j>=0&&a[j]>temp;j-=incr){a[j+incr]=a[j];}a[j+incr]=temp;}}
}归并排序
#include<bits/stdc++.h>
using namespace std;
void Merge(int Arr[],int start,int mid,int endd)
{int temp[10010];int i=start,j=mid+1,k=start;while(i!=mid+1&&j!=endd+1){if(Arr[i]>Arr[j])temp[k++]=Arr[j++];elsetemp[k++]=Arr[i++];}while(i!=mid+1)temp[k++]=Arr[i++];while(j!=endd+1)temp[k++]=Arr[j++];for(i=start;i<=endd;i++)Arr[i]=temp[i];
}
void MergeSort(int a[],int start,int endd)
{int mid;if(start<endd){ mid=start+(endd-start)/2;MergeSort(a,start,mid);MergeSort(a,mid+1,endd);//左右两块Merge(a,start,mid,endd); }
}
int main()
{int n;int a[10010];cin>>n;for(int i=0;i<n;i++) cin>>a[i];MergeSort(a,0,n-1);for(int i=0;i<n;i++) cout<<a[i]<<" ";return 0;
}第二种写法（一个函数）：
void msort(int b,int e)//归并排序
{if(b==e) return;int mid=(b+e)/2,i=b,j=mid+1,k=b;msort(b,mid),msort(mid+1,e);while(i<=mid&&j<=e)if(a[i]<=a[j])c[k++]=a[i++];elsec[k++]=a[j++],ans+=mid-i+1;//统计答案while(i<=mid)c[k++]=a[i++];while(j<=e)c[k++]=a[j++];for(int l=b;l<=e;l++)a[l]=c[l];
} 堆排序
可移步这道题第二篇题解 我觉得写的非常好！！！
登录 - 洛谷
//堆排序
#include<iostream>
#include<bits/stdc++.h>
using namespace std;void SiftAdjust(int a[],int n,int i)
{//n是a数组有效数据的范围，它是慢慢变小的//i是要调整的那个节点的编号 int f,left;//f 用来记忆双亲 left算出i的左孩子编号 for(f=i,left=2*i+1;left<=n-1;)//计算新的孩子{//f记下要调整的i号节点，keft就变成右孩子的下标 if(left+1<=n-1 && a[left]<a[left+1] )//右孩子存在，且，右边值更大 left=left+1;//left++ left就变成右孩子的下标 if(a[left]>a[f])//孩子的最大值和双亲f比，若孩子更大，则交换 {int t=a[left];a[left]=a[f];a[f]=t;}else break; //孩子的值 小，就结束 return f=left; //继续向下调整，刚才的孩子成为新的双亲，再上去计算新的孩子 left=2*f+1; //计算出新孩子，这句话放for表达式3也可以 }}
void HeapSort(int a[],int n)
{//8 3 6 1 68 12 19 3 1//k=0 1 2 3 4 5 6 7 8//调整 中间节点 for(int i=(n-2)/2;i>=0;i--){SiftAdjust(a,n,i);} //调整根节点 for(int j=0;j<n;j++)cout<<a[j]<<" "; cout<<endl;for(int i=0;i<n-1;i++){int t=a[n-1-i];// n-1 n-2 n-3 n-4a[n-1-i]=a[0];a[0]=t;//交换第一个与最后一个数SiftAdjust(a,n-1-i,0);//调整剩下n-1-i个 维护根 for(int j=0;j<n;j++)cout<<a[j]<<" ";cout<<endl;}
}
int main()
{int a[100],i=0;while(cin>>a[i]&&a[i]){i++;}int n=i;HeapSort(a,n);return 0;} 维护堆排序
void heapify(int arr[],int n,int i)
{int largest=i;int lson=i*2+1;int rson=i*2+2;if(lson<n && arr[largest]<arr[lson])largest=lson;if(rson<n&&arr[largest]<arr[rson])largest=rson;//找出三个节点中最大的节点 if(largest!=i){swap(&arr[largest],&arr[i]);heapify(arr,n,largest);}} 桶排序
桶排序是计数排序的升级版，也是分治算法。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。简言之，将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。
具体移步：https://blog.csdn.net/m0_64036070/article/details/123826962
#include<bits/stdc++.h>
using namespace std;
int a,n,m,b[1000];
int main()
{cin>>n>>m;for(int i=0;i<m;i++)cin>>a,++b[a]; //记录票出现的次数for(int i=0;i<1000;i++)while(b[i]--)cout<<i<<" "; //根据票出现的次数输出return 0;
}总结：
比赛：小数据用插入；大数据用快排
P1923 【深基9.例4】求第 k 小的数
思路 1 (60pts)： O(nlog2n)
想法：对原数组进行快速排序，然后 O(1) 输出。
#include<bits/stdc++.h>
using namespace std;
int x[5000005],k;
int main()
{int n;scanf("%d%d",&n,&k);for(int i=0;i<n;i++)scanf("%d",&x[i]);sort(x,x+n);//快排printf("%d",x[k]);
}
思路 2 (100pts)： O(n)
想法：根据快排思想来寻找第 k 小的数。
快排的核心思想是二分。
在原二分的基础上可以进行修改：因为每次递归都会将数组划分为三部分，而答案只会在这三部分中的一个，不需要再对其他部分进行搜索，从而达到优化时间复杂度的效果。
#include<bits/stdc++.h>
using namespace std;
int x[5000005],k;
void qsort(int l,int r)
{int i=l,j=r,mid=x[(l+r)/2];do{while(x[j]>mid)j--;while(x[i]<mid)i++;if(i<=j){swap(x[i],x[j]);i++;j--;}}while(i<=j);//快排后数组被划分为三块： l<=j<=i<=rif(k<=j) qsort(l,j);//在左区间只需要搜左区间else if(i<=k) qsort(i,r);//在右区间只需要搜右区间else //如果在中间区间直接输出{printf("%d",x[j+1]);exit(0);}
}
int main()
{int n;scanf("%d%d",&n,&k);for(int i=0;i<n;i++)scanf("%d",&x[i]);qsort(0,n-1);
}
思路 3 (100pts)：O(n)
C++ 的宝库：STL
在 STL 里有一个神奇的函数 nth_element。
它的用法是 nth_element(a+x,a+x+y,a+x+len);。
结论：差不多就是将我们的思路 2 做了一遍。
nth_element 的时间复杂度是O(n) 的，不过 STL 常数普遍较大……但还是能过此题。
#include<bits/stdc++.h>
using namespace std;
int x[5000005],k;
int main()
{int n;scanf("%d%d",&n,&k);for(int i=0;i<n;i++)scanf("%d",&x[i]);nth_element(x,x+k,x+n);//简短又高效printf("%d",x[k]);
}
在 Ta 的博客查看
刚翻了一下原来P1138第k小整数，发现竟然没人用nth_element神器，这里介绍一下。
在强大的STL库中存在一个神奇的函数，那就是nth_element，这个函数主要用来将数组元素中第k小的整数排出来并在数组中就位，随时调用，可谓十分实用。
函数语句：nth_element(数组名,数组名+第k小元素,数组名+元素个数)
具体如何用见下面AC代码：
#include<bits/stdc++.h>
using namespace std;
long long n,k,a[5000010];
int main()
{scanf("%d%d",&n,&k);for(int i=0;i<n;i++)scanf("%d",&a[i]);nth_element(a,a+k,a+n);//使第k小整数就位 printf("%d",a[k]);//调用第k小整数
}
暴力枚举
加油
