赛前模拟2025/8/27

__H_J_M__ · 2025-08-27 15:46:01 · 个人记录

Part 0 赛事主要时间线\color{white} \textsf {游祭}

[8:00]() 开始考试，先纵观全局，哇！两道原题（也有人说是四道，反正我只写过两道，有一道还没写出来），于是随即就十分兴奋啊，太 Amazing 了，于是想着赶紧写完 T1 再切 T2 T3 。

[8:50]() 切完T1，为了唤起”当年“写这道题的记忆，进入了厕所进行 深度搜索 ，实在是太 Amazing 了，我终于想起来了，当时死磕了一个小时，没有写出来。

[10:00]() 写了T2的一个十分 Amazing 贪心。

[10:05]() 开始写T3大模拟，因为以前写过一遍，也AC了，所以写的时候十分自信，但是挂了二十

[11:00]() T3大样例过了，开始写T4，最开始写了一个简单的DP却发现看漏了情况，只有k<=2时满足，头脑一热全删了，好不容易写完了暴力。

Part 1 赛时

T1

一看就十分像一个典型的DP啊，写了一会就出来了，这次也是十分的顺利啊，一次性全对了（包括大样例）。

但是当我想要关掉时，却想起了一句名言：

十年OI一场空

不开long long见祖宗

于是： #define int long long。 还好我又测了一遍大样例：

十分的 Amazing 啊，差的十分的远，把DP数组输出来才发现，在计算中的第二项莫名奇妙的出现了一个奇怪的数，检查一番后发现是这个问题：

for(int j=0;j<=n;j++)
    f[i]=f[j-1]+1;

f[-1]!!! 于是判了个零

T2

这道题我考场上的思路十分简单，枚举K，看一下哪一个D[i]减1后答案最小，时间复杂度：

预计得分60分

T3

太可惜了，写过的没有AC

错误点：

• 没有处理-1的情况 -10pts
• 未处理无效移动 -10pts

对于第二点，这里给出一些解释：

对于下面这组样例

输入：
3
1 0
1 0
2 1 0
2 2 0
0

输出：

0 0 1
0 0 1
3 1 1

你会发现，其实这个样例只需要1步便可以消除完成，但他要求的是3步， 因此我们需要进行一些无效操作

但在我的代码中，我判断不会交换两个相同的方块（这是一个我自认为十分理所应当的剪枝），因而在这组样例之中，我会输出

1 0 1
1 0 1
3 1 1

按照题目要求，我们应当输出字典序小的，因而这是错的。

T4

除了暴力以外，我还用 lca写了一个 k=1 的情况

Part 2 关于题目

T1

首先我们应当确认DP状态：

定义:

dp[i][j][k][0/1]表示考虑到A的第i位，B的第j位，当使用了k段字串后第i位匹不匹配j位时的方案数

易得:

如果A[i]==b[j]

f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1]
f[i][j][k][1]=f[i-1][j-1][k][1]+f[i-1][j-1][k-1][1]+f[i-1][j-1][k][0]

否则

f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1]
f[i][j][k][1]=0;

注意

如果这样开，f的大小为：

而我们发现每一次只会访问i-1， 所以可以直接滚动数组

T2

先看一个样例

蓝色的是每一个站中最后来的乘客，绿色的是车。

每一个站中最后来的乘客来的时间用lev[]表示 在不用加速器时理论每一次到站的时间用arr[]表示

图中黄色线段为当对途中三角形的地方进行氮气加速后造成的影响，我们发现，只要arr>lev，就会不断造成影响

且只要一个乘客在这个这个范围内，就会减去一点时间，所以我们枚举k每一次找贡献最大，并-1

代码：

#include <bits/stdc++.h>
using namespace std;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
const int N=1e3+5,M=1e4+5,K=1e5+5;
int n,m,k;
int d[N];
int vis[N];
int arr[N],lev[N];
struct node{
    int T,a,b;
}c[M];
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/

