2025常熟理工学院天梯选拔赛题解

说在前面的话......

首先感谢全体出题人和验题人，和积极参赛的大伙们！

也感谢牛客提供平台，以及 $qcjj$ 、 $Silencer76$ 、苯环帮忙，让我们可以把这些题目推给大伙一块玩嗷！

这次是我们第一次在牛客上办天梯选拔赛和同步赛，希望大伙也都玩的开心~ 在此也祝男神女神们都节日快乐哦~

由于牛客的 $ioi$ 赛制没法为测试点单独设置分数，因此同步赛得分会出现小数，未来我们也会尽可能想办法优化哒~

$Sincere\ Apology:$ 赛时 $L2-3$ 数据出现了问题，大伙一块来拷打一下出题人 $\color{#CC0}{NoonMaple}$ $qwq$

另外似乎题目难度 & 码量有些高于预期（只能说题目的区分度还是可以吧），未来我们也会尽力优化嗷，让大伙打的舒服一些~

希望大伙多多包涵嗷~ 也欢迎大家来吐槽~

附赠出锅的同学爆金币的图片（

alt

L1 基础级

L1-1 简单题目

出题人：可爱的聂老师（我们教练！） $qwq$

L1-2 Jiangly’s A+B-C Problem

出题人： $\color{#CC0}{A\_Little\_BadBoy}$

$Interesting\ Fact：$ 这道题一开始 $a,b,c$ 数据范围是 $[-10^9,10^9]$ ，可以卡一下 $long\ long$ 。不过后来还是改到 $[-10^8,10^8]$ 了，让大伙都体验一下和 $\color{red}{j}\color{black}{iangly}$ 组队的快乐！

晚安玛卡巴卡，梦里什么都有~

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

int a, b, c;

signed main()
{
    cin >> a >> b >> c;
    cout << "Result = "<< a + b - c;
    return 0;
}

L1-3 判断两个程序的中断优先级

出题人： $\color{#0A5}{JunK\_Shen}$

这题就是简单的 $if$ 判断。读懂题目算是最难的一步了 $QAQ$

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

int a[2], b[2];

signed main()
{
    cin >> a[0] >> a[1] >> b[0] >> b[1];
    if (a[0] < b[0])
        cout << "A";
    else if (a[0] > b[0])
        cout << "B";
    else if (a[1] < b[1])
        cout << "A";
    else
        cout << "B";
    return 0;
}

L1-4 v98pro

出题人： $\color{#0A5}{strohl}$

直接循环看自己在已知的 $29$ 人数组里有多少大于自己的数，自己的排名就是大于自己分数的人数 $+1$ 。

注意一共有 $30$ 人。前 $10\%$ 是前 $3$ 名，前 $30\%$ 是前 $9$ 名，前 $60\%$ 是前 $18$ 名。

#include<bits/stdc++.h>
using namespace std;
const int N=35;
int a[N];
signed main()
{
    for(int i=1;i<=29;i++)
    {
        cin >>a[i];
    }
    int x;
    cin >>x;
    int cnt=1;
    for(int i=1;i<=29;i++)
    {
        if(a[i]>x)
            cnt++;
        else break;
    }
    if(cnt>=1&&cnt<=3)
        cout<<1<<" ";
    else if(cnt>=4&&cnt<=9)
        cout<<2<<" ";
    else if(cnt>=10&&cnt<=18)
        cout<<3<<" ";
    else cout<<4<<" ";
    return 0;
}

L1-5 书法

出题人： $\color{#CC0}{NoonMaple}$

(似乎有些同学对这题的指针有些不同的看法，这里提一下，本题中是“|”这个样子的嗷)

所有的操作总的来说可以分为两类：第一类：移动指针；第二类：添加字符。

只需要维护指针的位置，利用 insert 函数实现插入的功能，很容易就能实现。注意移动指针时是否会越界。核心部分代码如下：

void solve(){
    string s;
    getline(cin,s);

    int pos=s.size();
    string op;
    while(cin>>op){
        if(op=="CTRL") continue;
        else if(op=="LEFT") pos=max(0ll,pos-1);
        else if(op=="RIGHT") pos=min((int)s.size(),pos+1);
        else{
            if(op=="S") cout<<s<<endl;
            else {
                int cnt=0;
                for(int i=1;i<op.size();i++) cnt=cnt*10+op[i]-'0';

                char c=s[pos-1];
                s.insert(pos,cnt,c);
                pos+=cnt;
            }
        }
    }
    cout<<s;
}

（要打天梯赛但还不会 $getline$ 的同学，快去学嗷！天梯赛爱考这个）

L1-6 魔方

出题人： $\color{#0A5}{漫画家}\color{#0A5}{wA\_C}$

题面吓人，但终究只是纸老虎。我们只要直接模拟一下两种操作即可（或者用取模的做法，因为每进行 $4$ 次 $L$ 操作或者 $R$ 操作，该操作会影响到的那些格子就会还原）。另外， $L$ 面和 $R$ 面全程其实都没有改变过。

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const ll N=1e6+10;
char g[10][10]= {
"  yy  ",
"  yy  ",
"oobbrr",
"oobbrr",
"  ww  ",
"  ww  ",
"  gg  ",
"  gg  ",
};
void L()
{
    for(ll k=0;k<2;k++)
    {
        char t=g[7][2];
        for(ll i=6;i>=0;i--)
            g[i+1][2]=g[i][2];
        g[0][2]=t;
    }    
}
void R()
{
    for(ll k=0;k<2;k++)
    {
        char t=g[0][3];
        for(ll i=0;i<8;i++)
        {
            g[i][3]=g[(i+1)%8][3];
        }
        g[7][3]=t;
    }      
}
void print()
{
    for(ll i=0;i<8;i++)
    {
        for(ll j=0;j<6;j++)
            cout << g[i][j] ;
        cout << endl;
    }
}

void solve()
{
    ll m;
    cin >> m;
    while(m--)
    {
        ll op;char c;
        cin >> op;
        if(op==1)
        {
            cin >> c;
            if(c=='L') L();
            else R();
        }
        else 
        {
            print();
        }
    } 
}

signed main()
{
   ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    // cin >> T;
    while(T--) solve();
    return 0;
}

L1-7 女神节的魔法花园

出题人： $\color{#CC0}{NoonMaple}$

注意不要看错题目里区间翻转的含义。一共分三种情况：

没有 $3$ ，直接输出 $0$ ；
只有一个 $3$ ，此时很容易发现不反转的话一定是 $0$ ，所以我们尽量考虑翻转。
- 如果这个 $3$ 在最后两个位置，要么无法翻转，要么翻转了整个字符串也还是一个 $3$ , 此时答案为 $0$ ；
- 如果不在最后两个位置，考虑到其余位置都为 $8$ ，我们尽量翻转更长的区间，能使两个 $3$ 的距离最大，那么以这个 $3$ 为区间左端点，最后一个 $8$ 为区间右端点，翻转这段区间，就会将后面所有的 $8$ 都变为 $3$ ，此时答案为：翻转区间长度 $-2$ ；
有两个及以上个 $3$ ，此时我们可以让最左端的 $3$ 不动，记这个 $3$ 的位置为 $pos$ ，用后面的 $3$ 作为翻转区间的左端点。不难发现，距离最左端的 $3$ 最远的 $3$ 一定是最后一个字符，此时答案为 $n-pos-1$ 。

此题只需找到第一个 $3$ 的位置，按照上述情况分类讨论即可。核心部分代码如下：

void solve(){
    int n;cin>>n;
    string s;cin>>s;
    int cnt=0;
    for(auto c:s){
        if(c=='3') cnt++;
    }
    if(cnt==0){
        cout<<"0"<<endl;
        return;
    }

    int pos=s.find('3');
    if(cnt==1){
        if(n-pos-1<2) cout<<0<<endl;
        else cout<<n-pos-2<<endl;
    }
    else cout<<n-pos-1<<endl;
}

$Bonus:$ 如果该题的特殊魔法的可使用次数为无限次，答案又将如何呢？

L1-8 KNN算法

出题人： $\color{#0A5}{JunK\_Shen}$ ， $\color{#CC0}{A\_Little\_BadBoy}$

$Interesting\ Fact：$ 这道题的最初版本又长又臭，比大家看到的版本大概长 $1/3\ \text{~}\ 1/2$ 。

纯纯模拟题。先把所有节点的信息存起来，然后按照到新对象的距离进行排序，距离相同的按照序号再排一下就行了。 $2\times 10^3$ 的数据量甚至允许 $O(n^2)$ 的排序。

然后每次查询暴力跑一下，这道题就结束了。没有啥特别的技巧，难点还是在读题上。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII array<int, 2>

const int inf = 4e18;
const int N = 2e3 + 5;
int t = 1, n, q, x, y, tp, k;
PII pos[N];
int type[N];
vector<int> arr;

bool cmp(int m1, int m2)
{
    int dis1 = (x - pos[m1][0]) * (x - pos[m1][0]) + (y - pos[m1][1]) * (y - pos[m1][1]);
    int dis2 = (x - pos[m2][0]) * (x - pos[m2][0]) + (y - pos[m2][1]) * (y - pos[m2][1]);
    if (dis1 == dis2)
        return m1 < m2; // 注意，这里比较的是序号！
    return dis1 < dis2;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> pos[i][0] >> pos[i][1] >> type[i];
        arr.push_back(i);
    }
    cin >> x >> y;
    sort(arr.begin(), arr.end(), cmp);

    while (q--)
    {
        cin >> k;
        map<int, int> mp;
        int ans = 0, tim = 0; // ans记录本次查询的答案，tim记录其出现的次数
        for (int i = 0; i < k; i++)
        {
            int now = type[arr[i]];
            mp[now]++;
            if (mp[now] == tim && now < ans)
                ans = now;
            else if (mp[now] > tim)
                ans = now, tim = mp[now];
        }
        cout << ans;
        if (q)
            cout << '\n';
    }
    return 0;
}

$Bonus:$ 如果数据范围加强到 $1\le n,q\le 5\times 10^5$ ，又该怎么优化呢？

L2 进阶级

L2-1 下棋

出题人： $\color{#CC0}{NoonMaple}$

并非博弈。冒充图论。

不难发现走的路线是固定的，对于奇数层节点，只需要记录其最大点权的儿子节点，对于偶数层节点，只需要记录最小点权儿子节点。然后一路走下去就结束了。

可以用 $bfs$ 或 $dfs$ 实现，也可以用 $stl$ 等别的各种暴力方法通过。时间复杂度 $O(n)$ 。核心部分代码如下：

#define PII array<int,2>
void solve(){
    int n,k;cin>>n>>k;
    vector<vector<int>>v(n+1);
    vector<int>a(n+1);
    for(int i=2;i<=n;i++){
        int x;cin>>x;
        v[x].push_back(i);
    }
    for(int i=1;i<=n;i++) cin>>a[i];

    queue<PII>q;
    q.push({1,1});
    while(!q.empty()){
        auto [u,c]=q.front();q.pop();

        int mx=0,net=-1;
        if(c&1) mx=-INF;
        else mx=INF;
        for(auto x:v[u]){
            if(c&1){
                if(a[x]>mx){
                    mx=a[x];
                    net=x;
                }
            }
            else{
                if(a[x]<mx){
                    mx=a[x];
                    net=x;
                }
            }
        }

        if(net!=-1){
            q.push({net,c+1});
            k+=mx;
        }
    }

    cout<<k<<endl;
}

L2-2 Dyzzzd的字符串

出题人： $\color{#0A5}{\large{漫画家}}\color{#0A5}{wA\_C}$

$Interesting\ Fact:$ $Dyzzzd$ 不是打错字了，验题人 $\color{#0A5}{dyzzd}$ 的 $cf$ 号就叫 $\color{#0AA}dyzzzd$ 。

看起来稍微有一点典的题。两种做法，一个是贪心加一点数学，一个是空间优化 $dp$ ，但前者是本题的最优解。

贪心 + 数学:

分两种情况：

① 全部取 $a$ 就能符合题意：显然地，设 $a$ 有 $tot$ 个，则答案为 $C(tot,k)$ 。

② 需要取 $b$ ：此时需要看从第一次取 $b$ 开始，这一次需要取到多少个连续的 $b$ ，而这次实际上又能提供多少个 $b$ 。

一个可能的误解：这种情况下最终的字符串一定是 $a...ab...b$ 的（X）。其实不然，比如 $k=4$ ， $abbbab$ ，得到的应是 $abab$ 。

对于 $a\color{#05F}{bbb}ab$ -> $a\color{#05F}{b}ab$ 这个例子，其第一次开始取 $b$ 时，实际需要连续取 $1$ 个 $b$ ，但实际上可以提供的有 $3$ 个 $b$ ，于是总的取法数就是 $C(3,1)=3$ 。

时间复杂度 $O(n)$ 。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII array<int, 2>

const int inf = 4e18;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int t = 1, n, k;
int lastpos = 0;
string s;

// 板子
int fpow(int a, int x)
{
    int _res = a % mod, _ans = 1;
    while (x)
    {
        if (x & 1)
            _ans = _ans * _res % mod;
        _res = _res * _res % mod;
        x >>= 1;
    }
    return _ans;
}

// mod必须是质数
int inv(int a)
{
    return fpow(a, mod - 2);
}

// 初始化，适用于数据范围<1e8的时候
// 复杂度 O(N)
int fz[N], fm[N];
void init()
{
    // 初始化复杂度O(N)
    fz[0] = fm[0] = 1;
    for (int i = 1; i <= 1000000; i++)
    {
        fz[i] = fz[i - 1] * i % mod;
    }
    fm[1000000] = fpow(fz[1000000], mod - 2);
    for (int i = 999999; i >= 1; i--)
    {
        fm[i] = fm[i + 1] * (i + 1) % mod;
    }
}

int C(int n, int k)
{
    // 查询时间复杂度O(1)
    if (n < k)
        return 0;
    return fz[n] * fm[k] % mod * fm[n - k] % mod;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    cin >> n >> k >> s;
    s = ' ' + s;
    int ans = 0;
    int pos = 0; // 记录最后一次可以取'a'的位置
    int now = k; // 记录k的剩余值（now可能变成负数）
    for (int i = 1; i <= n; i++)
        if (s[i] == 'a')
            now--, pos = i;
        else if (s[i] == 'b')
        {
            if (now == n - i + 1) // 这种情况下，最后的那些是不得不取的
            {
                // 从pos+1~i，一定都是'b'
                // 不超过pos的'a'，一定都会被取到
                int b = i - pos;
                int j = i + 1; // 记录下一次取到'a'的位置
                while (j <= n && s[j] == 'b')
                    j++, b++;
                now -= (n - j + 1);
                // 中间这些'b'，还需要取now个
                ans = C(b, now);
                cout << ans;
                return 0;
            }
        }
    ans = C(k - now, k); // 此时只能是全部取'a'，'a'的数量是k-now个
    cout << ans;
    return 0;
}

还有一种挺好的想法：直接把 $a$ 先全部取掉，如果还不够，就从后往前取 $b$ 。

空间优化dp：

这种做法需要先求出子字符串。求解该子字符串的方法也算是很经典的了，我们用一个单调栈即可。

接下来，我们对于这个子字符串求 $dp$ 。我们假设原字符串是 $a$ ，得到的子字符串是 $b$ ， $dp[n][m]$ 表示 $a$ 串的前 $i$ 位，能够满足 $b$ 串的前 $j$ 位的子字符串有多少种。

浅浅推一下状态转移方程：对于某个位置，要么匹配上，要么没匹配上，而只有 $a[i]==b[j]$ 时才能匹配上。所以如果 $a[i]\neq b[j]$ ，则 $dp[i][j]=dp[i-1][j]$ ，否则 $dp[i][j]=dp[i-1][j]+dp[i-1][j-1]$ 。最后输出 $dp[a.size()][b.size()]$ 即可。

但显然直接这么写会 $MLE$ 。可以发现，在推 $dp[i][j]$ 的时候，只会用到第 $(i-1)$ 层的状态，所以可以直接优化掉第一维。这也是经典的 $dp$ 优化了。时间复杂度 $O(n^2)$ ，可以勉强通过 $10^4$ 的数据（但是，如果本题字符串里还有其他字符，那这就是唯一解了）。

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll N = 1e4 + 5;
const ll mod = 1e9 + 7;
ll vis[N], dp[N];
void solve()
{
    ll m, k;
    cin >> m >> k;
    string a, b = "";
    cin >> a;

    for (int i = 0; i < m; i++)
    {
        while ((b.size() + m - i != k) && b.size() && b.back() > a[i])
            b.pop_back();
        b.push_back(a[i]);
    }
    while (b.size() > k)
        b.pop_back();

    a = ' ' + a;
    b = ' ' + b;
    dp[0] = 1;
    for (int i = 1; i <= m; i++)
        for (int j = b.size() - 1; j >= 1; j--)
            if (a[i] == b[j])
                (dp[j] += dp[j - 1]) %= mod;
    cout << dp[b.size() - 1];
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

L2-3 彩排（Easy）

出题人： $\color{#CC0}{NoonMaple}$ （被拷打）

$Very\ Bad\ Fact:$ 这道题是全场被 $hack$ 过和修改过最多次的题，甚至在赛时还被 $hack$ 了（点名表扬）。第二名是 $L3-2$ 。

按照入场时间 $s_i$ 对所有人排序，按照能力值 $a_i$ 为第一关键字，退场时间 $t_i$ 为第二关键字从小到大用优先队列存放。

对于每位演员，若队头演员的退场时间小于当前演员，则出队，否则记录当前演员的答案，即 $max(0,a_i-q.top().first)$ 。

其他的排序方法如果做法合理也是可以过的。时间复杂度 $O(nlogn)$ 。核心部分代码如下：

#define PII array<int,2>
struct P{
    int a,s,t;
    int id,ans;
};

bool cmp(P a,P b){return a.s<b.s;}
bool cmpid(P a,P b){return a.id<b.id;}

void solve(){
    int n;cin>>n;
    vector<P>p(n+1);
    for(int i=1;i<=n;i++){
        cin>>p[i].a>>p[i].s>>p[i].t;
        p[i].id=i;
    }

    sort(p.begin()+1,p.end(),cmp);
    priority_queue<PII,vector<PII>,greater<PII>>q;//{a[i],t[i]};
    for(int i=1;i<=n;i++){
        while(!q.empty()){
            auto [c,r]=q.top();
            if(r<=p[i].s){
                q.pop();
                continue;
            }

            if(p[i].a>c) p[i].ans=p[i].a-c;
            break;
        }
        q.push({p[i].a,p[i].t});
    }

    sort(p.begin()+1,p.end(),cmpid);
    for(int i=1;i<=n;i++) cout<<p[i].ans<<" ";
}

L2-4 shadow of the labyrinth

出题人： $\color{#0A5}{strohl}$

需要考虑怎么在边走迷宫边杀最多 $F.O.E$ ，但本质是变种走迷宫。

首先一个队列就够了，预处理将所有在视野范围内的格子标为类墙壁（不是墙壁，但是也不能走的那种），但请注意终点也可能会在 $F.O.E$ 视野范围内，所以需要预存终点坐标。

接下来就是普通 $bfs$ ，如果从下一个可能走到的格子是 $F.O.E$ 就把 $F.O.E$ 消灭，把它视野范围内的类墙壁全部标记为可走的地面。可以发现这样的 $bfs$ 过程就是能清除最多 $F.O.E$ 的最优情况。

至于走到终点的情况，只需要记录下在这种 $bfs$ 的过程中队头元素是否有出现过终点坐标就 $ok$ 。

时间复杂度 $O(nm)$ 。思路不难，不过码量略微有一点点大（但和接下来的 $L3$ 比起来，好像也就不算什么了）。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+10;
char mp[N][N];
int foevis[N][N];
bool vis[N][N];
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int n,m,k;
int cnt=0;
int flag=0;
queue<pair<int,int>> q;
int sx,sy;
int ex,ey;
void opfoe(int op,int x,int y,int t)
{
    int sxi=dx[t-1],syi=dy[t-1];
    while(x>=1&&x<=n&&y>=1&&y<=m)
    {
        if(op==1)
        {
            if(mp[x][y]=='*')
                mp[x][y]='.';
            else break;
        }
        else
        {
            if(mp[x][y]!='#')
                mp[x][y]='*';
            else break;
        }
        x+=sxi;y+=syi;
    }
}
void bfs()
{
    q.push({sx,sy});
    vis[sx][sy]=1;
    while(!q.empty())
    {
        int nowx=q.front().first;
        int nowy=q.front().second;
        q.pop();
        if(nowx==ex&&nowy==ey)
            flag=1;
        for(int i=0;i<4;i++)
        {
            int nx=nowx+dx[i];
            int ny=nowy+dy[i];
            if(!(nx>=1&&nx<=n&&ny>=1&&ny<=m))
                continue;
            if(mp[nx][ny]=='*'&&foevis[nx][ny]!=0)
            {
                cnt++;
                opfoe(1,nx,ny,foevis[nx][ny]);
            }
            if(vis[nx][ny]==0&&mp[nx][ny]=='.')
            {
                vis[nx][ny]=1;
                q.push({nx,ny});
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin >>mp[i][j];
            if(mp[i][j]=='S')
            {
                mp[i][j]='.';
                sx=i;sy=j;
            }
            if(mp[i][j]=='E')
            {
                mp[i][j]='.';
                ex=i;ey=j;
            }
        }
    }
    for(int i=1;i<=k;i++)
    {
        int x,y,t;
        cin >>x>>y>>t;
        foevis[x][y]=t;
        opfoe(2,x,y,t);
    }
    bfs();
    if(flag==1)
        cout<<"YES"<<'\n';
    else cout<<"NO"<<'\n';
    cout<<cnt<<'\n';
    return 0;
}

L3 登顶级

L3-1 数织

出题人： $\color{#0A5}{strohl}$

数据经过一次加强，加强之前是 $n×m$ 最多 $20$ ，那直接枚举每个格子到底是填 $0$ 和 $1$ ，再确认每行/每列的连续格子数量满不满足约束就行。

现在经过加强以后扩大到 $6\times6$ ，需要进行一定程度的优化。可以发现对于 $6\times6$ 的题目，每行的最复杂约束是 $2\ 1\ 1$ （即一行内有两个长度为 $1$ 的连续段），此时每行共有 $10$ 种情况，所以枚举每行的可能情况再判断合法性即可。以下是两种优化思路：

①通过二进制枚举每一行可能的所有情况，再对每一行的所有可能性进行组合，组合完去确认列是否合规。

②通过枚举每行的每个数之前有多少空格，需要保证空格总数 $+$ 方块总数 $=m$ 。组合完去确认列是否合规。

极限情况下，我们也只需要判断 $10^6$ 种情况的合法性。最坏时间复杂度 $O(10^m \times nm)$ 。

$std$ 是第二种优化思路。

#include <bits/stdc++.h>
const int N=10;
using namespace std;
#define int long long
int n,m;
vector<int> l[N];
vector<int> h[N];
vector<int> space[N];//记录第i行的第j个连续方块前应该填多少空格
int temp[N][N];
int ans[N][N];
int total[N];//记录每一行的方块总数
int ansflag=0;
void dfs(int nowi,int sum,int cnt)
{
    //组合完毕
    if(nowi==n+1)
    {
        int flag=0;
        vector<int> nowst;
        for(int i=1;i<=m;i++)
        {
            int is1=0;
            int nowcnt=0;
            for(int j=1;j<=n;j++)
            {
                if(is1==0&&temp[j][i]==1)
                {
                    is1=1;
                    nowcnt=1;
                }
                else if(is1==1&&temp[j][i]==1)
                    nowcnt++;
                else if(is1==1&&temp[j][i]==0)
                {
                    nowst.push_back(nowcnt);
                    is1=0;
                    nowcnt=0;
                }
            }
            if(is1==1) nowst.push_back(nowcnt);
            if(nowst!=l[i])
            {
                flag=1;
            }
            nowst.clear();
        }
        if(flag==0)
        {
            ansflag++;
            for(int xi=1;xi<=n;xi++)
            {
                for(int xj=1;xj<=m;xj++)
                {
                    ans[xi][xj]=temp[xi][xj];
                }
            }
        }
        return ;
    }
    //当前行已经枚举完了空格，开始填充然后进入下一行的枚举
    if(cnt==h[nowi].size())
    {
        int pos=1;
        for(int i=0;i<h[nowi].size();i++)
        {
            int cnt0=space[nowi][i];
            int cnt1=h[nowi][i];
            for(int j=1;j<=cnt0;j++,pos++)
                temp[nowi][pos]=0;
            for(int j=1;j<=cnt1;j++,pos++)
                temp[nowi][pos]=1;
        }
        for(;pos<=m;pos++)
        {
            temp[nowi][pos]=0;
        }
        dfs(nowi+1,m-total[nowi+1],0);
        return ;
    }
    //枚举该行目前数字前应该填多少空格
    int st;
    if(cnt==0)
        st=0;
    else st=1;
    for(int i=st;i<=sum;i++)
    {
        space[nowi].push_back(i);
        dfs(nowi,sum-i,cnt+1);
        space[nowi].pop_back();
    }
}
signed main()
{
    cin >>n>>m;
    for(int i=1;i<=n;i++)
    {
        int k;cin >>k;
        for(int j=1;j<=k;j++)
        {
            int x;cin >>x;
            h[i].push_back(x);
            total[i]+=x;
        }
    }
    for(int i=1;i<=m;i++)
    {
        int k;cin >>k;
        for(int j=1;j<=k;j++)
        {
            int x;cin >>x;
            l[i].push_back(x);
        }
    }
    dfs(1,m-total[1],0);
    if(ansflag==1)
    {
        cout<<"YES"<<'\n';
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cout<<ans[i][j];
            }
            cout<<'\n';
        }
    }
    else cout<<"NO"<<'\n'<<ansflag<<'\n';
    return 0;
}

L3-2 gxy学长的精灵融合

出题人： $\color{#CC0}{A\_Little\_BadBoy}$

$Interesting\ Fact:$ 这道题是验题过程中让各位出题人和验题人最红温的题（点名表扬）。

纯纯的贪心，但是如果不细想可能会贪错。

首先要注意到本题特别强调了还未融合时强壮值可以为负，所以只取一个的情况需要特判。特判在之后的分析中不会再强调。

除上述特判的情况外，如果一只精灵的攻击力为非正数，且其强壮值不为 $1$ ，则这只精灵在之后的计算中没有意义，直接排除。

先说错误贪心（校内赛 $12\ pts$ ，同步赛 $15\ pts$ ）：

① 将所有的精灵按照攻击力从大到小排序；

② 维护 $tot$ 为强壮值之和。根据攻击力从大到小取，取的时候如果 $tot=0$ 且当前要取的是 $-1$ 强壮值的精灵，则将其放到一个 $queue$ 中暂存，等 $tot>0$ 之后再取出；否则直接取即可。

这种解法的 $hack$ 如下：

正解是取后面 $4$ 个即可。错误原因在于，某一组强壮值 $(-1,1)$ 的精灵组合可能比直接取强壮值 $\ge 0$ 的精灵拥有更大的收益。

既然该问题的重点在于强壮值 $(-1,1)$ 的精灵组合，那我们便能想到枚举 $(-1,1)$ 的组数（换句话说，就是枚举强壮值 $-1$ 的精灵数量）。在组合 $(-1,1)$ 的精灵时，强壮值 $-1$ 的精灵和 $1$ 的精灵都取攻击力最大的即可。

假设现在枚举到取 $k$ 对 $(-1,1)$ ，则我们可以直接考虑剩下还没取的强壮值 $1$ 或 $0$ 的精灵，从大到小贪心取即可。这个做法是 $O(n^2)$ 的，但已经几乎能 $AC$ 了（校内赛 $26\ pts$ ，同步赛 $25\ pts$ ）。

最终优化方式不唯一，但都是基于上面枚举 $(-1,1)$ 的组数的方法进行的。

**方法一：**三指针（ $Proposed\ by:\ \color{#F0F}{\large{算法天才琪露诺}}$ ）

开三个数组并按照攻击力排序，分别代表强壮值 $-1,0,1$ 的精灵。对于每个数组，我们额外放进去一个攻击力 $-1e11$ 的，表示什么也不取。这个时候正好把特判搞掉（即只取一个精灵的情况）。

设三个指针 $l,m,r$ ，分别对应三个数组。现在枚举取强壮值 $-1$ 的数量，按从大到小遍历。首先，强壮值 $1$ 的精灵个数一定要大于等于强壮值 $-1$ 的精灵个数，因此用 $while$ 循环把强壮值 $1$ 的精灵全部放进去；之后，开始找强壮值 $0$ 和 $1$ 的精灵来凑 $k$ 攻击力，在强壮值 $1$ 和 $0$ 中选最大的去凑。

当我们再取下一个强壮值 $-1$ 的精灵时，由于刚才 $while$ 循环保证强壮值 $1$ 的精灵大于等于强壮值 $-1$ 的精灵个数了，因此如果够取，强壮值 $0$ 和 $1$ 可以往前删数的，则选攻击力小的一直删（可能的话），保证 $l+m+r$ 最小。

就这样一直进行下去，枚举完所有情况，取最优解再模拟一遍即可。

时间复杂度：排序 $O(nlogn)$ ，三指针过程 $O(n)$ 。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fs first
#define sc second
#define all1(x)	x.begin()+1,x.end()
typedef pair<ll,ll> PLI;
const int mod=1e9+7;  //998244353;

bool cmp(PLI a,PLI b){return a.fs>b.fs;}

void solve(){
	 int n;ll k;
	 cin>>n>>k;
	 vector<vector<PLI>> a(3);  //-1\0\1
	 for(int i=0;i<3;i++)	a[i].push_back({-1e11,0});
	 ll ansmx=-1e17,ansmxf=-1;
	 for(int i=0;i<n;i++){
	 	int x;ll y;
	 	cin>>x>>y;
	 	if(y>ansmx)	ansmx=y,ansmxf=i+1;
	 	a[x+1].push_back({y,i+1});
	 }
	 for(int i=0;i<3;i++)	sort(all1(a[i]),cmp);
     if(ansmx>=k){
	 	cout<<"YES\n1\n"<<ansmxf<<'\n';
	 	return;
	 }

	 int l=0,m=0,r=0;ll sum=0,anssize=1e8,ansf=0;
	 int n0=a[0].size(),n1=a[1].size(),n2=a[2].size();
	 for(int l=0;l<a[0].size();l++){
	 	if(l)	sum+=a[0][l].fs;
	 	while(r<l && r+1<n2)
	 		sum+=a[2][++r].fs;
	 	if(r<l)	continue;
	 	while(sum<k){
	 		if((m+1<n1 && r+1<n2 && a[1][m+1].fs>=a[2][r+1].fs && a[1][m+1].fs>0)  || ((m+1<n1) && (r+1>=n2) &&a[1][m+1].fs>0) )
	 			sum+=a[1][++m].fs;
	 		else if((m+1<n1 && r+1<n2 && a[1][m+1].fs<a[2][r+1].fs && a[2][r+1].fs>0) || ((m+1>=n1) && (r+1<n2)&&a[2][r+1].fs>0))
	 			sum+=a[2][++r].fs;
	 		else break;
	 	}
	 	while(sum>=k){
	 		if(m>0 && r>l && a[1][m].fs<=a[2][r].fs && sum-a[1][m].fs>=k)	sum-=a[1][m--].fs;
	 		else if(r==l && m>0 && sum-a[1][m].fs>=k)	sum-=a[1][m--].fs;
	 		else if(r>l && sum-a[2][r].fs>=k)	sum-=a[2][r--].fs;
	 		else break;
	 	}
	 	if(l+m+r <= anssize && sum>=k)
	 		anssize=l+m+r,ansf=l;
	 }
	 if(anssize<5e7){
	 	cout<<"YES"<<'\n';
	 	cout<<anssize<<'\n';
	 	vector<int> ans;
	 	for(int i=1;i<=ansf;i++)	ans.push_back(a[2][i].sc),ans.push_back(a[0][i].sc);
	 	for(int i=ansf,j=0;i+j+ansf<anssize;){
	 		if(i+1<a[2].size() && j+1<a[1].size()){
	 			if(a[2][i+1].fs>=a[1][j+1].fs)	ans.push_back(a[2][++i].sc);
	 			else ans.push_back(a[1][++j].sc);
	 		}
	 		else{
	 			if(i+1<a[2].size())	ans.push_back(a[2][++i].sc);
	 			else ans.push_back(a[1][++j].sc);
	 		}
	 	}
	 	for(int i=0;i<ans.size();i++)	cout<<ans[i]<<" \n"[i==ans.size()-1];
	 	return;
	 }
	 else{
	 	cout<<"NO"<<'\n';
	 	vector<int> ans;
	 	int ff;ll ss=0;
	 	for(ff=1;ff<n2 && a[2][ff].fs>0;ff++)	ss+=a[2][ff].fs,ans.push_back(a[2][ff].sc);
	 	for(int i=1;i<n1 && a[1][i].fs>0;i++)	ss+=a[1][i].fs,ans.push_back(a[1][i].sc);
	 	for(int i=1;i<n0 && a[0][i].fs>0 && i<ff;i++)	ss+=a[0][i].fs,ans.push_back(a[0][i].sc);
	 	for(int i=ff;i<n2 && i<n0 && a[0][i].fs+a[2][i].fs>0;i++)	ss+=a[0][i].fs+a[2][i].fs,ans.push_back(a[2][i].sc),ans.push_back(a[0][i].sc);
	 	if(ans.size() && ss>ansmx){
	 		cout<<ans.size()<<'\n';
	 		for(int i=0;i<ans.size();i++)	cout<<ans[i]<<" \n"[i==ans.size()-1];
	 	}
	 	else	cout<<1<<'\n'<<ansmxf<<'\n';
	 }
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	int t;cin>>t;while(t--)
	solve();
	return 0;
}

方法二： $set$ （ $Proposed\ by:\ \color{#CC0}{A\_Little\_BadBoy}$ ）

① 我们开一个 $set$ ，维护所有强壮值 $\ge 0$ 的精灵（只放攻击力 $>0$ 的即可），在放精灵进 $set$ 的同时维护 $set$ 内所有精灵的攻击力之和 $\_atk$ ；再开两个按照攻击力排好序的数组，分别存放强壮值为 $1$ 和强壮值为 $-1$ 的精灵。然后我们不断从 $set$ 内删最小的元素（同时 $\_atk$ 扣除对应攻击力），直到如果删掉下一个精灵会使得 $\_atk<k$ 为止。此时 $set$ 内的元素即为取 $0$ 对 $(-1,1)$ 的结果（特别地，如果此时 $set$ 为空，则该情况不成立，因为至少要取 $1$ 个）。

② 接下来进行枚举。

当我们从取 $(t-1)$ 对 $(-1,1)$ 的状态转移到取 $t$ 对 $(-1,1)$ 的状态时，先从①中提到的两个数组中各取一个最大的组合（如果此时取出的强壮值 $1$ 的精灵在 $set$ 里面，注意要将其取出来，并且注意别重复计算）计算贡献。然后按照①的方法更新 $set$ ，得到取 $t$ 对的最优解。

我们再设 $times[t]$ 为取 $t$ 组 $(-1,1)$ 的最少精灵选取数， $atk[t]$ 为取 $t$ 组 $(-1,1)$ 的攻击力之和。我们定义取 $t$ 对的最优解是合法的，当且仅当满足以下条件之一：

(1) $atk[t-1]<k$ ，（即取 $(t-1)$ 对所得答案为 $NO$ ），且 $atk[t]>atk[t-1]$ （攻击力更优），

(2) $atk[t-1]\ge k$ ，（即取 $(t-1)$ 对所得答案为 $YES$ ），且 $times[t] \le times[t-1]$ （所取精灵数不是更劣）。

如果取 $t$ 对的最优解是合法的，那么我们就继续看取 $(t+1)$ 对的最优解；否则，取 $(t-1)$ 对的最优解就是全局最优解。

最后这个重要结论的详细证明如下：

alt

（如果取 $(t-1)$ 对的情况不成立的话，直接认为这组解更好即可。按标程写法的话，这倒是不用特判）

如果不想考虑上面这么多，也可以直接枚举完所有取 $(-1,1)$ 的情况，取全局最优后再模拟一遍。考虑的更少，但码量更大。

时间复杂度：常数稍微有点大的 $O(nlogn)$ 。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PI3 array<int, 3>
const int inf = 4e18;
const int N = 2e5 + 5;
int T, n, k;
vector<PI3> Neg, g1;  // Neg存放强壮值-1的，g1存放强壮值1的
set<PI3> Select;      // Select存放强壮值0或1、且会被选中的
vector<PI3> op;       // 记录最终的答案序列
int Group = 0;        // 代表当前已经组合的(-1,1)组数
int times[N], atk[N]; // 分别代表选择了对应组(-1,1)后，当前选择的精灵总数，和得到的攻击力总和

bool Valid() // 检测现在多取了一组(-1,1)后，还有没有必要再去看下一组的情况得到的是不是一组更好的解
{
    if (atk[Group - 1] >= k) // 如果上组答案是YES，则当前times不能比之前更劣
        return times[Group] <= times[Group - 1];
    return atk[Group] > atk[Group - 1]; // 如果上组答案是NO，则当前atk必须比之前更优
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> n >> k, Group = 0, Neg.clear(), g1.clear(), Select.clear(), op.clear(), times[0] = atk[0] = 0;
        PI3 special = {-inf, -inf, -inf}; // 单独判断只取最大的一个的情况
        for (int i = 1; i <= n; i++)
        {
            int t, a;
            cin >> t >> a;
            if (a > special[0])
                special = {a, t, i};
            if (a <= 0 && t <= 0) // 如果攻击力非正，则只有当强壮值为1时才有意义
                continue;
            if (t == -1)
                Neg.push_back({a, t, i});
            else
            {
                if (a > 0)
                    Select.insert({a, t, i}), times[0]++, atk[0] += a;
                if (t == 1)
                    g1.push_back({a, t, i});
            }
        }
        sort(Neg.begin(), Neg.end()), sort(g1.begin(), g1.end());
        while (Select.size() && atk[0] - (*Select.begin())[0] >= k) // 如果攻击力已经超过了，则直接删除
        {
            atk[0] -= (*Select.begin())[0], times[0]--;
            Select.erase(Select.begin());
        }
        while (Neg.size() && g1.size())
        {
            Group++;
            vector<PI3> lost; // 在这次操作中，被删除的全部放到这
            op.push_back(g1.back());
            op.push_back(Neg.back());
            atk[Group] = atk[Group - 1] + Neg.back()[0] + g1.back()[0], times[Group] = 2 * Group + Select.size();
            if (Select.erase(g1.back())) // 看这一次组合(-1,1)时，有没有从Select里选择1
                atk[Group] -= g1.back()[0], lost.push_back(g1.back()), times[Group]--;
            Neg.pop_back(), g1.pop_back();

            while (Select.size() && atk[Group] - (*Select.begin())[0] >= k)
            {
                atk[Group] -= (*Select.begin())[0], times[Group]--, lost.push_back(*Select.begin());
                Select.erase(Select.begin());
            }
            if (!Valid()) // 如果这组解还没有上一组好，说明上一组是最优解
            {
                Group--, op.pop_back(), op.pop_back();
                for (PI3 i : lost)
                    op.push_back(i);
                break;
            }
        }
        for (PI3 i : Select)
            op.push_back(i);
        if ((special[0] >= atk[Group]) || (special[0] >= k) || (!times[Group])) // 如果只取一个是最优解，或者只取一个是唯一解
            cout << (special[0] >= k ? "YES\n1\n" : "NO\n1\n") << special[2] << '\n';
        else
        {
            cout << (atk[Group] >= k ? "YES\n" : "NO\n") << op.size() << '\n';
            for (PI3 i : op)
                cout << i[2] << ' ';
            cout << '\n';
        }
    }
    return 0;
}

**方法三：**二分（ $Proposed\ by:\ \color{#CC0}{NoonMaple}$ ）

类似之前的，不同的在于每次取完 $(-1,1)$ 之后（把用过的强壮值 $1$ 的精灵拿掉之后），我们对剩余强壮值 $\ge 0$ 的直接去二分。

写起来应该还是很复杂的，不过理论时间复杂度也能达到 $O(nlogn)$ 。

L3-3 我嘞个豆

出题人： $\color{#CC0}{A\_Little\_BadBoy}$

稍微拷打一下自己，虽然这道题的模型确实不错，但对于 $L3-3$ 而言，难度还是偏高了 $qwq$

$L3-3$ 是一道模板题！把这道题出到这里，也是因为觉得这个模型非常地有趣，对大伙应该是有帮助的。

当然放到比赛里的时候我们也对该题做了修改的啦~

首先是炸弹，如果四个方向都攻击不到吃豆人，那就直接用炸弹炸这一格（全用炸弹炸，校内赛可拿 $4\ pts$ ，同步赛 $5\ pts$ ）。但是注意本题中吃豆人是可以重叠在一块的，所以我们对这部分的吃豆人需要去重。以后的讨论中，我们不再考虑只能用炸弹炸的吃豆人。

如果没见过这个模型，很容易想到每次取能够消灭最多吃豆人的方式进行贪心，虽然样例 $2$ 已经把这种做法 $hack$ 了 $QAQ$ 。（这种解法最多可以拿 $15\ pts$ ，不过根据实际写法的不同，得分也可能不同）。

正解是二分图最大匹配。（如果还没学过二分图的话，可以参考 https://oi-wiki.org/graph/bi-graph/ 嗷）。

为什么这么一个模型能够转换为二分图呢？

我们先把这个模型给弱化一下，假设整个题目里只有吃豆人，没有吸能球。那对于每个吃豆人，能打到它的方式一定只有从行或者列上攻击。所以，我们可以把行和列抽象成二分图两侧的点，那么每个吃豆人就是连接着某行和某列之间的边，这样一个二分图模型不就建立起来了吗？（所以说，如果题目中的某个东西的解决方案只有 $2$ 种，就可以去考虑二分图的做法）。

现在要把所有吃豆人消灭掉，那就相当于对于所建的二分图的每一条边，我们都需要选中这条边的至少一个端点才行。这个问题便是二分图中的经典问题——最小顶点覆盖。最小顶点覆盖有几个点，那就是用激光炮攻击了几次。

那现在加（麻）强（烦）版与弱化版相比，会有什么问题呢？

① 从行上攻击时，从左侧攻击和从右侧攻击的结果会不同；同样地，从列上攻击时，从上方攻击和从下方攻击的结果会不同。因此，对于 $n\times m$ 的基地，我们就需要建 $2n$ 个左侧点和 $2m$ 个右侧点。

② 如果还按照弱化版的方法建边，可能会建立重复的边，导致最小顶点覆盖计算错误。就拿这个最简单的举例：

1 1 1
1111 1 1

此时如果在左和上之间建边，又在右和上之间建边，又在左和下之间建边，又在右和下之间建边，那这样求得的最小顶点覆盖将是 $2$ 。为了阻止重复的建边，我们要注意到：如果某一个吃豆人可以从行 $/$ 列的两侧被攻击到，那么我们只需要选择其中一侧建边即可。

③ 某些点可能没有办法建边。对于某些点而言，其可能只能从所在行或所在列被攻击到。此时，我们就可以直接贪心，直接用激光炮轰掉它，顺便把路径上的其他吃豆人给轰掉。注意这一步要在建图之前完成。

于是我们就得到了 $30\ pts$ 的正解：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII array<int, 2>
#define A array<int, 3>
#define B bitset<4>

const int N = 705;
int T, n, m, k, x, y, ans;
set<PII> bomb;
bool ball[N][N];
string s;
vector<int> g[N << 1]; // 存二分图，建边时：行->列
B Vis[N][N];           // bitset<4>里的四维分别表示从该方向能否攻击到。这里用bitset只是为了方便（别被吓到），多开1维用bool数组也能写写（不过bitset有好用的函数）

// 二分图匹配板子（匈牙利算法）
int linker[N << 1];
bool vis[N << 1];
bool dfs(int m1)
{
    for (int i : g[m1])
        if (!vis[i])
        {
            vis[i] = 1;
            if (linker[i] == -1 || dfs(linker[i]))
            {
                linker[i] = m1;
                return 1;
            }
        }
    return 0;
}
int solve()
{
    int ret = 0;
    for (int i = 1; i <= m * 2; i++)
        linker[i] = -1;
    for (int i = 1; i <= n * 2; i++)
    {
        for (int j = 1; j <= m * 2; j++)
            vis[j] = 0;
        ret += dfs(i);
    }
    return ret;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> n >> m >> k, ans = 0, bomb.clear();
        for (int i = 1; i <= n * 2; i++)
            g[i].clear();
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                ball[i][j] = 0;
        while (k--)
        {
            cin >> s >> x >> y;
            if (s[0] == 'b')
                ball[x][y] = 1;
            else
            {
                for (int j = 0; j < 4; j++)
                {
                    Vis[x][y][j] = s[j] - '0';
                    if (j > 1 && Vis[x][y][j - 2]) // 如果从两边都可以打到它，则只考虑一边即可（否则可能会重复）
                        Vis[x][y][j] = 0;          // 这样一来，第0和第2位上至多一个是1，第1和第3位上至多一个是1
                }
                if (Vis[x][y].none()) // 如果全是0则只能用炸弹
                    bomb.insert({x, y});
            }
        }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (Vis[i][j].count() == 1) // 如果它只能从一个方向被攻击到，则先贪心地用激光炮从该方向打掉它
                {
                    int pos = 0; // pos对应攻击方向
                    while (!Vis[i][j][pos])
                        pos++;
                    ans++;
                    if (pos & 1) // 把激光炮路径上的全部消灭掉
                        for (int kk = (pos == 1 ? 1 : n); kk >= 1 && kk <= n && (!ball[kk][j]); kk += (pos == 1 ? 1 : -1))
                            Vis[kk][j] = 0;
                    else
                        for (int kk = (pos == 0 ? 1 : m); kk >= 1 && kk <= m && (!ball[i][kk]); kk += (pos == 0 ? 1 : -1))
                            Vis[i][kk] = 0;
                }
        for (int i = 1; i <= n; i++) // 最后处理既能从行上攻击到，又能从列上攻击到的
            for (int j = 1; j <= m; j++)
                if (Vis[i][j].any())
                    g[i + Vis[i][j][2] * n].push_back(j + Vis[i][j][3] * m), Vis[i][j] = 0;
        cout << (ans += solve() + bomb.size()) << "(Bomb=" << bomb.size() << ')';
        if (T)
            cout << '\n';
    }
    return 0;
}

写在后面的话......

在这场比赛举办的过程中也发生了一些有趣的事情，和大家分享分享~

① 在 $3.8\ 10:00$ 时，我们在同步赛的比赛说明页面加了一个小彩蛋：*什么，你说这个牛牛杯头顶怎么不是尖尖的？那我问你，...（手动狗头）*这句话中，点一下划线部分有惊喜（？）

② $L3-2$ 这个题号似乎有着什么魔力一样，被放到过 $L3-2$ 的题目都被 $hack$ 了好几次（现 $L2-3$ 一开始的定位就是 $L3-2$ ，只不过后面被 $hack$ 地掉到 $L2-3$ 了）

③ 在比赛开始前，我们让出题人做了一轮同步赛通过率预测（过题人数占实际参赛的人数比例）。预测结果和实际结果对比如下：

通过率	L1-1	L1-2	L1-3	L1-4	L1-5	L1-6	L1-7	L1-8
预测平均值	99%	99%	94%	89%	41%	61%	41%	51%
实际值	100%	98%	97%	90%	35%	54%	23%	18%

通过率	L2-1	L2-2	L2-3	L2-4	L3-1	L3-2	L3-3
预测平均值	51%	33%	34%	22%	9%	4%	2%
实际值	13%	13%	6%	1%	1%	0%	0%

考虑到有些同学 $8$ 点的时候去打 $atc$ 了，实际数据偏差应该还是有点大的。

④ 由于牛客没法设置部分分，因此比赛分数可能出现小数。不过，除了分数设置之外，校内赛和同步赛的所有配置都是一样的（包括题目和每道题设置的测试点）。我们每个题的测试点也放的比较少（但强度都是经过验证的， $L2-3$ 除外 $qwq$ ），算是模仿天梯赛吧（天梯赛的测试点数量也很少，分点得分）。

⑤ 虽然我们的确为这次比赛做了很多准备，但毕竟是第一次在牛客上办天梯模拟赛，这次比赛中还是出现了一些不该出现的问题。我们也会在之后的比赛中整改（从下次公开赛开始，我们会强制要求所有出题人写 $Validator$ ；并且会根据本次公开赛的情况，相应调整未来比赛题目的难度），算是亡羊补牢为时不晚吧~

最后，再次感谢所有人对我们常熟理工学院的支持！也欢迎大伙以后再来参加我们 $cslg$ 的比赛嗷！

题解 | 2025常熟理工学院天梯选拔赛（同步赛）

2025常熟理工学院天梯选拔赛题解

说在前面的话......

L1 基础级

L1-1 简单题目

L1-2 Jiangly’s A+B-C Problem

L1-3 判断两个程序的中断优先级

L1-4 v98pro

L1-5 书法

L1-6 魔方

L1-7 女神节的魔法花园

L1-8 KNN算法

L2 进阶级

L2-1 下棋

L2-2 Dyzzzd的字符串

L2-3 彩排（Easy）

L2-4 shadow of the labyrinth

L3 登顶级

L3-1 数织

L3-2 gxy学长的精灵融合

L3-3 我嘞个豆

写在后面的话......