玩游戏(game)

玩游戏(game)

题目背景

x 正在玩游戏。

题目描述

x 有一个长度为 \(n\) 的数列 \(a\),还有一个长度为 \(n\) 的数列 \(x\),并且数列 \(x\) 恰好为 \(1\sim n\) 的一个排列。

第 \(0\) 轮时,数列 \(a_i=i,i\in [1,n]\)。

接下来的每一轮,x 都会进行一次操作。将上一轮中 \(a_i\) 替换为 \(a_{x_i}\)。

同时,x 还要求恰好在第 \(m\) 轮时,数列 \(a_i=i,i\in [1,n]\),即与第 \(0\) 轮状态相同,并且不存在 \(t(1\le t<m)\),使得在第 \(t\) 轮时,数列 \(a_i=i,i\in [1,n]\)。

现在 x 要求你构造一组合法的数列 \(x\),若没有合法的数列 \(x\),则输出 \(-1\)。

由于出题人懒得写 spj,所以 x 要你输出字典序最小的数列 \(x\)。

输入格式

一行,两个正整数 \(n,m\)。

输出格式

一行,\(n\) 个数,即满足要求的字典序最小的数列 \(x\)。

样例

样例输入 1

8 7

样例输出 1

1 3 4 5 6 7 8 2

样例输入 2

8 8

样例输出 2

2 3 4 5 6 7 8 1

样例输入 3

8 9

样例输出 3

-1

数据范围与提示

对于 \(20\%\) 的数据,\(1\le n\le 10^3,1\le m\le 10^7\)

对于另外 \(10\%\) 的数据,\(m=1\)。

对于 \(100\%\) 的数据,\(1\le n\le 3\times 10^6,1\le m\le 10^{14}\)

solution

题解

发现如果一个数若干轮后又回到自己,那么这个数以及过程中的那些数可以构成一个大小为 \(b_i\) 的环。

所以这道题就变成了构造满足任意长度,和为 \(n\),最小公倍数为 \(m\) 的数列 \(b\),并使其字典序最小。

即要满足:

  1. \(1\le k,b_i\le n\)

  2. \(b_1+b_2+b_3+\cdots+b_k=n\)

  3. \(\operatorname{lcm}(b_1,b_2,b_3,\cdots,b_k)=m\)

  4. 满足 \(1,2,3\) 的前提下,字典序最小。

因此可以将 \(m\) 分解质因数,相同底数的乘到一起,让这些数作为数列 \(b\),如果不够 \(n\),可以补 \(1\)。

周期越大的越往后放,轮到该周期时,把 \(t\) 放到 \(t+b_i-1\) 之后,可以证明,此时字典序最小。

std

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,p,q=1,cnt;
long long m,ans[20],sum;
int main()
{
    scanf("%d%lld",&n,&m);
    for(long long i=2;i*i<=m;i++)
    {
        if(m%i==0) p++,ans[p]=1;
        else continue;
        while(m%i==0)
        {
            ans[p]*=i;
            m/=i;
        }
        sum+=ans[p];
    }
    if(m!=1)
    {
        ans[++p]=m;
        sum+=ans[p];
    }
    if(n<sum)
    {
        printf("-1\n");
        return 0;
    }
    sort(ans+1,ans+p+1);
    for(int i=1;i<=n;i++)
    {
        if(i<=n-sum)
        {
            printf("%d ",i);
            continue;
        }
        cnt++;
        if(cnt==ans[q])
        {
            cnt=0;
            printf("%lld ",i-ans[q]+1);
            q++;
        }
        else printf("%d ",i+1);
    }
    return 0;
}

后话

吐槽

思维简单,代码好写,没有毒瘤的小清新题目。

本题部分 idea 来源于翻牌游戏,本来以为还算中等,没想到被爆切QAQ。

看来还是我太菜了。

总结

\(100\times 5+0\times 1=500\)

平均得分:\(83.33\)

得分越来越高了,我越来越菜了。QAQ

上一篇:CF1375F Integer Game


下一篇:Unity scene & game 相机管理学习