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

Sherry

2026-07-09 19:26:57

发布于：浙江

14阅读

0回复

0点赞

赛纲介绍

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

题目编号	题目名称	题目难度
T1	装饰花园	入门
T2	星愿徽章编号	普及-
T3	水晶整理	普及-
T4	选人规则	普及-
T5	迷宫寻路	普及-
T6	星光灯带	普及/提高-

T1 装饰花园

题目大意

边界和两条对角线都是 *，其余都是 #。

题解思路

对于下标范围是 $1\sim n$ 的二维网络，行号或列号至少有一个为 $1$ 或 $n$ 即为边界。

这里规定了 $n$ 为奇数，可以写出两个对角线上位置的下标寻找规律，主对角线规律为 $i==j$ ，副对角线规律为 $i+j==n+1$ 。

参考代码

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

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == 1 || i == n || j == 1 || j == n || i == j || i + j == n + 1) {
                cout << "*";
            } else {
                cout << "#";
            }
        }
        cout << endl;
    }

    return 0;
}

T2 星愿徽章编号

题目大意

十进制编号的所有数位都是同一个数字，即为整齐编号。需要计算 $1\sim n$ 范围内的整齐编号数量。

题解思路

枚举所有的数来判断是否是整齐编号，由于查询的次数较多，会出现超时的情况。

可以写出 $1\sim 4$ 位数中所有的整齐编号，发现其中的规律： $x$ 位数中最多只有 $9$ 个整齐编号 $111...111,222...222,...,999...999$ 。

所以可以将 $n$ 存为字符串，通过 .size() 方法获取字符串长度即为最大的数位长度。

需要注意，最大位数的情况下，由于 $n$ 的大小限制，相同的数不能超过最高位的数字，与最高位数字相同的情况需要单独判断。比如 $n$ 为 $4396$ 时是四位数，四位的整齐编号中最大只能到 $3333$ ， $4444$ 需要判断是否超过 $n$ 。

参考代码

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

