传送门:CF
[前题提要]:一道*1800,本题思路很好想,就是找循环,但是细节较多,故写一篇题解
直接进入正题.
模拟一下题意,最后不难发现我们最后的字符串应该是一个字符串S1的循环加上一个S2的形式.(当然可能没有S2).
更具体的举一个小栗子,设 x , y , z , k x,y,z,k x,y,z,k为字符串,包含了多个字符.那么我们最后的字符串的形式应该如下:
X
X
XY
X
X
XYZ
X
X
XY
X
X
XYZK
也就是很多个循环套在一起的形式.显然对于我们想要找的位置 p p p,我们应该从外部一层一层递归去找它属于哪一个循环,也就是一层一层的去掉我们的循环.更具体的来讲,如果我们的 p p p所处于的值在 K K K字符串中的一个字符位置,那么显然我们此时的答案就是找到K,然后在里面找位置,此时就很好解决了.
但是如果不处于我们的K位置应该怎么解决呢,我们就会发现显然他是处于之前的那一个循环之中的.我们对每一个循环节取一个模,就可以顺利的将最外层的一层循环去掉,此时只要看内一层的循环即可.也就是说,此时我们只需要考虑(假设此时的位置处于Y位置的话):
X
X
XY
X
X
XYZ
那么此时我们操作方式就是和上面一样的了.如果此时的 p p p处于增加字符的位置(也就是Z)的位置,我们可以很容易的将这个字符算出(只要将p减去循环节的长度乘循环的次数就可以算出在Z的具体位置).如果不是的话,那么显然在更内部的循环之中,那我们又可以去掉一个循环…
这样反复递归,最后就可以求出来了.
下面是具体的代码部分:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls (rt<<1)
#define rs (rt<<1|1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
inline void print(__int128 x){
if(x<0) {
putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
#define maxn 1000000
#define int __int128
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Q{
int opt,x;
}ques[maxn];
signed main() {
int T=read();
while(T--) {
int n=read();int q=read();
vector<int>v;int num=0;
v.push_back(0);map<int,int>mp;int cnt=0;
for(int i=1;i<=n;i++) {
ques[i].opt=read();ques[i].x=read();
if(ques[i].opt==1) {
num++;
}
else {
if(v.back()>=1e18) continue;
mp[++cnt]=i;
v.push_back(num);
num=num*(ques[i].x+1);
}
}
int len=0;
for(int i=1;i<=q;i++) {
int k=read();
int pos=0;
if(k>v[cnt]*(ques[mp[cnt]].x+1)) {
print(ques[k-v[cnt]*(ques[mp[cnt]].x+1)+mp[cnt]].x);cout<<" ";
continue;
}
int flag=0;
for(int j=cnt;j>=1;j--) {
k=(k-1)%v[j]+1;
if(k>v[j-1]*(ques[mp[j-1]].x+1)) {
print(ques[k-v[j-1]*(ques[mp[j-1]].x+1)+mp[j-1]].x);cout<<" ";
break;
}
else {
continue;
}
}
}
cout<<endl;
}
return 0;
}
