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

Sherry

2026-09-03 11:42:23

发布于：浙江

11阅读

0回复

0点赞

赛纲介绍

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

题目编号	题目名称	题目难度
T1	彩灯折返	入门
T2	星环巡检	普及-
T3	星尘观测窗	普及-
T4	星轨校准	普及-
T5	隔墙穿行	普及/提高-
T6	星塔连线	普及/提高-

T1 彩灯折返

题目大意

机器人从第 $p$ 盏灯出发，按照初始方向在 $n$ 盏灯之间往返移动。每次操作先点亮当前位置，再移动一格；如果下一格越界，则先掉头再移动。

求 $q$ 次操作后每盏灯被点亮的次数。

题解思路

按照题意直接模拟机器人的位置和方向。

使用 dir 表示当前方向：向右时为 $1$ ，向左时为 $-1$ 。每次操作先令当前位置的计数加一，再检查 $p+dir$ 是否越界。如果越界，就令 dir=-dir，最后移动到 $p+dir$ 。

当 $n=1$ 时，机器人不会移动，唯一一盏灯会被点亮 $q$ 次，对此情况单独处理。

参考代码

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

long long ans[200010];

int main(){
    int n,p;
    long long q;
    char op;
    cin>>n>>q>>p>>op;

    if(n==1){
        cout<<q<<endl;
        return 0;
    }

    int dir;
    if(op=='R'){
        dir=1;
    }
    else{
        dir=-1;
    }

    for(long long i=1;i<=q;i++){
        ans[p]++;
        if(p+dir<1||p+dir>n){
            dir=-dir;
        }
        p=p+dir;
    }

    for(int i=1;i<=n;i++){
        cout<<ans[i];
        if(i<n){
            cout<<" ";
        }
    }
    cout<<endl;

    return 0;
}

T2 星环巡检

题目大意

$n$ 个展台围成一圈。机器人从第 $p$ 个展台开始，每次先记录当前位置，再顺时针移动 $k$ 个展台。

求 $q$ 次巡检中记录过多少个不同的展台。

题解思路

将展台编号放在模 $n$ 的意义下考虑。机器人记录的位置依次为：

$p, p+k, p+2k, \cdots \pmod n$

设机器人经过 $t$ 次移动后第一次回到起点，则需要满足：

$tk\equiv 0\pmod n$

最小的正整数 $t$ 为：

$\frac{n}{\gcd(n,k)}$

因此，机器人移动形成的循环中共有 $\dfrac{n}{\gcd(n,k)}$ 个不同展台。如果巡检次数 $q$ 小于循环长度，只会记录前 $q$ 个不同展台；否则会记录完整个循环。

答案为：

$\min\left(q,\frac{n}{\gcd(n,k)}\right)$

初始位置 $p$ 只影响具体经过哪些展台，不影响不同展台的数量。

参考代码

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

long long gcd(long long a,long long b){
    while(b!=0){
        long long t=a%b;
        a=b;
        b=t;
    }
    return a;
}

long long getans(long long n,long long k,long long q){
    long long g=gcd(n,k);
    long long len=n/g;

    if(q<len){
        return q;
    }
    else{
        return len;
    }
}

int main(){
    long long n,k,p,q;
    cin>>n>>k>>p>>q;

    cout<<getans(n,k,q)<<endl;

    return 0;
}

T3 星尘观测窗

题目大意

给出长度为 $n$ 的序列，统计有多少个连续区间 $[l,r]$ 满足：

$\max(a_l,a_{l+1},\cdots,a_r)-\min(a_l,a_{l+1},\cdots,a_r)\le D$

题解思路

使用双指针维护一个满足条件的滑动窗口 $[l,r]$ 。

从左到右枚举右端点 $r$ ，将 $a_r$ 加入窗口。参考代码使用 map 记录窗口内每个数的出现次数，因此：

mp.begin()->first 是窗口最小值；
mp.rbegin()->first 是窗口最大值。

如果最大值与最小值之差大于 $D$ ，就不断删除左端点对应的元素并右移 $l$ ，直到窗口重新满足条件。

