主页
搜索
最近更新
数据统计
赞助我们
系统公告
1
/
1
请查看完所有公告
题解：AT_abc410_c [ABC410C] Rotatable Array
最后更新于 2025-06-16 12:24:59
作者
DPOI
分类
题解
题解
AT_abc410_c
复制 Markdown
查看原文
更新内容
~~连E都挂掉的蒟蒻来水一波C题解~~ ### 做法 #### $O(qk)$ 做法 直接用队列模拟。 #### $O(qn)$ 做法 先想到 $k$ 太大，又想到每移动 $n$ 次，序列是不会变得，所以可以用 $k$ 先对 $n$ 取模，即可优化到 $O(qn)$ 的时间复杂度，但依旧无法通过。 #### $O(q)$ 做法 容易想到操作 $3$ 是瓶颈，如果我们可以不去修改整个序列，而只用修改一个变量就可以了，我们可以设置一个变量，来记录整个序列的起点相较于 $1$ 偏移了多少，这样操作 $3$ 就仅需修改这个变量，对于操作 $2$ 或者操作 $1$，我们就根据这个起点偏移量取改就可以了。可以通过。 ### CODE ```cpp #include<bits/stdc++.h> #define int long long using namespace std; int a[1000005]; int f; signed main(){ int n,q;cin>>n>>q; f=0; for (int i=1;i<=n;++i)a[i]=i; while (q--){ int op;cin>>op; if (op==1){ int p,x; cin>>p>>x; int pos=(p-1+f)%n+1; a[pos]=x; } else if (op==2){ int p; cin>>p; int pos=(p-1+f)%n+1; cout<<a[pos]<<'\n'; } else if (op==3){ int k;cin>>k;k%=n; f+=k; } } } ```
正在渲染内容...
点赞
0
收藏
0
