8.26算法训练

本文主要是介绍8.26算法训练，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.八皇后 Checker Challenge

输入：

输出：

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

是以前寒假写过的题目，所以有的影响，大致思路就是用深度遍历然后判断是否在对角线上就ok了，有大概思路的话，还是不难的。

AC:

#include<bits/stdc++.h>
using namespace std;
int sum=0,n;
int a[50],b[50];
int fun(int x,int y) {                     //判断是否在对角线上，正方形所以判断长是否对于宽就行了for(int i=1; i<x; i++) {int sj=abs(y-a[i]),sg=x-i;if(sj==sg)return 0;}return 1;
}
void fds(int m) {if(m>n) {if(sum<3) {                           //输出合格的前三个（因为n大于等于6，所以不用考虑无合格数据出现的情况）for(int i=1; i<m; i++)cout<<a[i]<<" ";cout<<endl;}sum++;                        //点数++} else {for(int i=1; i<=n; i++) {a[m]=i;if(b[i]==0) {                     //继续遍历b[i]=1;if(fun(m,i))fds(m+1);b[i]=0;}}}}
int main() {cin>>n;fds(1);cout<<sum;return 0;
}

2.Labyrinth（迷宫）

输入1：

4 5
3 2
1 2
.....
.***.
...**
*....

输入2：

4 4
2 2
0 1
....
..*.
....
....

一开始思路就错了，然后卡了两边测试5，后面理清大概思路，然后套用一下模板也是能写出来的（平时写题写少了，然后看到题目没有仔细去思考用什么方法，然后加入误区）这里也是一个队列加广度遍历就ok了。

AC：

#include<bits/stdc++.h>
using namespace std;
int n,m,r,c,x,y;
char s[2010][2010];
bool vis[2010][2010];
int xx[4]= {1,-1,0,-0};
int yy[4]= {0,0,-1,1};
int ans;
struct node {int x,y,l,r;//x,y表示当前坐标，l,r分别表示还能向左和向右走的步数
};
int main() {cin>>n>>m>>r>>c>>x>>y;for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {cin>>s[i][j];}}deque<node> q;//双端队列q.push_back((node) {r,c,x,y});while(!q.empty()) {node p;p=q.front();q.pop_front();if(vis[p.x][p.y]==1||(p.l<0)||(p.r<0)) continue;vis[p.x][p.y]=1;ans++;for(int i=0; i<4; i++) {int dx=p.x+xx[i];int dy=p.y+yy[i];if(dx<=0||dx>n||dy<=0||dy>m||s[dx][dy]=='*'||vis[dx][dy]==1) continue;if(i==0||i==1) {q.push_front((node) {dx,dy,p.l,p.r});continue;}if(i==2) {q.push_back((node) {dx,dy,p.l-1,p.r});continue;}if(i==3) {q.push_back((node) {dx,dy,p.l,p.r-1});}}}cout<<ans;return 0;
}

3.滑雪

输入：

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

思路：不知道大佬怎么想的，反正这里我是先想着最费时间的方法，就是一个一个dfs遍历，然后再一个一个比较，当时想的是，如果时间不过关的话在想其他的方法。而且因为前两道是搜索，所以这个一开始也是先想的搜索。

AC:

#include<bits/stdc++.h>
using namespace std;
int dx[4]= {0,0,1,-1};
int dy[4]= {1,-1,0,0};
int n,m,a[201][201],s[201][201],ans;
bool use[201][201];
int dfs(int x,int y) {if(s[x][y])return s[x][y];s[x][y]=1;                         //题目中答案是有包含这个点的for(int i=0; i<4; i++) {int xx=dx[i]+x;int yy=dy[i]+y;if(xx>0&&yy>0&&xx<=n&&yy<=m&&a[x][y]>a[xx][yy]) {dfs(xx,yy);s[x][y]=max(s[x][y],s[xx][yy]+1);}}return s[x][y];
}
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++)ans=max(ans,dfs(i,j));cout<<ans;return 0;
}

4.Make All Equal（使所有均相等）

输入：

7
1
1
3
1 2 3
3
1 2 2
5
5 4 3 2 1
6
1 1 2 2 3 3
8
8 7 6 3 8 7 6 3
6
1 1 4 5 1 4

思路：有点看不懂，但是感觉又看的懂，就是往（n-最多次出现的数）的这个思路想，我反正是没怎么看懂题目的，但是我感觉应该是这样，然后就AC了，就ok了,总而言之，我觉得这题有点抽象。

AC：

#include<bits/stdc++.h>
using namespace std;
int t,n,m,ans,num;
int a[505],b[505];
int main() {cin>>t;while(t--) {ans=0;memset(b,0,sizeof(b));cin>>n;for(int i=1; i<=n; i++) {cin>>a[i];b[a[i]]++,ans=max(ans,b[a[i]]);}//	cout<<endl<<ans<<" "<<n<<endl;cout<<n-ans<<endl;}return 0;
}

5.Generate Permutation（生成排列）

输入：

思路：由例子可知道，偶然数的时候一定为-1，可以写多组案例自己测试一下，然后就看奇数了，然后自己在草稿本上多写几组数据进行观察，会发现奇数最快的情况，也就是所需要的最小回车数就是两台机器都从两边开始，次数是最快的，很明显这是个思维题，然后打印数据即可。

AC：

#include<bits/stdc++.h>
using namespace std;
int t,n,m,ans,num;
int a[505],b[505];
int main() {cin>>t;while(t--) {cin>>n;if (n%2==0) cout<<"-1"<<endl;else {for (int i = 1; i < (n+1)/2; ++i) cout<<i<<' ';for (int i = n; i >= (n+1)/2 ; --i) cout<<i<<' ';cout<<endl;}}return 0;
}

5.Moving Chips（移动筹码）

输入：

5
8
0 1 1 1 0 1 1 0
6
0 1 0 0 0 0
6
1 1 1 1 1 1
5
1 0 1 0 1
9
0 1 1 0 0 0 1 1 0

思路：多写几个例子就知道只要找到所有1之间有多少个o就行了。

AC:

#include<bits/stdc++.h>
using namespace std;
int t,n,m,ans=0,num;
int a[505];
int main() {cin>>t;while(t--) {m=0,ans=0,num=0;cin>>n;for(int i=1; i<=n; i++) {cin>>a[i];if(a[i]==1)m=1;               //碰到第一个1才开始判断if(m) {if(a[i]==0)num++;else {ans+=num;//	cout<<ans<<" "<<num<<" "<<i<<endl;num=0;}}}//	cout<<endl<<ans<<endl<<endl;cout<<ans<<endl;}return 0;
}