首页 > 其他分享 >AtCoder Beginner Contest 265 F Manhattan Cafe

AtCoder Beginner Contest 265 F Manhattan Cafe

时间:2023-06-12 22:33:23浏览次数:49  
标签:AtCoder typedef Beginner Contest int long maxn && mod

洛谷传送门

AtCoder 传送门

考虑 dp,\(f_{i, j, k}\) 表示考虑到第 \(i\) 维,\(\sum\limits_{x = 1}^i |p_x - r_x| = j, \sum\limits_{x = 1}^i |q_x - r_x| = k\) 的方案数。转移是容易的,枚举 \(r_i\) 即可,\(f_{i, j, k} = \sum\limits_r f_{i - 1, j - |p_i - r|, k - |q_i - r|}\)。

复杂度 \(O(nD^3)\),无法接受,考虑下标拆绝对值后前缀和优化。简单讨论一下就行。以 \(p_i \le q_i\) 的情况为例:

  1. \(r_i < p_i\),\(f_{i, j, k}\) 能从 \(\cdots, f_{i - 1, j - 2, k - q_i + p_i - 2}, f_{i - 1, j - 1, k - q_i + p_i - 1}\) 转移;
  2. \(p_i \le r_i \le q_i\),\(f_{i, j, k}\) 能从 \(f_{i - 1, j, k - q_i + p_i}, f_{i - 1, j - 1, k - q_i + p_i + 1}, \cdots, f_{i - 1, j - q_i + p_i, k}\) 转移;
  3. \(r_i > q_i\),\(f_{i, j, k}\) 能从 \(f_{i - 1, j - b_i + a_i - 1, k - 1}, f_{i - 1, j - b_i + a_i - 2, k - 2}, \cdots\) 转移。

也就是说我们只要维护对角线前缀和就好了。

要注意下标越界的问题。对于第 \(1, 3\) 种情况,能转移的是一段前缀或后缀,只要特判下标是否越界即可;对于第 \(2\) 种情况,因为能转移的是一段区间,如果下标为负,就要找到第一个 \(0\) 开始转移。

想清楚了写起来挺快的,不存在难写的问题。注意一些细节问题即可,比如符号写反,或者没取模等等,别像我一样有一处漏了取模然后傻傻调试 20min 就行。

时间复杂度 \(O(nD^2)\),可以通过。

code
// Problem: F - Manhattan Cafe
// Contest: AtCoder - AtCoder Beginner Contest 265
// URL: https://atcoder.jp/contests/abc265/tasks/abc265_f
// Memory Limit: 1024 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 1010;
const int mod = 998244353;

