1.藏宝图非常经典的岛屿问题bfs来写题目背景给定一个由数字组成的二维网格地图其中0代表水域1代表普通陆地2~9代表包含宝藏的陆地要求统计地图中岛屿的总数量岛屿定义上下左右相邻的非 0 区域为一个岛屿仅共享顶点不算相邻包含至少一个宝藏2~9的岛屿数量。解题思路核心算法广度优先搜索BFS采用BFS遍历每个未访问的陆地 / 宝藏区域完成两个核心统计每发现一个未访问的非 0 格子代表新岛屿总岛屿数 1遍历岛屿过程中若发现任意一个 2~9 的格子标记该岛屿为 “有宝藏岛屿”最终统计这类岛屿数量。具体步骤输入处理读取地图行数、列数将每行字符串转换为整数型二维数组方便数值判断遍历地图逐行逐列检查每个格子遇到非 0 格子时启动 BFSBFS 遍历岛屿从当前格子出发向上下左右四个方向扩展标记已访问的格子置为 0同时检查是否包含宝藏统计结果完成所有岛屿遍历后输出总岛屿数和有宝藏的岛屿数。#includebits/stdc.husing namespace std;const int d[]{-1,1,0,0};const int e[]{0,0,-1,1};bool q(int h,int i,int a,int b){return h0hai0ib;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int a,b,f0,g0;cinab;vectorvectorint c(a,vectorint(b));for(int h0;ha;h){string s;cins;for(int i0;ib;i){c[h][i]s[i]-0;}}for(int h0;ha;h){for(int i0;ib;i){if(c[h][i]!0){f;queuepairint,int j;bool k(c[h][i]2);j.emplace(h,i);c[h][i]0;while(!j.empty()){int lj.front().first;int mj.front().second;j.pop();for(int n0;n4;n){int old[n];int pme[n];if(q(o,p,a,b)c[o][p]!0){if(c[o][p]2)ktrue;j.emplace(o,p);c[o][p]0;}}}if(k)g;}}}coutf g;}2.谁管谁叫爹直接模拟就行解题思路核心算法模拟 数字各位和计算本题是典型的模拟题核心逻辑是严格按照题目给定的规则分步执行各位和计算编写函数遍历数字的每一位累加得到各位数字之和倍数判定分别判断 A 是否能被 SB 整除、B 是否能被 SA 整除胜负判定按题目优先级依次判断倍数条件若条件平局则比较原始数字大小。具体步骤输入优化关闭同步流加速输入输出适配多组测试用例的场景读取测试用例数输入 n表示有 n 组待判定的数字对处理每组测试用例读取 A 和 B 两个数字计算 A 的各位和 SA、B 的各位和 SB判定 A% SB0、B% SA0 两个条件按规则输出获胜方循环处理所有测试用例直至结束。#includebits/stdc.husing namespace std;long long f(long long x){long long s 0;while (x) {s x % 10;x / 10;}return s;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin n;while (n--) {long long a, b;cin a b;long long c f(a), d f(b);bool e (a % d 0), g (b % c 0);if (e !g)cout A\n;else if (g !e)cout B\n;else cout (a b ? A : B) \n;}}3.满树的遍历先看是不是k阶满树再遍历。借用了一些ai之力。解题思路核心算法邻接表建树 迭代式前序遍历 统计判定本题需分三步完成核心逻辑围绕 “树的存储” 和 “树的遍历 / 统计” 展开树的存储用邻接表存储每个结点的子结点便于后续遍历和统计度与满树判定遍历所有结点的子结点列表统计最大子结点数树的度检查所有有子结点的结点是否子结点数都等于树的度判定是否为满树前序遍历采用迭代式栈实现前序遍历避免递归深度溢出子结点逆序入栈保证升序访问。具体步骤输入处理与建树读取结点总数输入每个结点的父结点用邻接表记录每个父结点的子结点根结点查找 子结点排序找到父结点为 0 的根结点对每个结点的子结点列表升序排序树的度计算遍历所有结点的子结点数量记录最大值树的度满树判定检查所有有子结点的结点是否子结点数均等于树的度迭代式前序遍历用栈模拟前序遍历子结点逆序入栈保证访问顺序为升序结果输出输出树的度、满树判定结果、前序遍历序列。代码逐行解析#includebits/stdc.husing namespace std;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int a, b 0, e 0;cin a;vectorvectorint c(a1);vectorint d(a 1);for (int i 1; i a; i) {cin d[i];c[d[i]].push_back(i);}for (int i 1; i a; i) {if (d[i] 0)b i;sort(c[i].begin(), c[i].end());e max(e, (int)c[i].size());}bool f true;for (int i1; ia; i) {if (c[i].size() 0 c[i].size() ! e)f false;}vectorint g;stackint h;h.push(b);while (!h.empty()) {int x h.top();h.pop();g.push_back(x);for (int i c[x].size() - 1; i 0; i--)h.push(c[x][i]);}cout e (f ? yes : no) \n;for (int i 0; i g.size(); i) {if (i 0)cout ;cout g[i];}cout \n;}4.大幂数从最高次模拟解题思路核心策略从高到低枚举幂次 累加验证本题核心要求是找到幂次最大的解因此采用「优先验证高幂次」的贪心策略具体逻辑幂次上限确定因 n231幂次 k 最大取 30231 超出范围k31 无意义倒序枚举幂次从 k30 到 k1 枚举保证第一个找到的解是幂次最大的最优解累加验证对每个幂次 k从 m1 开始累加 1k2k...mk若和等于 n 则输出结果若和超过 n 则终止当前幂次验证溢出保护计算 mk 时提前判断是否溢出避免数值错误。#includebits/stdc.husing namespace std;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);long long a;cina;for(int b30;b1;b--){long long c0;int d1;while(true){long long e1;bool ffalse;for(int g0;gb;g){if(ea/d){ftrue;break;}e*d;}if(f||ca-e)break;ce;if(ca){for(int h1;hd;h){if(h1)cout;couth^b;}cout\n;return 0;}d;}}coutImpossible for a.\n;return 0;}5.影响力题目分析本题的核心是计算网格中每个点到所有其他点的切比雪夫距离之和再乘以该点的国家实力值得到最终的总代价。切比雪夫距离定义dist(A,B)max(∣iA−iB∣,∣jA−jB∣)总代价公式为 总代价所有。直接暴力计算每个点的距离和时间复杂度为 O(nm(nm))对于 nm≤106 的数据范围会超时因此需要通过数学转换优化。算法思路切比雪夫距离转曼哈顿距离对坐标 (x,y) 做变换uxyvx−y则切比雪夫距离可转换为max(∣x1−x2∣,∣y1−y2∣)21(∣u1−u2∣∣v1−v2∣)因此所有点到 (i,j) 的切比雪夫距离之和等价于 21×(所有u到u0的绝对值和所有v到v0的绝对值和)。前缀和快速计算绝对值和对于有序的数值序列可通过前缀和数组在 O(1) 时间内计算任意值到所有元素的绝对值之和。由于 u 和 v 的取值是连续的我们可以直接统计每个值的出现次数构建前缀和数组无需排序进一步优化效率。#include iostream#include vector#include algorithmusing namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin n m;vectorvectorlong long S(n, vectorlong long(m));for (int i 0; i n; i) {for (int j 0; j m; j) {cin S[i][j];}}int total n * m;int max_u n m;vectorlong long prefix_cnt_u(max_u 2, 0);vectorlong long prefix_sum_u(max_u 2, 0);for (int u 2; u max_u; u) {int x_min max(1, u - m);int x_max min(n, u - 1);int cnt max(0, x_max - x_min 1);prefix_cnt_u[u] prefix_cnt_u[u - 1] cnt;prefix_sum_u[u] prefix_sum_u[u - 1] (long long)u * cnt;}int offset m - 1;int max_v_idx (n - 1) offset;vectorlong long prefix_cnt_v(max_v_idx 1, 0);vectorlong long prefix_sum_v(max_v_idx 1, 0);for (int idx 0; idx max_v_idx; idx) {int v idx - offset;int x_min max(1, v 1);int x_max min(n, v m);int cnt max(0, x_max - x_min 1);if (idx 0) {prefix_cnt_v[idx] cnt;prefix_sum_v[idx] (long long)v * cnt;} else {prefix_cnt_v[idx] prefix_cnt_v[idx - 1] cnt;prefix_sum_v[idx] prefix_sum_v[idx - 1] (long long)v * cnt;}}long long total_sum_u prefix_sum_u[max_u];long long total_sum_v prefix_sum_v[max_v_idx];for (int i 1; i n; i) {for (int j 1; j m; j) {int u0 i j;int v0 i - j;long long cnt_le_u prefix_cnt_u[u0];long long sum_le_u prefix_sum_u[u0];long long sum_u (long long)u0 * cnt_le_u - sum_le_u (total_sum_u - sum_le_u) - (long long)u0 * (total - cnt_le_u);int idx_v v0 offset;long long cnt_le_v prefix_cnt_v[idx_v];long long sum_le_v prefix_sum_v[idx_v];long long sum_v (long long)v0 * cnt_le_v - sum_le_v (total_sum_v - sum_le_v) - (long long)v0 * (total - cnt_le_v);long long sum_dist (sum_u sum_v) / 2;long long res S[i - 1][j - 1] * sum_dist;if (j 1) {cout ;}cout res;}cout \n;}return 0;}
2026计协wp
1.藏宝图非常经典的岛屿问题bfs来写题目背景给定一个由数字组成的二维网格地图其中0代表水域1代表普通陆地2~9代表包含宝藏的陆地要求统计地图中岛屿的总数量岛屿定义上下左右相邻的非 0 区域为一个岛屿仅共享顶点不算相邻包含至少一个宝藏2~9的岛屿数量。解题思路核心算法广度优先搜索BFS采用BFS遍历每个未访问的陆地 / 宝藏区域完成两个核心统计每发现一个未访问的非 0 格子代表新岛屿总岛屿数 1遍历岛屿过程中若发现任意一个 2~9 的格子标记该岛屿为 “有宝藏岛屿”最终统计这类岛屿数量。具体步骤输入处理读取地图行数、列数将每行字符串转换为整数型二维数组方便数值判断遍历地图逐行逐列检查每个格子遇到非 0 格子时启动 BFSBFS 遍历岛屿从当前格子出发向上下左右四个方向扩展标记已访问的格子置为 0同时检查是否包含宝藏统计结果完成所有岛屿遍历后输出总岛屿数和有宝藏的岛屿数。#includebits/stdc.husing namespace std;const int d[]{-1,1,0,0};const int e[]{0,0,-1,1};bool q(int h,int i,int a,int b){return h0hai0ib;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int a,b,f0,g0;cinab;vectorvectorint c(a,vectorint(b));for(int h0;ha;h){string s;cins;for(int i0;ib;i){c[h][i]s[i]-0;}}for(int h0;ha;h){for(int i0;ib;i){if(c[h][i]!0){f;queuepairint,int j;bool k(c[h][i]2);j.emplace(h,i);c[h][i]0;while(!j.empty()){int lj.front().first;int mj.front().second;j.pop();for(int n0;n4;n){int old[n];int pme[n];if(q(o,p,a,b)c[o][p]!0){if(c[o][p]2)ktrue;j.emplace(o,p);c[o][p]0;}}}if(k)g;}}}coutf g;}2.谁管谁叫爹直接模拟就行解题思路核心算法模拟 数字各位和计算本题是典型的模拟题核心逻辑是严格按照题目给定的规则分步执行各位和计算编写函数遍历数字的每一位累加得到各位数字之和倍数判定分别判断 A 是否能被 SB 整除、B 是否能被 SA 整除胜负判定按题目优先级依次判断倍数条件若条件平局则比较原始数字大小。具体步骤输入优化关闭同步流加速输入输出适配多组测试用例的场景读取测试用例数输入 n表示有 n 组待判定的数字对处理每组测试用例读取 A 和 B 两个数字计算 A 的各位和 SA、B 的各位和 SB判定 A% SB0、B% SA0 两个条件按规则输出获胜方循环处理所有测试用例直至结束。#includebits/stdc.husing namespace std;long long f(long long x){long long s 0;while (x) {s x % 10;x / 10;}return s;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin n;while (n--) {long long a, b;cin a b;long long c f(a), d f(b);bool e (a % d 0), g (b % c 0);if (e !g)cout A\n;else if (g !e)cout B\n;else cout (a b ? A : B) \n;}}3.满树的遍历先看是不是k阶满树再遍历。借用了一些ai之力。解题思路核心算法邻接表建树 迭代式前序遍历 统计判定本题需分三步完成核心逻辑围绕 “树的存储” 和 “树的遍历 / 统计” 展开树的存储用邻接表存储每个结点的子结点便于后续遍历和统计度与满树判定遍历所有结点的子结点列表统计最大子结点数树的度检查所有有子结点的结点是否子结点数都等于树的度判定是否为满树前序遍历采用迭代式栈实现前序遍历避免递归深度溢出子结点逆序入栈保证升序访问。具体步骤输入处理与建树读取结点总数输入每个结点的父结点用邻接表记录每个父结点的子结点根结点查找 子结点排序找到父结点为 0 的根结点对每个结点的子结点列表升序排序树的度计算遍历所有结点的子结点数量记录最大值树的度满树判定检查所有有子结点的结点是否子结点数均等于树的度迭代式前序遍历用栈模拟前序遍历子结点逆序入栈保证访问顺序为升序结果输出输出树的度、满树判定结果、前序遍历序列。代码逐行解析#includebits/stdc.husing namespace std;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int a, b 0, e 0;cin a;vectorvectorint c(a1);vectorint d(a 1);for (int i 1; i a; i) {cin d[i];c[d[i]].push_back(i);}for (int i 1; i a; i) {if (d[i] 0)b i;sort(c[i].begin(), c[i].end());e max(e, (int)c[i].size());}bool f true;for (int i1; ia; i) {if (c[i].size() 0 c[i].size() ! e)f false;}vectorint g;stackint h;h.push(b);while (!h.empty()) {int x h.top();h.pop();g.push_back(x);for (int i c[x].size() - 1; i 0; i--)h.push(c[x][i]);}cout e (f ? yes : no) \n;for (int i 0; i g.size(); i) {if (i 0)cout ;cout g[i];}cout \n;}4.大幂数从最高次模拟解题思路核心策略从高到低枚举幂次 累加验证本题核心要求是找到幂次最大的解因此采用「优先验证高幂次」的贪心策略具体逻辑幂次上限确定因 n231幂次 k 最大取 30231 超出范围k31 无意义倒序枚举幂次从 k30 到 k1 枚举保证第一个找到的解是幂次最大的最优解累加验证对每个幂次 k从 m1 开始累加 1k2k...mk若和等于 n 则输出结果若和超过 n 则终止当前幂次验证溢出保护计算 mk 时提前判断是否溢出避免数值错误。#includebits/stdc.husing namespace std;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);long long a;cina;for(int b30;b1;b--){long long c0;int d1;while(true){long long e1;bool ffalse;for(int g0;gb;g){if(ea/d){ftrue;break;}e*d;}if(f||ca-e)break;ce;if(ca){for(int h1;hd;h){if(h1)cout;couth^b;}cout\n;return 0;}d;}}coutImpossible for a.\n;return 0;}5.影响力题目分析本题的核心是计算网格中每个点到所有其他点的切比雪夫距离之和再乘以该点的国家实力值得到最终的总代价。切比雪夫距离定义dist(A,B)max(∣iA−iB∣,∣jA−jB∣)总代价公式为 总代价所有。直接暴力计算每个点的距离和时间复杂度为 O(nm(nm))对于 nm≤106 的数据范围会超时因此需要通过数学转换优化。算法思路切比雪夫距离转曼哈顿距离对坐标 (x,y) 做变换uxyvx−y则切比雪夫距离可转换为max(∣x1−x2∣,∣y1−y2∣)21(∣u1−u2∣∣v1−v2∣)因此所有点到 (i,j) 的切比雪夫距离之和等价于 21×(所有u到u0的绝对值和所有v到v0的绝对值和)。前缀和快速计算绝对值和对于有序的数值序列可通过前缀和数组在 O(1) 时间内计算任意值到所有元素的绝对值之和。由于 u 和 v 的取值是连续的我们可以直接统计每个值的出现次数构建前缀和数组无需排序进一步优化效率。#include iostream#include vector#include algorithmusing namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin n m;vectorvectorlong long S(n, vectorlong long(m));for (int i 0; i n; i) {for (int j 0; j m; j) {cin S[i][j];}}int total n * m;int max_u n m;vectorlong long prefix_cnt_u(max_u 2, 0);vectorlong long prefix_sum_u(max_u 2, 0);for (int u 2; u max_u; u) {int x_min max(1, u - m);int x_max min(n, u - 1);int cnt max(0, x_max - x_min 1);prefix_cnt_u[u] prefix_cnt_u[u - 1] cnt;prefix_sum_u[u] prefix_sum_u[u - 1] (long long)u * cnt;}int offset m - 1;int max_v_idx (n - 1) offset;vectorlong long prefix_cnt_v(max_v_idx 1, 0);vectorlong long prefix_sum_v(max_v_idx 1, 0);for (int idx 0; idx max_v_idx; idx) {int v idx - offset;int x_min max(1, v 1);int x_max min(n, v m);int cnt max(0, x_max - x_min 1);if (idx 0) {prefix_cnt_v[idx] cnt;prefix_sum_v[idx] (long long)v * cnt;} else {prefix_cnt_v[idx] prefix_cnt_v[idx - 1] cnt;prefix_sum_v[idx] prefix_sum_v[idx - 1] (long long)v * cnt;}}long long total_sum_u prefix_sum_u[max_u];long long total_sum_v prefix_sum_v[max_v_idx];for (int i 1; i n; i) {for (int j 1; j m; j) {int u0 i j;int v0 i - j;long long cnt_le_u prefix_cnt_u[u0];long long sum_le_u prefix_sum_u[u0];long long sum_u (long long)u0 * cnt_le_u - sum_le_u (total_sum_u - sum_le_u) - (long long)u0 * (total - cnt_le_u);int idx_v v0 offset;long long cnt_le_v prefix_cnt_v[idx_v];long long sum_le_v prefix_sum_v[idx_v];long long sum_v (long long)v0 * cnt_le_v - sum_le_v (total_sum_v - sum_le_v) - (long long)v0 * (total - cnt_le_v);long long sum_dist (sum_u sum_v) / 2;long long res S[i - 1][j - 1] * sum_dist;if (j 1) {cout ;}cout res;}cout \n;}return 0;}
