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

Sherry

2026-10-28 10:34:21

发布于：浙江

10阅读

0回复

0点赞

赛纲介绍

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

题目编号	题目名称	题目难度
T1	翻牌橱窗	入门
T2	野餐分装	普及-
T3	倒读便笺	普及-
T4	整箱发货	普及/提高-
T5	救援分区	普及/提高-
T6	互助训练	普及+/提高

T1 翻牌橱窗

题目大意

给出一个由 $0$ 和 $1$ 组成的矩阵，每次将指定行或指定列中的所有数字翻转，即 $0$ 变成 $1$ ， $1$ 变成 $0$ 。求所有操作结束后矩阵中 $1$ 的数量。

题解思路

按照操作顺序直接模拟即可。

如果操作一行，就固定行号，遍历这一行的所有列；如果操作一列，就固定列号，遍历这一列的所有行。将原来的数字 $a_{i,j}$ 修改为 $1-a_{i,j}$ ，就能完成翻转。

每次操作都在当前矩阵上修改，同一个位置被翻转两次后会恢复原状。所有操作结束后，遍历矩阵累加各位置的数字，就是黑色朝上的翻牌数量。

发现对于同一个位置的多次翻转，行与列的翻转产生的效果是相同的，翻转的处理顺序也不影响最终的结果，并且同一位置在经历偶数次的翻转后会恢复原状。因此可以先记录每一行与每一列的翻转情况，将行列的翻转次数简化到 $0$ 或 $1$ ，再对每一行和每一列进行翻转。

参考代码

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

int n,m;
int a[55][55];

void change(int op,int x){
    if(op==1){
        for(int j=1;j<=m;j++) a[x][j]=1-a[x][j];
    }
    else{
        for(int i=1;i<=n;i++) a[i][x]=1-a[i][x];
    }
}

int answer(){
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ans+=a[i][j];
        }
    }
    return ans;
}

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

    for(int i=1;i<=q;i++){
        int op,x;
        cin>>op>>x;
        change(op,x);
    }
    cout<<answer()<<endl;
    return 0;
}

T2 野餐分装

题目大意

将 $m$ 块饼干全部装入 $n$ 个餐盒，每盒至少装 $1$ 块，任意两盒的饼干数量相差不超过 $1$ 。求字典序最小的分装方案。

题解思路

先计算平均分配时的商和余数：

$b=\left\lfloor\frac{m}{n}\right\rfloor,\qquad r=m\bmod n$

由于任意两盒的数量之差不超过 $1$ ，每个餐盒只能装 $b$ 块或 $b+1$ 块。

先给每个餐盒装 $b$ 块，还剩 $r$ 块。因此恰好有 $r$ 个餐盒需要再装 $1$ 块，其余 $n-r$ 个餐盒保持不变。

要使字典序最小，就要让较小的数尽量靠前，所以前 $n-r$ 个餐盒装 $b$ 块，后 $r$ 个餐盒装 $b+1$ 块。题目保证 $m\ge n$ ，因此每盒至少有 $1$ 块饼干。

$m$ 最大为 $10^{18}$ ，需要使用 long long 保存饼干数量。

参考代码

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

long long n,m;

void solve(){
    long long b=m/n,r=m%n;
    for(long long i=1;i<=n;i++){
        if(i>1) cout<<" ";
        if(i<=n-r){
            cout<<b;
        }
        else{
            cout<<b+1;
        }
    }
    cout<<endl;
}

int main(){
    cin>>n>>m;
    solve();
    return 0;
}

T3 倒读便笺

题目大意

给出一个包含小写字母和合法圆括号的字符串。每次将最内层括号中的字母翻转并删除括号，直到所有括号都被删除，输出最终字符串。

题解思路

括号可能嵌套，因此需要先处理内层，再处理外层，可以用递归完成。

使用全局变量 pos 记录当前读到的位置。函数 solve() 负责处理当前这一层的内容，并返回其中所有内层括号已经处理完的字符串。

从当前位置开始，有三种情况：

遇到字母，直接加入当前结果，并将 pos 加一。
遇到左括号，先将 pos 加一，递归处理括号内部。递归返回后，跳过对应的右括号，将返回的字符串翻转，再接到当前结果后面。
遇到右括号或字符串末尾，结束当前层的处理并返回结果。

需要注意，递归函数遇到右括号时不会自己跳过它，而是由调用这一层的函数执行 pos++。这样每一对括号就能对应起来。

例如处理 ab(cd(ef)g)h 时，内层先返回 ef，调用者将它翻转为 fe，外层得到 cdfeg；外层返回后再翻转为 gefdc，最终得到 abgefdch。

虽然读取位置只向前移动，但同一个字母可能在多层括号中参与翻转和拼接。题目限制字符串长度不超过 $2000$ 、嵌套深度不超过 $100$ ，这种直接按层处理的做法就能够满足要求。

参考代码

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