对于固定的右端点 $r$ ，当 $[l,r]$ 满足条件时，它的任意后缀也满足条件。因此，以 $r$ 为右端点的合法区间共有：

$r-l+1$

将这个数量累加到答案中即可。答案最多达到 $\dfrac{n(n+1)}2$ ，需要使用 long long。

每个元素至多进入和离开窗口一次。

参考代码

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

long long a[200010];

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

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

    map<long long,int> mp;

    int l=1;
    long long ans=0;

    for(int r=1;r<=n;r++){
        mp[a[r]]++;

        while(mp.rbegin()->first-mp.begin()->first>D){
            mp[a[l]]--;
            if(mp[a[l]]==0){
                mp.erase(a[l]);
            }
            l++;
        }

        ans+=r-l+1;
    }

    cout<<ans<<endl;

    return 0;
}

T4 星轨校准

题目大意

给出 $n$ 个信号点的位置。每移动一个信号点 $1$ 个单位会产生 $1$ 的代价。

选择至少 $k$ 个信号点，将它们移动到同一个整数位置，求最小总代价。

题解思路

如果一个方案将多于 $k$ 个点移动到同一位置，那么只保留其中任意 $k$ 个点，代价不会增加。因此只需要考虑恰好选择 $k$ 个点。

先将所有位置从小到大排序。最优选择一定可以对应排序数组中一段长度为 $k$ 的连续区间：如果选择了区间两侧较远的点，却跳过了中间的点，用中间的点替换较远的点不会使代价变大。

对于一段排好序的数，将所有数移动到中位数时绝对距离之和最小。因此枚举每个长度为 $k$ 的区间 $[l,r]$ ，其中：

$r=l+k-1,qquad mid=\left\lfloor\frac{l+r}{2}\right\rfloor$

目标位置取 $a_{mid}$ 。设 pre[i] 为排序后前 $i$ 个数的前缀和，则左侧所有点移动到中位数的代价为：

$a_{mid}(mid-l+1)-(pre[mid]-pre[l-1])$

右侧所有点移动到中位数的代价为：

$(pre[r]-pre[mid])-a_{mid}(r-mid)$

两部分相加就是当前区间的最小代价，枚举所有区间取最小值即可。 $k$ 为偶数时，两个中间数之间的任意整数都能取得最小值，参考代码选择左侧中位数，同样正确。

参考代码

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

long long a[200010],pre[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);

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

    long long ans=4000000000000000000LL;

    for(int l=1;l+k-1<=n;l++){
        int r=l+k-1;
        int mid=(l+r)/2;

        long long left=a[mid]*(mid-l+1)-(pre[mid]-pre[l-1]);
        long long right=(pre[r]-pre[mid])-a[mid]*(r-mid);
        long long now=left+right;

        if(now<ans){
            ans=now;
        }
    }

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

T5 隔墙穿行

题目大意

在一个由空地和墙壁组成的迷宫中，从起点走到终点。可以正常走到相邻空地，也可以一步穿过相邻的一堵墙，到达墙另一侧的空地，但不能连续两步穿墙。

求到达终点的最少步数，无法到达则输出 $-1$ 。

题解思路

每次正常移动或穿墙移动的代价都是 $1$ ，可以使用 BFS 求最短路。

能否在下一步穿墙，不仅与当前位置有关，还与上一步是否穿墙有关。因此将状态设为：

$(x,y,last)$

其中 last=0 表示上一步不是穿墙，last=1 表示上一步是穿墙。使用 dis[x][y][last] 记录到达该状态的最少步数。

从一个状态出发有两类转移：

如果相邻格是空地，可以正常走到相邻格，新状态的 last=0。
只有当当前状态的 last=0 时才能穿墙。如果相邻格是墙、同方向再前进一格仍在迷宫内且为空地，就可以一步到达墙后的空地，新状态的 last=1。

BFS 第一次到达每个状态时得到的就是最短距离。最终取终点两个状态的较小距离；如果均不可达，则输出 $-1$ 。

状态数不超过 $2nm$ ，每个状态只会检查四个方向。

