1.组队
思路：从每个位置可以选取的人选入手，每个人选不可重复，组合求最大。
方法一：深搜dfs
#include<bits/stdc++.h>
using namespace std;
int team[20][6],maxs=0,vis[20];
void dfs(int sum,int n) //sum为出场运动员的分数求和 n为目前要选择的号位
{
if(n==6)
{
if(sum>maxs)
maxs=sum;
return ;
}
for(int i=0;i<20;i++)
{
if(!vis[i])
{
vis[i]=1;
dfs(sum+team[i][n],n+1);
vis[i]=0;
}
}
}
int main()
{
freopen("201901.txt","r",stdin); //放在当前目录下面
for(int i=0;i<20;i++)
{
for(int j=0;j<6;j++)
cin>>team[i][j];
}
dfs(0,1); //因为下标0是运动员编号 所以从1开始dfs
cout<<maxs;
}方法二：多重循环
#include<bits/stdc++.h>
using namespace std;
int team[20][6],maxs=0,vis[20];
int main()
{
freopen("201901.txt","r",stdin); //放在当前目录下面
for(int i=0;i<20;i++)
{
for(int j=0;j<6;j++)
cin>>team[i][j];
}
for(int i=0;i<20;i++)
{
for(int j=0;j<20;j++)
{
for(int k=0;k<20;k++)
{
for(int l=0;l<20;l++)
{
for(int m=0;m<20;m++)
{
if(i!=j&&i!=k&&i!=l&&i!=m&&j!=k&&j!=l&&j!=m&&k!=l&&k!=m&&l!=m) //五个位置人员各不相同
{
int s=team[i][1]+team[j][2]+team[k][3]+team[l][4]+team[m][5];
if(s>maxs)
maxs=s;
}
}
}
}
}
}
cout<<maxs;
}2.年号字符
思路：模拟26进制转换过程，个人认为栈很符合这个思想
#include<bits/stdc++.h>
using namespace std;
stack<int> ans;
int main()
{
int n=2019;
while(n)
{
int t=n%26;
ans.push(t);
n/=26;
}
while(!ans.empty())
{
putchar('A'+ans.top()-1);
ans.pop();
}
return 0;
}3.数列求值
思路：模拟就好，没啥难的，注意取余就行
解法一：省内存，小动一下脑子
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[10]={1,1,1};
for(int i=3;i<20190324;i++)
{
a[3]=(a[0]+a[1]+a[2])%10000;
a[0]=a[1]%10000;
a[1]=a[2]%10000;
a[2]=a[3];
}
cout<<a[3];
return 0;
}解法二：开销大，很丝滑
#include<bits/stdc++.h>
using namespace std;
int a[20190324]={1,1,1};
int main()
{
for(int i=3;i<20190324;i++)
{
a[i]=(a[i-3]+a[i-2]+a[i-1])%10000;
}
cout<<a[20190323];
return 0;
}4.数的分解
思路：挺简单的，暴力就行，也没啥坑
方法一：多重for循环
#include<bits/stdc++.h>
using namespace std;
int ans=0;
bool check(int n)
{
while(n)
{
if(n%10==2||n%10==4)
return false;
n/=10;
}
return true;
}
int main()
{
int d=2019/3;
for(int i=1;i<=d;i++)
{
for(int j=i+1;j<=2*d;j++)
{
for(int k=j+1;k<2019;k++)
{
if(check(i)&&check(j)&&check(k)&&i+j+k==2019)
ans++;
}
}
}
cout<<ans;
}方法二：深搜dfs
#include<bits/stdc++.h>
using namespace std;
int ans=0,a[1100],count1=0;
void dfs(int sum,int n,int j)
{
if(n==3)
{
if(sum==2019)
ans++;
return ;
}
for(int i=j;i<count1;i++)
{
dfs(sum+a[i],n+1,i+1); //和加上当前下标值 个数+1 下一个数开始的下标=当前下标+1
}
}
int main()
{
for(int i=1;i<=2019;i++)
{
int flag=0,t=i;
while(t)
{
if(t%10==2||t%10==4)
{
flag=1;
break;
}
t/=10;
}
if(!flag)
a[count1++]=i;
}
dfs(0,0,0);
//前一个0代表此时和为0，第二个0代表目前总共有几个数 ，最后一个0记录“上一个已经用过的坐标 的下一个，即开始使用的第一个坐标”
cout<<ans;
}5.迷宫
思路：广搜常用于求最优化路径，注意点：a.路径相同输出ASCII码最小的，设置搜索顺序时按照ASCII由小到大即可；b.不用记录最短路径，只用记录每次的方向，因为第一个找到的值一定是最小的。深搜时，需要记录每次的方向和步数，因为第一次走到的不一定是步数最少的，注意点：得到结果比较时，<即可，=的话后面的字符串序列ASCII值更大。
解法一：bfs广搜
#include<bits/stdc++.h>
using namespace std;
char a[30][50];
int d[4][2]={{1,0},{0,-1},{0,1},{-1,0}}; //d,l,r,u
char dr[4]={'D','L','R','U'};
int vis[30][50];
struct node{
int x,y;
string str;
node(int xx,int yy,string ss) //构造函数
{
x=xx;
y=yy;
str=ss;
}
};
int MAP[30][50]{//迷宫
{0,1,0,1,0,1,0,1,0,0,1,0,1,1,0,0,1,0,0,1,0,1,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,0,1,0,0,0,1,0,1,0,1,0},
{0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,1,0,0,1,1,0,1,0,0,1,0,1},
{0,1,1,1,1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,0,0,0,1,1,0,1,0,0,1,0,1,1,1,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0},
{0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,1,1,0,1,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,1,0,0,1,0,1,1},
{0,0,0,1,1,1,1,1,0,0,0,0,0,0,1,0,1,0,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0},
{1,1,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,0,1,0,1,0,1,1,0,0,0,1,1,0,1,0,0,1,1,0,1,0,1,0,1,0,1,1,1,1,0,1,1,1},
{0,0,0,1,1,0,1,1,0,1,0,1,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,1,1,1,0,0,0,0,0,0,0},
{1,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,0,1,1,0,0,0,0,1,0,0,0,0,1,1,1,0,1,0},
{0,0,1,1,1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,1,1,0,0,0,0,1,0,0,1},
{1,1,0,0,0,1,1,0,1,0,0,0,0,1,1,1,0,0,1,0,0,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,1,0,1,0,0,0},
{0,0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,1,0,0,1,0,1,0,1,0,1,1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,1,0,1},
{1,1,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,1,0,0,1,0,0,0,1,0,1,0,0},
{0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,1,1,0,0,1,1,1,1,0,1,0,0,0,1,1,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,1,1},
{1,0,1,0,1,0,1,0,0,1,1,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,1,0,1,1,0,0,1,1,1,1,0,1,1,0,1,0,0,0,0,1,0,0,0},
{1,0,1,0,1,0,1,0,1,0,0,0,0,1,1,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,1,0,1,0,0,0,0,0,1,1,1,0,1,1,1,0,1,0,0,1},
{1,0,0,0,0,0,0,0,1,0,1,1,0,0,0,1,0,0,0,0,1,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,1,0,0,0,0,0,0,0,0,1,0,0},
{1,0,1,0,1,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,1,1,1,1,0,1,0,1,0,0,1},
{0,0,1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0,0,1,0,1,0,1,0,0,0,1,1,0,1,0,1,0,1,1,0,1,1,1,0,0,0,0,1,1,0,1,0,1},
{1,1,0,0,1,0,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,1,1,0,0,0,0,1,0},
{0,0,0,0,1,0,0,0,1,1,0,0,0,0,1,1,0,1,0,1,1,0,1,0,0,0,0,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0,1,1,1,0,1},
{1,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,1,1,1,0,1,1,0,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,0,0,0,0,1},
{0,0,1,0,1,0,0,0,0,1,0,0,0,0,1,1,0,1,0,1,0,1,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1},
{1,0,1,0,0,0,0,1,0,0,0,1,1,0,0,1,0,0,0,1,0,0,0,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,0,1,0},
{0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,1,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0},
{1,1,0,1,0,0,0,0,0,0,1,0,0,1,1,1,0,1,1,1,0,0,1,0,0,1,0,0,0,0,1,1,1,0,1,0,0,1,0,1,1,0,1,1,1,0,1,0,0,0},
{0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,1,1,1,0,1,0,0,0,0,0,0,1,1,0,0,1,1},
{1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,1,1,1,1,0,0,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0},
{1,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,1,0,0,0,0,0,0,0,1,0,0,1,0,1,0,1,0,0,0,1,0,1,1,1,0,1,0,0,0},
{0,0,1,1,1,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,1},
{1,0,0,0,0,0,0,1,1,0,0,1,1,1,0,1,0,1,1,1,0,1,0,0,0,1,0,0,0,1,1,0,1,1,1,0,1,0,1,0,1,1,0,1,1,1,1,0,0,0}
};
queue<node> q;
bool check(int tx,int ty) //检查下标是否越界，是否被访问过，是否有障碍
{
// cout<<tx<<" "<<ty<<" "<<vis[tx][ty]<<" "<<MAP[tx][ty]<<endl;
if(tx<0||tx>=30||ty<0||ty>=50||vis[tx][ty]||MAP[tx][ty]==1)
return false;
return true;
}
void bfs()
{
node no(0,0,"");
q.push(no);
vis[0][0]=1;
while(!q.empty())
{
node t=q.front();
if(t.x==29&&t.y==49) //到达右下角
{
cout<<t.str<<endl;
break;
}
q.pop();
for(int i=0;i<4;i++)
{
int tx=d[i][0]+t.x;
int ty=d[i][1]+t.y;
if(check(tx,ty))
{
q.push(node(tx,ty,t.str+dr[i]));
vis[tx][ty]=1;
}
}
}
}
int main()
{
// freopen("201901.txt","r",stdin);
// for(int i=0;i<50;i++)
// {
// for(int j=0;j<30;j++)
// cin>>a[i][j];
// }
bfs();
}解法二：深搜（目测代码没问题，但是因为深搜，数据又很大，很久没跑出来，有问题大家可以给我说，我的代码给大家一个参考）
#include<bits/stdc++.h>
using namespace std;
char a[30][50];
int d[4][2]={{1,0},{0,-1},{0,1},{-1,0}}; //d,l,r,u
char dr[4]={'D','L','R','U'};
int vis[30][50];
int minStep=1000;
string minStr;
int MAP[30][50]{//迷宫
{0,1,0,1,0,1,0,1,0,0,1,0,1,1,0,0,1,0,0,1,0,1,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,0,1,0,0,0,1,0,1,0,1,0},
{0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,1,0,0,1,1,0,1,0,0,1,0,1},
{0,1,1,1,1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,0,0,0,1,1,0,1,0,0,1,0,1,1,1,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0},
{0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,1,1,0,1,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,1,0,0,1,0,1,1},
{0,0,0,1,1,1,1,1,0,0,0,0,0,0,1,0,1,0,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0},
{1,1,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,0,1,0,1,0,1,1,0,0,0,1,1,0,1,0,0,1,1,0,1,0,1,0,1,0,1,1,1,1,0,1,1,1},
{0,0,0,1,1,0,1,1,0,1,0,1,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,1,1,1,0,0,0,0,0,0,0},
{1,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,0,1,1,0,0,0,0,1,0,0,0,0,1,1,1,0,1,0},
{0,0,1,1,1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,1,1,0,0,0,0,1,0,0,1},
{1,1,0,0,0,1,1,0,1,0,0,0,0,1,1,1,0,0,1,0,0,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,1,0,1,0,0,0},
{0,0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,1,0,0,1,0,1,0,1,0,1,1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,1,0,1},
{1,1,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,1,0,0,1,0,0,0,1,0,1,0,0},
{0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,1,1,0,0,1,1,1,1,0,1,0,0,0,1,1,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,1,1},
{1,0,1,0,1,0,1,0,0,1,1,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,1,0,1,1,0,0,1,1,1,1,0,1,1,0,1,0,0,0,0,1,0,0,0},
{1,0,1,0,1,0,1,0,1,0,0,0,0,1,1,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,1,0,1,0,0,0,0,0,1,1,1,0,1,1,1,0,1,0,0,1},
{1,0,0,0,0,0,0,0,1,0,1,1,0,0,0,1,0,0,0,0,1,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,1,0,0,0,0,0,0,0,0,1,0,0},
{1,0,1,0,1,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,1,1,1,1,0,1,0,1,0,0,1},
{0,0,1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0,0,1,0,1,0,1,0,0,0,1,1,0,1,0,1,0,1,1,0,1,1,1,0,0,0,0,1,1,0,1,0,1},
{1,1,0,0,1,0,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,1,1,0,0,0,0,1,0},
{0,0,0,0,1,0,0,0,1,1,0,0,0,0,1,1,0,1,0,1,1,0,1,0,0,0,0,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0,1,1,1,0,1},
{1,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,1,1,1,0,1,1,0,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,0,0,0,0,1},
{0,0,1,0,1,0,0,0,0,1,0,0,0,0,1,1,0,1,0,1,0,1,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1},
{1,0,1,0,0,0,0,1,0,0,0,1,1,0,0,1,0,0,0,1,0,0,0,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,0,1,0},
{0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,1,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0},
{1,1,0,1,0,0,0,0,0,0,1,0,0,1,1,1,0,1,1,1,0,0,1,0,0,1,0,0,0,0,1,1,1,0,1,0,0,1,0,1,1,0,1,1,1,0,1,0,0,0},
{0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,1,1,1,0,1,0,0,0,0,0,0,1,1,0,0,1,1},
{1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,1,1,1,1,0,0,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0},
{1,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,1,0,0,0,0,0,0,0,1,0,0,1,0,1,0,1,0,0,0,1,0,1,1,1,0,1,0,0,0},
{0,0,1,1,1,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,1},
{1,0,0,0,0,0,0,1,1,0,0,1,1,1,0,1,0,1,1,1,0,1,0,0,0,1,0,0,0,1,1,0,1,1,1,0,1,0,1,0,1,1,0,1,1,1,1,0,0,0}
};
bool check(int tx,int ty) //检查下标是否越界，是否被访问过，是否有障碍
{
if(tx<0||tx>=30||ty<0||ty>=50||vis[tx][ty]||MAP[tx][ty]==1)
return false;
return true;
}
void dfs(int x,int y,int step,string str)
{
// cout<<x<<" "<<y<<" "<<step<<" "<<str<<endl;
if(x<0||x>=30||y<0||y>=30||step>=minStep)
return;
if(x==29&&y==49)
{
if(step<minStep)
{
minStep=step;
minStr=str;
cout<<minStep<<" "<<minStr<<endl;
}
return ;
}
for(int i=0;i<4;i++)
{
int tx=x+d[i][0];
int ty=y+d[i][1];
if(!vis[tx][ty]&&MAP[tx][ty]==0)
{
vis[tx][ty]=1;
dfs(tx,ty,step+1,str+dr[i]);
vis[tx][ty]=0;
}
}
}
int main()
{
dfs(0,0,0,"");
cout<<minStr;
}6.特别数的和
思路：很简单，模拟即可，也没坑
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,ans=0;
cin>>n;
for(int i=1;i<=n;i++)
{
int t=i;
int flag=0;
while(t)
{
if(t%10==0||t%10==2||t%10==1||t%10==9)
{
flag=1;
break;
}
t/=10;
}
if(flag)
ans+=i;
}
cout<<ans;
}7.完全二叉树的权值
思路：考察二叉树的性质，只要知道二叉树的每层的节点数是，那就很好办，或者意识到每层的节点个数是1，2，4，....直到最后一层特别判断就好。
#include<bits/stdc++.h>
using namespace std;
int t;
int main(){
int N;
int deep = 1; //深度
long long sum = 0; //每行的和
long long max_sum = INT_MIN; //最大的和
int max_deep = 1;
cin>>N;
for(int i = 1; i <= N; ++i){
cin>>t;
sum += t;
if(i == pow(2, deep) - 1){
if(max_sum < sum){ //注意不要取等号，因为题目要最小的深度
max_deep = deep;
max_sum = sum;
}
sum = 0;
++deep;
continue;
}
if(i==N) //需要特判一下 如果不是满二叉树但是最后一层的值更大的话结果就不对
{
if(max_sum < sum){
max_deep = deep;
max_sum = sum;
}
}
}
cout<<max_deep<<endl;
return 0;
}8.等差数列
思路： 明确等差是相邻两个数的差值，但并不是最小的那个差值就是最后要求的等差值，因为另外比他大的等差值可能没它大，但是他俩最大公约数为1，意味着这样求出来的等差数列肯定是错的。进而就能想到所有相邻数的差值的最大公约数即为整个序列的公差，那么序列的长度=(max-min)/公差+1.
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int A[N];
int n;
int gcd(int a,int b) //求最大公约数
{
while(b)
{
int t=a%b;
a=b;
b=t;
}
return a;
}
int main(){
cin>>n;
for(int i=0;i<n;i++)
scanf("%d",&A[i]);
sort(A,A+n); //排序后方便比较
int md=A[1]-A[0];
if(md==0) //这种情况是所有数相等 输出数的个数即可
{
cout<<n<<endl;
return 0;
}
for(int i=2;i<n;i++) //求所有相邻数插值的最大公约数
{
int t=A[i]-A[i-1];
t=gcd(t,md);
if(t<md)
md=t;
}
cout<<(A[n-1]-A[0])/md+1<<endl;
return 0;
}9.后缀表达式
思路：
- 没有减号，直接求和。
- 有减号的情况：
如果有负数存在的话：
- 如果负数的个数num不等于n+m+1的话，我们是可以通过加括号的形式，将所有的减号变为加号的。-5 -4 -3 -2 1,+++-,1-(
- 如果负数的个数num等于n+m+1的话，肯定会留出一个负数来，无法通过加括号的形式变为正的，那么就只能加上这个负数，贪心去想，肯定是负数中最大的那个(绝对值最小的那个)。-5 -4 -3 -2 -1,+++-,-1-()，，，++--，
-1-（（-5+（-4）+（-3））-（-2）
如果说没有负数的话，那么只能减去最小的那个数，剩下的就可以通过加括号的形式变为加了。如，1，2,3,4,5，两个+，两个-，则为5+4+3-（1-2）
1,2,3,4,5 +++-,2+3+4+5-1
1,2,3,4,5 +---,5+4-（1-2-3）
坑点：注意数组开2e5+100, 因为N or M小于1e5，两个加起来开小了数组会越界；另外计算的时候注意负数相加的个数。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX=2e5+100;
int N,M,num;
int A[MAX];
LL sum=0;
int main(){
cin>>N>>M;
for(int i=0;i<=N+M;i++)
{
scanf("%d",&A[i]);
sum+=A[i];
if(A[i]<0)
num++; //记录负数的个数
}
sort(A,A+N+M+1);
if(M==0) //全是+
{
cout<<sum<<endl;
return 0;
}
// 存在-
// 分为两大类： 1.有负数：a.负数的数目等于N+M+1（即全负数）,绝对值求和+2*最大的负数 ；b.负数个数小于N+M+1，将所有的数绝对值求和
// 2.无负数：所有的数求和-2*最小数
if(num) //存在-
{
if(num==N+M+1) //全为负数
{
for(int i=0;i<N+M;i++)
sum-=2*A[i];
}
else //存在正数
{
for(int i=0;i<num;i++)
sum-=2*A[i];
}
}
else //存在-且全为负数
{
sum-=2*(A[0]);
}
cout<<sum;
return 0;
}10.灵能传输
思路：前缀和+排序+贪心，详情思路请见yxc的视频，我只能说yyds
坑点：暂存s0和sn时别忘了用LL，不然会溢出，另外注意处理f数组的顺序
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX=3e5+10;
int T;
LL a[MAX];
LL s[MAX],f[MAX];
bool st[MAX];
int main(){
cin>>T;
while(T--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
s[i]=s[i-1]+a[i]; //计算前缀和
}
LL s0=s[0],sn=s[n];
if(s0>sn)
swap(s0,sn);
sort(s,s+n+1);
for(int i=0;i<=n;i++) //确定s0排序后的位置
{
if(s0==s[i])
{
s0=i;
break;
}
}
for(int i=n;i>=0;i--) //确定sn排序后的位置 从右往左是保证sn一定在s0右边 即使两数相等
{
if(sn==s[i])
{
sn=i;
break;
}
}
memset(st,false,sizeof st); //用st数组标记哪些数字已经走过
int l=0,r=n;
for(int i=s0;i>=0;i-=2) //从s0往左跳
{
f[l++]=s[i];
st[i]=true;
}
for(int i=sn;i<=n;i+=2) //从sn往右跳
{
f[r--]=s[i];
st[i]=true;
}
for(int i=0;i<=n;i++)
{
if(st[i]==false)
{
f[l++]=s[i];
}
}
LL ans=0;
for(int i=1;i<=n;i++)
{
ans=max(abs(f[i]-f[i-1]),ans);
}
cout<<ans<<endl;
}
return 0;
}