/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
signed main(){
    cin>>n>>m>>k;
    int tim=0;
    for(int i=2;i<=n;i++)
        cin>>d[i];
    for(int i=1;i<=m;i++){
        int T,a,b;cin>>T>>a>>b;
        c[i]={T,a,b};
        lev[a]=max(lev[a],T);
        vis[b]++;
    }
    for(int i=1;i<=n;i++){
        tim+=d[i];
        arr[i]=tim;
        tim=max(tim,lev[i]);
    }
    while(k--){
        int maxn=0,id=-1;
        for(int i=2;i<=n;i++){
            if(!d[i]) continue;
            int sum=0;
            for(int j=i;j<=n;j++){
                sum+=vis[j];
                if(arr[j]<=lev[j])
                    break;
            }
            if(sum>maxn)
                maxn=sum,id=i;
        }
        d[id]--;
        for(int i=id;i<=n;i++){
            arr[i]--;
            if(arr[i]<lev[i])
                break;
        }
    }

    int ans=0;
    for(int i=1;i<=m;i++){
        ans+=arr[c[i].b]-c[i].T;
    }
    cout<<ans<<'\n';
    return 0;
}

T3

#include <bits/stdc++.h>
using namespace std;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
int n;
int dx[2]={1,-1};
int vis[10][15];
int a[10][15];
struct node{
    int a,b,d;
}step[10];
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
void check(int x,int y){
    if(a[x][y]==0) return;
    if(a[x][y]==a[x+1][y]&&a[x][y]==a[x+2][y])
        vis[x][y]=vis[x+1][y]=vis[x+2][y]=1;
    if(a[x][y]==a[x][y+1]&&a[x][y]==a[x][y+2])
        vis[x][y]=vis[x][y+1]=vis[x][y+2]=1;
}
bool checker(){
    for(int i=1;i<=5;i++){
        for(int j=1;j<=7;j++){
            check(i,j);
        }
    }
    bool flag=0;
    for(int i=1;i<=5;i++)
        for(int j=1;j<=7;j++)
            if(vis[i][j])
                a[i][j]=0,flag=1,vis[i][j]=0;
    return flag;
}
void fall_down(){
    for(int i=1;i<=5;i++){
        int tot=0;
        for(int j=1;j<=7;j++){
            if(a[i][j]) a[i][++tot]=a[i][j];
        }
        for(int j=tot+1;j<=7;j++)
            a[i][j]=0;
    }
}
void dfs(int x){
//  print();
    if(x==n+1){
        for(int i=1;i<=5;i++)
            for(int j=1;j<=7;j++)
                if(a[i][j])
                    return;
        for(int i=1;i<=n;i++)
            cout<<step[i].a-1<<' '<<step[i].b-1<<' '<<step[i].d<<'\n';
        exit(0);
        return;
    }
    int Y[10][15];
    for(int i=1;i<=5;i++){
        for(int j=1;j<=7;j++){
            if(a[i][j]==0) continue;
            for(int d=0;d<2;d++){
                memcpy(Y,a,sizeof Y);
                int nx=i+dx[d],ny=j;
                if(nx<1||nx>5) continue;
//              if(a[nx][ny]==a[i][j]) continue;
                swap(a[nx][ny],a[i][j]);
                fall_down();
                while(checker())
                    fall_down();
                step[x]={i,j,dx[d]};
                dfs(x+1);
                memcpy(a,Y,sizeof a);
            }
        }
    }
}

/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
signed main(){
//  freopen("mayan.in","r",stdin);
//  freopen("mayan.out","w",stdout);
    cin>>n;
    for(int i=1;i<=5;i++){
        int x,cnt=0;
        while(cin>>x&&x){
            a[i][++cnt]=x;
        }
    }
    fall_down();
    while(checker())
        fall_down();
    bool flag=0;
    for(int i=1;i<=5;i++)
        for(int j=1;j<=7;j++)
            if(a[i][j])
                flag=1;
    if(!flag){
        cout<<0;
        return 0;
    }
    dfs(1);
    cout<<-1;
    return 0;
}