描述

题目描述

首先我们化简一下题意，其实我们就是发现本题就是一个简单的模拟的过程，每页我们可以有四首歌曲，如果我们的按键超过了这页里面的歌曲，那么我们就会翻一页，但是我们要注意这么一个问题，我们只有在第一首歌曲往回翻的时候，我们是直接蹦到最后一页，或者当我们在最后一首歌曲的时候，我们向下翻页，我们会蹦到第一页，其他时候，比如我们执行一个向下的操作，我们只会把目前列表里面的第一个变到上一页，其他的不变，最后一个更新一下，同理我们执行向上的操作，我们只会把目前列表里面的最后一个删除掉，然后其他的不变

样例解释

10
UUUU

我们这个的意思就是我们有十首歌曲，然后我们要向上翻四次，目前的地方是在第一首歌曲这里，然后我们模拟一下这个样例，我们U一次，现在我们跳到了最后一页，当前的列表是（7，8，9，10），然后当前的位置就是10，我们再向上一次，我们会发现其实我们并没有跳出这页，那么我们不需要翻页，我们只需要把我们当前的一个位置向上移动一个位置即可，那么我们的位置就是变化到了9，以此类推，最后我们的位置刚好到了7，那么我们最后的位置就是7，因为我们其实只翻过一次页，那么当前的一个列表就是（7，8，9，10）所以最后的答案输出就是

7 8 9 10
7

知识点： 字符串模拟

难度： 一星

题解

解题思路

首先遇到这种题，其实题意繁琐，但是我们第一件事就是化简题意，化简之后我们会发现其实就是一个简单的模拟题目，我们想我们该怎么实现这么模拟的问题，我们先不想什么优化的办法，我们就按照题意，一步一步的来模拟这个问题，首先加入我们是U操作，我们究竟是有多少种可能，首先如果我们当前的位置是在第一首歌曲的这个位置，那么我们是不是就是要跳到最后一首歌曲，然后更新我们的列表，然后其他情况，如果我们当前的位置是在当前列表的头部，我们向上移动一次的时候，我们是不是就是会把我们原来列表的尾部向上了一位，然后更新了我们当前列表的头部，然后剩下的最后一种情况就是，它不是当前列表的头部，那么我们是不是可以不管怎么移动，他都是不会更新我们的这个列表，我们是不是只是需要更新我们当前的位置即可，D操作也是如此，其实就是三种情况，然后我们暴力模拟一遍即可求出答案

解法一：完全暴力模拟

时空复杂度分析：

首先其实我们并没有引入太多的额外空间，唯一的空间就是我们的这个字符串的大小，也就是说我们的空间复杂度就是 O($nn$) 的，然后我们的时间复杂度呢，其实我们是完全暴力模拟的，就只有一层for循环，我们的时间复杂度就非常好计算也是O($nn$) 的

C++代码实现

#include <iostream>
#include <cstring>
using namespace std;

void solve()
{
    int n;
    string s;
    while (cin >> n >> s) {  // 输入我们的字符串
        int pos = 1, head = 1, end = min(4, n);
        // 首先 pos 是我们当前光标的一个位置
        // head 是我们当前列表的头部是哪一首歌曲
        // end 是我们当前列表尾部是哪一首歌曲，而且我们要特判一下，一页最多四首歌曲，但是我们的歌曲总量可能会少于四首
        for (auto& it : s) { 
            if (it == 'U') {  // 如果是向上操作
                pos--; // 先把我们的光标 - 1
                if (pos < 1) { // 如果我们光标比我们第一首歌曲的位置都要小，说明我们要跳到最后一页的位置上面
                    pos = n; // 我们更新一下我们的pos的位置 
                    head = max(1, n - 4 + 1); // 这里我们更新一下列表的头部
                    end = n; // 更新一下列表的尾部
                } else { // 如果我们的pos没有小于1
                    if (pos < head) { // 如果我们当前的这个位置要是比我们当前的列表头还要小，说明要更新列表了
                        head = pos; // 更新我们的列表头部
                        end--; // 更新我们的列表尾部
                    }
                }
            } else { // 如果我们是向下的一个操作
                pos++; // 先把我们光标的位置向下移动
                if (pos > n) { // 如果我们光标的位置比我们最后一首歌曲的位置还要大
                    pos = 1; // 我们更新我们当前的光标的位置
                    head = 1; // 那么我们的头部就是 1
                    end = min(4, n); // 此时依然如此我们要判断，我们的列表的尾部是否比4小
                } else { // 如果我们没有比最后一个还要大
                    if (pos > end) {  // 如果我们当前的光标比我们列表的最后一个还要大
                        head++; // 我们要把我们的首部更新
                        end = pos; // 我们要把我们的尾部也要更新
                    }
                }
            }
        }
        for (int i = head; i <= end; i++)
            cout << i << " ";
        cout << "\n";
        cout << pos << "\n";
        // 输出我们的列表和我们的当前的光标位置在哪里
    }
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
    return 0;
}

