首页 书籍 蓝桥杯

# 九宫幻方

#include <bits/stdc++.h>
using namespace std;
int vis[10], a[5][5], ans[5][5];
int n, cnt;
pair<int, int>p[10];
bool check(){
    int sum = a[1][1] + a[2][2] + a[3][3]; // 取一条对角线的值
    if(sum != a[1][3] + a[2][2] + a[3][1]) return false; // 判断另一条对角线的和是否等于 sum，不等于则不是九宫幻方
    for(int i = 1 ; i <= 3 ; i ++) {
        int tmp1 = 0, tmp2 = 0; //tmp1 表示行的和，tmp2 表示列的和
        for(int j = 1 ; j <= 3 ; j ++) tmp1 += a[i][j], tmp2 += a[j][i];
        if(tmp1 != sum || tmp2 != sum) return false; // 如果行的和或列的和不等于 sum，则排列矩阵不是九宫幻方
    }
    return true; // 是九宫幻方
}
// 深度优先搜索尝试填充空白格子
void dfs(int now) {// 当前已经填充了多少个空白格子
    if(now > n) {// 所有空白格子都填充了数字，
        if(check()) {
            cnt++;
            for(int i = 1; i <= 3; i++)
                for(int j = 1; j <= 3; j++)
                    ans[i][j] = a[i][j];// 保存答案
        }
        return;
    }
    int x = p[now].first, y = p[now].second;// 第 now 个空白格子在矩阵中的行和列位置
    for(int k = 1; k <= 9; k++) {
        if(vis[k])//k 用过了
            continue;
        a[x][y] = k;
        vis[k] = 1;
        dfs(now + 1);
        a[x][y] = 0;// 回溯
        vis[k] = 0;
    }
}
 
int main() {
    // 读入初始矩阵
    for(int i = 1; i <= 3; i++)
        for(int j = 1; j <= 3; j++) {
            cin >> a[i][j];
            if(!a[i][j])// 遇到 0
                p[++n] = make_pair(i, j);// 保存 0 的位置
            vis[a[i][j]] = 1;// 已经用过的数字标记
        }
    dfs(1);
    if(cnt == 1) {
      for (int i = 1; i <= 3; i++){
          for (int j = 1; j <= 3; j++) {
          cout << ans[i][j] << " ";
        }
        cout << "\n";
      } 
       
        // 输出单个九宫幻方矩阵
    } else
        cout << "Too Many\n";
    return 0;
}
# 穿越雷区


# 题目：


给定一个 n × n 的方阵，方阵由起点（记为 A）、终点（记为 B）、道路组成。 道路有两种属性：正（记为＋）、负（记为－）。 我们每次可以从一个位置移动到其相邻位置（上、左、下、右），但在移动的过程中需满 足以下要求。 （1）不能离开方阵。 （2）必须正负交替移动：如果当前所处道路的属性为正，则下一步只能走到属性为负的 道路或起点 A 或终点 B；如果当前所处道路的属性为负，则下一步只能走到属性为正的道路或起点 A 或终点 B。 现在问从起点 A 走到终点 B 的最少移动次数是多少（若无法走到则输出 −1）?


# 分析：


# 代码：


