当前位置: 首页 > news >正文

CF2145F Long Journey

你在 \(0\) 时刻位于数轴上的 \(0\) 位置。每个时刻开始时,你可以选择右移一个单位,或者停在原地。在第 \(t\) 个时刻结束时,如果你的位置 \(p\) 满足 \(p \equiv b_{t\bmod n} \pmod {a_{t\bmod n}}\),那么你就输了,注意 \(0\) 时刻可能已经满足这个条件,但是忽略这种情况。

询问到达数轴上 \(m\) 位置需要的最少时间,或报告不可能。

\[1\le n,a_i \le 10,1\le m \le 10^{12} \]


敏锐地注意到数据范围非常小。

首先一个观察是,能向前走的时候就向前走一定是最优的。

证明是,假设某一个时刻等待能够比向前走更快达到终点,

image

那么我们调整成如图的绿色路线一定不会更劣。

image

因此我们只需要贪心地向前走就可以了。

考虑加速这个过程。

发现 \(\text{LCM}(1,2,3,4,5,6,7,8,9,10)=2520\)

因此我们可以记录 \(f_{i,j,k}\),表示当前状态满足 \(t\equiv i\pmod n\)\(p\equiv j\pmod {LCM}\),经过 \(2^k\) 时间后,能走多远。

边界状态是 \(f_{i,j,0}=[j+1\not\equiv b_{(i+1)\bmod n} \pmod {a_{(i+1)\bmod n}}]\)

然后可以简单递推,查询的时候倍增即可。

#pragma GCC optimize("Ofast", "inline")
#include <algorithm>
#include <iostream>
#include <vector>
#include <tuple>const int N = 11, M = 60, L = 2521;
#define rep(i,a,b) for(int i(a);i<=(b);++i)
#define rap(i,a,b) for(int i(a);i<(b);++i)
typedef long long i64;i64 m;
int n;
int a[N], b[N], pow2[M];
i64 dp[M][N][L];
void solve() {std::cin >> n >> m; int L = 1;rep(i, 1, n) std::cin >> a[i], L = L * a[i] / std::__gcd(L, a[i]);rep(i, 1, n) std::cin >> b[i];a[0] = a[n], b[0] = b[n], pow2[0] = 1;rap(i, 1, M) pow2[i] = pow2[i-1] * 2 %n;rap(i, 0, n) {rap(j, 0, L) {int x = (i + 1) % n;dp[0][i][j] = (j + 1) % a[x] != b[x];}}i64 turn = 1;rap(k, 1, M) {rap(i, 0, n) {rap(j, 0, L) {int a = (i + turn) % n, b = (j + dp[k-1][i][j]) % L;dp[k][i][j] = dp[k-1][i][j] + dp[k-1][a][b];}}	turn = turn * 2 %n;}i64 last = m, ans = 0;int a = 0, b = 0;for(int i = M - 1; i >= 0; --i) {if(last > dp[i][a][b]) {last -= dp[i][a][b];b = (b + dp[i][a][b]) %L;a = (a + pow2[i]) %n;ans += 1ll << i;}}for(int i = M - 1; i >= 0; --i) {if(dp[i][a][b] == 0) {b = (b + dp[i][a][b]) %L;a = (a + pow2[i]) %n;ans += 1ll << i;}}if(dp[0][a][b] == 0) std::cout << "-1\n";else std::cout << ans+1 << "\n";
}int main() {std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);int t; std::cin >> t; for(; t--; ) solve();
}
http://www.hskmm.com/?act=detail&tid=27181

相关文章:

  • 强化学习实验环境库 gym/Gymnasium
  • 设备的分配与回收
  • Encoding.RegisterProvider(CodePagesEncodingProvider.Instance)了解
  • TortoiseGit——Error:Unable to write index
  • 2025 年最新推荐超声波清洗机源头厂家排行榜:深度解析各品牌核心优势与选购指南龙门式/悬挂链/全自动/多臂式/多槽式超声波清洗机厂家推荐
  • 2025 年等离子清洗机源头厂家最新推荐排行榜:聚焦大气真空宽幅等多类型设备,精选实力口碑双优企业自动化/常压/低温/大腔体/射频等离子清洗机厂家推荐
  • 2025 年最新推荐!国内空调机组厂家权威排行榜,含冷凝热回收等多类型机组企业优选指南冷凝热回收/泳池热泵/屋顶式/海水源养殖热泵空调机组厂家推荐
  • 基于Zernike灰度矩的亚像素边缘检测实现(精度0.05 pixel)
  • 鸿蒙应用开发从入门到实战(十七):ArkUI组件List列表布局
  • 2025 最新推荐!AI 写作工具公司榜单:综合实力、用户体验与新锐品牌深度解析
  • 2025 最新推荐:AI 写小说工具公司口碑排行榜,聚焦卓越品质与新锐实力的权威指南
  • Gitee领航本土DevOps平台发展新纪元:数字化转型中的中国方案
  • 一天一款实用的AI工具,第5期,AI翻译成日语
  • 2025 年最新推荐金相厂家榜单:涵盖磨抛机 / 切割机 / 显微镜等设备,助力企业精准选品
  • Go工程打包版本号
  • C#调用matlab封装的dll报错
  • 生产设备数据采集怎么做?主要有哪些应用?
  • 2025 年编码器源头厂家最新推荐榜单:聚焦无磁 / 光学 / 脉冲 / 绝对型等多类型编码器,精选优质企业助力采购决策
  • 2025 年绝对式编码器源头厂家最新推荐榜单:增量 / 多圈 / 二进制 /ssi/ 拉线型产品优质企业全面盘点
  • go.work工作区
  • 2025 房屋改造设计公司最新推荐榜:覆盖全场景需求,精准匹配老房 / 小户型 / 局部改造优质品牌
  • 2025 年最新推荐碳纤维布源头厂家口碑排行榜:实力企业重点项目案例与选择指南全解析建筑/加固/300克/碳纤维加固布厂家推荐
  • 如何在AutoCAD中进行GIS建库?
  • Java方法的值传递机制学习笔记
  • Gitee发布MCP Server:重新定义AI赋能的代码协作新时代
  • 小程序上传文件,如发票
  • AI问答与搜索引擎:信息获取的现状
  • 2025 年别墅电梯优质厂家最新推荐排行榜:聚焦技术安全与市场口碑,助力业主精准选购家用/自建房/电梯维修/电梯加装/电梯改造/老旧小区加装电梯厂家推荐
  • 跨网文件摆渡系统是什么?你想了解的问题都在这!
  • 使用Grok获取Sora2邀请码