最近蓝桥杯官网已经把十五届题目上架了，我会尽快的将题解发出来，没有发的过段时间再补。
数字接龙
一个很鹅心的搜索题，一不注意就会写错，比赛的时候写不来，题目上架后也WA了两个样例才过。
题目大意：
也就是说从(1,1)开始 ，下一步路的数据总是要比当前数据大1，超过k就取模，然后还不能交叉走路，如第四点所说，一个田字格里面，从1走到3后，便不能从2到4，也不能从4到2，每个格子只能走一次。
思路：
由于数据比较小，而且还有特判不能多走，所以可以选择暴力搜索，具体细节很多，从代码里面慢慢理解就行。
代码：
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<stack>
#include<numeric>
#include<stdlib.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7, N = 2e5 + 5, inf = 2e18;
int n, k;
int a[15][15];
bool vis[15][15];
bool ban[15][15][15][15];//禁止通行
int xx[] = {-1, -1, 0, 1, 1, 1, 0, -1};//路径
int yy[] = {0, 1, 1, 1, 0, -1, -1, -1};
string ans = "9";
bool in_map(int x, int y) {
if (x <= n && x >= 1 && y <= n && y >= 1)return true;
return false;
}
void dfs(int x, int y, int cnt, string teep) {
if (x == n && y == n && teep.size() == n * n - 1) {
ans = min(ans, teep);
return ;
}
//cout<<1;
//cout << teep << '\n';
for (int i = 0; i < 8; i++) {
int nx = x + xx[i], ny = y + yy[i];
//不在地图
if (!in_map(nx, ny))continue;
//数据不符合
if (a[nx][ny] != (cnt + 1) % k)continue;
//走过了
if (vis[nx][ny])continue;
if (i & 1) { //斜着走
if (i == 1 && !ban[x][y + 1][x - 1][y] && !ban[x - 1][y][x][y + 1]) { //没有禁令
vis[nx][ny] = true;
ban[x][y + 1][x - 1][y] = ban[x - 1][y][x][y + 1] = true;
ban[x][y][nx][ny]=ban[nx][ny][x][y]=true;
string new_teep = teep;
teep += ('0' + i); //不太会转换
dfs(nx, ny, a[nx][ny], teep);
teep = new_teep;
//回溯
ban[x][y][nx][ny]=ban[nx][ny][x][y]=false;
ban[x][y + 1][x - 1][y] = ban[x - 1][y][x][y + 1] = false;
vis[nx][ny] = false;
} else if (i == 3 && !ban[x + 1][y][x][y + 1] && !ban[x][y + 1][x + 1][y]) {
vis[nx][ny] = true;
ban[x + 1][y][x][y + 1] = ban[x][y + 1][x + 1][y] = true;
ban[x][y][nx][ny]=ban[nx][ny][x][y]=true;
string new_teep = teep;
teep += ('0' + i); //不太会转换
dfs(nx, ny, a[nx][ny], teep);
teep = new_teep;
//回溯
ban[x][y][nx][ny]=ban[nx][ny][x][y]=false;
ban[x + 1][y][x][y + 1] = ban[x][y + 1][x + 1][y] = false;
vis[nx][ny] = false;
} else if (i == 5 && !ban[x][y - 1][x + 1][y] && !ban[x + 1][y][x][y - 1]) {
vis[nx][ny] = true;
ban[x][y - 1][x + 1][y] = ban[x + 1][y][x][y - 1] = true;
ban[x][y][nx][ny]=ban[nx][ny][x][y]=true;
string new_teep = teep;
teep += ('0' + i); //不太会转换
dfs(nx, ny, a[nx][ny], teep);
teep = new_teep;
//回溯
ban[x][y][nx][ny]=ban[nx][ny][x][y]=false;
ban[x][y - 1][x + 1][y] = ban[x + 1][y][x][y - 1] = false;
vis[nx][ny] = false;
} else if (i == 7 && !ban[x][y - 1][x - 1][y] && !ban[x - 1][y][x][y - 1]) {
vis[nx][ny] = true;
ban[x][y - 1][x - 1][y] = ban[x - 1][y][x][y - 1] = true;
ban[x][y][nx][ny]=ban[nx][ny][x][y]=true;
string new_teep = teep;
teep += ('0' + i); //不太会转换
dfs(nx, ny, a[nx][ny], teep);
//回溯
teep = new_teep;
ban[x][y][nx][ny]=ban[nx][ny][x][y]=false;
ban[x][y - 1][x - 1][y] = ban[x - 1][y][x][y - 1] = false;
vis[nx][ny] = false;
}
} else { //横着走
vis[nx][ny] = true;
string new_teep = teep;
teep += ('0' + i); //不太会转换
dfs(nx, ny, a[nx][ny], teep);
teep = new_teep;
vis[nx][ny] = false;
}
}
}
void solve() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
string x = "";
vis[1][1] = true;
dfs(1, 1, a[1][1], x);
cout << (ans == "9" ? "-1" : ans) << '\n';
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}握手问题
题目大意：
总共有 5050 人参加了本次会议。每个人要与其他人都握手一次，问至少握手多少次。
思路：
写一个二维数组，双重循环遍历，i与j握手后将数组a[i][j]标记为1，数组a[j][i]标记为2，如果a[i][j]已经是2了，就不用更改为1了，最后再遍历一次，输出1的个数就行。
代码：
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<stack>
#include<numeric>
#include<stdlib.h>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7, N = 2e5 + 5, inf = 2e18;
void solve() {
cout<<1204;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}