#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int nex[4][2] = <!--swig0-->; // 表示移动时的 4 个方向
int n, a[N][N]; //a [i][j] 表示点的正负信息。a [i][j]=1 表示点 (i,j) 的能量值为正，a [i][j]=0 表示
// 点 (i,j) 的能量值为负，a [i][j] = -1 表示点 (i,j) 为 B
int vis[N][N]; //vis [i][j] 表示在搜索的过程中点是否走过。vis [i][j]=1 表示点 (i,j) 已经走过，
//vis [i][j]=0 表示点 (i,j) 还没走过
pair<int, int>st, ed; //st 记录点 A 的位置，ed 存储点 B 的位置
struct node{
    int x, y, cnt;
};
bool check(int x, int y){
    if(x < 1 || x > n || y < 1 || y > n || vis[x][y]) return false;
    return true;
}
int bfs(int x, int y){
    pair<int, int>u = make_pair(x, y);
    queue<node>que;
    que.push(node{x, y, 0});
    vis[x][y] = 1;
    while(!que.empty()){
        node u = que.front();
        if(u.x == ed.first && u.y == ed.second) return u.cnt;
        que.pop();
        int x = u.x , y = u.y;
        for(int i = 0; i <= 3; i ++){
            int tx = x + nex[i][0];
            int ty = y + nex[i][1];
            if(!check(tx , ty) || a[tx][ty] == a[x][y]) continue ;
            vis[tx][ty] = 1;
            que.push(node{tx, ty, u.cnt + 1});
        }
    }
    return -1;
}
signed main(){
    cin >> n;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            char x;
            cin >> x;
            if(x == 'A') st.first = i, st.second = j, a[i][j] = -1;
            else if(x == 'B') ed.first = i, ed.second = j , a[i][j] = -1;
            else if(x == '+') a[i][j] = 1;
            else a[i][j] = 0;
        }
    }
    cout << bfs(st.first, st.second) << '\n';
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int n, ans; //ans 记录答案
int a[N][N]; //a [i][j] 表示点的正负信息。a [i][j] = 1 表示点 (i,j) 的能量值为正，a [i][j]=0 表示
// 点 (i,j) 的能量值为负，a [i][j] = -1 表示点 (i,j) 为 B
int vis[N][N]; //vis 记录到达 (x,y) 的移动步数
pair<int, int> st, ed; //st 记录点 A 的位置，ed 存储点 B 的位置
void dfs(int x, int y, int cnt) {
    //x,y 表示当前点的位置，cnt 表示到达该点的移动步数
    if(cnt > ans) return; // 剪枝：如果移动步数大于 ans，那么该走法一定不是最优的，就没必要走下去了
    if(cnt > vis[x][y]) return; // 剪枝：如果到达 (x,y) 的移动步数大于 vis [x][y]，说明从起点走到 (x,y) 有更优的走法，那么该走法到达终点的移动步数一定不是最优的
    if(x < 1 || x > n || y < 1 || y > n) return; // 保证移动的正确性
    if(x == ed.first && y == ed.second) {
        ans = cnt; // 到达终点，记录（更新）答案
        return;
    }
    // 记录（更新）走到 (x,y) 的移动步数
    vis[x][y] = cnt;
    //a [tx][ty] 的能量特征不能等于 a [x][y] 的能量特征
    int tx = x - 1, ty = y;
    if(a[tx][ty] != a[x][y]) dfs(tx, ty, cnt + 1);
    tx = x + 1, ty = y;
    if(a[tx][ty] != a[x][y]) dfs(tx, ty, cnt + 1);
    tx = x, ty = y - 1;
    if(a[tx][ty] != a[x][y]) dfs(tx, ty, cnt + 1);
    tx = x, ty = y + 1;
    if(a[tx][ty] != a[x][y]) dfs(tx, ty, cnt + 1);
}
signed main() {
    cin >> n;
    ans = 0x3f3f3f3f;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            vis[i][j] = 0x3f3f3f3f;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            char x;
            cin >> x;
            if(x == 'A') st.first = i, st.second = j, a[i][j] = -1;
            else if(x == 'B') ed.first = i, ed.second = j, a[i][j] = -1;
            else if(x == '+') a[i][j] = 1;
            else a[i][j] = 0;
        }
    }
    dfs(st.first, st.second, 0);
    cout << ans << '\n';
    return 0;
}
# 小朋友的崇拜圈


# 题目：


【问题描述】 班里 N 个小朋友，每个人都有自己最崇拜的一个小朋友（也可以是自己）。 在一个游戏中，需要小朋友坐一个圈，每个小朋友都有自己最崇拜的小朋友在他的 右手边。 求满足条件的圈最大多少人？小朋友编号为 1, 2, 3, . . . , N。


# 分析：


（1）从每一个没有被标记的节点开始，一路走，直到出现环边，停止； （2）走的同时为节点打上标记，并记录边的编号； （3）当走到被其他路线标记过的点后，将重复走相同的路（见下图），没有意义，停止；


