牛客练习赛1-C-圈圈题解

迷南。 2022-12-28 12:45 141阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入描述
     *  输出描述
     *  输入
     *  输出
     *  备注
 *  算法分析
 *  解题代码
 *  代码巧妙点
 *   *  一、预处理
     *  二、在加的过程中要多次寻找

--------------------

链接：https://ac.nowcoder.com/acm/contest/2/C  
来源：牛客网

# 题目描述 #

shy有一个队列`a[1], a[2],…,a[n]`。现在我们不停地把头上的元素放到尾巴上。在这过程中我们会得到n个不同的队列，每个队列都是`a[k],a[k+1],…,a[n],a[1],…,a[k-1]`的形式。在这些队列中，我们可以找到字典序最小的。

shy无聊的时候会给队列的每个元素加一玩。但是为了使得游戏不这么无聊，shy加一以后会给每个元素`模m`，这样子字典序最小的序列就会变了，生活就变得有趣。

很显然这样子`加m次以后，序列会变成原来的样子`。所以现在shy想知道，在他没有加一前，加一时，加二时,….,加m-1时字典序最小的序列的第k（和上面的k没有关系）个元素分别是几。

## 输入描述 ##

> 第一行三个整数**n，m，k**表示序列长度，取模的数和要求的序列的第几个元素。  
> 接下来一行**n**个整数表示初始序列。

## 输出描述 ##

> **m**个整数表示答案。

## 输入 ##

5 6 3
    1 2 1 2 3

## 输出 ##

1
    2
    3
    5
    5
    0

## 备注 ##

> 对于30%的数据，1≤n,m≤100；  
> 对于100%的数据，1≤n,m≤50000, 1≤k≤n, 0≤a\[i\]<m；

# 算法分析 #

这道题第一眼看上去，就动不了手，想了半天，看了题解才明了

这道题目的关键点在于：**只有某一个数字出现了对于m的溢出时，序列才会发生改变**

**但怎么对初始序列和改变以后的序列进行重新组合排序呢？**

这里就用到了\*\*`二分`\*\*，二分去寻找LCP（最长公共前缀），并且比较LCP后的那个数字，如果数字更小，那么这个数字就应该放在队首。

这个解题思路成立的关键点在于\*\*`不停地把头上的元素放到尾巴上`\*\* ，因此可以把序列看作一个循环队列。

# 解题代码 #

#include <iostream>
    #include <vector>
    using namespace std;
    #define int long long
    
    const int N=20;
    const int base=1e9+7;
    int n,m,k,l,r,ans,mid,a[N],ha[N],p[N];
    vector<int>v[N];
    
    int bj(int x,int y,int add)
    {
        
        l = 0;r = n;
    
        while(l<r)
        {
        
            mid = (l + r + 1) / 2;
            
            //以x为起点，和以y为起点的长度为mid的子序列，是否相等
            if(ha[x + mid - 1] - ha[x - 1] * p[mid] == ha[y + mid - 1] - ha[y - 1] * p[mid])
                l = mid;    //相等就把可能想等的子序列的长度扩大。
            else
                r = mid - 1;    //不等就把可能的想等的子序列的长度缩小
        }
    
        //l实际上是 以x为起点，和以y为起点相等的最大长度
        //如果l==n，就意味着x和y实际上是相同的位置，得到的长度为n的序列
        if(l == n)
            return x;
        
        //因为以x为起点，和以y为起点的序列相同的，那么就比较这两个串后的那个不同的数字，
        //将小的字符的下标返回，作为序列的排头元素
        //（以x为起点和以y为起点的长度为l的串是等价的，因此可以将这之后的更小的字典的数字替换到第一个位置）
        if((a[x + l] + add) % m <= (a[y + l] + add) % m)
            return x;
        else{
        
            //否则返回y
            return y;
        }
    }
    
    signed main()
    {
        
        scanf("%lld%lld%lld",&n,&m,&k);
        for(int i = 1; i <= n; i++)
        {
        
            scanf("%lld",&a[i]);
            v[m-a[i]].push_back(i); //记录的是加i次后会改变的数字集
            a[i + n] = a[i];	//多存一轮在末尾，类似于尾首相连
        }
        
        //一维字符串hash
        for(int i = 1; i <= n + n; i++)
            ha[i] = ha[i - 1] * base + a[i];
        p[0] = 1;
        for(int i = 1; i <= n + n; i++)
            p[i] = p[i-1] * base;
        //一维字符串hash
        
        //反复寻找可以作为排头的数字的下标
        ans = 1;
        for(int i = 2; i <= n; i++)
            ans = bj(ans, i, 0);
        
        printf("%lld\n",a[ans + k - 1]);
        
        for(int i = 1; i < m; i++)
        {
        
            //如果加第i次时，有数字会发生对m的溢出，那么这个序列就会发生变化
            //那么就需要重新计算序列的排序顺序
            //如果没有，那么就是原排序顺序，则还是那个位置
            if(v[i].size())
            {
        
                //否则就以这个发生改变的数字为序列的排头元素
                ans = v[i][0];
                //用这个排头元素去寻找 后面有可能作为排头的元素 是否比当前这个排头形成的序列字典序更小
              	//返回作为排头元素的元素下标
                for(int j = 1; j < v[i].size(); j++)
                    ans = bj(ans, v[i][j], i);
            }
            printf("%lld\n",(a[ans + k - 1] + i) % m);
        }
        
        return 0;
    }

# 代码巧妙点 #

## 一、预处理 ##

for(int i = 1; i <= n; i++)
    {
        
        scanf("%lld",&a[i]);
        v[m-a[i]].push_back(i); //记录的是加i次后会改变的数字集
        a[i + n] = a[i];	//多存一轮在末尾，类似于尾首相连
    }

1、vector数组v在输入时就预先存入在加i时，会发生对m溢出的数字

2、在a数组中多存一轮序列，就不用复杂的去考虑头尾移动的复杂情况（因为可以将头元素移动到尾部）

## 二、在加的过程中要多次寻找 ##

if(v[i].size())
        {
        
            //否则就以这个发生改变的数字为序列的排头元素
            ans = v[i][0];
            //用这个排头元素去寻找 后面有可能作为排头的元素 是否比当前这个排头形成的序列字典序更小
          	//返回作为排头元素的元素下标
            for(int j = 1; j < v[i].size(); j++)
                ans = bj(ans, v[i][j], i);
        }

因为，一次加1的操作可能导致多个数同时发生对m溢出。

所以，要在此次 发生对m溢出的数 中，通过比较去寻找真正的排头元素