int main(){
    int t;
    cin >> t;
    while(t--){
        string n;
        cin >> n;

        int x = n[0] - '0';
        int len = n.size();

        int ans = 9 * (len - 1) + x;

        string s = "";
        for(int i = 0; i < len; i++){
            s += n[0];
        }

        if(s > n){
            ans--;
        }

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

T3 水晶整理

题目大意

当 $a_{i}$ 处于 $a_j\sim a_{j}+k$ 范围时，第 $i$ 块水晶就能吸收第 $j$ 块水晶，但能量值不会发生改变。求最少可能剩下多少块水晶，即尽可能地让水晶被吸收。

题解思路

由于吸收规则存在大小限制但与位置无关，这里可以先排序方便判断是否能够吸收。在吸收过程中，由于吸收不会改变能量值，所以可以从前往后检查当前水晶是否能够被吸收。

考虑被哪个水晶吸收时，可以采用贪心双指针的方法，如果后面的某个水晶能吸收前面的水晶，则让后面的水晶继续吸收，知道无法吸收再更换后面的较大水晶。

参考代码

#include <bits/stdc++.h>
using namespace std;
int a[200010];
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    
    int i=1;
    int j=2;
    int cnt=0;
    while(j<=n){
        if(a[i]==a[j]){
            j++;
        }
        else if(a[i]+k>=a[j]){
            cnt++;
            i++;
        }
        else{
            i++;
        }
    }
    cout<<n-cnt<<endl;
    return 0;
}

T4 选人规则

题目大意

在未被选走的学生中，选择能力评分最高的学生，并将他和他左右各 $k$ 名最近的未被选走的学生一起选走。两队交替选择，直到所有学生都被选择，按原始顺序输出学生所在的队伍编号。

题解思路

本题的关键是按照规则不断选择“当前还没有被选走的最高能力评分学生”，并把他左右两边最近的 $k$ 名未被选走学生一起选走。

如果每一轮都从所有学生中重新寻找最高能力评分，复杂度会比较高。因此可以先把所有学生按照能力评分从大到小排序。之后从排序后的数组中依次向后找，第一个还没有被选走的学生，就是当前所有未被选走学生中能力评分最高的人。

难点在于：当一些学生已经被选走后，某个学生左边或右边“最近的 $k$ 名未被选走学生”不一定是原数组中相邻的 $k$ 个位置。

因此可以用类似双向链表的方式维护当前还没有被选走的学生顺序：

pre[i] 表示当前状态下，第 $i$ 个学生左边最近的未被选走学生。
next[i] 表示当前状态下，第 $i$ 个学生右边最近的未被选走学生。

每次选中能力最高的学生后：

向左沿着 pre 找最多 $k$ 个学生，把他们标记为当前队伍。
向右沿着 next 找最多 $k$ 个学生，把他们标记为当前队伍。
把这些被选走的学生从链表中删除。
当前队伍编号在 $1$ 和 $2$ 之间切换。

由于每名学生只会被选走一次，也只会从链表中删除一次，所以链表维护部分的总复杂度是 $O(n)$ 。排序复杂度是 $O(n\log n)$ ，因此总时间复杂度为： $O(n\log n)$ ，适合本题 $n\le 2\times 10^5$ 的数据范围。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n,k;
int vis[200010];
struct node{
    int a;//能力评分
    int b;//位置编号
    int next;//下一个节点编号
    int pre;//前一个节点编号
}p[200010],q[200010];
bool cmp(node x,node y){
    return x.a>y.a;
}
int main() {
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>p[i].a;
        p[i].b=i;
        p[i].next=i+1;
        p[i].pre=i-1;
    }
    p[1].pre=-1;
    p[n].next=-1;
    for(int i=1;i<=n;i++){
        q[i]=p[i];
    }
    sort(q+1,q+n+1,cmp);

    int cnt=n;
    int flag=1;
    int i=1;
    while(cnt>0){
        while(vis[q[i].b]!=0){
            i++;
        }
        
        int num=q[i].b;
        for(int j=1;j<=k;j++){
            int cur=p[num].pre;
            if(cur==-1){
                break;
            }
            vis[cur]=flag;
            p[num].pre=p[cur].pre;
            if(p[num].pre!=-1){
                p[p[num].pre].next=num;
            }
            cnt--;
        }

        for(int j=1;j<=k;j++){
            int cur=p[num].next;
            if(cur==-1){
                break;
            }
            vis[cur]=flag;
            p[num].next=p[cur].next;
            if(p[num].next!=-1){
                p[p[num].next].pre=num;
            }
            cnt--;
        }        
        
        vis[num]=flag;   
        if(p[num].pre==-1&&p[num].next==-1){
            cnt--;
            break;
        }
        else if(p[num].pre==-1){
            p[p[num].next].pre=p[num].pre;
            cnt--;
        }
        else if(p[num].next==-1){
            p[p[num].pre].next=p[num].next;
            cnt--;
        }
        else{
            p[p[num].next].pre=p[num].pre;
            p[p[num].pre].next=p[num].next;
            cnt--;
        }

        if(flag==1){
            flag=2;
        }
        else{
            flag=1;
        }
    }

    for(int i=1;i<=n;i++){
        cout<<vis[i];
    }
    return 0;
}

T5 迷宫寻路

题目大意

常规的有障碍物迷宫，只能在空地前进。离开迷宫的条件是超出迷宫的边界，即下标超出 $1\sim n$ 行或超出 $1\sim m$ 列范围。

题解思路

从起点出发，广度优先搜索记录到达每个位置的移动次数，这里的位置需要在迷宫范围基础上再向外扩展一圈，以此确定超出边界所需的步数。

但由于询问的起点较多，如果多次广搜会有重复的过程，这里可以将外层扩展的一圈位置作为起点入队，进行反向的广搜，确定从外界到达每一个迷宫内位置所需的移动次数，可以避免重复计算。

参考代码

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

struct node{
    int x,y;
};

int n,m,k;
int a[1010][1010];
int dis[1010][1010];

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

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

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

    queue<node>q;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]==0&&(i==1||i==n||j==1||j==m)){
                dis[i][j]=1;
                q.push({i,j});
            }
        }
    }

    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(a[nx][ny]==1){
                continue;
            }

            if(dis[nx][ny]!=-1){
                continue;
            }

            dis[nx][ny]=dis[x][y]+1;
            q.push({nx,ny});
        }
    }

    for(int i=1;i<=k;i++){
        int x,y;
        cin>>x>>y;

        cout<<dis[x][y]<<endl;
    }

    return 0;
}

T6 星光灯带

题目大意