参考代码

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

struct node{
    int x,y,last;
};

int n,m;
int a[1010][1010];
int dis[1010][1010][2];
int sx,sy,tx,ty;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

int inside(int x,int y){
    return x>=1&&x<=n&&y>=1&&y<=m;
}

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

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

    cin>>sx>>sy>>tx>>ty;

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

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

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

        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];

            if(inside(nx,ny)&&a[nx][ny]==0&&dis[nx][ny][0]==-1){
                dis[nx][ny][0]=dis[x][y][last]+1;
                q.push({nx,ny,0});
            }

            int wx=x+dx[i];
            int wy=y+dy[i];
            int px=x+2*dx[i];
            int py=y+2*dy[i];

            if(last==0&&inside(wx,wy)&&inside(px,py)&&a[wx][wy]==1&&a[px][py]==0&&dis[px][py][1]==-1){
                dis[px][py][1]=dis[x][y][last]+1;
                q.push({px,py,1});
            }
        }
    }

    int ans=-1;
    if(dis[tx][ty][0]!=-1){
        ans=dis[tx][ty][0];
    }
    if(dis[tx][ty][1]!=-1&&(ans==-1||dis[tx][ty][1]<ans)){
        ans=dis[tx][ty][1];
    }

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

T6 星塔连线

题目大意

给出一棵以 $1$ 号节点为根的树，每个节点有一个初始亮度。一次操作可以将某个节点的整棵子树亮度全部加 $1$ 或全部减 $1$ 。

求使所有节点亮度变为 $0$ 的最少操作次数。

题解思路

在节点 $u$ 上进行的操作只会影响 $u$ 及其后代，不会再影响它的父节点。因此可以按照从根到叶子的顺序依次确定每个节点必须进行的操作。

设 effect[u] 表示根到 $u$ 的路径上已经确定的所有操作，对 $u$ 及其子树产生的累计影响。

对于根节点，为了将亮度 $a_1$ 变成 $0$ ，必须产生净影响：

$effect[1]=-a_1$

所需操作次数为 $|effect[1]|$ 。

对于非根节点 $u$ ，设父节点为 $f$ 。处理 $u$ 前，祖先操作已经使它的亮度变为：

$a_u+effect[f]$

为了让 $u$ 变成 $0$ ，必须在以 $u$ 为根的子树上补充净操作量：

$need=-(a_u+effect[f])$

这需要 $|need|$ 次操作，并且：

$effect[u]=effect[f]+need$

处理完父节点后有 $effect[f]=-a_f$ ，因此也可以写成：

$need=a_f-a_u$

所以答案等价于：

$|a_1|+\sum_{u\ne 1}|a_u-a_{\mathrm{fa}(u)}|$

这个选择是被当前节点变为 $0$ 的要求唯一确定的。来自后代的操作无法影响当前节点，所以不可能通过之后的操作减少这部分代价。因此逐层累加 $|need|$ 就能得到最优答案。

参考代码先用栈得到父节点一定先于子节点的遍历顺序，再依次进行上述计算，避免递归层数过深。

每个节点处理一次，每条边遍历常数次。

参考代码

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

int head[200010],to[400010],nxt[400010],cnt;
int fa[200010],st[200010],ord[200010];
long long a[200010],effect[200010];
long long ans;

void add(int u,int v){
    cnt++;
    to[cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

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

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

    for(int i=1;i<=n-1;i++){
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }

    int top=0;
    int tot=0;
    st[++top]=1;
    fa[1]=0;

    while(top>0){
        int u=st[top];
        top--;
        ord[++tot]=u;

        for(int i=head[u];i!=0;i=nxt[i]){
            int v=to[i];
            if(v==fa[u]){
                continue;
            }
            fa[v]=u;
            st[++top]=v;
        }
    }

    effect[1]=-a[1];
    ans=llabs(effect[1]);

    for(int i=2;i<=tot;i++){
        int u=ord[i];
        int f=fa[u];
        long long need=-(a[u]+effect[f]);
        ans+=llabs(need);
        effect[u]=effect[f]+need;
    }

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