Educational Codeforces Round 133 (Rated for Div. 2)CD题解

过AB补CD

C. Robot in a Hallway

题意

题意：现有 2∗m 的方格。现在你在第一行第一列，需要遍历所有方格，且满足以下的条件：

• 每个方格上有数字a_i,j，只有在第a_i,j秒之后才能移动到该方格。
• 每一秒，你可以移动到相邻位置（上下左右相邻的方格）中可以移动到的方格，或者什么也不做。
• 每一个方格只能经过一次。

求最少需要的时间。

数据范围：$1\le m\le 2\ast 10^5$

tags：思维，后缀和

思路

• 首先，需要知道只有两种移动方式：

  1. 蛇形移动
  2. U形移动

• 移动过程肯定是先蛇形移动，到了某一列在开始U形移动，有三种情形：

  

  1. 第一种情况因为起点终点同一列，不同于第23种情况，单独讨论它。
  2. 第二三种情况一样，蛇形移动可以一步一步遍历过去，但是难点在于求后面的U形移动

• U形移动：这里我理解的好久好久才明白😭😭

  先假设到起点时蛇形移动的时间位now，并且目前所在列为第i列*（行无所谓，因为不管在上行还是在下行求法都是一样的）*

  1. 从起点第i列移动到第n列，取下面最大值：

     1. now+n-i：不用等待，直接一步一步走
     2. a[行][j]+1+n-j，其中j取i+1到n的最大值：需要等a[行][j]开放，后面不需要等待直接一步一步走

     取最大值为temp后，temp即为中起点第i列移动到第n列的最少花费

  2. 从另一行第n列移动到终点第i+1列，取下面最大值：

     1. temp+1+n-(i+1)：不用等待一步一步走*（注意还有换行的+1步）*
     2. a[另一行][j]+1+j-(i+1)=a[另一行][j]+j-i，其中j取i+1到n的最大值：需要等a[另一行][j]开放，后面不需要等待一步一步走

     取最大值为temp，此时temp即为从起点到终点的最小花费时间

  3. 每一个蛇形走位都重复上面步骤，取最小值

  最主要的是求a[行][j]+i+n-j与a[另一行][j]+j-i，其中对与每一个蛇形走位，n与i*（起点）*是定值，于是就只用取a[行][j]-j与a[另一行][j]+j，j分别取i+1到n、n到i+1的最大值，因为要求最大值，我们就可以维护后缀和：a[i][j]-j与a[i][j]+j最大值即可，这样就只用O(1)就能求出来了

至于上面说的第一种情况，求法和求U型一样，不过注意起点(0,1)和终点(1,1)位置

notice：在蛇形和U形移动中换行我用的是滚动数组的形式

代码

复杂度：$O(m)$

#include
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;

const int maxm=2e5+5;
int m;
ll a[2][maxm],max1[2][maxm],max2[2][maxm];

void init(){
	max1[0][m+1]=max1[1][m+1]=max2[0][m+1]=max2[1][m+1]=-inf;
	for(int i=0;i<2;i++){
		for(int j=m;j>=1;j--){
			max1[i][j]=max(max1[i][j+1],a[i][j]-j);//维护a[i][j]-j最大值
			max2[i][j]=max(max2[i][j+1],a[i][j]+j);//维护a[i][j]+j最大值
		}
	}
}

void solve(){
	ll mn=inf,now=a[1][1]+1;//先往下移一步，不管第一种情况（以(0,1)为起点的U型）
	for(int i=1;i<=m;i++){
		ll temp=max(now+m-i,max1[i&1][i+1]+m+1);//U形：从该行第i+1列到第n列
		mn=min(mn,max(temp+m-i,max2[(i+1)&1][i+1]-i));//U形：从另一行第n列到第i+1列
		now=max(now+1,a[i&1][i+1]+1);//蛇形：往右走一步
		now=max(now+1,a[(i+1)&1][i+1]+1);//蛇形：往上走一步
	}
	ll temp=max(1ll*m-1,max1[0][2]+m+1);//特判第一种情况，U形：从(0,0)到(0,n)
	temp=max(temp+m,max2[1][1]);//从(1,n)到(1,1)
	cout<>t;t;t--){
		cin>>m;
		for(int i=0;i<2;i++)
		for(int j=1;j<=m;j++)
		cin>>a[i][j];
		init();
		solve();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

D. Chip Move

题意

给定一个n和一个k，初始时从0位置开始，第i步可以选择长度为(k + i - 1)正倍数的步长。问1~n中的每个x，从0走到x有多少种方案。

数据范围：$1\le k,n\le 10^5$

tags：动态规划（完全背包变形）

思路

DP抽象意义：dp[i][j]：走i步可以到坐标j的方案数

状态转移方程：假设当前一步可以走step步

• 普通版：dp[i][j]+=dp[i-1][j-k*step],k=1,2,3...这是直观的来源，但是每一步都要枚举k，会超时
• 完全背包版：dp[i][j]+=dp[i-1][j-step]+dp[i][j-step]类似于完全背包

边界条件：dp[0][0]=1

遍历：

• 遍历过程中k是变化的，但是总步数$(k+k+i)(i+1)/2\le n$

• 注意要状态压缩，不然数组会存不下，并且不能用一维数组*（因为每次都得统计一下当前状态的方案数，若用一维会掺杂上一个状态的方案）*，用轮换dp

样例1模拟一下：

代码

#include 
#define ll long long
using namespace std;

const ll mod = 998244353, maxn = 2e5 + 5;
ll n, k;
ll dp[2][maxn];
ll out[maxn];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>k;
	dp[0][0]=1;
	for(int i=0;k+i*(i+1)/2<=n;i++){
		ll step=k+i;
		for(int j=step;j<=n;j++){
			dp[(i+1)&1][j]=(dp[i&1][j-step]+dp[(i+1)&1][j-step])%mod;
		}
		for(int j=0;j<=n;j++){
			out[j]=(out[j]+dp[(i+1)&1][j])%mod;
			dp[i&1][j]=0;
		}
	}
	for(int i=1;i<=n;i++)cout<