2023.8月信友队暑期集训内容总结
mamingyu0927 · · 个人记录
2023.8月信友队暑期集训内容总结
1.链表
指针
a是a的地址,变量前要加*;
c=&a , d=&b -> c+d=a+b;
单向链表
计算机的两种存储结构：
1.顺序储存（以数组方式）
2.链式存储（以链表方式）
链式存储结构(链表)由一系列结点组成，是用一组非连续的存储单元来存储结点数据，且链表的长度不是固定的。
优点1:存储空间是动态分配的，只要计算机内存空间还有空闲，就不会发生溢出。
优点2:插入或者删除元素方便，时间复杂度为O(1)那么，链表中第个结点称为头结点，最后一个结点称为尾结点。头结点通常不存储数据，尾结点的指针为空(NULL)。
单向链表代码
（第一步）
struct node{
int data;//存储元素本身的数据(整型)
node *next;//存储下一个结点的地址
};（第二步）
node *head,*tail;
head = new node;//申请空间
head->next = NULL;//结构体指针变量访问成员通过结构体指针运算符“->”
tail = head; //尾结点就是头结点，此时相当于建立了只包含一个结点的链表（第三步）
node *p;//当前结点
for(int i=1;i<=n;i++){
p = new node ;
cin>>p->data;//5 3
p->next = NULL;//指针域初始化为空
tail->next=p;//将新结点p链接到链表的尾结点之后
tail=p;//更新链表的尾结点
}
链表能执行的功能
打印：
p = head;
while(p->next!=NULL){
cout <<p->next->data;p = p->next;
}查找：
p = head->next;
while( p->data != 3 && p->next != NULL ){
p = p->next;
}删除：
p->next=p->next->next;例题1：《数组-删除某个数》
代码：
#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node *next;
}*head,*tail;
int main(){
int n,m;
while(cin>>n){
head=new Node;
head->next=NULL;
tail=head;
Node *p;
for(int i=1;i<=n;i++){
p=new Node;
cin>>p->data;
p->next=NULL;
tail->next=p;
tail=p;
}
cin>>m;
p=head;
bool f=0;
while(p->next!=NULL){
if(p->next->data==m&&f==0){
f=1;
break;
}
p=p->next;
}
if(f==1){
p->next=p->next->next;
}
p=head;
while(p->next!=NULL){
cout<<p->next->data<<" ";
p=p->next;
}
cout<<endl;
}
return 0;
}例题2：《双链表》
代码：
#include<bits/stdc++.h>
using namespace std;
int e[100005],l[100005],r[100005],idx;
void init(){
r[0]=1;
l[1]=0;
idx=2;
}
void insert(int k,int x){
e[idx]=x;
r[idx]=r[k];
l[idx]=k;
l[r[k]]=idx;
r[k]=idx;
idx++;
}
void del(int k){
r[l[k]]=r[k];
l[r[k]]=l[k];
}
int main(){
init();
int m;
cin>>m;
for(int i=1;i<=m;i++){
string s;
cin>>s;
if(s=="L"){
int x;
cin>>x;
insert(0,x);
}else if(s=="R"){
int x;
cin>>x;
insert(l[1],x);
}else if(s=="D"){
int k;
cin>>k;
del(k+1);
}else if(s=="IL"){
int k,x;
cin>>k>>x;
insert(l[k+1],x);
}else if(s=="IR"){
int k,x;
cin>>k>>x;
insert(k+1,x);
}
}
for(int i=r[0];i!=1;i=r[i]){
cout<<e[i]<<" ";
}
return 0;
}2.数据结构与STL
常见容器：
stack(栈),queue(队列),vector(动态数组),set(集合),map(映射)数据结构：
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。 动态数组是指在声明时没有确定数组大小的数组，即忽略圆括号中的下标；当要用它时，可随时用ReDim语句重新指出数组的大小。使用动态数组的优点是可以根据用户需要，有效利用存储空间。 集合，简称集，是数学中一个基本概念，也是集合论的主要研究对象。集合论的基本理论创立于19世纪，关于集合的最简单的说法就是在朴素集合论（最原始的集合论）中的定义，即集合是“确定的一堆东西”，集合里的“东西”则称为元素。现代的集合一般被定义为：由一个或多个确定的元素所构成的整体。 在数学里，映射是个术语，指两个元素的集之间元素相互“对应”的关系，为名词。映射，或者射影，在数学及相关的领域经常等同于函数。 基于此，部分映射就相当于部分函数，而完全映射相当于完全函数。stack:
1.push(x)
2.pop()
3.top()
4.empty()
5.size()queue:
1.push(x)
2.pop()
3.front()
4.back()
5.empty()
6.size()优先队列：
1.从小到大：priority_queue<int,vector<int>,greater<int> > q;
2.从大到小：priority_queue<int,vector<int>,less<int> > q;
priority_queue <int> q：
1.push(x)
2.pop()
3.top()
4.empty()
5.size()vector :
1.push_back(x);
2.pop_back();
3.size();
4.intsert(it,x);
5.erase();
6.clear();set :
1.insert(x);
2.find(x);
3.erase(first,last);
4.clear();
5.lower_bound(x);
6.upper_bound(x);
7.size();
8.empty();
9.count(x);map:
1.size();
2.find(key);
3.erase();
4.clear();例题1:《验证栈序列》
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin>>T;
while(T--){
int n;
cin>>n;
stack <int> stk;
int a[n+5]={0},b[n+5]={0},sum=1;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
for(int i=1;i<=n;i++){
stk.push(a[i]);
while(stk.top()==b[sum]){
stk.pop();
sum++;
if(stk.empty()){
break;
}
}
}
if(stk.empty()){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
}
return 0;
}例题2:《合并果子》
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
priority_queue <int,vector<int>,greater<int> > q;
for(int i=1;i<=n;i++){
int x;
cin>>x;
q.push(x);
}
int sum=0;
while(q.size()>=2){
int x=q.top();
q.pop();
int y=q.top();
q.pop();
sum+=x+y;
q.push(x+y);
}
cout<<sum;
return 0;
} 例题3:《模板库应用2-模板题3》
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
scanf("%d",&n);
set <int> a[10];
set <int> b;
for(int i=1;i<=n;i++){
int op;
scanf("%d",&op);
int x,y;
if(op==1){
scanf("%d%d",&x,&y);
a[x].insert(y);
}else if(op==2){
scanf("%d%d",&x,&y);
if(a[x].count(y)!=0){
a[x].erase(y);
}
}else if(op==3){
scanf("%d%d",&x,&y);
for(auto it=a[y].begin();it!=a[y].end();it++){
a[x].insert(*it);
}
a[y].clear();
}else if(op==4){
scanf("%d%d",&x,&y);
for(auto it=a[y].begin();it!=a[y].end();it++){
if(a[x].count(*it)){
b.insert(*it);
}
}
a[x]=b;
b.clear();
a[y].clear();
}else if(op==5){
scanf("%d%d",&x,&y);
if(a[x].count(y)==0){
cout<<"No\n";
}else{
cout<<"Yes\n";
}
}else if(op==6){
scanf("%d",&x);
cout<<a[x].size()<<endl;
}
}
return 0;
}例题4:《【模板】map》
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int q;
cin>>q;
map <int,long long> mp;
for(int i=1;i<=q;i++){
int n;
cin>>n;
int x,y;
if(n==1){
cin>>x>>y;
mp[x]+=y;
}else if(n==2){
cin>>x;
if(mp.find(x)!=mp.end()){
cout<<"YES\n";
}else{
cout<<"NO\n";
}
}
}
for(auto it=mp.begin();it!=mp.end();it++){
cout<<it->first<<" "<<it->second<<endl;
}
return 0;
}例题5:《模板库应用2-模板题2》
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
map<string,int> a;
for(int i=1;i<=n;i++){
int op;
string name;
cin>>op>>name;
if(op==1){
int x;
cin>>x;
a[name]=x;
}else if(op==2){
if(a.find(name)!=a.end()){
cout<<a[name]<<endl;
}else{
cout<<"Not found."<<endl;
}
}
}
return 0;
}例题6：《爱排队的史莱姆》
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int a[n+5]={0};
priority_queue <int,vector<int>,less<int> > q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n; ){
while(q.size()<m&&i<=n){
q.push(a[i]);
i++;
}
cout<<q.top()<<" ";
q.pop();
}
return 0;
} 例题7：《排队》
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
scanf("%d",&n);
queue <int> q;
priority_queue <int,vector<int>,greater<int> > q2;
for(int i=1;i<=n;i++){
int m;
scanf("%d",&m);
if(m==1){
int x;
scanf("%d",&x);
q.push(x);
}else if(m==2){
if(!q2.empty()){
printf("%d\n",q2.top());
q2.pop();
}else{
printf("%d\n",q.front());
q.pop();
}
}else if(m==3){
while(!q.empty()){
q2.push(q.front());
q.pop();
}
}
}
return 0;
}例题8：《查询数集》
代码：
#include<bits/stdc++.h>
using namespace std;
int b[1000005]={0};
int main(){
int a,n;
while(cin>>a>>n){
priority_queue<int,vector<int>,greater<int> > q;
q.push(a);
for(int i=1;i<=n;i++){
int x=q.top();
q.pop();
if(b[i-1]!=x){
b[i]=x;
}else{
i--;
}
q.push(x*2+1);
q.push(x*3+1);
}
cout<<b[n]<<" ";
}
return 0;
} 3.尺取，差分，前缀和
一.尺取
利用双指针来找出答案，同时向前或一左一右向中间查都可以
二.前缀和
通常用于求解以下问题：
1.需要频繁查询某个区间的和；
2.及到子数组的计算
3.数值更新较少
4.预处理时间可以接受分为一维的和二维的
三.差分
与前缀和相反，求差，也分为一维的和二维的
例题1：《最大的和》
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int a[n+5]={0};
int sum[n+5]={0};
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]=a[i]+sum[i-1];
}
int maxsum=-1e9;
for(int i=m;i<=n;i++){
maxsum=max(maxsum,sum[i]-sum[i-m]);
}
cout<<maxsum;
return 0;
} 例题2：《玉米地》
代码：
#include<bits/stdc++.h>
using namespace std;
int a[3005][3005]={0};
int sum[3005][3005]={0};
int main(){
int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
}
}
for(int i=1;i<=q;i++){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
cout<<sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]<<endl;
}
return 0;
} 例题3：《街区建设》
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int a[N]={0};
int sum[N]={0};
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int l,r,h;
cin>>l>>r>>h;
a[l]+=h;
a[r+1]-=h;
}
for(int i=1;i<=n;i++){
sum[i]=a[i]+sum[i-1];
cout<<sum[i]<<" ";
}
return 0;
} 例题4：《大哈贴广告》
代码：
#include<bits/stdc++.h>
using namespace std;
int sum[5000][5000]={0};
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
sum[x1][y1]+=1;
sum[x1][y2+1]-=1;
sum[x2+1][y1]-=1;
sum[x2+1][y2+1]+=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
cout<<sum[i][j]<<" ";
}
cout<<endl;
}
return 0;
} 例题5：《连续子区间的和》
代码：
#include<bits/stdc++.h>
using namespace std;
int a[100005]={0};
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int sum=0;
int ss=0;
for(int i=1,j=1;i<=n;i++){
while(sum<m&&j<=n){
sum+=a[j];
j++;
}
if(sum==m){
ss++;
}
sum-=a[i];
}
cout<<ss;
return 0;
} 例题6：《简单的求和》
代码：
#include<bits/stdc++.h>
using namespace std;
long long a[100005]={0};
int main(){
long long n,k;
cin>>n>>k;
for(long long i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
long long sum=0,ss=0;
for(long long i=1,j=n;i<j; ){
if(a[i]+a[j]<k){
i++;
}
else if(a[i]+a[j]>k){
j--;
}
else if(a[i]+a[j]==k){
long long cnt1=1;
while(a[i]==a[i+1]&&i<j){
i++;
cnt1++;
}
long long cnt2=1;
while(a[j]==a[j-1]&&i<j){
j--;
cnt2++;
}
ss+=cnt1*cnt2;
j--;
}
}
cout<<ss;
return 0;
} 例题7：《长度最小的子数组》
代码：
#include<bits/stdc++.h>
using namespace std;
long long a[300005]={0};
long long n,s;
int main(){
long long T;
cin>>T;
while(T--){
long long sum=0;
int minl=1e9;
cin>>n>>s;
for(long long i=1;i<=n;i++){
cin>>a[i];
}
if(s==0){
cout<<1<<endl;
continue;
}
for(int i=1,j=1;i<=n;i++){
while(sum<s&&j<=n){
sum+=a[j];
j++;
}
if(sum>=s){
minl=min(minl,j-i);
}
sum-=a[i];
}
if(minl==1e9){
cout<<0<<endl;
}else{
cout<<minl<<endl;
}
}
return 0;
} 例题8：《激光炸弹》
代码：
#include<bits/stdc++.h>
using namespace std;
int a[5050][5050]={0};
int main(){
int n,R;
cin>>n>>R;
for(int i=1;i<=n;i++){
int x,y,v;
cin>>x>>y>>v;
a[x+1][y+1]+=v;
}
for(int i=1;i<=5000;i++){
for(int j=1;j<=5000;j++){
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
}
int maxn=-1e9;
for(int i=R;i<=5000;i++){
for(int j=R;j<=5000;j++){
maxn=max(maxn,a[i][j]-a[i][j-R]-a[i-R][j]+a[i-R][j-R]);
}
}
cout<<maxn;
return 0;
} 例题9：《矩阵翻转》
代码：
#include<bits/stdc++.h>
using namespace std;
int a[500][500];
int main(){
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
while(q--){
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
for(int i=x1;i<=x2;i++){
for(int j=y1;j<=y2;j++){
a[i][j]=1-a[i][j];
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
return 0;
}4.贪心算法
贪心算法（greedy algorithm，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择 。（1）经典贪心
例题1：《最大字段和》
代码：
#include<bits/stdc++.h>
using namespace std;
void f(int n){
int a[n+5]={0},f[n+5]={0};
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
int maxn=-50000;
for(int i=1;i<=n;i++){
if(i==1){
f[i]=a[i];
}else{
f[i]=max(a[i],f[i-1]+a[i]);
}
maxn=max(maxn,f[i]);
}
printf("%d",maxn);
}
int main(){
int n;
scanf("%d",&n);
f(n);
return 0;
}例题2：《分发蛋糕》
代码：
#include<bits/stdc++.h>
using namespace std;
int a[105]={0},b[105]={0};
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
cin>>b[i];
}
sort(a+1,a+n+1);
sort(b+1,b+m+1);
int k=0,sum=0;
for(int i=1;i<=n;i++){
for(int j=k+1;j<=m;j++){
if(b[j]>=a[i]){
k=j;
sum++;
break;
}
}
}
cout<<sum;
return 0;
}例题3：《分发糖果》
代码：
#include<bits/stdc++.h>
using namespace std;
int a[105]={0};
int b[105]={0};
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=1;
}
for(int i=1;i<n;i++){
if(a[i]<a[i+1]){
b[i+1]=b[i]+1;
}
}
for(int i=n;i>1;i--){
if(a[i]<a[i-1]){
b[i-1]=max(b[i-1],b[i]+1);
}
}
int sum=0;
for(int i=1;i<=n;i++){
sum+=b[i];
}
cout<<sum;
return 0;
}例题4：《课程选择》
代码：
#include<bits/stdc++.h>
using namespace std;
struct Node{
int start,end;
}a[50000];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].start>>a[i].end;
}
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
if(a[i].end>a[j].end){
Node t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
int sum=1,x=a[1].end;
for(int i=2;i<=n;i++){
if(a[i].start>=x){
sum++;
x=a[i].end;
}
}
cout<<sum;
return 0;
}例题5：《李永林的梦》
代码：
#include<bits/stdc++.h>
using namespace std;
struct Node{
int start,end;
}a[50000];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].start>>a[i].end;
}
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
if(a[i].end>a[j].end){
Node t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
int sum=1,x=a[1].end+1;
for(int i=2;i<=n;i++){
if(a[i].start>=x){
sum++;
x=a[i].end+1;
}
}
cout<<sum;
return 0;
}例题6：《删除被覆盖区间》
代码：
#include<bits/stdc++.h>
using namespace std;
struct Node{
int l,r;
}a[1000001];
bool cmp(Node a,Node b){
if(a.l!=b.l){
return a.l<b.l;
}else{
return a.r>b.r;
}
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].l>>a[i].r;
}
sort(a+1,a+n+1,cmp);
int l=a[1].l,r=a[1].r,cnt=0;
for(int i=2;i<=n;i++){
if(a[i].l>=l&&a[i].r<=r){
cnt++;
}else if(a[i].l>=l&&a[i].r>r){
r=a[i].r;
}else if(a[i].l>r){
l=a[i].l;
r=a[i].r;
}
}
cout<<n-cnt;
return 0;
}例题7：《非洲小孩》
代码：
#include<bits/stdc++.h>
using namespace std;
struct Node{
int h1,m1,h2,m2;
}a[105];
bool cmp(Node a,Node b){
if(a.h2!=b.h2) return a.h2<b.h2;
return a.m2<b.m2;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d:%d-%d:%d",&a[i].h1,&a[i].m1,&a[i].h2,&a[i].m2);
if(a[i].h1>a[i].h2||a[i].h1==a[i].h2&&a[i].m1>a[i].m2){
swap(a[i].h1,a[i].h2);
swap(a[i].m1,a[i].m2);
}
}
sort(a+1,a+n+1,cmp);
Node N=a[1];
int cnt=1;
for(int i=2;i<=n;i++){
if(a[i].h1>N.h2||a[i].h1==N.h2&&a[i].m1>N.m2){
N=a[i];
cnt++;
}
}
cout<<cnt;
return 0;
}例题8：《雷达安置》
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int x[N],y[N];
struct Node{
int l,r;
}a[N];
bool cmp(Node a,Node b){
return a.r<b.r;
}
int main(){
int n,d,cnt=1;
cin>>n>>d;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
}
for(int i=1;i<=n;i++){
a[i].l=x[i]-int(sqrt(d*d-y[i]*y[i]));
a[i].r=x[i]+int(sqrt(d*d-y[i]*y[i]));
}
sort(a+1,a+n+1,cmp);
int ans=a[1].r;
for(int i=2;i<=n;i++){
if(ans>=a[i].l){
continue;
}else{
cnt++;
ans=a[i].r;
}
}
if(cnt==0){
cout<<-1;
}else{
cout<<cnt;
}
return 0;
}例题9：《忙碌的老师》
代码：
#include<bits/stdc++.h>
using namespace std;
priority_queue <int,vector<int>,greater<int> > q;
struct Node{
int b,e;
bool operator<(Node x){
if(b!=x.b){
return b<x.b;
}else{
return e<x.e;
}
}
}a[100005];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].b>>a[i].e;
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
if(q.empty()||a[i].b<=q.top()){
q.push(a[i].e);
}else{
q.pop();
q.push(a[i].e);
}
}
cout<<q.size();
return 0;
}（2）朴素贪心
例题1：《大哈的字符串2》
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
string a,b;
cin>>a>>b;
cout<<a[0];
for(int i=1;i<a.size();i++){
if(b[0]>a[i]){
cout<<a[i];
}else{
break;
}
}
cout<<b[0];
return 0;
} 例题2：《水壶》
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
long long a[N]={0},sum[N]={0};
int main(){
long long n,k;
cin>>n>>k;
for(long long i=1;i<=n;i++){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
long long maxn=-1e9;
for(long long i=k+1;i<=n;i++){
maxn=max(maxn,sum[i]-sum[i-k-1]);
}
cout<<maxn;
return 0;
} 例题3：《异或与乘积》
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,MOD=1e9+7;
long long n,a[N]={0},cnt=0,sum=1;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
if(a[i]==1) cnt++;
else if((a[i]&1)==0&&cnt!=0) a[i]++,cnt--;
if(cnt==0) break;
}
for(int i=1;i<=n;i++) sum=sum*a[i]%MOD;
cout<<sum;
return 0;
} 例题4：《CCC》
代码：
#include<bits/stdc++.h>
using namespace std;
int a[105]={0};
bool cmp(int n,int m){
return n>m;
}
int main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1,cmp);
double sum=0;
for(int i=k;i>=1;i--){
sum=max(sum,(sum+a[i])/2);
}
printf("%.5f",sum);
return 0;
} 例题5：《过河问题》
代码：
#include<bits/stdc++.h>
using namespace std;
int a[1000005]={0};
int f[1000005]={0};
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
f[1]=a[1],f[2]=a[2],f[3]=a[1]+a[2]+a[3];
for(int i=4;i<=n;i++){
f[i]=min(f[i-2]+a[1]+2*a[2]+a[i],f[i-1]+a[i]+a[1]);
}
cout<<f[n];
return 0;
} 例题6：《纪念品分组》
代码：
#include<bits/stdc++.h>
using namespace std;
bool cmp(int n,int m){
return n>m;
}
int main(){
int n,m,a[500000]={0};
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a[i];
}
sort(a+1,a+m+1,cmp);
int sum=0;
for(int i=1;i<=m;i++){
if(a[i]+a[m]<=n){
m--;
}
sum++;
}
cout<<sum;
return 0;
}例题7：《替换字母》
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[200005];
int f(int n,int m,char x){
int sum=0;
for(int i=1;i<=n;i++){
if(a[i]!=x){
i=i+m-1;
sum++;
}
}
return sum;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int minn=1e9+5;
for(char i='a';i<='z';i++){
minn=min(minn,f(n,m,i));
}
cout<<minn;
return 0;
} 例题8：《砍树king》
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
long long x[N]={0},h[N]={0};
int main(){
long long n;
cin>>n;
for(long long i=1;i<=n;i++){
cin>>x[i]>>h[i];
}
long long cnt=2;
for(long long i=2;i<n;i++){
if(h[i]<x[i]-x[i-1]){
cnt++;
}else{
if(h[i]<x[i+1]-x[i]){
cnt++;
x[i]=x[i]+h[i];
}
}
}
if(n==1){
cout<<1;
}else{
cout<<cnt;
}
return 0;
} 例题9：《独木桥》
代码：
#include<bits/stdc++.h>
using namespace std;
int a[5005]={0};
int main(){
int l,n;
cin>>l>>n;
int sum=0,cnt=0;
for(int i=1;i<=n;i++){
cin>>a[i];
sum=max(min(l+1-a[i],a[i]),sum);
cnt=max(max(l+1-a[i],a[i]),cnt);
}
cout<<sum<<" "<<cnt;
return 0;
}5.二分答案
每次取中间值，找出符合要求的答案函数
非递减的有序序列
1.lower_bound(v.begin(),v.end(),key)-v.begin()//返回有序序列中大于等于key的第一个值的位置
2.upper_bound(v.begin(),v.end(),key)-v.begin()//返回有序序列中大于key的第一个值的位置非递增的有序序列
1.lower_bound(v.begin(),v.end(),key，greater<int>())-v.begin()//返回有序序列中小于等于key的第一个值的位置
2.upper_bound(v.begin(),v.end(),key，greater<int>())-v.begin()//返回有序序列中小于key的第一个值的位置使用方法(若无满足条件值，返回v.size())
int a[10]={1,2,2,3,4,4,7,8,8,8};
cout<<upper_bound(a,a+10,7)-a<<endl;//7
cout<<upper_bound(a,a+10,8)-a<<endl;//10
cout<<upper_bound(a,a+10,-1)-a<<endl;//0
cout<<lower_bound(a,a+10,4)-a<<endl;//4
cout<<lower_bound(a,a+10,8)-a<<endl;//7
cout<<lower_bound(a,a+10,9)-a<<endl;//10例题1：《愤怒的牛》
代码：
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[500000]={0};
bool check(int d){
int cnt=1,y=a[1];
for(int i=1;i<=k;i++){
if(a[i]-y>=d){
if(++cnt==n){
return true;
}
y=a[i];
}
}
return false;
}
int main(){
cin>>k>>n;
for(int i=1;i<=k;i++){
cin>>a[i];
}
sort(a+1,a+k+1);
int left=1;
int right=a[k]-a[1];
while(left<=right){
int m=(left+right)/2;
if(check(m)){
left=m+1;
}else{
right=m-1;
}
}
cout<<right;
return 0;
}例题2：《年夜饭》
代码：
#include<bits/stdc++.h>
using namespace std;
long long n;
long long a[200005]={0};
long long b[200005]={0};
bool check(long long d){
long long cnt=0;
for(long long i=1;i<=n;i++){
if(a[i]<=d){
continue;
}else if(b[i]<=d){
cnt+=b[i];
}else{
return false;
}
}
return cnt<=d;
}
int main(){
cin>>n;
long long max1=0,max2=0;
for(long long i=1;i<=n;i++){
cin>>a[i];
max1=max(max1,a[i]);
}
for(long long i=1;i<=n;i++){
cin>>b[i];
max2+=b[i];
}
long long left=1;
long long right=max(max1,max2);
while(left<=right){
long long m=(left+right)/2;
if(check(m)){
right=m-1;
}else{
left=m+1;
}
}
cout<<left;
return 0;
}例题3：《跳石头》
代码：
#include<bits/stdc++.h>
using namespace std;
int l,n,m;
int a[100000]={0};
bool check(int d){
int cnt=0,y=a[0];
for(int i=1;i<=n+1;i++){
if(a[i]-y<d){
cnt++;
}else{
y=a[i];
}
}
if(cnt>m){
return false;
}else{
return true;
}
}
int main(){
cin>>l>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
a[0]=0;
a[n+1]=l;
int left=1;
int right=l;
while(left<=right){
int m=(left+right)/2;
if(check(m)){
left=m+1;
}else{
right=m-1;
}
}
cout<<right;
return 0;
}例题4：《木材加工》
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005]={0};
bool check(int d){
int cnt=1;
for(int i=1;i<=n;i++){
if(a[i]>=d){
cnt+=a[i]/d;
if(cnt>=m){
return true;
}
}
}
return false;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int small=1;
int big=100000000;
while(small<=big){
int x=(small+big)/2;
if(check(x)){
small=x+1;
}else{
big=x-1;
}
}
cout<<big;
return 0;
}例题5：《装果子》
代码：
#include<bits/stdc++.h>
using namespace std;
long long n,m,sum,maxn;
long long a[1000005]={0};
bool check(long long d){
long long cnt=1,f=d;
for(long long i=1;i<=n;i++){
if(f<a[i]){
cnt++;
f=d;
}
f-=a[i];
}
return cnt<=m;
}
int main(){
scanf("%lld%lld",&n,&m);
for(long long i=1;i<=n;i++){
scanf("%lld",&a[i]);
sum+=a[i];
maxn=max(maxn,a[i]);
}
long long left=maxn;
long long right=sum;
while(left<=right){
long long mid=(left+right)/2;
if(check(mid)){
right=mid-1;
}else{
left=mid+1;
}
}
printf("%lld",left);
return 0;
}6.搜索
（1）普通搜索
一.宽搜（广搜）
宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。二.深搜
深度优先搜索（DFS)是用于遍历或搜索树或图数据结构的算法。该算法从根节点开始(在图的情况下选择一些任意节点作为根节点)，并在回溯之前尽可能沿着每个分支进行探索。法国数学家查尔斯·皮埃尔·特雷毛为解决迷宫的策略,在19世纪研究了深度优先搜索。（2）搜索的剪枝
通过某种判断，避免一些不必要的遍历过程。搜索的时间复杂度通常很大，通过剪枝对搜索进行优化，可以大大提高程序运行的效率。（3）记忆化搜索
顾名思义，记忆化搜索就是让程序记住一些东西，然后可以在需要用的时候可以瞬间调用，不需要再进行一次复杂的计算！怎么记？首先，记忆需要大脑来存储数据，什么来模拟大脑？ 数组。其次，记忆需要现有的知识用来记住，知识从哪里来？以前求出的数据。这样，我们如果要用到以前求过的数据，就可以从数组中调用，可以大大提高我们程序的运行速度。例题1：《走迷宫》
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,sum=0;
char a[50][50];
bool f[50][50]={0};
int d[4][2]={-1,0,0,-1,0,1,1,0};
void dfs(int x,int y){
if(x==n&&y==m){
sum++;
return ;
}
for(int i=0;i<4;i++){
int nx=x+d[i][0];
int ny=y+d[i][1];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!='#'&&f[nx][ny]==0){
f[nx][ny]=1;
dfs(nx,ny);
f[nx][ny]=0;
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
f[1][1]=1;
dfs(1,1);
cout<<sum;
return 0;
}例题2：《相约KFC》
代码：
#include<bits/stdc++.h>
using namespace std;
char a[250][250];
bool f[250][250]={0};
int n,m,sx1,sy1,sx2,sy2,fx,fy;
struct Node{
int x,y,step;
};
int d[4][2]={-1,0,0,-1,0,1,1,0};
int bfs(int x,int y){
for(int i=1;i<=n;i+=1){
for(int j=1;j<=m;j++){
f[i][j]=0;
}
}
queue <Node> q;
q.push(Node{x,y,0});
f[x][y]=1;
while(!q.empty()){
Node nt=q.front();
q.pop();
for(int i=0;i<4;i++){
int nx=nt.x+d[i][0];
int ny=nt.y+d[i][1];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!='#'&&f[nx][ny]==0){
if(nx==fx&&ny==fy){
return nt.step+1;
}
f[nx][ny]=1;
q.push(Node{nx,ny,nt.step+1});
}
}
}
return -1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]=='@'){
sx1=i;
sy1=j;
}else if(a[i][j]=='&'){
sx2=i;
sy2=j;
}else if(a[i][j]=='F'){
fx=i;
fy=j;
}
}
}
if(bfs(sx1,sy1)==-1||bfs(sx2,sy2)==-1||max(bfs(sx1,sy1),bfs(sx2,sy2))>180){
cout<<"Meeting cancelled";
}else{
cout<<max(bfs(sx1,sy1),bfs(sx2,sy2));
}
return 0;
}例题3：《气运测试》
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=10005;
int n,m,x;
int a[N],b[N],c[N],d[N],r[N];
bool f[N];
void bfs(){
queue <int> q;
q.push(m);
f[m]=1;
r[m]=0;
bool flag=0;
while(!q.empty()){
int t=q.front();
q.pop();
if(t==x){
flag=1;
cout<<r[t];
break;
}
if(f[a[t]]==0){
q.push(a[t]);
f[a[t]]=1;
r[a[t]]=r[t]+1;
}
if(f[b[t]]==0){
q.push(b[t]);
f[b[t]]=1;
r[b[t]]=r[t]+1;
}
if(f[c[t]]==0){
q.push(c[t]);
f[c[t]]=1;
r[c[t]]=r[t]+1;
}
if(f[d[t]]==0){
q.push(d[t]);
f[d[t]]=1;
r[d[t]]=r[t]+1;
}
}
if(flag==0){
cout<<"NO";
}
}
int main(){
cin>>n>>m>>x;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i]>>c[i]>>d[i];
}
bfs();
return 0;
}例题4：《八连通》
代码：
#include<bits/stdc++.h>
using namespace std;
char a[105][105];
bool f[105][105]={0};
int n,m,cnt=0;
struct Node{
int x,y;
}st,ed,t,nt;
bool check(Node a){
return a.x>=1&&a.x<=n&&a.y>=1&&a.y<=m;;
}
int d[8][2]={-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};
queue <Node> q;
void bfs(Node st){
q.push(st);
f[st.x][st.y]=1;
while(!q.empty()){
t=q.front();
q.pop();
for(int i=0;i<8;i++){
nt.x=t.x+d[i][0];
nt.y=t.y+d[i][1];
if(check(nt)&&a[nt.x][nt.y]=='W'&&f[nt.x][nt.y]==0){
f[nt.x][nt.y]=1;
q.push(nt);
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='W'&&f[i][j]==0){
cnt++;
st.x=i;
st.y=j;
bfs(st);
}
}
}
cout<<cnt;
return 0;
} 例题5：《分配工作》
代码：
#include<bits/stdc++.h>
using namespace std;
int n,a[25][25],minn=1e9;
bool f[25]={0};
void dfs(int k,int sum){
if(sum>minn){
return ;
}
if(k>n){
minn=min(minn,sum);
return ;
}
for(int i=1;i<=n;i++){
if(f[i]==0){
f[i]=1;
dfs(k+1,sum+a[k][i]);
f[i]=0;
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
dfs(1,0);
cout<<minn;
return 0;
}例题6：《升降问题》
代码：
#include<bits/stdc++.h>
using namespace std;
int a[250];
bool f[250]={0};
int n,x,y;
struct Node{
int step,x;
}st,ed,t,nt;
queue <Node> q;
bool check(Node a){
return a.x>=1&&a.x<=n;
}
int bfs(Node st){
q.push(st);
f[st.x]=1;
while(!q.empty()){
Node t=q.front();
q.pop();
if(t.x==ed.x){
return t.step;
}
for(int i=1;i<=2;i++){
if(i==1){
nt.x=t.x+a[t.x];
}else{
nt.x=t.x-a[t.x];
}
nt.step=t.step+1;;
if(check(nt)&&f[nt.x]==0){
f[nt.x]=1;
q.push(nt);
}
}
}
return -1;
}
int main(){
while(-1){
cin>>n;
if(n==0){
return 0;
}
cin>>x>>y;
for(int i=1;i<=n;i++){
cin>>a[i];
}
st.x=x;
ed.x=y;
cout<<bfs(st);
}
return 0;
}7.动态规划
（1）背包
一.01背包
01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2至Wn，与之相对应的价值为P1,P2至Pn。01背包是背包问题中最简单的问题。01背包的约束条件是给定几种物品，每种物品有且只有一个，并且有权值和体积两个属性。在01背包问题中，因为每种物品只有一个，对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中，则不需要处理。如果选择将其放入背包中，由于不清楚之前放入的物品占据了多大的空间，需要枚举将这个物品放入背包后可能占据背包空间的所有情况。 [1]二.完全背包
完全背包问题一般是指：有N件物品和一个能背重量为W的背包，第i件物品的重量为weight[i]。每件物品有无限个(也就是可以放入背包多次），求怎样可以使背包物品价值总量最大。完全背包与01背包问题的区别在于01背包物品只有一个，完全背包有无数个。完全背包问题与01背包问题大致相同，唯一不同的地方体现在遍历顺序方面。三.分组背包
分组背包，通俗的讲就是，给你N组物品，然后每一组你至多选择一个物品(也可以不选).每个物品都有自己的体积和价值，现在给你一个容里为M的背包，让你用这个背包装物品，使得物品价值总和最大.四.多重背包
多重背包我们其实可以看成为01背包和完全背包的组合。也可以把多重背包问题只转换成01背包问题，我们一起来看看解题思路。（2）区间动态规划
区间动态规划是动态规划大家族中非常重要的一员。顾名思义，它是一种解决区间问题的方法。（3）线性动态规划
在我们利用动态规划解决问题的过程通常会有以下几个常见的专业术语，分别是：状态定义，状态的转移，初始化和边界条件。下面我们对这几个专业术语做一个简单的介绍。例题1:《采药》
代码：
/*/
思路：本题用二维背包,输入完后，要先创建一个二维数组dp,然后遍历m和t;
如果j大于等于a[i].time，将dp[i][j]赋值为的dp[i-1][j]和dp[i-1][j-a[i].time]+a[i].money的最大值；
否则把dp[i][j]赋值为dp[i-1][j];
最终答案就是dp[m][t];
/*/
#include<bits/stdc++.h>
using namespace std;
int t,m;
struct Node{
int time,money;
}a[105];
int dp[105][1005];
int main(){
cin>>t>>m;
for(int i=1;i<=m;i++){
cin>>a[i].time>>a[i].money;
}
for(int i=1;i<=m;i++){
for(int j=0;j<=t;j++){
if(j>=a[i].time){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i].time]+a[i].money);
}else{
dp[i][j]=dp[i-1][j];
}
}
}
cout<<dp[m][t];
return 0;
}例题2：《美丽手镯》
代码：
/*/
思路：与《采药》相似，但是需要优化，不能使用二维数组，得换成一维的；
输入完后，要还是先定义一个数组dp(一维)，然后遍历n,再从m遍历到a[i].w;
接着就可以直接给dp[j]赋值，不需要加判断；
最终答案为dp[m]。
/*/
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct Node{//定义结构体；
int w,v;
}a[100005];
int dp[100005];//定义dp;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i].w>>a[i].v;//输入；
}
for(int i=1;i<=n;i++){
for(int j=m;j>=a[i].w;j--){
dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);//给dp赋值；
}
}
cout<<dp[m];//输出。
return 0;
}例题3：《疯狂的采药》
代码：
#include<bits/stdc++.h>
using namespace std;
long long m,n,w[1000001],c[1000001],dp[10000001];
int main(){
cin>>m>>n;
for(long long i=1;i<=n;i++) cin>>w[i]>>c[i];
for(long long i=1;i<=n;i++){
for(long long j=w[i];j<=m;j++){
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
}
}
cout<<dp[m];
return 0;
}例题4：《庆功宴》
代码：
#include<bits/stdc++.h>
using namespace std;
long long n,m,a,b,num,w[5005],v[5005],dp[10005],cnt=0;
int main(){
cin>>n>>m;
for(long long i=1;i<=n;i++){
cin>>a>>b>>num;
for(long long j=1;num-j>=0;j*=2){
num-=j;
w[++cnt]=a*j;
v[cnt]=b*j;
}
if(num>0){
w[++cnt]=a*num;
v[cnt]=b*num;
}
}
for(long long i=1;i<=cnt;i++){
for(long long j=m;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[m];
return 0;
}例题5：《分组背包》
代码：
#include<bits/stdc++.h>
using namespace std;
int v,n,t,w,c,p,wi[1000][1000],ci[1000][1000],dp[10005];
int main(){
cin>>v>>n>>t;
for(int i=1;i<=n;i++){
cin>>w>>c>>p;
wi[p][0]++;
wi[p][wi[p][0]]=w;
ci[p][wi[p][0]]=c;
}
for(int i=1;i<=t;i++){
for(int j=v;j>=0;j--){
for(int k=1;k<=wi[i][0];k++){
if(j>=wi[i][k]){
dp[j]=max(dp[j],dp[j-wi[i][k]]+ci[i][k]);
}
}
}
}
cout<<dp[v];
return 0;
}例题6：《石子合并》
#include<bits/stdc++.h>
using namespace std;
int n,a,sum[305],dp[305][305];
int main(){
memset(dp,0x3f,sizeof(dp));//
cin>>n;
for(int i=1;i<=n;i++){
cin>>a;
sum[i]=sum[i-1]+a;
dp[i][i]=0;
}
for(int len=2;len<=n;len++){
for(int i=1;len+i-1<=n;i++){
int l=i,r=len+i-1;
for(int k=l;k<r;k++){
dp[l][r]=min(dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1],dp[l][r]);
}
}
}
cout<<dp[1][n];
return 0;
}
例题7：《最长上升子序列》
代码：
#include<bits/stdc++.h>
using namespace std;
void f(int n){
int a[n+5]={0},f[n+5]={1};
for(int i=1;i<=n;i++){
cin>>a[i];
}
f[1]=1;
int maxn=1;
for(int i=2;i<=n;i++){
int m=0;
for(int j=1;j<i;j++){
if(a[j]<a[i]){
if(f[j]>m){
m=f[j];
}
}
}
f[i]=m+1;
if(f[i]>maxn){
maxn=f[i];
}
}
cout<<maxn;
}
int main(){
int n;
cin>>n;
f(n);
return 0;
}例题8：《过河卒》
代码：
#include<bits/stdc++.h>
using namespace std;
long long n,m,x,y,dp[50][50];
int dx[8]={-2,-1,2,-1,-2,1,1,2};
int dy[8]={-1,-2,-1,2,1,-2,2,1};
int main(){
cin>>n>>m>>x>>y;
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
dp[i][j]=1;
}
}
dp[x][y]=0;
for(int i=0;i<8;i++){
if(x+dx[i]<0||y+dy[i]<0){
continue;
}
dp[x+dx[i]][y+dy[i]]=0;
}
for(int i=1;i<=n;i++){
if(dp[0][i]==0){
for(int j=i+1;j<=n;j++){
dp[0][j]=0;
}
break;
}
}
for(int i=1;i<=m;i++){
if(dp[i][0]==0){
for(int j=i+1;j<=m;j++){
dp[j][0]=0;
}
break;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(dp[i][j]==0){
continue;
}
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
cout<<dp[n][m];
return 0;
} 8.数论
数论（number theory ），是纯粹数学的分支之一，主要研究整数的性质。整数可以是方程式的解（丢番图方程）。有些解析函数（像黎曼ζ函数）中包括了一些整数、质数的性质，透过这些函数也可以了解一些数论的问题。透过数论也可以建立实数和有理数之间的关系，并且用有理数来逼近实数（丢番图逼近）。运用一些数学公式例题1：《筛选法求质数》
代码：
#include<bits/stdc++.h>
using namespace std;
bool x[10000001]={1,1};
void isPrime(int n){
for(int i=1;i*i<=n;i++){
if(x[i]==0){
for(int j=i*i;j<=n;j=j+i){
x[j]=1;
}
}
}
}
int main(){
int n;
cin>>n;
isPrime(n);
for(int i=2;i<=n;i++){
if(x[i]==0){
cout<<i<<' ';
}
}
return 0;
}例题2：《分解质因式》
代码：
#include<bits/stdc++.h>
using namespace std;
bool isPrime(int n){
if(n<2){
return false;
}
for(int i=2;i*i<=n;i++){
if(n%i==0){
return false;
}
}
return true;
}
int main(){
int n;
cin>>n;
cout<<n<<"=";
if(isPrime(n)){
cout<<n;
return 0;
}
for(int i=2;i*i<=n;i++){
while(n%i==0){
cout<<i<<"*";
n/=i;
}
}
cout<<n;
return 0;
}9.图论
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。例题1：《无向图的连通分量》
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,cnt;
bool f[10005]={0};
vector<int> v[10005];
void dfs(int x){
f[x]=1;
for(int i=0;i<v[x].size();i++){
if(f[v[x][i]]==0){
dfs(v[x][i]);
}
}
return ;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=1;i<=n;i++){
if(f[i]==0){
cnt++;
dfs(i);
}
}
cout<<cnt;
return 0;
}例题2：《小埋学习图之环问题》
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,minn=1e9+5;
int dis[1005]={0};
bool f[1005]={0};
vector<int> v[1005];
struct Node{
int x,fa;
};
void bfs(int x){
f[x]=1;
dis[x]=0;
queue<Node> q;
q.push(Node{x,-1});
while(!q.empty()){
int nx=q.front().x;
int nfa=q.front().fa;
q.pop();
for(int i=0;i<v[nx].size();i++){
if(f[v[nx][i]]==0){
f[v[nx][i]]=1;
q.push(Node{v[nx][i],nx});
dis[v[nx][i]]=dis[nx]+1;
}else{
if(nfa!=v[nx][i]){
minn=min(minn,dis[nx]+dis[v[nx][i]]+1);
}
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=1;i<=n;i++){
bfs(i);
memset(f,0,sizeof(f));
memset(dis,0,sizeof(dis));
}
if(minn==1e9+5){
cout<<-1;
}else{
cout<<minn;
}
return 0;
}10.树
1. 根节点：树结构的顶层节点，没有父节点的节点。
2. 子节点：具有父节点的节点，从父节点延伸出来的节点。
3. 叶节点：没有子节点的节点，也可以称为终端节点。
4. 父节点：具有子节点的节点。
5. 兄弟节点：具有相同父节点的节点。
6. 祖先节点：某个节点的父节点、父节点的父节点等等。
7. 子树：以某个节点为根节点的所有节点的集合，包括该节点本身及
其后代节点。
8. 层级：树中节点所处的层数，根节点为第一层，其子节点为第二层，
依此类推。
9. 深度：树中节点到根节点的最长路径所经过的边数，又称为树的高
度。
10. 平衡树：具有较为平衡的左子树和右子树的树结构，以提高查找、
插入和删除等操作的效率。
11. 二叉树：每个节点最多只有两个子节点的树结构。
12. 二叉搜索树：二叉树的一种特殊形式，左子节点的值小于等于父
节点的值，右子节点的值大于等于父节点的值。
13. 遍历：按照一定顺序访问树中的所有节点。
14. 先序遍历：先访问根节点，然后递归地先序遍历左子树，再递归
地先序遍历右子树。
15. 中序遍历：先递归地中序遍历左子树，然后访问根节点，最后递
归地中序遍历右子树。
16. 后序遍历：先递归地后序遍历左子树，然后递归地后序遍历右子
树，最后访问根节点。
17. 层序遍历：按层次顺序从上到下遍历树的节点，先访问根节点，
再按从左到右的顺序依次访问每一层的节点。
18. AVL树：平衡因子为-1、0或1的二叉搜索树，用于提高查找效率。
19. 红黑树：一种自平衡的二叉搜索树，用于提高插入、删除和查找
等操作的效率。
20. B树：一种自平衡的多路搜索树，用于存储大量的数据。例题1：《树的深度》
代码：
#include<bits/stdc++.h>
using namespace std;
int n,maxn=0;
bool t[1005][1005],f[1005];
void dfs(int x,int dep){
maxn=max(maxn,dep);
for(int i=1;i<=n;i++){
if(t[x][i]==1&&f[i]==0){
f[i]=1;
dfs(i,dep+1);
}
}
}
int main(){
cin>>n;
for(int i=2;i<=n;i++){
int x;
cin>>x;
t[x][i]=1;
t[i][x]=1;
}
f[1]=1;
dfs(1,1);
cout<<maxn;
return 0;
}例题2：《树的宽度》
代码：
#include<bits/stdc++.h>
using namespace std;
int n,maxn=-1e9;
int d[10005];
bool t[10005][10005],f[10005];
void dfs(int x,int dep){
maxn=max(maxn,dep++);
for(int i=1;i<=n;i++){
if(t[x][i]==1&&f[i]==0){
f[i]=1;
d[dep]++;
dfs(i,dep+1);
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
char c;
cin>>c;
t[i][j]=c-'0';
t[j][i]=c-'0';
}
}
f[1]=1;
dfs(1,1);
int maxx=-1e9;
for(int i=1;i<=n;i++){
maxx=max(maxx,d[i]);
}
cout<<maxx;
return 0;
}总结
失分点总结：
1.数组没仔细看大小，常开的过大或太小；
2.对于一些细节检查不出错；
3.对STL部分函数没有掌握；
4.对自己的代码不熟悉，容易打错；
5.学会了freopen收获：
1.掌握了许多原本不会的新算法，如：链表，STL数据结构，尺取差分前缀和，除01背包外的其他背包，深搜，动态规划，数论，图论，树