首页 > 其他分享 >Atcoder ABC221G Jumping sequence

Atcoder ABC221G Jumping sequence

时间:2023-06-09 16:02:44浏览次数:41  
标签:Atcoder limits sequence int sum 符号 Jumping zf 10

发现这个 \((x, y)\) 对应的是曼哈顿距离不太好求,那直接逆时针旋转 \(45\) 度(其实应该还要伸长 \(\sqrt{2}\) 倍,但是可以当做 \(d_i\) 也伸长 \(\sqrt{2}\) 倍不用去管)转化成切比雪夫距离 \((x - y, x + y)\)。
同时对应的 \(4\) 个方向在旋转后对应的方向也得到了改变:\(U(-d, d), R(d, d), D(d, -d), L(-d, -d)\),这个可以通过上面得到的 \((x - y, x + y)\) 带进去算。
然后就发现可以分 \(x, y\) 轴来算了,因为 \(x\) 轴的符号无非就正或负,\(y\) 轴同理,\(2\) 个符号结合在一起都能对上 \(4\) 个方向中的 \(1\) 个。

然后考虑如何求解方案,设方案中符号为正的数的和为 \(a\),符号为负的数的和为 \(b\),要得到的数为 \(s\),则可以得到以下式子:
\(\begin{cases}a + b = \sum\limits_{i = 1}^n d_i\\ a - b = s\end{cases}\)
所以可以得到 \(2a = \sum\limits_{i = 1}^n d_i +s\)。
于是当 \((\sum\limits_{i = 1}^n d_i + s) \bmod 2 = 1\) 或 \(\sum\limits_{i = 1}^n d_i +s < 0\) 时无解。

那么这个时候就可以去构造 \(a\) 了,这个东西还是挺板的,因为 \(a\) 代表的是符号为正的数的和,所以对于一个数只有不变或者 \(+d_i\) 这 \(2\) 种操作,然后就上一个背包。
但是时空复杂度 \(O(nm)\),其中 \(m\) 为背包上限,此题中为 \(3.6\times 10^6\),时空全炸。
但能发现这个背包只用记录合不合法,于是 bitset 优化,带上一个 \(\frac{1}{w}\) 的常数。
于是就可以跑背包先判断能不能凑出 \(a\),不能则无解,能再倒退找到对应方案,最后 \(x, y\) 轴的符号相结合得到答案。

时空复杂度 \(O(\frac{nm}{w})\)。

// lhzawa(https://www.cnblogs.com/lhzawa/)
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10, M = 3.6e6 + 10;
bitset<M> f[N];
int d[N];
int zf[N];
int main() {
	int n, a, b;
	scanf("%d%d%d", &n, &a, &b);
	int x = a - b, y = a + b;
	f[0].set(0);
	int s = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &d[i]);
		s += d[i];
		f[i] = f[i - 1]  | (f[i - 1] << d[i]);
	}
	if (x + s < 0 || y + s <0 || (s + x) % 2 == 1 || (s + y) % 2 == 1) {
		printf("No\n");
		return 0;
	}
	x = (s + x) / 2, y = (s + y) / 2;
	if ((! f[n][x]) || (! f[n][y])) {
		printf("No\n");
		return 0;
	}
	for (int i = n; i >= 1; i--) {
		if (x >= d[i] && f[i - 1][x - d[i]]) {
			zf[i] += 1, x -= d[i];
		}
		if (y >= d[i] && f[i - 1][y - d[i]]) {
			zf[i] += 2, y -= d[i];
		}
	}
	printf("Yes\n");
	for (int i = 1; i <= n; i++) {
		switch(zf[i]) {
			case 0: {
				printf("L");
				break;
			}
			case 1: {
				printf("D");
				break;
			}
			case 2: {
				printf("U");
				break;
			}
			case 3: {
				printf("R");
				break;
			}
		}
	}
	return 0;
}

标签:Atcoder,limits,sequence,int,sum,符号,Jumping,zf,10
From: https://www.cnblogs.com/lhzawa/p/17469425.html

