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

Sherry

2026-10-04 10:29:17

发布于：浙江

8阅读

0回复

0点赞

赛纲介绍

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

题目编号	题目名称	题目难度
T1	星码校验	入门
T2	星光增幅	普及-
T3	星石叠合	普及-
T4	星港连桥	普及/提高-
T5	风向通道	普及/提高-
T6	星愿配对	普及/提高-

T1 星码校验

题目大意

给出 $n$ 个编号，分别计算每个编号从左到右的奇数位数字和、偶数位数字和。如果两者差值的绝对值不超过 $k$ ，则该编号为稳定星码。求稳定星码的数量。

题解思路

将编号作为字符串读入，依次遍历每一位，将字符减去 '0' 得到对应数字，再按位置分别累加。

需要注意，字符数组的下标从 $0$ 开始，所以偶数下标对应题目中的奇数位，奇数下标对应题目中的偶数位。

每处理完一个编号，判断 abs(odd-even)<=k 是否成立，成立则答案加一。

参考代码

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

char s[30];

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

    int ans=0;
    for(int i=1;i<=n;i++){
        cin>>s;
        int odd=0;
        int even=0;
        int len=strlen(s);

        for(int j=0;j<len;j++){
            if(j%2==0){
                odd+=s[j]-'0';
            }
            else{
                even+=s[j]-'0';
            }
        }

        if(abs(odd-even)<=k){
            ans++;
        }
    }

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

T2 星光增幅

题目大意

$n$ 盏灯的初始亮度都是 $0$ 。进行 $m$ 次区间增幅，每次将 $[l,r]$ 中所有灯的亮度增加 $w$ 。求最终的最高亮度，以及达到最高亮度的灯的数量。

题解思路

如果每次都遍历整个区间修改亮度，最坏需要 $O(nm)$ 的时间。由于只询问所有操作完成后的结果，可以使用差分数组。

设差分数组为 d。将区间 $[l,r]$ 全部增加 $w$ ，只需要修改两个位置：

$d[l]=d[l]+w,\qquad d[r+1]=d[r+1]-w$

所有操作结束后，从左到右求差分数组的前缀和，就能得到每盏灯的最终亮度。

用 now 记录当前亮度，mx 记录最高亮度，cnt 记录出现次数。如果 now>mx，更新最高亮度并将次数设为 $1$ ；如果 now==mx，将次数加一。

差分数组需要能够访问第 $n+1$ 个位置，但统计答案时只遍历 $1\sim n$ 。亮度最高可能达到 $2\times 10^{14}$ ，差分值和累计亮度都需要使用 long long。

参考代码

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

long long d[200010];

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

    for(int i=1;i<=m;i++){
        int l,r;
        long long w;
        cin>>l>>r>>w;
        d[l]+=w;
        d[r+1]-=w;
    }

    long long now=0;
    long long mx=-1;
    int cnt=0;
    for(int i=1;i<=n;i++){
        now+=d[i];
        if(now>mx){
            mx=now;
            cnt=1;
        }
        else if(now==mx){
            cnt++;
        }
    }

    cout<<mx<<" "<<cnt<<endl;
    return 0;
}

T3 星石叠合

题目大意

从左到右依次放入星石。如果最右端两块星石的数字相同，就将它们合成一块数字加 $1$ 的星石，并继续检查能否合成。求最终剩余星石的数量及从左到右的数字。

题解思路

每次合成都只会发生在最右端，可以使用栈维护当前剩余的星石。

用数组 st 模拟栈，top 表示栈内元素数量。每次将新数字放入栈顶，再检查栈顶两个数字是否相同。

如果相同，就令 st[top-1]++，再将 top 减一，表示两块星石合成一块。合成后的星石可能继续与前一块合成，所以这里需要使用 while 循环。

所有数字处理完后，top 就是剩余数量，st[1] 到 st[top] 就是从左到右的结果。

虽然有两层循环，但每次合成都使星石数量减少 $1$ ，总合成次数不超过 $n-1$ 。

