专栏文章

赛前模拟2025/8/27

___H_J_M__
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio3w5oy
此快照首次捕获于
2025/12/02 12:56
3 个月前
此快照最后确认于
2025/12/02 12:56
3 个月前
查看原文

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数组输出来才发现，在计算中的第二项莫名奇妙的出现了一个奇怪的数，检查一番后发现是这个问题：
CPP
for(int j=0;j<=n;j++)
    f[i]=f[j-1]+1;
f[-1]!!! 于是判了个零

T2

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

T3

太可惜了，写过的没有AC
错误点：
  • 没有处理-1的情况 -10pts
  • 未处理无效移动 -10pts
对于第二点，这里给出一些解释：
对于下面这组样例
CPP
输入：
3
1 0
1 0
2 1 0
2 2 0
0

输出：

0 0 1
0 0 1
3 1 1
你会发现，其实这个样例只需要1步便可以消除完成，但他要求的是3步， 因此我们需要进行一些无效操作
但在我的代码中，我判断不会交换两个相同的方块（这是一个我自认为十分理所应当的剪枝），因而在这组样例之中，我会输出
CPP
1 0 1
1 0 1
3 1 1
按照题目要求，我们应当输出字典序小的，因而这是错的。

T4

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

Part 2 关于题目

T1

首先我们应当确认DP状态：
定义:
CPP
dp[i][j][k][0/1]表示考虑到A的第i位，B的第j位，当使用了k段字串后第i位匹不匹配j位时的方案数
易得:
CPP
如果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的大小为：
1000∗200∗200∗2∗4=320000000字节=320MB1000*200*200*2*4=320000000字节=320MB
而我们发现每一次只会访问i-1， 所以可以直接滚动数组

T2

先看一个样例
蓝色的是每一个站中最后来的乘客，绿色的是车。
每一个站中最后来的乘客来的时间用lev[]表示 在不用加速器时理论每一次到站的时间用arr[]表示
图中黄色线段为当对途中三角形的地方进行氮气加速后造成的影响，我们发现，只要arr>lev，就会不断造成影响
且只要一个乘客在这个这个范围内，就会减去一点时间，所以我们枚举k每一次找贡献最大，并-1
代码：
CPP
#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

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...