# 代码：


#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, ans, nex[N], number[N], vis[N];
//nex [x] 表示 x 的崇拜对象
//number [x] 表示边 x->nex [x] 的编号
void dfs(int x, int cnt, int id) {
    //x 表示当前走到的节点，cnt 表示当前边的编号，id 表示当前路线的编号
    if(vis[x] && vis[x] != id) return; // 如果 x 已经被其他路线标记过，则返回
    if(vis[x]) { // 说明找到了环边
        ans = max(ans, (cnt-1) - number[x] + 1); // 更新答案：cnt-1 表示上一条边的编号，即红色箭头的编号
        return; // 结束递归
    }
    vis[x] = id; // 为节点 x 打上标记
    number[x] = cnt; // 为边 x->nex [i] 添加编号
    dfs(nex[x], cnt + 1, id); // 继续搜索
}
signed main() {
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> nex[i];
    for(int i = 1; i <= n; i++)
        dfs(i, 1, i);
    cout << ans << '\n';
    return 0;
}
# 迷宫与陷阱


# 题目：


给定一个由 N × N 个格子组成的迷宫以及一个常数 K，迷宫的起点在左上角，终点在 右下角，小明需要从起点走到终点。 迷宫中的格子有以下几种类型。 （1）普通的格子（记为 “.”）：可以经过。 （2）墙壁（记为 “#”）：无法经过。 （3）拥有无敌道具的格子（记为 “%”）：可以经过，经过后接下来的 K 步将处于无敌状 态，但格子会变为普通的格子。 （4）陷阱（记为 “X”）：若处于无敌状态则可以经过，否则不可经过。 小明的每一步可以移动到当前位置上、下、左、右相邻的格子上，但前提是这些格子可 以经过。 请问从起点走到终点的最少步数是多少（若不能离开，则输出 −1）? 保证起点和终点一定是普通的格子。


# 分析


# 代码：


#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
struct node{
    int x, y; // 表示移动到的位置
    int cnt; // 表示移动的步数
    int status; // 表示接下来的 status 步都将保持无敌状态。status > 0 则处于无敌状态，status = 0 则处于普通状态
};
int n, k;
int nex[4][2] = <!--swig1-->; // 表示移动时的 4 个方向
int a[N][N], vis[N][N], s[N][N]; //a [][] 表示格子的类型，vis [][] 标记格子是否被访问过，s [][] 记录经过格子时最大的可保持无敌状态的步数
bool check(int x, int y, int status){
    // 不能离开迷宫，不能经过墙壁
    if(x < 1 || x > n || y < 1 || y > n || a[x][y] == 3) return false;
    // 如果不是无敌状态，不能经过陷阱
    if(a[x][y] == 2 && !status) return false;
    return true;
}
int bfs(){
    queue<node> que;
    que.push(node{1, 1, 0, 0}); // 从 (1,1) 出发
    vis[1][1] = 1; // 标记 (1,1) 被访问过
    while(!que.empty()){
        node u = que.front();
        que.pop();
        if(u.x == n && u.y == n) return u.cnt; // 到达 (n,n) 点则停止搜索
        for(int i = 0; i <= 3; i++){
            int tx = u.x + nex[i][0];
            int ty = u.y + nex[i][1];
            if(!check(tx, ty, u.status)) continue;
            int status = max(0, u.status - 1);
            if(a[tx][ty] == 1){ // 陷阱
                vis[tx][ty] = 1;
                a[tx][ty] = 0; // 陷阱走过就变为普通的格子
                que.push(node{tx, ty, u.cnt + 1, k});
            }
            else { // 普通的格子
                if(!vis[tx][ty]) { // 如果没有走过，那么有必要走一次
                    vis[tx][ty] = 1;
                    que.push(node{tx, ty, u.cnt + 1, status});
                    continue;
                }
                if(status <= s[tx][ty]) continue; // 可保持的无敌状态劣于上一次，没有必要再走一次
                // 可保持的无敌状态优于上一次，有必要再走一次
                s[tx][ty] = status;
                que.push(node{tx, ty, u.cnt + 1, max(0, status)});
            }
        }
    }
    return -1;
}
signed main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            char x;
            cin >> x;
            if(x == '%') a[i][j] = 1;
            else if(x == 'X') a[i][j] = 2;
            else if(x == '#') a[i][j] = 3;
        }
    }
    cout << bfs() << '\n';
    return 0;
}
# 扫地机器人


