news 2026/8/11 12:30:16

2026计协wp

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
2026计协wp

1.藏宝图

非常经典的岛屿问题，bfs来写

题目背景

给定一个由数字组成的二维网格地图，其中：

  • 0代表水域
  • 1代表普通陆地
  • 2~9代表包含宝藏的陆地要求统计：
  1. 地图中岛屿的总数量（岛屿定义：上下左右相邻的非 0 区域为一个岛屿，仅共享顶点不算相邻）；
  2. 包含至少一个宝藏（2~9）的岛屿数量。

解题思路

核心算法：广度优先搜索（BFS）

采用BFS遍历每个未访问的陆地 / 宝藏区域，完成两个核心统计：

  1. 每发现一个未访问的非 0 格子，代表新岛屿，总岛屿数 + 1；
  2. 遍历岛屿过程中，若发现任意一个 2~9 的格子，标记该岛屿为 “有宝藏岛屿”，最终统计这类岛屿数量。

具体步骤

  1. 输入处理：读取地图行数、列数，将每行字符串转换为整数型二维数组，方便数值判断；
  2. 遍历地图：逐行逐列检查每个格子，遇到非 0 格子时启动 BFS；
  3. BFS 遍历岛屿：从当前格子出发，向上下左右四个方向扩展，标记已访问的格子（置为 0），同时检查是否包含宝藏；
  4. 统计结果：完成所有岛屿遍历后，输出总岛屿数和有宝藏的岛屿数。

#include<bits/stdc++.h>
using 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 h>=0&&h<a&&i>=0&&i<b;}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a,b,f=0,g=0;
cin>>a>>b;
vector<vector<int>> c(a,vector<int>(b));
for(int h=0;h<a;h++){
string s;
cin>>s;
for(int i=0;i<b;i++){
c[h][i]=s[i]-'0';
}
}
for(int h=0;h<a;h++){
for(int i=0;i<b;i++){
if(c[h][i]!=0){
f++;
queue<pair<int,int>> j;
bool k=(c[h][i]>=2);
j.emplace(h,i);
c[h][i]=0;
while(!j.empty()){
int l=j.front().first;
int m=j.front().second;
j.pop();
for(int n=0;n<4;n++){
int o=l+d[n];
int p=m+e[n];
if(q(o,p,a,b)&&c[o][p]!=0){
if(c[o][p]>=2)k=true;
j.emplace(o,p);
c[o][p]=0;
}
}
}
if(k)g++;
}
}
}
cout<<f<<" "<<g;
}

2.谁管谁叫爹

直接模拟就行

解题思路

核心算法：模拟 + 数字各位和计算

本题是典型的模拟题，核心逻辑是严格按照题目给定的规则分步执行：

  1. 各位和计算：编写函数遍历数字的每一位，累加得到各位数字之和；
  2. 倍数判定：分别判断 A 是否能被 SB 整除、B 是否能被 SA 整除；
  3. 胜负判定：按题目优先级依次判断倍数条件，若条件平局则比较原始数字大小。

具体步骤

  1. 输入优化：关闭同步流加速输入输出，适配多组测试用例的场景；
  2. 读取测试用例数：输入 n，表示有 n 组待判定的数字对；
  3. 处理每组测试用例：
    • 读取 A 和 B 两个数字；
    • 计算 A 的各位和 SA、B 的各位和 SB；
    • 判定 A% SB==0、B% SA==0 两个条件；
    • 按规则输出获胜方；
  4. 循环处理所有测试用例，直至结束。

#include<bits/stdc++.h>
using 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之力。

解题思路

核心算法：邻接表建树 + 迭代式前序遍历 + 统计判定

本题需分三步完成，核心逻辑围绕 “树的存储” 和 “树的遍历 / 统计” 展开：

  1. 树的存储：用邻接表存储每个结点的子结点，便于后续遍历和统计；
  2. 度与满树判定：
    • 遍历所有结点的子结点列表，统计最大子结点数（树的度）；
    • 检查所有有子结点的结点，是否子结点数都等于树的度，判定是否为满树；
  3. 前序遍历：采用迭代式栈实现前序遍历（避免递归深度溢出），子结点逆序入栈保证升序访问。

具体步骤

  1. 输入处理与建树：读取结点总数，输入每个结点的父结点，用邻接表记录每个父结点的子结点；
  2. 根结点查找 + 子结点排序：找到父结点为 0 的根结点，对每个结点的子结点列表升序排序；
  3. 树的度计算：遍历所有结点的子结点数量，记录最大值（树的度）；
  4. 满树判定：检查所有有子结点的结点，是否子结点数均等于树的度；
  5. 迭代式前序遍历：用栈模拟前序遍历，子结点逆序入栈保证访问顺序为升序；
  6. 结果输出：输出树的度、满树判定结果、前序遍历序列。

代码逐行解析

#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b = 0, e = 0;
cin >> a;
vector<vector<int>> c(a+1);
vector<int> 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 i=1; i<=a; i++) {
if (c[i].size() > 0 && c[i].size() != e)f = false;
}
vector<int> g;
stack<int> 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.大幂数

从最高次模拟

解题思路

核心策略：从高到低枚举幂次 + 累加验证