图解算法

解法二：解法一的优化

不一样的部分

因为我们其实发现，代码一就是完全考虑的模拟，但是有一个边界情况，就是如果我们的歌曲的数量没有我们的列表的四多的话，我们会进行很多复杂的思考过程，那么我们不如，把这个单独的问题拿出来判断，直接判断它最后是向上还是向下移动即可，但是我们还要考虑这么一个问题，就是我们最后的移动可能是要大于了n的，所以我们要最后再取一个模，这个题目给的数据很小的，如果你一直D不取模，也可以过，但是我们要追求的是考虑全面无BUG，所以我们要加上

时空复杂度分析

空间复杂度是：$O(n)O(n)$ 的，因为我们没有引用什么多余的变量，我们只是用到了一个长度为n的一个字符串，时间复杂度也是 $O(n)O(n)$ 的，因为我们其实只有一个for循环，所以我们只需要跑一遍循环就可以

C++代码实现

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

void solve()
{
    string s;
    int n;
    while (cin >> n >> s) {
        if (n <= 4) { // 我们进行一个分类讨论，如果它小于等于4，那么我们不论怎么移动，列表其实就是固定的
            int pos = 1;
            for (auto& it : s) {
                if (it == 'U')
                    pos--;
                else
                    pos++;
            }
            // 这里我们直接判断他是向上走了还是向下走了，这样我们可以少考虑一些列表变换的问题
            for (int i = 1; i <= n; i++)
                cout << i << " ";
            cout << "\n";
            pos >= 0 ? cout << pos % n << "\n" : cout << (n + pos + 1) % n << "\n"; // 这里有一点要注意的就是我们有可能最后的位置超过了我们的n，我们要取一个模，变到n的这个范围内
            // 输出列表以及位置
        } else {
            int pos = 1, head = 1, end = 4;
            // 首先 pos 是我们当前光标的一个位置
            // head 是我们当前列表的头部是哪一首歌曲
            // end 是我们当前列表尾部是哪一首歌曲，而且我们要特判一下，一页最多四首歌曲，但是我们的歌曲总量可能会少于四首
            for (auto& it : s) {
                if (it == 'U') { // 如果是向上操作
                    pos--; // 先把我们的光标 - 1
                    if (pos < 1) { // 如果我们光标比我们第一首歌曲的位置都要小，说明我们要跳到最后一页的位置上面
                        pos = n; // 我们更新一下我们的pos的位置
                        head = n - 4 + 1; // 这里我们更新一下列表的头部
                        end = n; // 更新一下列表的尾部
                    } else { // 如果我们的pos没有小于1
                        if (pos < head) { // 如果我们当前的这个位置要是比我们当前的列表头还要小，说明要更新列表了
                            head = pos; // 更新我们的列表头部
                            end--; // 更新我们的列表尾部
                        }
                    }
                } else { // 如果我们是向下的一个操作
                    pos++; // 先把我们光标的位置向下移动
                    if (pos > n) { // 如果我们光标的位置比我们最后一首歌曲的位置还要大
                        pos = 1; // 我们更新我们当前的光标的位置
                        head = 1; // 那么我们的头部就是 1
                        end = 4; // 此时依然如此我们要判断，我们的列表的尾部是否比4小
                    } else { // 如果我们没有比最后一个还要大
                        if (pos > end) { // 如果我们当前的光标比我们列表的最后一个还要大
                            head++; // 我们要把我们的首部更新
                            end = pos; // 我们要把我们的尾部也要更新
                        }
                    }
                }
            }
            for (int i = head; i <= end; i++)
                cout << i << " ";
            cout << "\n";
            cout << pos << "\n";
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
    return 0;
}