掌握贪心、分治、深度优先搜索、广度优先搜索、简单的线性动态规划算法。
红与黑 连通性问题：
#include<iostream>
#include<cstring>
using namespace std;
int n,m,v[30][30],d[8][2]={{0,1},{1,0},{0,-1},{-1,0}},sx,sy,cnt=0;
char a[30][30];
void dfs(int x,int y){
for(int i=0;i<=3;i++){
int nx=x+d[i][0],ny=y+d[i][1];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!='#'&&v[nx][ny]==0){
v[nx][ny]=1;
cnt++; //计数
dfs(nx,ny);
}
}
}
int main() {
while(cin>>m>>n){ //n行m列
if(m==0&&n==0) break;
memset(a,0,sizeof(a)); //初始化
memset(v,0,sizeof(v));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]=='@'){
sx=i;sy=j;
}
}
}
cnt=1; //起点也要算1个
v[sx][sy]=1;
dfs(sx,sy);
cout<<cnt<<endl;
}
return 0;
} BFS同样可以解决连通性问题。
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int n,m,v[30][30],sx,sy,d[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
char a[30][30];
struct point{
int x,y;
};
int bfs(){
memset(v,0,sizeof(v)); //初始化v数组
int ans=0;
queue<point> q; //队列
point p;p.x=sx;p.y=sy;v[sx][sy]=1;
q.push(p); //头结点入队
while(!q.empty()){
point p=q.front();ans++;q.pop();//出队，ans记录出队次数
for(int i=0;i<=3;i++){ //扩展上下左右四个方向
point pp;
pp.x=p.x+d[i][0];pp.y=p.y+d[i][1];
if(pp.x>=1&&pp.x<=n&&pp.y>=1&&pp.y<=m&&a[pp.x][pp.y]=='.'&&v[pp.x][pp.y]==0){
v[pp.x][pp.y]=1; //标记
q.push(pp); //入队
}
}
}
return ans; //走过的结点的数量
}
int main(){
while(cin>>m>>n){ //注意行列是反的
if(n==0&&m==0) break;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]=='@'){
sx=i;sy=j;
}
}
}
cout<<bfs()<<endl;
}
return 0;
}密室逃脱 多轮广搜：
第一轮，起点(1,1)，终点的为值比1大一点的数字；
第二轮，起点是第一轮终点的坐标，终点数字递增；以此类推，直到走到矩阵中最大的数字。每一轮通过BFS计算该轮的最小步数，累加。
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int t,n,m,v[110][110],d[4][2]={{0,1},{0,-1},{-1,0},{1,0}},mx;
int a[110][110];
struct point{
int x,y,step,v;
}b[10010];
int bfs(int sx,int sy,int ex,int ey){
memset(v,0,sizeof(v)); //初始化v数组
queue<point> q; //队列
point p;p.x=sx;p.y=sy;p.step=0;v[sx][sy]=1; //起点入队
q.push(p); //头结点入队
while(!q.empty()){
point p=q.front();q.pop();//出队，ans记录出队次数
if(p.x==ex&&p.y==ey){
return p.step;
}
for(int i=0;i<=3;i++){ //扩展上下左右四个方向
point pp;
pp.x=p.x+d[i][0];pp.y=p.y+d[i][1];pp.step=p.step+1;
if(pp.x>=1&&pp.x<=n&&pp.y>=1&&pp.y<=m&&a[pp.x][pp.y]>0&&v[pp.x][pp.y]==0){
v[pp.x][pp.y]=1; //标记
q.push(pp); //入队
}
}
}
return -1; //走不到ex,ey则返回-1
}
int main(){
cin>>t;
while(t--){
cin>>n>>m;
mx=-1;
memset(b,0,sizeof(b)); //初始化b数组
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
b[a[i][j]].x=i;b[a[i][j]].y=j;b[a[i][j]].v=1;
mx=max(mx,a[i][j]);
}
}
int sx=1,sy=1,ans=0; //起点为1,1 ,初始走了0步
for(int i=2;i<=mx;i++){
if(b[i].v){//密码数字存在，则作为广搜终点走一次
int ex=b[i].x,ey=b[i].y;
int r=bfs(sx,sy,ex,ey);//广搜多次，从小搜到最大的数字
if(r==-1){ //只要有一个数字走不到，那就走不通
ans=-1;
break;
}else{
ans+=r;
}
sx=ex;sy=ey; //终点变起点，继续解密下一个数字
}
}
cout<<ans<<endl;
}
return 0;
}最小新整数
贪心策略：先消除第一个从前往后单调递增的最高点（最大数字）。
#include<iostream>
#include<string>
using namespace std;
int main(){
string s;
int n,t;
cin>>t;
while(t--){
cin>>s>>n;
int len=s.size();
while(n--){
for(int i=0;s[i]!='\0';i++){ //字符串结束的位置停止
if(s[i]>s[i+1]){ //贪心，先消除从前往后单调递增的最高点
s.erase(i,1);
break;
}
}
}
cout<<s<<endl;
}
return 0;
} 计算逆序数
归并排序：在合并的过程中，计算逆序对个数并累加起来
#include<iostream>
#include<string>
using namespace std;
int a[100010],n,b[100010],ans=0;
void merge(int a[],int s,int m,int e,int b[]){ //合并数据
int l=s,r=m+1,i=s;
while(l<=m&&r<=e){
if(a[l]>a[r]){ //在该条件里面，计算逆序对
ans+=e-r+1; //a[l]与右侧r~e的所有数字组成逆序对
b[i]=a[l]; //a[l]并入b数组
l++;i++;
}else{
b[i]=a[r]; //a[r]并入b数组
r++;i++;
}
}
while(l<=m){ //继续并入
b[i]=a[l];l++;i++;
}
while(r<=e){ //继续并入
b[i]=a[r];r++;i++;
}
for(int i=s;i<=e;i++){
a[i]=b[i]; //回填到a数组
}
return;
}
void msort(int a[],int s,int e,int b[]){
if(s>=e) return ;
int m=(s+e)/2; //分治，前半段s~m，后半段m+1~e
msort(a,s,m,b);
msort(a,m+1,e,b);
merge(a,s,m,e,b); //合并
return ;
}
int main(){
while(cin>>n){
if(n==0) break;
for(int i=1;i<=n;i++){
cin>>a[i];
}
ans=0;
msort(a,1,n,b); //利用归并排序计算逆序对
cout<<ans<<endl;
}
return 0;
} #include<iostream>
using namespace std;
int n,a[100010],b[100010],ans;
void msort(int s,int e){ //s起点 e终点
if(s>=e) return;
int mid=(s+e)/2; //一分为二
msort(s,mid); //左半部分 排序
msort(mid+1,e); //右半部分 排序
//合并：左半部分 和 右半部分合并
int l=s,r=mid+1,i=s;
while(l<=mid&&r<=e){ //l->mid或者r->e，有一个数组先被合并完了
if(a[l]>a[r]){
ans+=e-r+1; //能够成逆序对的元素
b[i]=a[l];
i++;l++;
}else{
b[i]=a[r];
i++;r++;
}
}
while(l<=mid){ //左半部分还没有合并完
b[i]=a[l];
i++;l++;
}
while(r<=e){ //右半部分还没有合并完
b[i]=a[r];
i++;r++;
}
for(int i=s;i<=e;i++){
a[i]=b[i]; //将合并后的结果回写到数组a
}
}
int main(){
while(cin>>n){
if(n==0) break;
for(int i=1;i<=n;i++){
cin>>a[i];
}
ans=0;
msort(1,n); //将a数组的第1个~第n个元素排序
cout<<ans<<endl;
}
return 0;
}圣诞老人的礼物
贪心策略：性价比从高到底排列，然后从前往后选价值最大。
#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
struct node{
double vi,wi,di; //di为单价
}a[110];
bool cmp(node n1,node n2){
return n1.di>n2.di; //单价从大到小排列
}
int n;
double w,tv=0;
int main(){
cin>>n>>w;
for(int i=1;i<=n;i++){
cin>>a[i].vi>>a[i].wi;
a[i].di=a[i].vi/a[i].wi; //计算单价
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
if(a[i].wi>w){
tv+=w*a[i].di; //w全部取，可能会拆开取
break;
}else{
tv+=a[i].vi; //vi全部取走
w-=a[i].wi; //减去相应的容量
}
}
cout<<setprecision(1)<<fixed<<tv;
return 0;
} 忍者道具
DFS：每个物品既可以放在一个已有的背包里，也可以开一个新的背包存放。
#include<iostream>
using namespace std;
int a[20],bag[20],ans=20;
int n,w;
void dfs(int x,int sum){ //正在放第x个物品，已经用了sum个背包
if(sum>=ans) return; //背包数量大于前面算过的ans，没必要继续计算
if(x==n+1){ //物品放完，看看背包数量是不是最小的
ans=min(ans,sum);
return;
}
for(int i=1; i<=sum;i++){ //尝试放在已有sum个背包里，每个都试试
if(bag[i]>=a[x]){ //背包容量够，就可以试着放
bag[i]-=a[x]; //放
dfs(x+1,sum); //尝试第x+1个物品
bag[i]+=a[x]; //回溯
}
}
bag[sum+1]-=a[x]; //尝试新开一个背包
dfs(x+1, sum+1); //尝试第x+1个物品，已经用了sum+1个背包
bag[sum+1]+=a[x]; //回溯
}
int main(){
cin>>n>>w;
for(int i = 1; i <= n; i++){
cin>>a[i];
bag[i] = w; //准备n个背包，每个背包容量是w
}
dfs(1, 1); //尝试第一个物品，已经用了1个背包
cout<<ans<<endl; //最少使用背包数量
return 0;
}