CF-Mark and His Unfinished Essay

题目大意:
给你一个长度不超过2e5的字符串 ,有 c 次操作和 q 次询问,每次操作选择从 l 到 r 位置的子串复制到字符串末尾,复制操作不超过40次,每次询问给你一个位置 k ,让你输出第 k 个位置上的字符

思路:
由于数据量很大,直接模拟不现实,可以从操作次数入手,考虑每次操作保存要复制字符串的新位置,查询时逐层递推返回到原来字符串的位置

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;
const int N = 50, M = 2 * N, mod = 1e9 + 7;
typedef long long LL;
LL n, c, q;
 
int l[N], r[N], lc[N], rc[N];
 
void solve() {
    cin >> n >> c >> q;
    string s;
    cin >> s;
    LL len = s.size();          //字符串长度
    for (LL i = 1; i <= c; i++) {
        cin >> l[i] >> r[i];     //第 i 次输入的区间左右端点
 
        LL now = r[i] - l[i] + 1;
        lc[i] = len + 1;         //lc[i]表示第i次的复制字符串左端点位置
        rc[i] = lc[i] + now - 1; //lc[i]表示第i次的复制字符串右端点位置
        len += now;              //字符串长度更新
    }
 
    while (q--) {
        LL k;
        cin >> k;
        for (LL i = c; i >= 1; i--) {   //返回到原字符串的位置
            if (lc[i] <= k && k <= rc[i]) { 
                k -= lc[i] - l[i];
            }
        }
        cout << s[k - 1] << endl;
    }
}
int main() {
    int T = 1;
    cin >> T;

    while (T--) {
        solve();
    }
}
全部评论

相关推荐

06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 13:47
机械打工仔:你自己匿名可以,这么好的公司就别给它匿名了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务