题解：AT_abc457_c [ABC457C] Long Sequence

Gardener2015 · 2026-05-10 11:36:46 · 题解

思路

我们可以建立一个变量 now 表示当前 B 数组中的元素个数，然后按顺序模拟每一次拼接，每次拼接先将 now 加上 L_i \times C_i，如果 K 小于等于 now，那么就说明 B_K 的值必定是序列 A_i 中的某一个 A_{i,j} 的值，我们只需要用 K 减去这一次拼接前的 now 的值再对 L_i 取模就可以得到 B_K 的值对应的序列 A_i 中的 A_{i,j} 的下标 j，但不过如果这个值为 0，那么 j 的值就是 L_i，最后输出 A_{i,j} 即可。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,k,l[200001],c,now;//不开long long见祖宗
map<long long,map<long long,long long> >a;//因为开数组会导致MLE，所以我使用map完成
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>l[i];
        for(int j=1;j<=l[i];j++)
            cin>>a[i][j];
    }
    for(int i=1;i<=n;i++){
        cin>>c;
        now+=c*l[i];//拼接增加长度
        if(k>now)//如果长度过短则直接跳到下一层循环
            continue;
        cout<<((k-(now-c*l[i]))%l[i]==0?a[i][l[i]]:a[i][(k-(now-c*l[i]))%l[i]])<<endl;//长度足够，输出答案
        break;
    }
    return 0;
}

AC 记录。