8.26算法训练
1.八皇后 Checker Challenge
输入：
6
输出：
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（生成排列）
输入：
3
1
2
3
思路：由例子可知道，偶然数的时候一定为-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;
}6.Guess The Tree（ 猜树）
输入：
1
4
1
1
3思路：
AC: