郑州大学2024年3月acm实验室招新赛题解（A-L）

这里感谢一下计算机学术交流协会会长，acm实验室的中坚成员，以及本次比赛的出题人之一孙昱涵将他的账号借给了我。

回顾一下的话，这场的难度其实不是很大，不过对招新的新手来说难度还是挺大的。去掉签到都没签出来的选手的话，可以看到大部分选手都只能做出四五题左右（最前面那两个是打星的非正式参赛选手）。

题目难度我觉得按顺序应该是：$A,I,L<C,E,F<D,J,K<B<G,H$ 。

虽然不连校园网大概率连不上，不过姑且还是放一下比赛链接

---

A.区间次大值

题面：

思路：

可以跑 $n^2$，所以直接暴力，枚举左端点 $l$，然后向右移动右端点 $r$，维护住区间的次大值，边移动边统计答案即可。

话说赛时评测机炸了，这题跑出来的全是WA。

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e3+5;
typedef long long ll;
 
int n,a[maxn];
ll ans=0;
 
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int l=1;l<=n;l++){
        int mx=a[l],mx2=0;
        for(int r=l+1;r<=n;r++){
            if(a[r]>mx){
                mx2=mx;
                mx=a[r];
            }
            else if(a[r]>mx2){
                mx2=a[r];
            }
            ans+=mx2;
        }
    }
    cout<<ans;
    return 0;
}

---

B.上课签到

题面：

思路：

不考虑统计路径上最大 $a_i$ 的条件的话，就是个普通的最短路。体感上感觉直接去找小于等于 $h$ 的所有路径上的最大 $a_i$ 是不太可能的。但是如果我们验证答案就会很简单，也就是我们提前设定一个最大的 $a_i$ 值，然后跑 $dijkstra$，这样一次验证就是 $(n+m)logn$ 的复杂度。

而这个答案具有单调性，即如果答案是 $x$，那么所有大于 $x$ 的答案也是可以通过验证的。这样就可以二分答案了。总的时间复杂度就是 $(n+m)lo{g}^{2}n$，可以通过。

这个二分既可以是值域上的二分，也可以是对点的 $a_i$ 值排序然后在上面二分。

code：

值域二分：

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define mk make_pair
using namespace std;
typedef long long ll;
const int maxn=1e4+5;
const int maxm=2e4+5;
const ll inf=1e18;
 
int n,m,st,ed;
ll H,a[maxn];
 
