思路大概是这样的:
记录每一个多次复制的位置,然后倒着来看,对于每一个位置考虑当前的 k(表示要求第 k 个数),如果 k 是比当前位置数字的个数大的,说明就在这个位置之后,就直接输出 k 个位置的数;反之,说明在这么多个复制里面,就对 Bk−1 取模(Bi 表示到第 i 个点的数字个数,Bk−1 就是复制的长度),如果取模后为 0,就更新为 Bk−1,因为 0 就相当于最后一个。
自己试了几个数据,好像都没问题,然后就 WA 了!
大家能不能帮忙指出错误,或给个错误数据也行呀~~~ qwq 求求了
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int SIZE = 1e5 + 10;
int N, Q;
int B[SIZE], Op[SIZE], Id;
map<int, int> A;
void solve()
{
Id = 0;
cin >> N >> Q;
A.clear();
int P, X, Flag = 0, Flag2 = 0;
std::vector<int> Pos;
Pos.push_back(0);
for (int i = 1; i <= N; i ++)
{
cin >> P >> X;
if (P == 2 && 2e18 / B[i - 1] < X + 1) Flag = i - 1, Flag2 = 1;
if (Flag) continue;
if (P == 1)
B[i] = B[i - 1] + 1, A[B[i]] = X, Op[i] = 1;
else
B[i] = B[i - 1] + (B[i - 1] * X), Op[i] = 2, Pos.push_back(i);
if (B[i] > 1e18) Flag = i;
}
reverse(Pos.begin(), Pos.end());
while (Q --)
{
int X;
cin >> X;
if (Flag2 && X > B[Flag]) X %= B[Flag];
if (!X) X = B[Flag];
for (auto c : Pos)
if (X > B[c])
{
cout << A[X] << " ";
break;
}
else
{
X %= B[c - 1];
if (!X) X = B[c - 1];
}
}
cout << endl;
}
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int Data;
cin >> Data;
while (Data --)
solve();
return 0;
}