BZOJ4095 : [Usaco2013 Dec]The Bessie Shuffle
The shuffle Dec
2023-09-11 14:15:02 时间
首先将排列和整个序列以及询问都反过来,问题变成给定一个位置$x$,问它经过若干轮置换后会到达哪个位置。
每次置换之后窗口都会往右滑动一个,因此其实真实置换是$p[i]-1$。
对于每个询问,求出轮数,倍增找到最终位置,注意当中途走到$0$时,说明离开了窗口,应及时终止。
时间复杂度$O((m+q)\log n)$。
#include<cstdio> const int N=100010,M=30; int n,m,q,i,j,x,r,k,a[M][N]; inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';} int main(){ read(n),read(m),read(q); for(i=m;i;i--)read(x),a[0][m-x+1]=i-1; for(i=1;i<M;i++)for(j=1;j<=m;j++)a[i][j]=a[i-1][a[i-1][j]]; while(q--){ read(x); if(x<m)r=m;else r=x,x=m; k=n-r+1; for(i=M-1;~i;i--)if((1<<i)<=k&&a[i][x])x=a[i][x],k-=1<<i,r+=1<<i; if(k)x=a[0][x],r++; printf("%d\n",n-(r-m+x)+1); } return 0; }
相关文章
- 新建maven指定jdk版本-eclipse新建maven项目报错The superclass "javax.servlet.http.HttpServlet" was not found on the Java Build Path的解决方案
- java错误:The superclass "javax.servlet.http.HttpServlet" was not found on the Java Bu
- [Web] Use Web Speech API to make the browser speak out loud using SpeechSynthesis
- [Grid Layout] Use auto-fill and auto-fit if the number of repeated grid tracks is not to be def
- [TypeScript] The Basics of Generics in TypeScript
- -- Warning: Skipping the data of table mysql.event. Specify the --events option explicitly.
- [Typescript] Use the Nullish Coalescing Operator in TypeScript (isNil)
- [Python] Normalize the data with Pandas
- [ES6] 04. The let keyword -- 2 Fiald case
- The data replication requires the processing of single BDoc instances
- 解决The type or namespace name 'XXXX' does not exist in the namespace 'XXXXXXXXX' 的错误
- 【Codeforces 1083A】The Fair Nut and the Best Path
- 成功解决MSB8020 The build tools for v141 (Platform Toolset = ‘v141‘) cannot be found. To build using the
- NLP:LSTM之父眼中的深度学习十年简史《The 2010s: Our Decade of Deep Learning / Outlook on the 2020s》的参考文献
- 已解决You should consider upgrading via the ‘e: pythonpython.exe -m pip install --upgrade pip’ comma
- How to get the window id of a window using c++ program in ubuntu?
- The old instructions for getting the code
- DevOps 创建pipline报错:The value specified for SourceVersion is not a valid commit ID
- HDU 4836 The Query on the Tree lca || 欧拉序列 || 动态树
- 用conda安装包出现The environment is inconsistent, please check the package plan carefully
- macOS The bottle needs the Xcode CLT to be installed
- The absolute uri: http://java.sun.com/jsp/jstl/core cannot be resolved in either web.xml or the jar
- java.lang.IllegalStateException: The specified child already has a parent. You must call removeView() on the child's parent first.
- 编译webrtc报错:ERROR: The installation of the Chrome OS default fonts failed.
- ERROR 1290 (HY000): The MySQL server is running with the --secure-file-priv option so it cannot ···
- Linux|错误集锦|prometheus Error on ingesting samples that are too old or are too far into the future的解决
- (六)Jenkins部署项目报错The username you provided is not allowed to use the text-based Tomcat Manager (error
- Accidental override: The following declarations have the same JVM signature (getWindow()Landroid/vie
- 【异常】Flink整合ES出错,The implementation of the provided ElasticsearchSinkFunction is not serializable.
- 解决办法:The name 'Response' does not exist in the current context