ABC221G Jumping sequence 题解
2021/11/4 23:13:33
本文主要是介绍ABC221G Jumping sequence 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题面
题意简述:
给定一个长度为 \(n\) 的序列 \(D,\)对于每一个 \(i\) 可以选择向一个方向走长度为 \(D_i\),问是否能走到 \((A,B)\)。
\(\texttt{Data Range:} 1\le n\le 2000,1\le D_i\le 1800,|A|,|B|\le 3.6\times 10^6\)。
首先把曼哈顿距离转化为切比雪夫距离 \((A,B)\rightarrow(A+B,A-B)\)。这样我们就将 \(x\),\(y\) 两维独立了。
对于操作,可以转化成如下形式:
- up:\((0,d)\rightarrow(-d,d)\);
- down:\((0,-d)\rightarrow(d,-d)\);
- left:\((-d,0)\rightarrow(-d,-d)\);
- right:\((d,0)\rightarrow(d,d)\)。
因此,问题就转化成:
给定 \(n\) 个正整数 \(D_i\),确定一组 \(\{C_i\}\) 使得 \(\sum C_i\times D_i=s\),其中 \(C_i\in\{1,-1\}\)。
假设 \(C_i=1\) 的数的和为 \(a\),\(C_i=-1\) 的数的和为 \(b\),所有数的和为 \(sum\),那么就有:
\[\begin{aligned} a-b&=s\\ b&=a-s\\ b&=sum-b-s\\ 2b&=sum-s \end{aligned} \]先把 \(sum-s\) 为奇数的情况判掉,然后跑一遍 bitset 优化 01 背包即可。
代码:
#include <bits/stdc++.h> #define DC int T = gi <int> (); while (T--) #define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__) #define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout) #define fi first #define se second #define pb push_back #define mp make_pair using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair <int, int> PII; typedef pair <LL, LL> PLL; template <typename T> inline T gi() { T x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();} while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return f * x; } const int N = 2003, M = N << 1; int n, a, b; int d[N]; int sum; bitset <3600003> f[N]; bool ans[N][2]; int main() { //freopen(".in", "r", stdin); freopen(".out", "w", stdout); n = gi <int> (), a = gi <int> (), b = gi <int> (); f[0][0] = 1; for (int i = 1; i <= n; i+=1) d[i] = gi <int> (), sum += d[i], f[i] = f[i - 1] | (f[i - 1] << d[i]); int x = a + b, y = a - b; if (x < -sum || x > sum || y < -sum || y > sum || ((sum - x) & 1) || ((sum - y) & 1)) return puts("No"), 0; x = sum - x, y = sum - y; x >>= 1, y >>= 1; if (!f[n][x] || !f[n][y]) return puts("No"), 0; int tmpx = x, tmpy = y; for (int i = n; i >= 1; i-=1) { if (tmpx >= d[i] && f[i - 1][tmpx - d[i]]) ans[i][0] = false, tmpx -= d[i]; else ans[i][0] = true; if (tmpy >= d[i] && f[i - 1][tmpy - d[i]]) ans[i][1] = false, tmpy -= d[i]; else ans[i][1] = true; } puts("Yes"); for (int i = 1; i <= n; i+=1) if (ans[i][0]) { if (ans[i][1]) cout << 'R'; else cout << 'U'; } else { if (ans[i][1]) cout << 'D'; else cout << 'L'; } return !!0; }
启发:
- 看到曼哈顿距离,马上考虑转成切比雪夫距离,这样可以将两维问题独立。
- 要有一定的推式子能力。
这篇关于ABC221G Jumping sequence 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验
- 2024-05-29AutoMQ 对象存储数据高效组织的秘密: Compaction
- 2024-05-29活动预告|来 GIAC 大会听大数据降本利器:AutoMQ 基于云原生重新设计的 Kafka