int head[maxn],cnt;
struct edge{
    int nxt,v;
    ll w;
}e[maxm<<1];
void add(int u,int v,ll w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
 
bool dijkstra(ll bound){
    vector<ll> d(maxn,inf);
    vector<bool> vis(maxn,false);
    priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > h;
    d[st]=0;
    h.push(mk(0ll,st));
    while(!h.empty()){
        int u=h.top().second;
        h.pop();
        if(u==ed)return true;
        if(vis[u])continue;
        else vis[u]=true;
        for(int i=head[u],v,w;i;i=e[i].nxt){
            v=e[i].v;
            w=e[i].w;
            if(d[u]+w>H || a[v]>bound)continue;
            if(d[v]>d[u]+w){
                d[v]=d[u]+w;
                h.push(mk(d[v],v));
            }
        }
    }
    return false;
}
 
int main(){
    cin>>n>>m>>st>>ed>>H;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1,u,v,w;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    ll l=a[st],r=1e18,mid;
    while(l<r){
        mid=(l+r)>>1;
        if(dijkstra(mid))r=mid;
        else l=mid+1;
    }
    cout<<((l==1e18)?-1:l)<<endl;
    return 0;
} 

点集二分：

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define mk make_pair
using namespace std;
typedef long long ll;
const int maxn=1e4+5;
const int maxm=2e4+5;
const ll inf=1e9;
 
int n,m,st,ed;
ll H,a[maxn],tmp[maxn];
 
int head[maxn],cnt;
struct edge{
    int nxt,v,w;
}e[maxm<<1];
void add(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
 
bool dijkstra(ll bound){
    if(bound<a[st])return false;
    vector<ll> d(maxn,inf);
    vector<bool> vis(maxn,false);
    priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > h;
    d[st]=0;
    h.push(mk(0ll,st));
    while(!h.empty()){
        int u=h.top().second;
        h.pop();
        if(u==ed)return true;
        if(vis[u])continue;
        else vis[u]=true;
        for(int i=head[u],v,w;i;i=e[i].nxt){
            v=e[i].v;
            w=e[i].w;
            if(d[u]+w>H || a[v]>bound)continue;
            if(d[u]+w<d[v]){
                d[v]=d[u]+w;
                h.push(mk(d[v],v));
            }
        }
    }
    return false;
}
 
int main(){
    cin>>n>>m>>st>>ed>>H;
    for(int i=1;i<=n;i++)cin>>a[i],tmp[i]=a[i];
    for(int i=1,u,v,w;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    sort(tmp+1,tmp+n+1);
    if(!dijkstra(tmp[n])){
        cout<<-1;
        return 0;
    }
    int l=1,r=n,mid;
    while(l<r){
        mid=(l+r)>>1;
        if(dijkstra(tmp[mid]))r=mid;
        else l=mid+1;
    }
    cout<<tmp[l]<<endl;
    return 0;
} 

---

C.魔法森林（一）

题面：

思路：

跟着操作跑一遍就行了，这题没人写是我没想到的，都被吓住了。

这个题的难点在于传送法阵的强制传送机制。首先需要将两个法阵的位置对应起来，其次需要在移动的时候实现这个传送。

对应法阵位置的方法：因为一个一个字符读取图的时候一定会先遇到一个字母，再遇到一个相同字母。所以存储第一个字母的位置，在读到第二个字母的时候将两个坐标用map相互映射一下就好。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int maxn=5005;
 
int n,m;
string mp[maxn];
map<pair<int,int>,pair<int,int> > sp;
map<char,pair<int,int> > tmp;
 
int fx[]={1,-1,0,0},fy[]={0,0,1,-1};
 
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>mp[i];
        mp[i]=" "+mp[i];
        for(int j=1;j<=m;j++){
            if(mp[i][j]!='.' && mp[i][j]!='#'){
                if(tmp.find(mp[i][j])==tmp.end())tmp[mp[i][j]]=make_pair(i,j);
                else {
                    pair<int,int> a=tmp[mp[i][j]],b=make_pair(i,j);
                    sp[a]=b;
                    sp[b]=a;
                }
            }
        }
    }
     
    int x,y,q;
    cin>>x>>y>>q;
    for(;q;q--){
        char op;
        cin>>op;
        int st;
        switch(op){
            case 'D':st=0;break;
            case 'U':st=1;break;
            case 'R':st=2;break;
            case 'L':st=3;break;
        }
        int vx=x+fx[st],vy=y+fy[st];
        if(vx<1 || vx>n || vy<1 || vy>m || mp[vx][vy]=='#')continue;
         
        if(mp[vx][vy]!='.'){
            x=sp[make_pair(vx,vy)].first;
            y=sp[make_pair(vx,vy)].second;
        }
        else {
            x=vx;
            y=vy;
        }
    }
    cout<<x<<" "<<y<<endl;
    return 0;
}

---

D.魔法森林（二）

题面：

思路：

一个耿直的BFS，赛时没有写出来的就nm离谱，代码能力不行导致的。

注意一下传送阵是强制传送的。

对传送法阵的处理还是和 $C$ 题一致，难点主要是要想明白在BFS时需要使用 $vis$ 数组对已经经过的位置进行标记，在碰到传送阵时，这个标记是标记传送前的位置还是传送后的位置。

我们 $vis$ 数组的职责是标记已经经过的位置，因为走这个位置之后所有可能的行走路径都会重复。换句话说，我们如果走某个位置之后所有可能的行走路径都会重复，那么就对这个位置进行标记。我们在进入一个位置的传送阵之后，我们还可以从另一个传送阵再传回来，这样有可能到终点更快，而我们如果再走前一个传送阵，后面就会重复，所以我们应该标记的是传送前的法阵位置。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
#define mk make_pair
using namespace std;
const int maxn=5005;
 
int n,m;
string mp[maxn];
map<pair<int,int>,pair<int,int> > sp;
map<char,pair<int,int> > tmp;
int vis[maxn][maxn];
 
int fx[]={1,-1,0,0},fy[]={0,0,1,-1};
 
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>mp[i];
        mp[i]=" "+mp[i];
        for(int j=1;j<=m;j++){
            if(mp[i][j]!='.' && mp[i][j]!='#'){
                if(tmp.find(mp[i][j])==tmp.end())tmp[mp[i][j]]=make_pair(i,j);
                else {
                    pair<int,int> a=tmp[mp[i][j]],b=make_pair(i,j);
                    sp[a]=b;
                    sp[b]=a;
                }
            }
        }
    }
     
    int sx,sy,ex,ey;
    queue<pair<int,int> > q;
    cin>>sx>>sy>>ex>>ey;
    vis[sx][sy]=1;
    q.push(mk(sx,sy));
    while(!q.empty()){
        int ux=q.front().first,uy=q.front().second;
        q.pop();
        if(ux==ex && uy==ey){
            cout<<vis[ux][uy]-1;
            return 0;
        }
        for(int i=0,x,y;i<4;i++){
            x=ux+fx[i];
            y=uy+fy[i];
            if(x<1 || x>n || y<1 || y>m || mp[x][y]=='#' || vis[x][y])continue;
             
            if(mp[x][y]=='.'){
                vis[x][y]=vis[ux][uy]+1;
                q.push(mk(x,y));
            }
            else {
                int tx=sp[make_pair(x,y)].first,ty=sp[make_pair(x,y)].second;
                vis[tx][ty]=vis[ux][uy]+1;
                q.push(mk(tx,ty));
            }
        }
    }
    cout<<-1<<endl;
    return 0;
}

