官方题解 | 挑战赛#34题解

Sherry

2026-08-06 17:35:03

发布于：浙江

45阅读

0回复

0点赞

赛纲介绍

本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平。

题目编号	题目名称	题目难度
T1	星灯焦点	入门
T2	展厅排期	普及-
T3	能量搭档	普及-
T4	同步钟声	普及-
T5	传送门迷宫	普及-
T6	星愿密码	普及/提高-

T1 星灯焦点

题目大意

给出一个 $n\times m$ 的数字矩阵，如果一个位置的数字同时等于所在行最大值和所在列最大值，则称为焦点灯。

求焦点灯数量。

题解思路

先预处理每一行和每一列的最大值。

使用 row[i] 保存第 $i$ 行最大值，使用 col[j] 保存第 $j$ 列最大值。

再次遍历矩阵，如果：

$a_{i,j}=row[i]$

并且：

$a_{i,j}=col[j]$

则该位置满足条件。

参考代码

#include <bits/stdc++.h>
using namespace std;

long long a[1010][1010];
long long row[1010],col[1010];

int main(){
    int n,m;
    cin>>n>>m;

    for(int i=1;i<=n;i++){
        row[i]=-1;
    }
    for(int j=1;j<=m;j++){
        col[j]=-1;
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            row[i]=max(row[i],a[i][j]);
            col[j]=max(col[j],a[i][j]);
        }
    }

    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]==row[i]&&a[i][j]==col[j]){
                ans++;
            }
        }
    }

    cout<<ans<<endl;
    return 0;
}

T2 展厅排期

题目大意

给出多个活动的开始时间和持续时间，活动之间需要留出整理时间，求最多安排多少活动。

题解思路

将每个活动转换为区间：

$[s_i,s_i+d_i-1]$

按照结束时间从小到大排序。

每次选择当前能够安排且结束时间最早的活动。

如果：

$s_i\ge last+c+1$

则选择该活动。

这是经典区间调度贪心问题。

参考代码

#include <bits/stdc++.h>
using namespace std;

struct node{
    long long l,r;
};

node a[200010];

bool cmp(node x,node y){
    if(x.r!=y.r){
        return x.r<y.r;
    }
    return x.l<y.l;
}

int main(){
    int n;
    long long c;
    cin>>n>>c;

    for(int i=1;i<=n;i++){
        long long s,d;
        cin>>s>>d;
        a[i].l=s;
        a[i].r=s+d-1;
    }

    sort(a+1,a+n+1,cmp);

    long long last=-4000000000000000000LL;
    int ans=0;
    for(int i=1;i<=n;i++){
        if(a[i].l>=last+c+1){
            ans++;
            last=a[i].r;
        }
    }

    cout<<ans<<endl;
    return 0;
}

T3 能量搭档

题目大意

选择两名同学组成队伍，使两人的能量和满足：

$L\le a_i+a_j\le R$

求最多队伍数量。

题解思路

先排序，然后使用双指针。

如果当前最小值和最大值之和小于 $L$ ，移动左指针。

如果大于 $R$ ，移动右指针。

如果满足条件，则组成一队，两个指针同时移动。

参考代码

#include <bits/stdc++.h>
using namespace std;

long long a[200010];

int main(){
    int n;
    long long L,R;
    cin>>n>>L>>R;

    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    sort(a+1,a+n+1);

    int l=1;
    int r=n;
    int ans=0;
    while(l<r){
        long long sum=a[l]+a[r];
        if(sum<L){
            l++;
        }
        else if(sum>R){
            r--;
        }
        else{
            ans++;
            l++;
            r--;
        }
    }

    cout<<ans<<endl;
    return 0;
}

T4 同步钟声

题目大意

两个钟分别每隔 $a$ 和 $b$ 分钟响一次，求第 $k$ 个响铃时间。

题解思路

设时间为 $x$ ，计算前 $x$ 个时间中响铃次数：

$count(x)= \lfloor\frac{x}{a}\rfloor+ \lfloor\frac{x}{b}\rfloor- \lfloor\frac{x}{lcm(a,b)}\rfloor$

寻找最小的 $x$ 满足：

$count(x)\ge k$

由于函数单调，因此使用二分答案。

参考代码

#include <bits/stdc++.h>
using namespace std;

long long getNum(long long x,long long a,long long b,long long lcm){
    return x/a+x/b-x/lcm;
}

