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

JamBrains 题解

题意题意

你吃过蘸蔓越莓酱的肉丸吗?科斯嘉简直爱不释手,尤其是在深夜解题时。实际上,他在电脑前吃得太投入:一些蔓越莓酱从罐子里滴出来,弄坏了他的键盘。但他还得继续解题。而且,他可不想像键盘那样被卡住!

科斯嘉使用的代码文件包含 \(n\) 行,编号从 \(1\)\(n\),其中第 \(i\) 行包含 \(s_i\) 个光标位置,从 \((i,1)\)\((i,s_i)\),将第 \(i\) 行第 \(j\) 个位置记作 \((i,j)\)

在部分按键损坏的情况下进行代码导航有点棘手。幸运的是,科斯嘉的向上和向右箭头仍能使用:

  • 向上键 \((\uparrow)\):若光标位于位置 \((i,j)\),如果 \(i=1\),光标保持原位;否则移动到位置 \((i-1, \min(j, s_{i-1}))\),其中 \(s_{i-1}\) 是第 \(i-1\) 行的长度。
  • 向右键 \((\rightarrow)\):若光标位于位置 \((i,j)\),如果 \(j<s_i\),光标移动到 \((i,j+1)\);否则移动到 \((i+1,1)\);但在位置 \((n,s_n)\) 时保持不动。

科斯嘉有个特殊技巧:他选择一个初始光标位置,开始执行无限次按键操作:先按 \(u\) 次向上键,接着按 \(r\) 次向右键,如此循环往复。

例如,设 \(n=5, u=2, r=5, s=\{5,2,4,3,1\}\)。从位置 \((4,3)\) 开始,前几次按键操作的光标移动轨迹如下:
\((4,3)\uparrow(3,3)\uparrow(2,2)\rightarrow(3,1)\rightarrow(3,2)\rightarrow(3,3)\rightarrow(3,4)\rightarrow(4,1)\dots\)

如果一个起始位置能通过执行此无限序列,使光标最终抵达第一行,则称该位置是成功的

你的任务是帮助科斯嘉计算代码文件中存在多少个成功的起始位置。

由于他的代码尚未完成,你还需要处理 \(q\) 次更新。每次更新会给出两个值 \(pos\)\(x\),你需要将 \(s_{pos}\) 重新赋值为 \(x\)。请输出在初始状态及每次更新后的问题答案。

形式化题意

对于一个长度为 \(n\) 的正整数序列 \(\{s\}_{i=1}^{n}\),定义

\[S=\{(i,j)\in \mathbb{Z}_+^2:i \le n,j\le s_i\} \]

对于一个 \((x,y)\in S\),定义

\[\uparrow(i,j)=\begin{cases} (1,j)& i=1\\ (i−1,\min\{j,s_{i−1}\}) & i \ne 1 \end{cases} \]

\[\rightarrow(i,j)=\begin{cases} (i,j+1)& j<s_i\\ (i+1,1) & i<n,j=s_i\\ (n,s_n)& i=n,j=s_n \end{cases} \]

再有两个正整数 \(u,r\),定义

\[a_i(x,y)=\begin{cases}(x,y)&i=0\\\uparrow(a_{i-1}(x,y))&i\ne 0,(i-1) \bmod (u+r)<u\\\rightarrow(a_{i-1}(x,y))&i\ne 0,u\le(i-1) \bmod (u+r)\end{cases} \]

\[S_{\text{Good}}=\{(x,y)\in S:\exists t \in \mathbb{N},a_t(x,y)\in\{(i,j)\in S:i=1\}\} \]

对于给定序列 \(\{s\}_{i=1}^{n}\),及正整数 \(n,u,r\),令

\[F(n,s,u,r)=|S_{\text{Good}}| \]

还有 \(q\) 个正整数对 \(\{(\mathrm{pos}_i,x_i)\}_{i=1}^{q}\),令

\[s^{(v)}_i=\begin{cases}s_i^{(v-1)}&i\ne \mathrm{pos}_v\\x_v& i=\mathrm{pos}_v\end{cases},v>0 \]

给了你 \(n,u,r,s^{(0)}\),你需要对于 \(v=0\dots q\),计算出

\[\mathrm{ans}_v=F(n,s^{(v)},u,r) \]

solution

结论1:答案具有单调性,即证:

对于 \((x_1,y_1),(x_2,y_2)\in S\),若 \((x_1,y_1) \le (x_2,y_2)\Leftrightarrow x_1<x_2\lor(x_1=x_2 \land y_1\le y_2),(x_2,y_2)\in S_{\text{Good}}\to(x_1,y_1) \in S_{\text{Good}}\)

首先显然 \(\uparrow(x_1,y_1)\le\uparrow(x_2,y_2),\rightarrow(x_1,y_1)\le\rightarrow(x_2,y_2)\)

于是 \(a_t(x_1,y_1) \le a_t(x_2,y_2)\),又 \(\exists t \in \mathbb{N},a_t(x_2,y_2)\in\{(i,j)\in S:i=1\}\),于是对于某个 \(j\)\(a_t(x_1,y_1) \le (1,j)\),得证。

结论2:\({\exists p \le n,p\in \mathbb{Z}_{+},S_{\text{good}}=\{(i,j)\in S:i \le p\}}\)

只需证明 \(\forall i \le n,j_1,j_2 \le s_i,i,j_1,j_2 \in\mathbb{Z}_+,(i,j_1)\in S_{\text{good}}\to (i,j_2)\in S_{\text{good}}\) 即可。

考虑数学

http://www.hskmm.com/?act=detail&tid=36550

相关文章:

  • 2025年10月注册公司推荐:权威榜对比评测
  • NVIDIA HGX B200降低碳排强度的技术突破
  • 2025年10月上海装修公司评测榜:五强性价比与资质全对比
  • 2025年10月洗碗机品牌评测:海信领衔榜单
  • 2025年10月洗碗机品牌排名:海信稳居热销榜
  • YSP_refs_cn_2025
  • 2025年10月油烟机品牌排名:海信榜首五强横向榜
  • 2025年10月代理记账公司推荐:权威榜单对比全维度评测
  • 2025年10月油烟机品牌排名榜:海信携四强实测盘点
  • 详细介绍:探索少样本分类的深度:A Closer Look at Few-shot Classification
  • 2025年10月办公家具公司推荐:性价比榜五强评价报告
  • 解题报告-邪恶的大叔
  • OOP-实验2
  • JS学习记录
  • 2025年10月小红书代理商推荐榜:官方授权与实战案例对比评测
  • 小波函数多尺度变换的 Curvelet 变换
  • 2025年10月西安种植牙医院推荐榜:五强对比评测
  • 2025年10月短视频营销公司对比评测榜:孙圈圈领衔增长型IP服务排行
  • 2025年10月抖音代理商榜单:本地推与千川服务能力对比
  • 三、阅读笔记三:提升开发效率的利器
  • 20232302 2025-2026-1《网络与系统攻防技术》实验二实验报告
  • 2025年10月医用面膜产品推荐:权威对比评测榜揭晓前五强
  • P11024 做题报告
  • 多模态数据湖技术深化,Data Agent新能力发布!“认知”将决定企业上限
  • 2025年10月投资纠纷律师推荐:五强榜单对比评测与选择指南
  • Web刷题篇-1 [BJDCTF2020]Easy MD5
  • 云斗 YDR Special# 004 S 模拟赛
  • Berry.Live:开箱即用的.NET直播流媒体服务器
  • 2025年10月上海ICL医生推荐榜:王晓瑛领衔五强对比
  • doris集成vertica 数据源catalog