本题核心要求是找到幂次最大的解，因此采用「优先验证高幂次」的贪心策略，具体逻辑：

  1. 幂次上限确定：因 n<231，幂次 k 最大取 30（231 超出范围，k=31 无意义）；
  2. 倒序枚举幂次：从 k=30 到 k=1 枚举，保证第一个找到的解是幂次最大的最优解；
  3. 累加验证：对每个幂次 k，从 m=1 开始累加 1k+2k+...+mk，若和等于 n 则输出结果；若和超过 n 则终止当前幂次验证；
  4. 溢出保护：计算 mk 时提前判断是否溢出，避免数值错误。

#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a;
cin>>a;
for(int b=30;b>=1;b--){
long long c=0;
int d=1;
while(true){
long long e=1;
bool f=false;
for(int g=0;g<b;g++){
if(e>a/d){
f=true;
break;
}
e*=d;
}
if(f||c>a-e)break;
c+=e;
if(c==a){
for(int h=1;h<=d;h++){
if(h>1)cout<<"+";
cout<<h<<"^"<<b;
}
cout<<"\n";
return 0;
}
d++;
}
}
cout<<"Impossible for "<<a<<".\n";
return 0;
}

5.影响力

题目分析

本题的核心是计算网格中每个点到所有其他点的切比雪夫距离之和，再乘以该点的国家实力值，得到最终的总代价。切比雪夫距离定义：dist(A,B)=max(∣iA​−iB​∣,∣jA​−jB​∣)，总代价公式为 总代价所有。

直接暴力计算每个点的距离和时间复杂度为 O(nm(n+m))，对于 nm≤106 的数据范围会超时，因此需要通过数学转换优化。

算法思路

  1. 切比雪夫距离转曼哈顿距离对坐标 (x,y) 做变换：u=x+y，v=x−y，则切比雪夫距离可转换为：max(∣x1​−x2​∣,∣y1​−y2​∣)=21​(∣u1​−u2​∣+∣v1​−v2​∣)因此，所有点到 (i,j) 的切比雪夫距离之和，等价于 21​×(所有u到u0​的绝对值和+所有v到v0​的绝对值和)。

  2. 前缀和快速计算绝对值和对于有序的数值序列，可通过前缀和数组在 O(1) 时间内计算任意值到所有元素的绝对值之和。由于 u 和 v 的取值是连续的，我们可以直接统计每个值的出现次数，构建前缀和数组，无需排序，进一步优化效率。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, m;
cin >> n >> m;

vector<vector<long long>> S(n, vector<long 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;
vector<long long> prefix_cnt_u(max_u + 2, 0);
vector<long 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;
vector<long long> prefix_cnt_v(max_v_idx + 1, 0);
vector<long 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;
}

版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/7/14 15:38:56

Redis高效缓存读写策略揭秘

Redis 的三种高效缓存读写策略&#xff01; 感恩生活&#xff0c;总有阳光穿透云层&#xff0c;无论多么艰难的时刻&#xff0c;总有希望在前方等待我们去探索与追求。在这个瞬息万变的世界中&#xff0c;把握住自己的方向&#xff0c;沿着自己的道路走下去&#xff0c;才能迎接…

作者头像 李华
网站建设 2026/7/14 15:39:10

IPv4与IPv6地址规划实战指南

IPv4 与 IPv6 地址规划 IPv4 地址由 32 位组成&#xff0c;通常表示为点分十进制&#xff08;如 192.168.1.1&#xff09;&#xff0c;而 IPv6 地址由 128 位组成&#xff0c;采用十六进制表示&#xff08;如 2001:0db8:85a3::8a2e:0370:7334&#xff09;。IPv4 地址空间有限&a…

作者头像 李华
网站建设 2026/7/14 15:39:13

决策树：原理、构建与优缺点

决策树的基本原理 决策树是一种监督学习算法&#xff0c;广泛应用于分类和回归任务。其核心思想是通过对数据集进行递归划分&#xff0c;构建一棵树状结构&#xff0c;每个内部节点代表一个特征测试&#xff0c;每个分支代表测试结果&#xff0c;每个叶节点代表最终的预测结果。…

作者头像 李华
网站建设 2026/7/14 15:39:12

华睿MVP：动态坐标系标定

一、整体流程 标定按钮标志位&#xff1a;先在全局变量中添加一个标志按钮标志位&#xff0c;使用bool值&#xff0c;初始化为false&#xff0c;当按钮按下时标志位变为true。通过分支模块进行判断&#xff0c;可以有效控制执行的次数。图像处理&#xff1a;先读取相机的设置参…

作者头像 李华
网站建设 2026/7/14 15:39:11

VUE3 若依 菜单跳转导致页面出现空白

前言记录一下&#xff1a;在用vue3若依框架时&#xff0c;出现切换菜单&#xff0c;跳转到其他页面会导致所有页面出现空白&#xff0c;刷新页面后又恢复正常解决办法注释AppMain中的transition 优点&#xff1a;解决了页面跳转空白的问题 缺点&#xff1a;页面跳转没有过渡动画…

作者头像 李华
网站建设 2026/7/14 15:39:11

基于SAM的交叉提示与自适应采样一致性用于半监督医学图像分割/文献速递-大模型与图像分割在医疗影像中应用

2026.3.16本研究提出了CPAC-SAM&#xff0c;一个基于SAM的交叉提示框架&#xff0c;通过原型引导的网格采样和提示一致性正则化&#xff0c;有效利用未标注数据进行SAM微调&#xff0c;显著提升了半监督医学图像分割的性能&#xff0c;尤其在标注数据极度稀缺时表现优异。Title…

作者头像 李华