首页 > ACM题库 > HDU-杭电 > HDU 2987-Cyclic antimonotonic permutations [解题报告]HOJ
2014
02-24

HDU 2987-Cyclic antimonotonic permutations [解题报告]HOJ

Cyclic antimonotonic permutations

问题描述 :

A permutation is a sequence of integers which contains each integer from 1 to n exactly once. In this problem we are looking for permutations with special properties:

1. Antimonotonic: for each consecutive 3 values pi-1, pi, pi+1 (1 < i < n), pi should either be the smallest or the biggest of the three values.
2. Cyclic: The permutation should consist of only one cycle, that is, when we use pi as a pointer from i to pi, it should be possible to start at position 1 and follow the pointers and reach all n positions before returning to position 1.

输入:

The input file contains several test cases. Each test case consists of a line containing an integer n, (3 ≤ n ≤ 106), the number of integers in the permutation. Input is terminated by n=0.

输出:

The input file contains several test cases. Each test case consists of a line containing an integer n, (3 ≤ n ≤ 106), the number of integers in the permutation. Input is terminated by n=0.

样例输入:

3
5
10
0

样例输出:

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

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1e6+10;
int a[maxn];
int main()
{
    int n;
    while(scanf("%d",&n)&&n)
    {
	a[1]=3;
	a[2]=1;
	for(int i=3;i<=n-2;i+=2)
	    a[i]=i+2;
	if(n&1)
	{
	    a[n]=n-1;
	    for(int i=n-1;i>2;i-=2)
		a[i]=i-2;
	}
	else
	{
	    a[n-1]=n;
	    a[n]=n-2;
	    for(int i=n-2;i>2;i-=2)
		a[i]=i-2;
	}
	printf("%d",a[1]);
	for(int i=2;i<=n;i++)
	    printf(" %d",a[i]);
	printf("\n");
    }
    return 0;
}

  1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  2. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  3. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。

  4. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  5. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  6. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法