专栏首页海天一树Codeforces Round #463 C.Permutation Cycle

Codeforces Round #463 C.Permutation Cycle

一、题目

http://codeforces.com/contest/932/problem/C

二、分析

(一)何谓Permutation Cycle

以例1中的6 5 8 3 4 1 9 2 7 第一个数是6,以6为位置,则第六个数是1,以1为位置,第一个数是6,以6为位置,第六个数是1……,这样6和1就构成了一个圈子。f(1) = 6, f(6) = 1,最短的周期是2

第二个数是5,以5为位置,第五个数是4,以4为位置,第四个数是3,以3为位置,第三个数是8,以8为位置,第八个数是2,以2为位置,第2个数是5,以5为位置,第五个数是4……这样5,4,3,8,2也构成了一个圈子。f(5) = 4, f(4) = 3, f(3) = 8, f(8) = 2, f(2) = 5,最短的周期是5。

(二)例子分析

对于例1中的6 5 8 3 4 1 9 2 7 p[1] = 6, p[2] = 5, p[3] = 8, p[4] = 3, p[5] = 4, p[6] = 1, p[7] = 9, p[8] = 2, p[9] = 7 f(1, j) = f(6, j-1) = p[6] = 1,此时j - 1 = 1 ==> j = 2 ==> g(1) = 2 f(2, j) = f(5, j-1) = f(4, j-2) = f(3, j-3) = f(8, j-4) = p[8] = 2,此时j - 4 = 1 ==> j = 5 ==> g(2) = 5 f(3, j) = f(8, j-1) = f(2, j-2) = f(5, j-3) = f(4, j-4) = p[4] = 3,此时j - 4 = 1 ==> j = 5 ==> g(3) = 5 …… 所以,g(1) = g(6) = g(7) = g(9) =2, g(2) = g(3) = g(4) = g(5) = g(8) = 5

对于例2中的1,2,3 p[1] = 1, p[2] = 2, p[3] = 3 f(1, j) = p[1] = 1 ==> j = 1 ==> g(1) = 1 f(2, j) = p[2] = 2 ==> j = 1 ==> g(2) = 1 f(3, j) = p[3] = 3 ==> j = 1 ==> g(3) = 1 所以,g(1) = g(2) = g(3) = 1

(三)思路

对于本题来说,实际上就是求 Ax + By = N,x >= 0, y >= 0 对于例1,A = 2, B = 5, N = 9,Ax + By = N ==> 2x + 5y = 9 ==> x = 2, y = 1 也就是说,9个数里,有两组2个数,使得g(i) = 2。这两组数分别为2, 1和4, 3 有一组5个数,使得g(i) = 5,这组数为6,7,8,9,5

再举一例,A = 3, B = 6, N = 9 3x + 6y = 9 ==> x = 1, y = 1 也就是说,9个数里,有一组3个数,使得g(i) = 3。这组数为2,3,1 另有一组6个数,使得g(i) = 6。这组数为5,6,7,8,9,4

再举一例,A = 4, B = 6, N = 9 4x + 6y = 9,无解。

三、代码

#include<cstdio>
int main()
{
    int n, a, b;
    int cnta, cntb;
    int flag = false;
    scanf("%d %d %d", &n, &a, &b);
    for (int i = 0; i * a <= n; i++)
    {
        int t = n - a * i;
        if (t % b == 0)
        {
            cnta = i;
            cntb = t / b;
            flag = true;
            break;
        }
    }
    int num = 1;
    int lastNum = num;
    if(!flag)
    {
         printf("-1\n");
    }
    else
    {
        for(int i = 1;i <= cnta;i++)
        {
            for(int k = 1;k < a;k++)
            {
                printf("%d ",++num);
            }
            printf("%d ",lastNum);
            num++;
            lastNum = num;
        }
        for(int i = 1;i <= cntb;i++)
        {
            for(int k = 1;k < b;k++)
            {
                printf("%d ",++num);
            }
            printf("%d ",lastNum);
            num++;
            lastNum = num;
        }
    }
    return 0;
}

运行结果:

9 2 5
2 1 4 3 6 7 8 9 5

本文分享自微信公众号 - 海天一树(gh_de7b45c40e8b),作者:海天一树

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-02-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序员必须掌握的8大排序算法

    分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基数排序)...

    海天一树
  • 2018年海淀区青少年程序设计思维挑战活动普及组详细答案

    海天一树
  • AtCoder Beginner Contest 100 完整解题报告

    https://beta.atcoder.jp/contests/abc100/tasks

    海天一树
  • Hackerrank GCD Product(莫比乌斯反演)

    attack
  • 1466: [蓝桥杯2019初赛]等差数列

    数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列,只记得其中N 个整数。现在给出这N 个整数,小明想知道包含这N 个整数的最短的等差数...

    可爱见见
  • 【USACO 2.1】The Castle

    饶文津
  • BZOJ3083: 遥远的国度(树链剖分)

    以下图片来自(https://blog.csdn.net/lcomyn/article/details/45718295)

    attack
  • 海量数据处理之bitmap

    本文将讲述Bit-Map算法的相关原理,Bit-Map算法的一些利用场景,例如BitMap解决海量数据寻找重复、判断个别元素是否在海量数据当中等问题.最后说说B...

    Spark学习技巧
  • BZOJ3262: 陌上花开(cdq分治)

    第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。

    attack
  • hdu1014

    @坤的

扫码关注云+社区

领取腾讯云代金券