相关文章

  • AtCoder Beginner Contest 240 D
    D-StrangeBallstag:栈模拟发现自己隔了快半年再做此题看错相同数字的球消失的条件,不是\(k\geq2\)而是\(k=a_i\)电子竞技不需要视力题意:当球\(a_i(1\leqi\leqN)\)有\(a_i\)个一起出现时,这\(a_i\)个球就会消失,问每次放一个球进去,放进去后还剩多少个球?用个......
  • AtCoder Beginner Contest 150 E Change a Little Bit
    洛谷传送门AtCoder传送门令\(S_i\getsS_i\oplusT_i\),那么代价中\(D\)变成\(S_i=1\)的\(i\)数量。转化为对所有\(f(S)\)求和,最后答案乘上\(2^n\)。考虑贪心地求\(f(S)\)。肯定是先选择小的\(C_i\),把\(S_i\)变成\(0\)。正确性显然。下面把\(C_i\)从大到......
  • 1502. Can Make Arithmetic Progression From Sequence
    /***1502.CanMakeArithmeticProgressionFromSequence*https://leetcode.com/problems/can-make-arithmetic-progression-from-sequence/description/*Asequenceofnumbersiscalledanarithmeticprogressionifthedifferencebetweenanytwoconsecut......
  • Codeforces 1588F - Jumping Through the Array
    显然无法用polylog的数据结构维护,序列分块也不行,考虑询问分块。每\(B\)个询问处理一次。将这个询问中\(2,3\)操作涉及到的点设为“关键点”,那么容易发现,环上每一段以关键点结尾的链在这块操作的过程中始终保持不变,也就是说我们可以把它们缩在一起。先预处理出每个块的增量......
  • AtCoder Beginner Contest 281 Ex Alchemy
    洛谷传送门AtCoder传送门考虑设\(f_i\)为\(i\)的答案,那么:\[f_i=[x_i](1+x)^A\prod\limits_{j=2}^{i-1}(1+f_jx)\]这个东西其实是可以分治FFT的。具体地,设分治区间为\([l,r]\),要求一个\(r-l+1\)次多项式\(\prod\limits_{i=l}^r(1+f_ix)\)。......
  • CF1838E - Count Supersequences
    先考虑正着做,我们只考虑整个\(b\)序列中出现的第一个子序列\(a\)。这样,我们就是要往\(a\)中插入\(m-n\)个数,其中\(a_{i-1}\)和\(a_i\)之间不能有\(a_i\)(否则就会有更靠前的子序列)。\(a_1\)前面不能有\(a_1\),\(a_n\)后面什么都可以有。我们发现,我们可以先枚举\(a......
  • AtCoder Beginner Contest 287 G Balance Update Query
    洛谷传送门AtCoder传送门线段树上二分入门题。考虑一个贪心:每次询问按\(a_i\)从大到小选。正确性显然。考虑动态开点线段树,每个结点\(a_i\in[l,r]\)存\(\sum\limits_{a_i\in[l,r]}b_i\)和\(\sum\limits_{a_i\in[l,r]}a_ib_i\)。线段树上二分找到第一个\(......
  • AtCoder Beginner Contest 258 G Grid Card Game
    洛谷传送门AtCoder传送门记\(b_i=\sum\limits_{j=1}^ma_{i,j},c_j=\sum\limits_{i=1}^na_{i,j}\)。首先考虑这样一个事情,就是对于\(b_i\le0\)的行有没有可能被选。如果选了它:如果没有选任何列,选这一行肯定不优;如果选了若干列,根据题目的要求,这若干列与这......
  • AtCoder Regular Contest 145
    A答案为Yes当且仅当$s[1]\ne$A或$s[n]\ne$B。注意判\(n=2\)。BAlice可胜利当且仅当\(n\gea\wedgen\bmoda<b\)。C显然我们应该凑\((2i-1,2i)\)。那么我们用一个括号序列描述\(2i-1\)和\(2i\),不难发现答案为\[\frac{\binom{2n}{n}}{n+1}......
  • AtCoder Beginner Contest 304 ABCDE
    AtCoderBeginnerContest304感觉手速场,后\(80\)分钟纯纯坐牢,A-FirstPlayer一些人坐成一个环,从年龄最小开始输出名字constintN=2e5+10;intn;strings[N];inta[N];voidsolve(){intm=1e9+2,p=1;cin>>n;for(inti=1;i<=n;......