参考代码

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

long long st[200010];

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

    int top=0;
    for(int i=1;i<=n;i++){
        long long x;
        cin>>x;
        st[++top]=x;

        while(top>=2&&st[top]==st[top-1]){
            st[top-1]++;
            top--;
        }
    }

    cout<<top<<endl;
    for(int i=1;i<=top;i++){
        cout<<st[i];
        if(i<top){
            cout<<" ";
        }
    }
    cout<<endl;
    return 0;
}

T4 星港连桥

题目大意

给出 $n$ 个星港和 $m$ 条候选桥梁，每条桥梁连接两个星港并有对应费用。选择一些桥梁使所有星港连通，求最小总费用；如果无法连通，则输出 $-1$ 。

题解思路

将星港看作点，桥梁看作无向边，建造费用看作边权。本题就是求无向图的最小生成树，可以使用 Kruskal 算法。

将所有边按费用从小到大排序，依次考虑是否选择。使用并查集维护当前已经连通的星港：

如果一条边的两个端点已经在同一个集合中，加入它会形成环，不需要选择。
如果两个端点位于不同集合，就选择这条边，累加费用，并合并两个集合。

每次选择的都是连接不同连通块的最便宜的边。如果某个最优方案没有这条边，加入它后可以在形成的环中，替换掉一条跨越这两个部分且费用不更低的边，总费用不会增加。因此按这个顺序选择能够得到最小生成树。

用 cnt 记录选择的边数。最后如果 cnt==n-1，说明所有星港已经连通，否则输出 $-1$ 。当 $n=1$ 时，不需要建桥，答案为 $0$ 。

参考代码使用路径压缩，并将较小的集合合并到较大的集合中，sz 记录集合大小。总费用需要使用 long long。

参考代码

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

struct edge{
    int u,v;
    long long w;
};

edge e[200010];
int fa[200010],sz[200010];

bool cmp(edge x,edge y){
    return x.w<y.w;
}

int find(int x){
    if(fa[x]==x){
        return x;
    }
    return fa[x]=find(fa[x]);
}

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

    for(int i=1;i<=m;i++){
        cin>>e[i].u>>e[i].v>>e[i].w;
    }

    for(int i=1;i<=n;i++){
        fa[i]=i;
        sz[i]=1;
    }

    sort(e+1,e+m+1,cmp);

    long long ans=0;
    int cnt=0;
    for(int i=1;i<=m;i++){
        int x=find(e[i].u);
        int y=find(e[i].v);
        if(x==y){
            continue;
        }

        if(sz[x]>sz[y]){
            swap(x,y);
        }
        fa[x]=y;
        sz[y]+=sz[x];
        ans+=e[i].w;
        cnt++;
    }

    if(cnt==n-1){
        cout<<ans<<endl;
    }
    else{
        cout<<-1<<endl;
    }

    return 0;
}

T5 风向通道

题目大意

每个格子有一个方向，可以向上下左右相邻格移动。如果移动方向与出发格子的方向相同，代价为 $0$ ；否则代价为 $1$ 。求起点到终点的最小总代价。

题解思路

将每个格子看作一个点，相邻格子之间的移动看作有向边。边权只可能是 $0$ 或 $1$ ，可以使用 0-1 BFS。

用 dis[x][y] 记录到达格子 $(x,y)$ 的最小能量。初始时将所有距离设为无穷大，起点距离设为 $0$ ，放入双端队列。

每次取出队首，检查四个方向。设移动到相邻格的代价为 $w$ ，如果：

$dis[x][y]+w<dis[nx][ny]$

就更新相邻格的距离，并根据代价决定入队位置：

$w=0$ 时，放到队首；
$w=1$ 时，放到队尾。

这样能够优先处理距离较小的位置：零代价移动仍在当前距离层，一代价移动进入下一层。格子第一次从队首取出并处理时，最短距离已经确定，可以用 vis 标记，跳过之后重复取出的记录。