string s;
int pos=0;

string solve(){
    string ans;
    while(pos<(int)s.size()&&s[pos]!=')'){
        if(s[pos]=='('){
            pos++;
            string t=solve();
            pos++;
            reverse(t.begin(),t.end());
            ans+=t;
        }
        else{
            ans+=s[pos];
            pos++;
        }
    }
    return ans;
}

int main(){
    cin>>s;
    cout<<solve()<<endl;
    return 0;
}

T4 整箱发货

题目大意

给出 $n$ 批零件的数量，每批可以不补充或补充 $1$ 个零件。选择至少 $k$ 批，使每批补充后的数量都能被同一个正整数 $d$ 整除，求 $d$ 的最大值。

题解思路

对于容量 $d$ ，数量为 $a_i$ 的一批零件能够被选中，当且仅当：

$a_i\bmod d=0\quad\text{或}\quad(a_i+1)\bmod d=0$

每批至少要装满一箱，因此答案不会超过 $v=\max(a_i)+1$ 。如果从大到小枚举每个 $d$ ，再逐批检查是否满足条件，最坏需要 $O(nv)$ 的时间，无法满足数据范围。

观察到 $a_i\le10^6$ ，可以用 cnt[x] 记录原数量为 $x$ 的批次有多少个，再改为枚举 $d$ 的倍数。

对于一个正倍数 $x$ ：

原数量为 $x$ 的批次，不补充就能整箱装好；
原数量为 $x-1$ 的批次，补充 $1$ 个后就能整箱装好。

因此，容量为 $d$ 时能够选择的批次数为：

$num(d)=\sum_{t=1}^{\lfloor v/d\rfloor}\bigl(cnt[td]+cnt[td-1]\bigr)$

当 $d\ge2$ 时，两个连续整数不可能同时被 $d$ 整除，所以同一批不会被重复统计。数量相同的不同批次则需要分别计数，这就是使用频次数组的原因。

枚举一个 $d$ 时，只需要检查约 $v/d$ 个倍数。即使检查所有候选值，总次数也不超过：

$\frac v2+\frac v3+\cdots+\frac vv=O(v\log v)$

这样就能将逐批判断改为可行的倍数统计。从 $v$ 开始向下枚举，第一次出现 num>=k 时，对应的 $d$ 就是最大答案。

任意正整数都可以通过不补充或补充 $1$ 变成偶数，因此 $d=2$ 对全部批次都可行。参考代码枚举到 $2$ 即可，合法输入下不会执行末尾的 return -1。

参考代码

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

int n,k,v;
int cnt[1000010];

int solve(){
    for(int d=v;d>=2;d--){
        int num=0;
        for(int x=d;x<=v;x+=d){
            num+=cnt[x]+cnt[x-1];
        }
        if(num>=k) return d;
    }
    return -1;
}

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        cnt[x]++;
        v=max(v,x+1);
    }
    cout<<solve()<<endl;
    return 0;
}

T5 救援分区

题目大意

给出一棵树，每个节点有人口数量，并可能设有医疗站和物资站。恰好删除一条边，使分出的两个区域都至少有一个医疗站和一个物资站，求两个区域人口总数之差的绝对值的最小值。无解时输出 $-1$ 。

题解思路

如果每次删除一条边后都重新遍历两个区域统计信息，会产生大量重复计算。可以先将树以 $1$ 号节点为根，统计每个节点的子树信息。

对于非根节点 $u$ ，删除它与父节点之间的边后，两个区域分别为：

以 $u$ 为根的子树；
整棵树除去这棵子树后的部分。

所以只要知道子树和整棵树的信息，就可以直接判断这条边能否删除，无需重新搜索。

参考代码先用 ord 数组模拟队列，得到父节点排在子节点前面的遍历顺序，并用 fa 记录父节点。再逆序遍历 ord，将每个节点的信息累加给父节点。由于孩子先处理，累加完成后：

people[u] 表示子树的人口总数；
med[u] 表示子树的医疗站数量；
sup[u] 表示子树的物资站数量。

根节点对应的三个值就是整棵树的总量。两个区域都有医疗站，等价于：

$0<med[u]<med[1]$

两个区域都有物资站，等价于：

$0<sup[u]<sup[1]$

当两个条件同时满足时，人口差为：

$\left|people[u]-(people[1]-people[u])\right| =\left|people[1]-2\times people[u]\right|$

枚举所有非根节点，在合法方案中取最小值。如果没有合法方案，则输出 $-1$ 。人口总数可能超过 int 范围，需要使用 long long。

参考代码

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

const int N=200010;
int n,tot,head[N],to[N*2],nxt[N*2];
int fa[N],ord[N],med[N],sup[N];
bool vis[N];
long long people[N];

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

