洛谷【LGR-171-Div.3】深圳科创学院基础赛 #7 &「RHOI」Round 2 第三题 Reverse and Rotate

发布时间:2024年01月17日


题目链接

链接: P10058 Reverse and Rotate

题目描述

在这里插入图片描述
在这里插入图片描述

解题思路

首先是本题使用的数据结构,需要满足可以在头部插入和删除同时也能在尾部完成插入和删除
所以我们使用双端队列
本题数据范围较大,一定不能暴力解决,仔细观察可以发现,<和>两种操作可以先使用一个变量cc储存起来,统计完了统一移动即可,那么反转操作,怎么办呢,反转两次就相当于没反转,但是中间穿插了<和>操作,所以每次遇到反转时,我们之前记录的变量cc要取相反数,因为反转就代表着<和>操作会反过来,最后把反转的次数和1进行与运算来判断单双数,进而判断是否需要进行反转,这样就能得到正确的结果

代码实现

#include<iostream>
#include<cstring>
#include<algorithm>
#include<deque>
using namespace std;
typedef long long LL;
LL n,cnt,cc=0,re=0;
string a;
deque<char> d;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> a;
    for (char c : a)
    {
        d.push_back(c);
    }
    int l = d.size();
    cin >> n;
    while (n--)
    {
        string b;
        cin >> b;
        if (b == "<")
        {
            cin >> cnt;
            cc -= cnt;
        }
        else if (b == ">")
        {
            cin >> cnt;
            cc += cnt;
            
        }
        else
        {
            re++;
        }
    }
    if (cnt >= 0)
    {
        for (int i = 0; i < (cnt % l); i++)
        {
            d.push_front(d.back());
            d.pop_back();
        }
    }
    else {
        for (int i = 0; i < (cnt % l); i++)
        {
            d.push_back(d.front());
            d.pop_front();
        }
    }
    if(re&1) reverse(d.begin(), d.end());
    for (auto c : d)
    {
        cout << c;
    }
    return 0;
}

总结

熟悉使用双端对列,掌握了对相对操作或重复操作进行时间复杂度压缩的思想

文章来源:https://blog.csdn.net/zkdjen/article/details/135599210
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。