# 题目：


n 个房间连成一排，第 i 个房间的编号为 i。 有 K 台机器人，起初它们分别位于 a1, a2, . . . , ak 号房间。 机器人每分钟可以移动到左右相邻的房间中，并将房间清扫干净（多台机器人可同时启 动，也可同时清理同一个房间）。 我们可以随意分配每台机器人的清扫路线，但要求这些机器人最终都要回归初始时所在 的房间。 问题是，满足所有房间都至少被清扫一次且所有机器人都回归初始房间最少需要花费多 长时间？


# 分析：


根据贪心思想确定清扫方法，即让每台机器人都要优先清扫其左边还未扫过的 格子，然后再往右清扫，以保证每次清扫的效率都最高。


出对于一个时间 t，它要想作为答案须满足以下两个条件。 （1）所有的机器人在 t 分钟内可清扫所有区域。 （2）t 是满足所有条件 1 的时间中最小的一个。


用枚举法求 t 替换为用二分法求 t 来降低时间复杂度。


# 代码：


#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k, a[N]; //a [i] 表示第 i 台机器人的位置
bool check(int mid){
    int pos = 0; //pos 用来表示 1~pos 区域已被清扫，pos+1~n 区域未被清扫
    for(int i = 1; i <= k; i++){ // 遍历 k 台机器人
        int t = mid;
        if(pos < a[i]) t -= (a[i] - pos - 1) * 2; // 往左清扫，需要花费的时间为 2 * (a [i] - pos - 1)
        if(t < 0) return false; // 如果时间小于 0，说明无法清扫完左边的区域，时间不够
        pos = a[i] + t / 2; // 如果还剩有时间，继续向右清扫
    }
    if(pos < n) return false; // 如果没有清扫完所有的区域，则说明时间不够
    return true;
}
signed main(){
    cin >> n >> k;
    for(int i = 1; i <= k; i++) cin >> a[i];
    sort(a + 1, a + 1 + k); // 位置排序
    int l = 0, r = 2 * n, ans = 2 * n;
    while(l <= r){
        int mid = l + r >> 1;
        if(check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << ans << '\n';
    return 0;
}
# 123


# 题目：


有一个序列，序列的第 1 项为整数 1，接下来 2 项为整数 1 至 2，接下来 3 项是整数 1 至 3，接下来 4 项是整数 1 至 4，依此类推，如 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, . . . 现给定 T 组 询问，每组询问包含两个整数 l, r，要求出序列中第 l 项到第 r 项的和。


# 分析：


总结数列公式，


# 代码：


#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6 + 10;
int pre[N];
int getPre(int x){ // 求 pre [x] 的公式
    return x * (x + 1) * (x + 2) / 6;
}
int calc(int x){
    int l = 0, r = 2e6, i = 0; // 用二分求 x 在第几组
    while(l <= r){
        int mid = l + r >> 1;
        if((mid + 1) * mid / 2 > x) r = mid - 1, i = mid;
        else l = mid + 1;
    }
    int j = x - (i - 1) * (i - 1 + 1) / 2; // 求 x 在第几组的第几个位置
    // sum[x] = pre[i - 1] + j * (j + 1) / 2;
    return getPre(i - 1) + j * (j + 1) / 2;
}
signed main(){
    // 递推求 pre [1 ~ 2000000]
    pre[1] = 1;
    for(int i = 2; i <= 2000000; i++) pre[i] = pre[i - 1] + i * (i + 1) / 2;
    int T = 1;
    cin >> T;
    while(T--){
        int l, r;
        cin >> l >> r;
        // sum[r] - sum[l - 1]
        cout << calc(r) - calc(l - 1) << '\n';
    }
    return 0;
}