需要注意，代价由出发格子 g[x][y] 决定；也不能在第一次入队时就把格子标记为已确定，因为之后仍可能找到代价更小的路径。

参考代码

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

struct node{
    int x,y;
};

int n,m;
char g[1010][1010];
int dis[1010][1010];
bool vis[1010][1010];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
char dc[4]={'U','D','L','R'};

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

    for(int i=1;i<=n;i++){
        cin>>(g[i]+1);
    }
    memset(dis,0x3f,sizeof(dis));

    int sx,sy,tx,ty;
    cin>>sx>>sy>>tx>>ty;

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

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

        int x=now.x;
        int y=now.y;
        if(vis[x][y]){
            continue;
        }
        vis[x][y]=true;

        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;
            }

            int w=1;
            if(g[x][y]==dc[i]){
                w=0;
            }

            if(dis[x][y]+w<dis[nx][ny]){
                dis[nx][ny]=dis[x][y]+w;
                if(w==0){
                    q.push_front({nx,ny});
                }
                else{
                    q.push_back({nx,ny});
                }
            }
        }
    }

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

T6 星愿配对

题目大意

将 $n$ 块星愿石全部两两配对，每块石头恰好使用一次。第 $i$ 块和第 $j$ 块配对得到 $c_{i,j}$ 点星愿值，求最大总星愿值。

题解思路

$n$ 不超过 $20$ ，可以用一个整数的二进制位表示哪些石头已经参与配对，进行状态压缩动态规划。

用状态 $s$ 的第 $i-1$ 位表示第 $i$ 块石头是否已经使用：这一位为 $1$ 表示已使用，为 $0$ 表示未使用。

dp[s] 记录按下面的顺序配对、到达状态 $s$ 时能够获得的最大星愿值。初始时 dp[0]=0，其余状态设为 $-1$ ，表示尚未到达。题目保证星愿值非负，因此可以用 $-1$ 区分不可达状态。

对于每个可达且尚未配完的状态，先找到编号最小的未使用石头 $i$ ，再枚举另一块未使用的石头 $j$ ，将它们配成一对。

只需要枚举 $j>i$ ，因为编号小于 $i$ 的石头已经全部使用。令新状态为：

$t=s\;|\;(1<<(i-1))\;|\;(1<<(j-1))$

这里的 | 是按位或运算，将对应的两个二进制位设为 $1$ 。转移为：

$dp[t]=\max(dp[t],dp[s]+c_{i,j})$

固定最小的未使用编号不会漏掉最优配对：对于任意一种完整配对方案，都可以先处理包含这块石头的一对，再用相同规则处理剩余石头。配对的先后顺序不会改变总星愿值。

每次转移都会将两个原本为 $0$ 的位置变为 $1$ ，所以 $t>s$ ，从小到大枚举状态即可。全部石头都使用时，状态为 $2^n-1$ ，答案就是 dp[(1<<n)-1]。

最多枚举 $2^n$ 个状态，每个状态用 $O(n)$ 的时间寻找石头和枚举搭档，总时间复杂度为 $O(n2^n)$ ，空间复杂度为 $O(2^n+n^2)$ 。总星愿值可能达到 $10^{10}$ ，需要使用 long long。

参考代码

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

long long c[25][25];
long long dp[1<<20];

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

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

    int lim=1<<n;
    for(int s=0;s<lim;s++){
        dp[s]=-1;
    }
    dp[0]=0;

    for(int s=0;s<lim-1;s++){
        if(dp[s]==-1){
            continue;
        }

        int i=1;
        while(s&(1<<(i-1))){
            i++;
        }

        for(int j=i+1;j<=n;j++){
            if(s&(1<<(j-1))){
                continue;
            }
            int t=s|(1<<(i-1))|(1<<(j-1));
            dp[t]=max(dp[t],dp[s]+c[i][j]);
        }
    }

    cout<<dp[lim-1]<<endl;
    return 0;
}