灯带安装能获得的美观值为覆盖位置的星光值之和减去安装所需的固定代价。灯带存在长度限制，不能过长也不能过短。灯带间至少要有一个空位隔开。计算能够得到的最大美观值。

题解思路

本题要求选择若干段连续区间作为灯带，每条灯带长度必须在 $[L,R]$ 之间，并且任意两条灯带之间至少要隔开一个空位置。每条灯带的贡献为区间星光值之和减去固定代价 $C$ 。

由于灯带之间不能重叠，并且必须至少间隔一个位置，所以可以考虑动态规划。

设： $dp[i]$ 表示只考虑前 $i$ 个位置时，能够获得的最大总美观值。

对于第 $i$ 个位置，有两种情况：

第一种情况是不让任何灯带以第 $i$ 个位置结尾，那么答案可以直接继承前一个位置： $dp[i]=dp[i-1]$

第二种情况是选择一条灯带以第 $i$ 个位置结尾。假设这条灯带的左端点为 $j$ ，那么它覆盖的区间是： $[j,i]$

长度需要满足： $L\le i-j+1\le R$

也就是说，左端点 $j$ 的范围是： $i-R+1\le j\le i-L+1$

如果选择区间 $[j,i]$ 作为最后一条灯带，那么前面的灯带最多只能放到 $j-2$ ，因为第 $j-1$ 个位置必须空出来作为间隔。

因此这一种情况的转移为：

$dp[i]=\max(dp[i],dp[j-2]+sum[i]-sum[j-1]-C)$

其中： $sum[i]$ 表示前 $i$ 个位置的星光值前缀和。

把式子整理一下： $dp[j-2]+sum[i]-sum[j-1]-C$ ，其中对于固定的 $i$ 来说， $sum[i]-C$ 是固定的，需要最大化的是： $dp[j-2]-sum[j-1]$

所以转移可以写成： $dp[i]=\max(dp[i-1],sum[i]-C+\max(dp[j-2]-sum[j-1]))$

其中 $j$ 的范围仍然是： $i-R+1\le j\le i-L+1$

如果直接枚举每个 $i$ 对应的所有 $j$ ，复杂度会达到 $O(nR)$ ，无法通过较大的数据范围。

观察发现，随着 $i$ 从小到大变化，合法的 $j$ 区间也是整体向右移动的。因此可以使用单调队列维护当前所有合法左端点 $j$ 中： $dp[j-2]-sum[j-1]$ 的最大值。

具体做法：

从左到右枚举右端点 $i$ 。
当 $j=i-L+1$ 合法时，把这个新的左端点加入单调队列。
单调队列中按照 dp[j-2]-sum[j-1] 从大到小维护。
如果队首的 $j<i-R+1$ ，说明这条灯带长度已经超过 $R$ ，需要弹出。
此时队首就是当前合法左端点中最优的 $j$ ，用它更新 dp[i]。
同时保留“不安装以 $i$ 结尾的灯带”的情况，即 dp[i]=dp[i-1]。

需要注意边界情况：

当 $j=1$ 时，前面没有位置，不需要间隔位置，此时前面的贡献应视为 $0$ 。
可以选择不安装任何灯带，所以答案不会小于 $0$ 。
星光值和答案可能很大，需要使用 long long。

单调队列中每个左端点最多进队一次、出队一次，所以动态规划部分是 $O(n)$ 。整体时间复杂度为： $O(n)$

参考代码

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

int n, L, R;
long long C;
long long a[200010];
long long sum[200010];
long long dp[200010];

long long getValue(int j){
    if(j <= 1){
        return -sum[j - 1];
    }
    return dp[j - 2] - sum[j - 1];
}

int main(){
    cin >> n >> L >> R >> C;

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

    deque<int> q;

    for(int i = 1; i <= n; i++){
        int j = i - L + 1;

        if(j >= 1){
            while(!q.empty() && getValue(q.back()) <= getValue(j)){
                q.pop_back();
            }
            q.push_back(j);
        }

        int left = i - R + 1;

        while(!q.empty() && q.front() < left){
            q.pop_front();
        }

        dp[i] = dp[i - 1];

        if(!q.empty()){
            dp[i] = max(dp[i], sum[i] - C + getValue(q.front()));
        }
    }

    cout << dp[n] << endl;

    return 0;
}