bool build(){
    int tail=1;
    ord[1]=1;
    vis[1]=true;
    for(int i=1;i<=tail;i++){
        int u=ord[i];
        for(int e=head[u];e;e=nxt[e]){
            int v=to[e];
            if(vis[v]) continue;
            vis[v]=true;
            fa[v]=u;
            ord[++tail]=v;
        }
    }
    return tail==n;
}

long long solve(){
    for(int i=n;i>=2;i--){
        int u=ord[i],p=fa[u];
        people[p]+=people[u];
        med[p]+=med[u];
        sup[p]+=sup[u];
    }

    long long ans=LLONG_MAX;
    for(int u=2;u<=n;u++){
        if(med[u]>0&&med[u]<med[1]&&sup[u]>0&&sup[u]<sup[1]){
            ans=min(ans,abs(people[1]-2*people[u]));
        }
    }
    if(ans==LLONG_MAX) return -1;
    return ans;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>people[i]>>med[i]>>sup[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    build();
    cout<<solve()<<endl;
    return 0;
}

T6 互助训练

题目大意

将学员按原顺序划分为若干连续小组，每组人数在 $1\sim k$ 之间，相邻两组人数不能相同。每组的贡献为组内人数乘以初始能力最大值，求所有小组贡献之和的最大值。

题解思路

考虑最后一组包含多少人。假设前 $i$ 名学员已经分组，最后一组长度为 $len$ ，则这一组是 $[i-len+1,i]$ ，前面需要接上前 $i-len$ 人的一个合法划分。

由于相邻组人数不能相同，只记录前面部分的最大得分是不够的，还需要知道它最后一组的人数。

可以先设 $f[i][len]$ 表示前 $i$ 人已经合法分组，最后一组长度为 $len$ 时的最大得分。令 $p=i-len$ ，对于 $p>0$ ，转移为：

$f[i][len]=len\times\max(a_{p+1},\ldots,a_i) +\max_{\substack{1\le j\le\min(k,p)\\j\ne len}}f[p][j]$

如果前面的部分无法合法分组，则这一状态不可达。 $p=0$ 时没有前一组，可以直接将当前组作为第一组，前面部分的贡献为 $0$ 。

直接枚举当前位置、当前组长度和前一组长度，需要 $O(nk^2)$ 的时间。 $n$ 最大为 $10^5$ ， $k$ 最大为 $100$ ，转移次数可能达到 $10^9$ ，需要优化。

观察发现，每次查询前面部分时，只排除一种末组长度，也就是当前的 $len$ 。因此对于每个前缀，只需要记录：

best1[i]：前 $i$ 人所有合法划分中的最大得分；
id[i]：取得 best1[i] 的一种末组长度；
best2[i]：末组长度不同于 id[i] 的所有合法划分中的最大得分。

当准备接上一组长度为 $len$ 的学员时：

如果 id[p]!=len，直接使用 best1[p]；
如果 id[p]==len，就使用 best2[p]。

这样，每次都能直接得到允许接在当前组前面的最大得分。

对于固定的 $i$ ，从小到大枚举 $len$ 。每次把左端点向左扩展一位，用 mx=max(mx,a[i-len+1]) 维护当前组最大值。结合上面的查询方式，整个处理过程就降为 $O(nk)$ 。

算出当前长度对应的得分 now 后，再更新本位置的两个最优值。如果 now 大于 best1[i]，就将原来的最优值移到 best2[i]，并更新 best1[i] 和 id[i]；否则尝试用 now 更新 best2[i]。由于每种长度只枚举一次，两个候选对应的末组长度一定不同。

这里的“次优”不是严格小于最优的得分。两种不同的末组长度可能取得相同得分，此时 best2[i] 可以等于 best1[i]，不能丢掉这种情况。

初始时将状态设为负无穷，表示不可达；令 best1[0]=0、id[0]=0，由于真实组长至少为 $1$ ，第一组就能正常接在空前缀后面。最后输出 best1[n]，得分使用 long long 保存。

参考代码

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

const int N=100010;
const long long NEG=-(1LL<<60);
int n,k,id[N];
long long a[N],best1[N],best2[N];
// best2 对应不同的小组人数；两种人数的最优得分相同时，它可以等于 best1。

long long solve(){
    for(int i=0;i<=n;i++){
        best1[i]=best2[i]=NEG;
        id[i]=-1;
    }
    best1[0]=0;
    id[0]=0;

    for(int i=1;i<=n;i++){
        long long mx=0;
        for(int len=1;len<=k&&len<=i;len++){
            mx=max(mx,a[i-len+1]);
            int p=i-len;
            long long pre=best1[p];
            if(id[p]==len) pre=best2[p];
            if(pre==NEG) continue;

            long long now=pre+len*mx;
            if(now>best1[i]){
                best2[i]=best1[i];
                best1[i]=now;
                id[i]=len;
            }
            else if(now>best2[i]){
                best2[i]=now;
            }
        }
    }
    return best1[n];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    cout<<solve()<<endl;
    return 0;
}