CF1179A-Valeriy-and-Deque题解

找规律题目

洛谷地址

题目描述

Recently, on the course of algorithms and data structures, Valeriy learned how to use a deque. He built a deque filled with n n elements. The $i$-th element is $a_i​ ( i = 1, 2, \ldots, n )$. He gradually takes the first two leftmost elements from the deque (let's call them $A$ and $B$ , respectively), and then does the following: if $A > B$ , he writes $A$ to the beginning and writes $B$ to the end of the deque, otherwise, he writes to the beginning $B$ , and $A$ writes to the end of the deque. We call this sequence of actions an operation.

For example, if deque was $[2, 3, 4, 5, 1]$ , on the operation he will write $B=3$ to the beginning and $A=2$ to the end, so he will get $[3, 4, 5, 1, 2]$ .

The teacher of the course, seeing Valeriy, who was passionate about his work, approached him and gave him $q$ queries. Each query consists of the singular number $m_j (j = 1, 2, \ldots, q)$ . It is required for each query to answer which two elements he will pull out on the $m_j$ -th operation.

Note that the queries are independent and for each query the numbers $A$ and $B$ should be printed in the order in which they will be pulled out of the deque.

Deque is a data structure representing a list of elements where insertion of new elements or deletion of existing elements can be made from both sides.

题解

这题其实是一个毒瘤找规律题目,暴力会TLE,不开long long会见祖宗

对于这样一组数据:

$1, 2, 3, 4, 5$

继续操作下去之后,

它变成了这样:

$23451$

$34512$

$45123$

$51234$

$52341$

$53412$

$54123$

$51234$

$52341$

有没有发现出现循环节了???

$51234$

$52341$

$53412$

$54123$

这就是重复的部分

我们继续尝试亿组数据,可以发现一个显然的条件:

最大的数总是出现循环节的开头,且循环节的长度为$n-1$

我们就可以利用这个来做题了

我们先找出它的循环节,对于他询问的不在循环节内的,我们暴力跑一遍就可以,在循环节内的,我们对询问的步数取个模,之后在循环节中查找便可.

详见注释

CODE

#include <deque>
#include <iostream>
#include <vector>
#define endl '\n'
#define LL long long

std::vector<LL> ans;
std::deque<LL> q;
LL n, QAQ, maxx, m, pos;
LL vis[400005][2], cnt; //记录非循环节的队列信息

inline LL max (LL a, LL b)
{
    return a > b ? a : b;
}

int main ()
{
    std::ios::sync_with_stdio (false); //读入小优化
    std::cin.tie (0);
    std::cout.tie (0);

    std::cin >> n >> QAQ;
    for (register LL i = 0, x; i < n; i++)
    {
        std::cin >> x;
        maxx = max (maxx, x);  //找到最大的元素
        q.push_back (x);  //加入双端队列
    }
    for (register LL i = 1, a, b, done = 1; true; i++)
    {
        a = q.front (), q.pop_front ();  //取出元素
        b = q.front (), q.pop_front ();
        vis[++cnt][0] = a;  //记录
        vis[cnt][1] = b;
        if (a == maxx)   //出现循环节
        {
            if (done)   //我们记录循环节首次出现的操作步数
            {
                pos = i;
                done = 0;
                ans.push_back (b);  //加入存储循环节的数组
            }
            else if (ans[0] == b and i - pos >= n - 1) //当它的元素与之前重复且以循环n-1遍
            {
                m = i - pos; //记录循环节的长度
                break;
            }
            else
                ans.push_back (b);  
        }
        if (a > b)
        {
            q.push_front (a);
            q.push_back (b);
        }
        else
        {
            q.push_back (a);
            q.push_front (b);
        }
    }

    for (register LL i = 1, cmd; i <= QAQ; i++)  //输出答案
    {
        std::cin >> cmd;
        if (cmd <= pos) //在循环节内
            std::cout << vis[cmd][0] << " " << vis[cmd][1] << endl;
        else //不在循环节内
            std::cout << maxx << " " << ans[(cmd - pos) % m] << endl;
    }
    return 0;
}

THE END