int n, m, a[maxn], b[maxn], f[2][maxn][maxn], g[3][maxn][maxn];

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &b[i]);
	}
	f[0][0][0] = 1;
	for (int i = 1, o = 1; i <= n; ++i, o ^= 1) {
		mems(f[o], 0);
		mems(g, 0);
		for (int j = 0; j <= m; ++j) {
			for (int k = 0; k <= m; ++k) {
				g[0][j][k] = f[o ^ 1][j][k];
				if (j && k) {
					g[0][j][k] = (g[0][j][k] + g[0][j - 1][k - 1]) % mod;
				}
			}
		}
		for (int j = m; ~j; --j) {
			for (int k = 0; k <= m; ++k) {
				g[1][j][k] = f[o ^ 1][j][k];
				if (j < m && k) {
					g[1][j][k] = (g[1][j][k] + g[1][j + 1][k - 1]) % mod;
				}
			}
		}
		for (int j = 0; j <= m; ++j) {
			for (int k = m; ~k; --k) {
				g[2][j][k] = f[o ^ 1][j][k];
				if (j && k < m) {
					g[2][j][k] = (g[2][j][k] + g[2][j - 1][k + 1]) % mod;
				}
			}
		}
		for (int j = 0; j <= m; ++j) {
			for (int k = 0; k <= m; ++k) {
				if (a[i] <= b[i]) {
					if (j - 1 >= 0 && k - b[i] + a[i] - 1 >= 0) {
						f[o][j][k] = (f[o][j][k] + g[0][j - 1][k - b[i] + a[i] - 1]) % mod;
					}
					if (j + 1 <= m && k - b[i] + a[i] - 1 >= 0) {
						f[o][j][k] = (f[o][j][k] + mod - g[1][j + 1][k - b[i] + a[i] - 1]) % mod;
					}
					int x = j - b[i] + a[i], y = k;
					if (x < 0) {
						y += x;
						x = 0;
					}
					if (y >= 0) {
						f[o][j][k] = (f[o][j][k] + g[1][x][y]) % mod;
					}
					if (j + a[i] - b[i] - 1 >= 0 && k - 1 >= 0) {
						f[o][j][k] = (f[o][j][k] + g[0][j + a[i] - b[i] - 1][k - 1]) % mod;
					}
				} else {
					if (j - a[i] + b[i] - 1 >= 0 && k - 1 >= 0) {
						f[o][j][k] = (f[o][j][k] + g[0][j - a[i] + b[i] - 1][k - 1]) % mod;
					}
					if (j - a[i] + b[i] - 1 >= 0 && k + 1 <= m) {
						f[o][j][k] = (f[o][j][k] + mod - g[2][j - a[i] + b[i] - 1][k + 1]) % mod;
					}
					int x = j, y = k - a[i] + b[i];
					if (y < 0) {
						x += y;
						y = 0;
					}
					if (x >= 0) {
						f[o][j][k] = (f[o][j][k] + g[2][x][y]) % mod;
					}
					if (j - 1 >= 0 && k + b[i] - a[i] - 1 >= 0) {
						f[o][j][k] = (f[o][j][k] + g[0][j - 1][k + b[i] - a[i] - 1]) % mod;
					}
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i <= m; ++i) {
		for (int j = 0; j <= m; ++j) {
			ans = (ans + f[n & 1][i][j]) % mod;
		}
	}
	printf("%d\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

标签:AtCoder,typedef,Beginner,Contest,int,long,maxn,&&,mod
From: https://www.cnblogs.com/zltzlt-blog/p/17476283.html

相关文章

  • Atcoder Beginner Contest 301
    A-OverallWinner题目大意A和T两人玩游戏,给定一串只由A和T组成的字符串,如果第i个字符是A,则A赢得第i轮的胜利,反之则T赢;当遍历完整个字符串后,谁赢的轮数多谁就是最终赢家,如果一样则谁最先达到该轮数谁赢,输出赢家的名字解题思路签到题不多嗦了神秘代码......
  • AtCoder Beginner Contest 278 ABCDE
    AtCoderBeginnerContest278A-ShiftProblemStatement题意:给你一个长度为n的序列,让你移走前面k个后面补k个0。Solution思路:按照题意模拟即可。#include<bits/stdc++.h>usingnamespacestd;inta[1100];intmain(){ intn,k; cin>>n>>k; k=min(k,n); for(int......
  • UNIQUE VISION Programming Contest 2023 New Year (AtCoder Beginner Contest 287) A
    UNIQUEVISIONProgrammingContest2023NewYear(AtCoderBeginnerContest287)A-MajorityProblemStatement题意:给你n个字符串,字符串是For表示agree,字符串Against表示disagree,让你判断最终是否通过。Solution思路:统计For和Against的数量,比较一下即可。#include......
  • AtCoder Beginner Contest 284 ABCDE
    AtCoderBeginnerContest284A-SequenceofStringsProblemStatement题意:给你n个字符串,让你倒序输出Solve#include<bits/stdc++.h>usingnamespacestd;constintN=20;strings[N];intmain(){ intn; cin>>n; for(inti=1;i<=n;i++) cin>>s......
  • Atcoder-AGC033C
    看到这道题,是个博弈论,没见过树上的,于是想到在数列里的博弈论,又联想到树的特殊形式————链。于是我们来讨论一下链的情况(对于没有硬币的点,我们就视为它被删掉了):讨论链的情况发现若是选择两端的点,顶点数会减一;若是选择中间的点,顶点数会减二。现在我们站在链的角度来思考......
  • AtCoder Beginner Contest 302
    A-Attack题目大意给定两个数a和b,问我们需要进行多少次a-b,才能让a小于等于0解题思路签到题不多嗦了神秘代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=1e6+10;signedmain(){inta,b,c;cin>>a>>b;if(a%b......
  • AtCoder Beginner Contest 305 题解
    https://atcoder.jp/contests/abc305/tasks_printE-ArtGalleryonGraph冷知识:md这题赛时没做出来/cy刚看到题:这是什么题啊,\(K,h\)都\(1e5\)能做吗/fn确实能做。考虑类似SPFA的操作。设\(a_x\)表示\(x\)还可以对距离最多为\(a_x\)的点产生贡献,然后就直接......
  • AtCoder Beginner Contest 258 F Main Street
    洛谷传送门AtCoder传送门发现这题有个远古的WA就来改了(发现走法很多种,不想分类讨论,考虑最短路。设起点编号为\(1\),终点为\(11\)。\(x=Bn\)和\(y=Bn\)把坐标系分成了若干块。考虑过起点作一条平行于\(Ox\)的直线,与左右两条\(x=Bn\)的线有两个交点,给它们编号......
  • AtCoder Beginner Contest 305
    A-WaterStation(abc305a)题目大意给定一个数字\(x\),输出一个数字,它是最接近\(x\)的\(5\)的倍数。解题思路令\(y=x\%5\),如果\(y\leq2\),那答案就是\(x-y\),否则就是\(x+5-y\)。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=long......
  • ATCoder [ABC167D] Teleporter
    #题目解析这段代码的目标是处理一个含有$n$个元素的整数序列,根据一定的规则,重复操作$k$次后,确定操作结束时位于序列哪个位置。##解题思路1.**读取输入**:首先,我们读取输入的整数$n$和$k$,以及整数序列`a`。我们需要对序列的每个元素减一,以适应从0开始的索引。cin......