---

E.LOP

题面：

思路：

CF原题，这个题主要是诱导你往游戏规则上想，实际上由于最后一局就是决胜局，因此最后一个赢的就是赢家。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
 
string s;
 
int main(){
    cin>>s;
    cout<<s[s.length()-1];
    return 0;
}

---

F.跳格子

题面：

思路：

对某个位置的砖块，它可以由前两个砖块转移过来，因此走到第 $i$ 个位置的砖块的方法数就是到达 $i-1$ 和 $i-2$ 位置上的方法数之和。直接递推即可。

code：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+5;
 
int n;
ll dp[maxn];
 
int main(){
    cin>>n;
    dp[1]=dp[2]=1;
    for(int i=3;i<=n;i++){
        dp[i]=(dp[i-1]+dp[i-2])%mod;
    }
    cout<<dp[n];
    return 0;
}

---

G.猜数字

题面：

思路：

魔王题之一，概率区间dp。

我们在随机取数的时候，除了一发入魂的情况，这个区间都是在一段一段变小的。而转移到某一段子区间的时候，如果我们知道这个子区间的期望，那么我们就可以算出原区间由这个情况转移过来的期望。而子区间也是这样来算每一种情况贡献的期望。

那么思路就比较明显了，设 $dp[i][j]$ 为区间 $[i,j]$ 生成 $x$ 的期望。发现下次生成的数只有三种情况：

1. 正好生成 $x$，这时期望贡献就是 $\frac{1}{j-i+1}$。
2. 生成的数为 $k(i\le k<x)$ 时，这时候期望为 $\frac{1}{j-i+1}\ast (dp[k][j]+1)$
3. 生成的数为 $k(x<k\le j)$ 时，这时候期望为 $\frac{1}{j-i+1}\ast (dp[i][k]+1)$

那么总的期望为： $$\begin{gathered} dp[i][j]=\frac{1}{j-i+1}+\sum _{k=i+1}^{x-1}\frac{1}{j-i+1}\ast (dp[k][j]+1)+ \\ \sum _{k=x+1}^{j-1}\frac{1}{j-i+1}\ast (dp[i][k]+1) \end{gathered}$$$$=\frac{1}{j-i+1}\ast (1+\sum _{k=i+1}^{x-1}(dp[k][j]+1)+\sum _{k=x+1}^{j-1}(dp[i][k]+1))$$

这里没有把求和符号中的 $+1$ 那个部分单独拆出来，是因为 $i+1$ 与 $x-1$ 以及 $x+1$ 与 $j-1$ 的大小关系不明确，有可能 $i+1<x-1$ 也有可能 $i+1>x-1$，直接拆出来不知道有几个 $1$。

回到正题，这个式子我们正常算的时候需要枚举左右端点和枚举 $k$，是 $O(n^3)$ 的，但是题目要求是 $O(n^2)$，的那么如何优化这个式子呢，如果我们把 $dp[k][j]+1$ 这个部分看成一个整体，发现当 $j$ 固定的时候，它相当于一个前缀和。同理当 $i$ 固定的时候，$dp[i][k]+1$ 也相当于一个前缀和。

