蓝桥杯练习题—

1.八皇后 Checker Challenge

题目链接
注意数组空间要开大点，防止对角线数组存不下

#include<iostream>
#include<cstring>
using namespace std;
const int N = 50;
int a[N];
int st1[N], st2[N], st3[N];
int n, cnt;// 行数 
void dfs(int u){if(u > n){cnt++;if(cnt <= 3){for(int i = 1; i <= n; i++) printf("%d ", a[i]);printf("\n");}return;}for(int i = 1; i <= n; i++){if(!st1[i] && !st2[u + i] && !st3[n - u + i]){st1[i] = 1;st2[u + i] = 1;st3[n - u + i] = 1;a[u] = i;dfs(u + 1);st1[i] = 0;st2[u + i] = 0;st3[n - u + i] = 0;}}
}int main(){scanf("%d", &n);dfs(1);printf("%d", cnt);return 0;
}

2.kkksc03考前临时抱佛脚

指数型枚举每道题交给哪个脑子解决

#include<iostream>
#include<cstring>
using namespace std;
const int N = 50;
int a[N][N], b[N];
int l, r;
int res, ans;void dfs(int pos, int u){if(u > b[pos]){res = min(res, max(l, r));return;}l += a[pos][u];dfs(pos, u + 1);l -= a[pos][u];r += a[pos][u];dfs(pos, u + 1);r -= a[pos][u];
}int main(){for(int i = 1; i <= 4; i++) scanf("%d", &b[i]);for(int i = 1; i <= 4; i++){l = 0, r = 0, res = 1e9;for(int j = 1; j <= b[i]; j++){scanf("%d", &a[i][j]);}dfs(i, 0);ans += res;}printf("%d", ans);return 0;
}

01 背包，一个物品只会被用一次，求一半容量背包最多能装多少物品，然后最短花费时间就是总容量减去一半容量最多能装的物品，sum - f[sum / 2]

#include<iostream>
#include<cstring>
using namespace std;
const int N = 50;
int a[N], b[N];
int f[1500];
int ans;int main(){for(int i = 1; i <= 4; i++) scanf("%d", &b[i]);for(int i = 1; i <= 4; i++){int sum = 0;memset(f, 0, sizeof(f));for(int j = 1; j <= b[i]; j++){scanf("%d", &a[j]);sum += a[j];}for(int ii = 1; ii <= b[i]; ii++){for(int jj = sum / 2; jj >= a[ii]; jj--){f[jj] = max(f[jj], f[jj - a[ii]] + a[ii]);}}ans += sum - f[sum / 2];}printf("%d", ans);return 0;
}

3.马的遍历

注意是 it.first 和 it.second 操作，不要用成 x 和 y 了

#include<iostream>
#include<cstring>
using namespace std;
const int N = 500;
int g[N][N], st[N][N];
pair<int, int> q[N * N];
int hh = 0, tt = -1;
int n, m;int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};void bfs(int x, int y){q[++tt] = {x, y};st[x][y] = 0;while(hh <= tt){auto it = q[hh++];for(int i = 0; i < 8; i++){int a = it.first + dx[i], b = it.second + dy[i];if(a < 1 || a > n || b < 1 || b > m) continue;if(st[a][b] >= 0) continue;st[a][b] = st[it.first][it.second] + 1;q[++tt] = {a, b};}}
}int main(){memset(st, -1, sizeof(st));int x, y;scanf("%d%d%d%d", &n, &m, &x, &y);bfs(x, y);for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){printf("%d ", st[i][j]);}printf("\n");}return 0;
}

4.奇怪的电梯

#include<iostream>
#include<cstring>
using namespace std;
const int N = 300;
int q[N], st[N];
int hh = 0, tt = -1;
int c[N];
int n, A, B;void bfs(int x){q[++tt] = x;st[x] = 0;while(hh <= tt){int it = q[hh++];//cout<<it<<endl;int a = it + c[it], b = it - c[it];if(a <= n && st[a] == -1){st[a] = st[it] + 1;if(a == B) return;q[++tt] = a;}if(b >= 1 && st[b] == -1){st[b] = st[it] + 1;if(b == B) return;q[++tt] = b;}}
}int main(){memset(st, -1, sizeof(st));int x, y;scanf("%d%d%d", &n, &A, &B);for(int i = 1; i <= n; i++) scanf("%d", &c[i]);bfs(A);printf("%d", st[B]);return 0;
}

5.Meteor Shower S

结构体存储坐标、时间、步数、判重

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 1005;
int ans = -1;
struct Point{int x, y, t, step, vis;
}g[N][N];int dx[] = {0, 0, -1, 1, 0};
int dy[] = {-1, 1, 0, 0, 0};void bfs(int x, int y){queue<Point> q;g[x][y].vis = 1;g[x][y].step = 0;q.push(g[x][y]);while(q.size()){auto it = q.front();q.pop();for(int i = 0; i < 4; i++){int a = it.x + dx[i], b = it.y + dy[i];if(a < 0 || b < 0 || g[a][b].vis == 1) continue;if(g[a][b].t == -1){ans = it.step + 1;return;}if(it.step >= g[a][b].t - 1) continue;g[a][b].vis = 1;g[a][b].step = it.step + 1;q.push(g[a][b]);}}
}int main(){memset(g, -1, sizeof(g));int m, x, y, t;scanf("%d", &m);for(int i = 0; i <= 1000; i++){for(int j = 0; j <= 1000; j++){g[i][j].x = i;g[i][j].y = j;}}for(int i = 1; i <= m; i++){scanf("%d%d%d", &x, &y, &t);for(int j = 0; j < 5; j++){int a = x + dx[j], b = y + dy[j];if(a >= 0 && b >= 0 && (g[a][b].t == -1 || g[a][b].t > t)) g[a][b].t = t;}}bfs(0, 0);printf("%d", ans);return 0;
}

6.选数

#include<iostream>
using namespace std;
const int N = 5e6 + 10;
int a[N], b[N];
int n, k;
int cnt;int check(int x){if(x < 2) return 0;for(int i = 2; i <= x / i; i++){if(x % i == 0) return 0;}return 1;
}void dfs(int u, int st){if(u > k){int sum = 0;for(int i = 1; i < u; i++) sum += b[i];if(check(sum)) cnt++;return;}for(int i = st; i <= n; i++){b[u] = a[i];dfs(u + 1, i + 1);}
}int main(){scanf("%d%d", &n, &k);	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);dfs(1, 1);printf("%d", cnt);return 0;
}

7.PERKET

#include<iostream>
using namespace std;
const int N = 20;
int s[N], b[N], st[N];
int n, ans = 1e9;void dfs(int u){if(u > n){int res1 = 1, res2 = 0;for(int i = 1; i <= n; i++){if(st[i]){res1 *= s[i];res2 += b[i];}}if(res1 == 1 && res2 == 0) return;ans = min(ans, abs(res1 - res2));return;}// 不选st[u] = 0;dfs(u + 1);st[u] = 0;// 选st[u] = 1;dfs(u + 1);st[u] = 0; 
}int main(){scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d%d", &s[i], &b[i]);dfs(0);printf("%d", ans);return 0;
}