int main(){
    int T;
    cin>>T;

    while(T--){
        long long a,b,k;
        cin>>a>>b>>k;

        long long g=__gcd(a,b);
        long long lcm=a/g*b;

        long long l=1;
        long long r=min(a,b)*k;
        while(l<r){
            long long mid=(l+r)/2;
            if(getNum(mid,a,b,lcm)>=k){
                r=mid;
            }
            else{
                l=mid+1;
            }
        }

        cout<<l<<endl;
    }

    return 0;
}

T5 传送门迷宫

题目大意

迷宫中存在传送门，相同字母的位置可以一步传送，求起点到终点最短距离。

题解思路

所有移动代价均为 $1$ ，因此使用 BFS。

普通移动扩展四个方向。

对于传送门，每种字母只需要展开一次：

第一次遇到某字母时，将所有对应位置加入队列。
后续不再重复展开。

避免重复计算。

参考代码

#include <bits/stdc++.h>
using namespace std;

struct node{
    int x,y;
};

int n,m;
char g[1010][1010];
int dis[1010][1010];
int head[26],nxt[1000010],px[1000010],py[1000010];
int used[26];
int tot;
int sx,sy,tx,ty;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

int main(){
    cin>>n>>m;

    string s;
    for(int i=1;i<=n;i++){
        cin>>s;
        for(int j=1;j<=m;j++){
            g[i][j]=s[j-1];
            dis[i][j]=-1;
            if(g[i][j]=='S'){
                sx=i;
                sy=j;
            }
            else if(g[i][j]=='T'){
                tx=i;
                ty=j;
            }
            else if(g[i][j]>='a'&&g[i][j]<='z'){
                int id=g[i][j]-'a';
                tot++;
                px[tot]=i;
                py[tot]=j;
                nxt[tot]=head[id];
                head[id]=tot;
            }
        }
    }

    queue<node> q;
    dis[sx][sy]=0;
    q.push({sx,sy});

    while(!q.empty()){
        node now=q.front();
        q.pop();

        int x=now.x;
        int y=now.y;

        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx<1||nx>n||ny<1||ny>m){
                continue;
            }
            if(g[nx][ny]=='#'){
                continue;
            }
            if(dis[nx][ny]!=-1){
                continue;
            }
            dis[nx][ny]=dis[x][y]+1;
            q.push({nx,ny});
        }

        if(g[x][y]>='a'&&g[x][y]<='z'){
            int id=g[x][y]-'a';
            if(used[id]==0){
                used[id]=1;
                for(int i=head[id];i!=0;i=nxt[i]){
                    int nx=px[i];
                    int ny=py[i];
                    if(dis[nx][ny]==-1){
                        dis[nx][ny]=dis[x][y]+1;
                        q.push({nx,ny});
                    }
                }
            }
        }
    }

    cout<<dis[tx][ty]<<endl;
    return 0;
}

T6 星愿密码

题目大意

字符串中包含数字和 ?，问号可以替换成任意数字。

求所有合法解码方案数量。

题解思路

使用动态规划。

设：

$dp[i]$

表示前 $i$ 个字符的方案数。

当前位置有两种转移：

单个字符：

$dp[i]+=dp[i-1]\times one(i)$

两个字符：

$dp[i]+=dp[i-2]\times two(i-1,i)$

其中需要计算问号情况下的组合数量。

每个位置只处理一次。

参考代码

#include <bits/stdc++.h>
using namespace std;

const long long MOD=1000000007LL;
char s[200010];
long long dp[200010];

int one(char c){
    if(c=='?'){
        return 9;
    }
    if(c=='0'){
        return 0;
    }
    return 1;
}

int two(char a,char b){
    if(a=='?'&&b=='?'){
        return 17;
    }
    if(a=='?'){
        if(b>='0'&&b<='6'){
            return 2;
        }
        return 1;
    }
    if(b=='?'){
        if(a=='1'){
            return 10;
        }
        if(a=='2'){
            return 7;
        }
        return 0;
    }

    int num=(a-'0')*10+(b-'0');
    if(num>=10&&num<=26){
        return 1;
    }
    return 0;
}

int main(){
    int n;
    cin>>n;
    cin>>(s+1);

    dp[0]=1;
    for(int i=1;i<=n;i++){
        dp[i]=(dp[i]+dp[i-1]*one(s[i]))%MOD;
        if(i>=2){
            dp[i]=(dp[i]+dp[i-2]*two(s[i-1],s[i]))%MOD;
        }
    }

    cout<<dp[n]<<endl;
    return 0;
}