那么怎么边算边记录这个前缀和呢？假设我们第一维枚举 $i$，第二维枚举 $j$，那么我们第二维在枚举 $j$ 的时候，$i$ 就是固定的，用一个变量记录 $s_{ik}={\sum }_{k=x+1}^{j-1}(dp[i][k]+1)$ 即可。而 ${\sum }_{k=i+1}^{x-1}(dp[k][j]+1)$ 这个前缀和看似不好处理，实际上我们对每个 $j$ 单独开一个变量来记录就可以了，具体来说就是用 $s_{kj}[j]={\sum }_{k=i+1}^{x-1}(dp[k][j]+1)$。

这题我一开始其实是从区间 $[1,n]$ 为起点开始推的，但是从 $[i,j]\to [1,n]$ 的期望和 $[i,j]\to x$ 的期望不是一回事，两者不能直接互通，导致想法假了，赛时被单防。不能给新生一点小小的acm震撼真是太可惜了。

code：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=5005;
const ll mod=998244353;
 
ll qpow(ll a,ll b){
    b%=mod-1;
    ll base=a%mod,ans=1;
    while(b){
        if(b&1){
            ans*=base;
            ans%=mod;
        }
        base*=base;
        base%=mod;
        b>>=1;
    }
    return ans;
}
ll inv(ll x){return qpow(x,mod-2);}
 
int n,x;
ll f[maxn][maxn];
ll skj[maxn],sik;
 
int main(){
    cin>>n>>x;
    for(int i=x;i>=1;i--){
        sik=0;
        for(int j=x;j<=n;j++){
            f[i][j]=(1ll+skj[j]+sik)*inv(j-i+1)%mod;
            skj[j]=(skj[j]+f[i][j]+1)%mod;
            sik=(sik+f[i][j]+1)%mod;
        }
    }
    cout<<f[1][n]<<endl;
    return 0;
}

---

H.抽卡记录

题面：

思路：

魔王题之一。

如果去除掉变化至多 $k$ 次的限制条件，这个题就是个裸的 $LIS$ （最长上升子序列）问题。加上 $k$ 次的限制条件就在原来的基础上多加一维其实就可以了，要界定最后是上升段还是下降段，就再加一维，这本质还是 $LIS$ 问题。经验还是不足。

具体来说，设 $dp[i][j][0/1]$ 表示前 $i$ 个数以第 $i$ 个数结尾（也就是必选第 $i$ 个数），变化了 $j$ 次，最后一段是在上升段还是下降段的最少删除次数。

转移的话就是枚举 $1\sim i-1$ 尝试由前面的某个位置转移过来。转移方法看代码。

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1005;
const int maxk=15;
const int inf=1e9;
 
int n,m,a[maxn];
//前i个数，变化k次，现在向上/下变化的最小删除次数 
int dp[maxn][maxk][2];
 
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<=1;k++)
                dp[i][j][k]=inf;
     
    for(int i=1;i<=n;i++){
        dp[i][0][0]=dp[i][0][1]=i-1;
        for(int j=i-1;j>=1;j--){
            for(int k=0;k<=m;k++){
                if(a[i]>a[j]){
                    dp[i][k][0]=min(dp[i][k][0],dp[j][k][0]+i-j-1);
                    if(k>0)dp[i][k][0]=min(dp[i][k][0],dp[j][k-1][1]+i-j-1);
                }
                else if(a[i]<a[j]){
                    dp[i][k][1]=min(dp[i][k][1],dp[j][k][1]+i-j-1);
                    if(k>0)dp[i][k][1]=min(dp[i][k][1],dp[j][k-1][0]+i-j-1);
                }
                else continue;
            }
        }
    }
    int ans=n-1;
    for(int i=1;i<=n;i++)
        for(int k=0;k<=m;k++)
            ans=min(ans,min(dp[i][k][0],dp[i][k][1])+n-i);
    cout<<n-ans;
    return 0;
}

---

I.安达的二维矩阵

题面：

思路：

签到题。读入第 $i$ 行的时候顺便数一下当前行有多少个 $1$，另外设置两个变量分别记录之前 $1$ 最多的行的编号和 $1$ 的个数，如果第 $i$ 行的 $1$ 个数更多，就转而记录第 $i$ 行的信息。

code：

#include <iostream>
#include <cstdio>
using namespace std;
 
int n,m;
 
int main(){
    cin>>n>>m;
    int x=1,y=0;
    for(int i=1,t;i<=n;i++){
        int cnt=0;
        for(int j=1;j<=m;j++){
            cin>>t;
            if(t==1)cnt++;
        }
        if(cnt>y)x=i,y=cnt;
    }
    cout<<x<<" "<<y;
    return 0;
}

---

J.安达的数字手术

题面：

思路：

