复兴提高班第十一课
2025-09-07 20:08:17
发布于：上海
1阅读
0回复
0点赞
T1棋盘
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; // 定义 long long 类型的别名为 ll
const ll N = 1e5 + 5; // 定义常量 N，用于数组大小等
const int _mod = 80112002; // 定义常量 _mod，可能用于某些模运算
int n, m, T; // n 是网格的大小，m 是输入的规则数量，T 没有用到
int s[105][105]; // 存储网格上的信息，值为 -1 表示未设置
int dp[105][105]; // dp 数组，存储从起点到每个位置的最短步数（或成本）
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 方向数组，用于表示上下左右四个方向
// 定义节点结构体，用于 BFS 中存储每个位置的状态
struct node {
int x, y, vis, ans; // x, y 是坐标，vis 表示之前访问的颜色，ans 是到达该位置的步数
};
// 定义节点的比较规则，按 ans 从小到大排序，最小的 ans 优先
bool operator<(node x, node y) {
return x.ans > y.ans; // 为了使优先队列从最小值开始处理
}
// 广度优先搜索（BFS）函数，计算从 (1, 1) 到 (n, n) 的最短路径
void bfs() {
priority_queue<node> q; // 使用优先队列来进行 BFS
int x, y, vis, ans, temp;
x = 1, y = 1, vis = -1, ans = 0; // 初始化起点 (1, 1)，vis = -1 表示无颜色限制，ans = 0 初始步数
dp[x][y] = ans; // 起点的步数为 0
q.push({x, y, vis, ans}); // 将起点加入队列
// BFS 主循环
while (!q.empty()) {
x = q.top().x; y = q.top().y; // 获取当前最优节点
vis = q.top().vis; ans = q.top().ans;
q.pop(); // 弹出当前节点
// 如果当前 dp[x][y] 已经比 ans 更小，跳过处理
if (dp[x][y] < ans) continue;
// 如果到达终点 (n, n)，输出结果并返回
if (x == n && y == n) {
cout << ans << endl;
return;
}
// 遍历四个方向
for (int i = 0; i < 4; i++) {
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if (xx < 1 || xx > n || yy < 1 || yy > n) continue; // 如果超出边界，跳过
int ans1;
// 如果目标位置没有预定的颜色（-1），则视为未设置颜色
if (s[xx][yy] == -1) {
if (vis != -1) continue; // 如果当前有颜色限制，且目标位置没有设置颜色，跳过
// 尝试将目标位置设置为不同的颜色
for (int j = 0; j <= 1; j++) {
ans1 = ans + 2; // 基础步数 + 2（因为我们更改了颜色）
if (s[x][y] != j) {
ans1++; // 如果当前颜色与目标颜色不一样，增加额外的步数
}
if (ans1 < dp[xx][yy]) { // 如果找到更优解，更新 dp 数组并将新节点加入队列
dp[xx][yy] = ans1;
q.push({xx, yy, j, ans1});
}
}
} else { // 如果目标位置已经设置了颜色
if (vis == -1) { // 如果当前没有颜色限制
if (s[xx][yy] == s[x][y]) { // 如果颜色相同，步数不变
ans1 = ans;
} else { // 如果颜色不同，增加 1 步
ans1 = ans + 1;
}
} else { // 如果有颜色限制
if (s[xx][yy] == vis) { // 如果颜色匹配，步数不变
ans1 = ans;
} else { // 如果颜色不匹配，增加 1 步
ans1 = ans + 1;
}
}
if (ans1 < dp[xx][yy]) { // 如果找到更优解，更新 dp 数组并将新节点加入队列
dp[xx][yy] = ans1;
q.push({xx, yy, -1, ans1}); // 设 vis = -1，表示没有颜色限制
}
}
}
}
cout << "-1" << endl; // 如果无法到达终点，输出 -1
}
int main() {
// freopen("test.in", "r", stdin); // 可以用于文件输入
// freopen("test.out", "w", stdout); // 可以用于文件输出
cin >> n >> m; // 输入网格大小 n 和规则数量 m
// 初始化网格和 dp 数组
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
s[i][j] = -1; // 默认设置网格没有颜色
dp[i][j] = 20005; // 设置一个较大的初始值
}
}
// 输入规则，设置网格上的颜色
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c; // 输入颜色规则
s[a][b] = c; // 设置网格位置的颜色
}
bfs(); // 执行 BFS 寻找最短路径
return 0;
}
T2宝物筛选
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 5000005;
int n, m, ans, cnt = 1;
int dp[1000005];
int w[1000005], v[1000005];
int a, b, c;
int main() {
cin>>n>>m;
for (int i = 1; i <= n; ++i) {
cin>>a>>b>>c;
for (int j = 1; j <= c; j <<= 1) {
v[++cnt] = j * a, w[cnt] = j * b;
c -= j;
}
if (c) v[++cnt] = a * c, w[cnt] = b * c;
}
for (int i = 1; i <= cnt; ++i)
for (int j = m; j >= w[i]; --j)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
cout<<dp[m]<<endl;
return 0;
}
T3海盗宝藏
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0;//计数器
int dis[101][101],a[10001];//距离数组及必经之路数组
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d",&a[i]);//输入必经之路
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&dis[i][j]);//输入距离
}
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
}
}
}
for(int i=2;i<=m;i++){
//计数
ans+=dis[a[i-1]][a[i]];
}
printf("%d",ans);
return 0;
}
T4汽车拉力比赛
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 5000005;
bool s[505][505];
bool sign = 1;
bool vis[505][505];
int n, m;
int a[505][505];
int ans, l, r, mid;
int qdx, qdy, temp;
int dir[4][2] = {{0, 1},
{0, -1},
{1, 0},
{-1, 0}};
struct node {
int x, y;
};
bool bfs() {
queue<node> q;
int now = 1;
q.push({qdx, qdy});
vis[qdx][qdy] = 1;
while (!q.empty()) {
node sum = q.front();
if (now == temp) {
return 1;
}
q.pop();
for (int i = 0; i < 4; i++) {
node num;
num.x = sum.x + dir[i][0];
num.y = sum.y + dir[i][1];
if (num.x < 1 || num.x > n || num.y < 1 || num.y > m || vis[num.x][num.y]) continue;
int tp = abs(a[num.x][num.y] - a[sum.x][sum.y]);
if (tp > mid) continue;
else {
if (s[num.x][num.y])now++;
q.push(num);
vis[num.x][num.y] = 1;
}
}
}
return 0;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
r = max(r, a[i][j]);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> s[i][j];
if (s[i][j]) temp++;
if (sign && s[i][j]) {
qdx = i, qdy = j;
sign = 0;
}
}
}
while (l <= r) {
mid = l + r >> 1;
memset(vis, 0, sizeof(vis));
if (bfs()) {
r = mid - 1;
ans = mid;
} else {
l = mid + 1;
}
}
cout << ans << endl;
return 0;
}
这里空空如也
有帮助，赞一个