- gf25051 的博客
《咸鱼概要 · 比赛》8月7日模拟赛全国青少年信息素养大赛国赛真题解析
-
gf25051
LV 7
@
2026-8-7 13:11:46
前言：
紧跟时事
我是一只小萌新，喵喵，给的方法都比较简单
T1 积木摆放
思路：不用理会题目在那叭叭叭，根本不用什么区间，A阶题目，先找到最大的数，然后把所有的次数都用在它身上，所以它肯定是最大的，直接输出即可
代码
这么简单的题目还看代码！
#include <bits/stdc++.h>
using namespace std;
int n,k,a[1005];
bool cmp(int x,int y){
return x>y;
}
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+1+n,cmp);//sort排序快速找出最大的元素
cout<<a[1]+k;//直接输出即可
return 0;
}
T2 密码破译
思路：看到字符串s长度<=100直接考虑暴力搜索，不管你怎么乱搞都不会超时，双重循环遍历每一种可能子串，配合哈希表进行桶排统计数量，最后找出最长合法子串
优化思路：从正向遍历改成反向遍历，这样只要找到合法子串就肯定是最大的，非常之快
笔者 太懒了 把这个问题留给大家，写出来记得发我
代码
#include <bits/stdc++.h>
//#define int long long
using namespace std;
string s,l;
int n,ans=INT_MIN;
bool check(string s){
int sl=s.size(),x,cnt=0;
unordered_map<char,int>mp;//哈希表进行桶排
for(int i=0;i<sl;i++){
mp[s[i]]++;
}
for(auto i=mp.begin();i!=mp.end();i++){
//判断是否为合法子串
cnt++;
if(cnt!=1){
if(i->second!=x){
return 0;
}
}
x=i->second;
}
return 1;
}
signed main(){
cin>>s;
n=s.size();
for(int i=0;i<n;i++){
for(int j=i+1;j<=n;j++){
l=s.substr(i,j-i);//截取每一个子串
if(check(l)==1){
//找出最大的合法子串
ans=max(ans,(int)l.size());
}
}
}
//如果ans并没有变化，就说明没有合法子串，输出0
if(ans==INT_MIN){
cout<<0;
return 0;
}
cout<<ans;
return 0;
}
T3 探险迷宫
思路：一开始看到数据范围n,m<=50，可以先考虑DFS大法师，只需要在进行上下左右四个方向遍历的前面加一个如果到达了传送门，就进行传送，遍历所有传送门并尝试
DFS代码
#include <bits/stdc++.h>
//#define int long long
using namespace std;
int n,m,sx,sy,ex,ey,ans=INT_MAX,l;
int dx[5]= {0,1,-1,0,0};//表示上下左右四个方向
int dy[5]= {0,0,0,1,-1};
struct xh {
int x,y;
//记录每个传送门的坐标位置
} ch[2505];
char g[55][55];//原地图
bool vis[55][55];//DFS里面要用到的记忆化，避免重复搜索
bool check(int x,int y) {
//检查是否该走法是否合法
if(x<1||x>n||y<1||y>m) {//检查是否越界
return 0;
}
if(g[x][y]=='1') {//检查是否撞墙
return 0;
}
if(vis[x][y]==1) {//检查是否走到了已经走过的地方
return 0;
}
//合法
return 1;
}
//x,y-->当前坐标，step-->当前步数，c-->是否使用过传送（全局只能用一次）
void dfs(int x,int y,int step,bool c) {
if(x==ex&&y==ey) {//是否到达终点
ans=min(step,ans);//取最优方案
return;
}
//剪枝优化：如果当前步数已经比最优方案差劲了，直接舍去
if(step>=ans) {
return;
}
if(g[x][y]=='P'&&c==0) {//如果处于传送门且还没传送过，进行传送
for(int i=1; i<=l; i++) {//遍历所有传送门
if(!(x==ch[i].x&&y==ch[i].y)) {//禁止传送到我本身就在的这个传送门
vis[ch[i].x][ch[i].y]=1;
c=1;
dfs(ch[i].x,ch[i].y,step,c);//传送不消耗步数
c=0;
vis[ch[i].x][ch[i].y]=0;//回溯
}
}
}
for(int i=1; i<=4; i++) {//遍历上下左右四个方向
int nx=x+dx[i];
int ny=y+dy[i];
if(check(nx,ny)) {//合法就可以进行移动
vis[nx][ny]=1;
dfs(nx,ny,step+1,c);
vis[nx][ny]=0;
}
}
}
signed main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
cin>>g[i][j];
if(g[i][j]=='S') {
sx=i,sy=j;//记录起始坐标
}
if(g[i][j]=='T') {
ex=i,ey=j;//记录终点坐标
}
if(g[i][j]=='P') {
l++;
ch[l].x=i,ch[l].y=j;//记录传送门坐标
}
}
}
dfs(sx,sy,0,0);//大法师，启动！
if(ans==INT_MAX) {//如果ans没有变过，就说明无法到终点，输出-1
cout<<-1;
return 0;
}
cout<<ans;//输出结果
return 0;
}
但是结果会告诉你一切......
嗯？拿错图了
出于无奈，我们只能考虑BFS冰法师
思路和DFS是一样的，只不过写法变了
BFS代码
#include <bits/stdc++.h>
//#define int long long
using namespace std;
int n,m,sx,sy,ans=INT_MAX,l;
int dx[5]= {0,1,-1,0,0};//表示上下左右四个方向
int dy[5]= {0,0,0,1,-1};
struct chuan {
int x,y;
//记录每个传送门的坐标位置
} ch[2505];
struct xh {
int x,y,step,c;
//BFS需要的四个参数
//x,y-->当前坐标，step-->当前步数，c-->是否使用过传送（全局只能用一次）
};
char g[55][55];//原地图
bool vis[55][55][2];//BFS里面要用到的记忆化，避免重复搜索，第三维表示是否用过传送
bool check(int x,int y) {
//检查是否该走法是否合法
if(x<1||x>n||y<1||y>m) {//检查是否越界
return 0;
}
if(g[x][y]=='1') {//检查是否撞墙
return 0;
}
return 1;
}
void bfs() {
queue<xh> q;
q.push({sx,sy,0,0});
//BFS初始建立队列
while(!q.empty()) {
xh fr=q.front();//取出队列最前面
q.pop();//将最前面弹出队列
if(g[fr.x][fr.y]=='T') {
//到达终点直接输出步数
//提示：BFS第一个搜到终点的路径就是最短路
cout<<fr.step;
return;
}
if(g[fr.x][fr.y]=='P'&&fr.c==0) {//如果位于传送门且还没传送过，进行传送
for(int i=1; i<=l; i++) {//遍历所有传送门
if(!(fr.x==ch[i].x&&fr.y==ch[i].y)) {//禁止传送到我本身就在的这个传送门
if(vis[ch[i].x][ch[i].y][1]==0) {//如果传送的位置还没有到过，可以进行传送
vis[ch[i].x][ch[i].y][1]=1;//打上标记，避免重复访问
q.push({ch[i].x,ch[i].y,fr.step,1});//入队
}
}
}
}
for(int i=1; i<=4; i++) {//遍历上下左右四个方向
int nx=fr.x+dx[i];
int ny=fr.y+dy[i];
if(check(nx,ny)) {//合法就可以进行移动
if(vis[nx][ny][fr.c]==0){//如果移动的位置还没有到过，可以进行移动
vis[nx][ny][fr.c]=1;//打上标记，避免重复访问
q.push({nx,ny,fr.step+1,fr.c});//入队
}
}
}
}
//如果所以路径都搜不到终点，输出-1
cout<<-1;
}
signed main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
cin>>g[i][j];
if(g[i][j]=='S') {
sx=i,sy=j;//记录起始坐标
}
if(g[i][j]=='P') {
l++;
ch[l].x=i,ch[l].y=j;//记录传送门坐标
}
}
}
bfs();//冰法师，启动！
return 0;
}
T4 物资补给
思路：第一眼背包，第二眼多重背包，注意多重背包采用反向遍历；比较简单的写法就是三重循环，第一个循环遍历n个物品，第二重循环遍历最大为m的背包容量，第三重循环遍历这个物品取多少件，n<=100绝对不会超时
优化思路：可以采用二进制拆分优化
笔者 其实不太会 把这个问题留给大家，写出来记得发我
代码
#include <bits/stdc++.h>
//#define int long long
using namespace std;
int n,m,w[2005],v[2005],a[2005],dp[2005];
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i]>>a[i];
//w[i]:重量，v[i]:价值，a[i]：件数
}
for(int i=1;i<=n;i++){//遍历n个物品
for(int j=m;j>=0;j--){//遍历最大为m的背包容量
for(int k=0;k<=a[i];k++){//遍历这个物品取多少件
if(k*w[i]>j){
//如果取这件物品后装不下了，就放弃
break;
}
//状态转移方程：比较原来的方法和取了这件物品的方法哪个价值大
dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);
}
}
}
cout<<dp[m];//输出背包容量为m时的结果
return 0;
}
比赛记录