如果是正常的删除某一个数位上的数，这个数的数位会减少 $1$，但是如果删除第一位的时候能出现前导零，就可以删掉多位数，因此如果删第一位能出现前导零，从而删掉多位，就删第一位就行了。

但是如果不是这种情况，考虑如何删数能使得数字最小（数位相同时其实就是字典序最小），发现其实我们删数的时候就是把第 $i$ 位的数删掉，然后把第 $i+1$ 位的数放到第 $i$ 位上，后面依次向前补。因此我们删数的时候一定删那种第 $i$ 位上的数大于第 $i+1$ 位上的数，这样后面数位向前补的时候，第 $i$ 位才会变得更小。因为是字典序最小，只要高位更小，整个串就最小。因此我们贪心地找到第一个 第 $i$ 位上的数大于第 $i+1$ 位上的数 的位置，删掉它就行了。找到最后都没找到的话，就删掉最后一位。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
int n;
string s;
 
bool lt(string a,string b){
    if(a.size()!=b.size())return a.size()<b.size();
    else return a<b;
}
 
int main(){
    cin>>n>>s;
    if(n==1){
        cout<<0<<endl;
        return 0;
    }
    string t,t2;
    int idx=1;
    while(idx<n && s[idx]=='0')idx++;
    t=s.substr(idx);
    if(!t.size())t="0";
     
    for(int i=1;i<n;i++){
        if(i+1<n && s[i]>s[i+1]){
            t2=s.substr(0,i)+s.substr(i+1);
            break;
        }
    }
    if(!t2.size())t2=s.substr(0,n-1);
    if(lt(t,t2))cout<<t;
    else cout<<t2;
    return 0;
}

---

K.跳楼梯

题面：

思路：

一开始我也往 $BFS$ 上想了，但是发现太过复杂，有可能需要访问负的下标，正的下标也可能超过 $n$。翻一下榜，发现 $A$ 掉这题的人有过的很快的，这说明这个题的码量和书写的难度并不大，所以直接尝试推结论，几分钟就出了。

这个题其实就相当于是选取等差数列上的某几个数改成 $-1$，使得它们的和等于 $n$。首先罗飞云要到达第 $n$ 层，首先你等差数列的总和必须得不小于 $n$，这样你把某些数改成 $-1$ 的时候，总和会变小，它才有可能等于 $n$。

发现正因为是等差数列，它有一个很优美的性质，就是我们只选择一个数变成 $-1$ 的话，从 $1$ 到 $x$总和会在原来的基础上减少 $2,3,4,\dots ,x+1$。如果我们找到第一个 $x$ ，使得 $1\sim x$ 的和 $tot$ 大于等于 $n$，这时只要 $tot$ 和 $n$ 相差不为 $1$，我们就可以从 $1\sim x$ 找到一个数把总和减少到 $n$。

这是因为 $tot-x$ 相当于 $1\sim x-1$ 的和，根据我们上面 $x$ 是第一个 使得 $1\sim x$ 的和 $tot$ 大于等于 $n$ 的位置 的前提，也就是 $tot-n<x$ ，如果 $tot-n\ge 2$ ，我们就一定能找到这个差值，继而找到变成 $-1$ 的那个数，这时答案就是 $x$。而当 $tot=n$ 的时候，答案就是 $x$，当 $tot-n=1$ 时，必须额外补一个 $-1$，这时答案就是 $x+1$。

这个 $x$ 的计算可以二分来算。直接暴力枚举 $O(t\sqrt{n})$ 也不会超时。

code：

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=1e6+5;
 
int T,n;
 
int main(){
    cin>>T;
    while(T--){
        cin>>n;
        int l=1,r=2000,mid;
        while(l<r){
            mid=(l+r)>>1;
            if(mid*(mid+1)/2>=n)r=mid;
            else l=mid+1;
        }
        if(l*(l+1)/2-n==1)cout<<l+1<<endl;
        else cout<<l<<endl;
    }
    return 0;
}

---

L.前缀和

题面：

思路：

就是算前缀和然后二分查询，题面问的很直白了。不过这题卡cin，需要取消同步或者改用scanf。

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
 
int n,Q;
ll s[maxn],sum;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); 
     
    cin>>n>>Q;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]+=s[i-1];
    }
    while(Q--){
        cin>>sum;
        if(sum>s[n])cout<<-1<<"\n";
        else cout<<(lower_bound(s+1,s+n+1,sum)-s)<<"\n";
    }
    return 0;
}