2015
05-24

Sub Sequence

Recently, YCC is studying sequence problems. And he is struggling with it!!!= =
For such an ACMer like you, it is commonly believed that you must know the Longest Increasing Subsequence problem. Now Let’s define some useful functions and symbols:
Let U(A) be the length of the longest increasing subsequence of the original sequence A;
Let D(A) be the length of the longest decreasing subsequence of the original sequence A;
Let H(A) be the maximum value of U(A) and D(A), that is H(A) = max{U(A), D(A)}.
H(A)!!! Ah… Zauber anzahl, ist es nicht?
Now YCC wants to study the attributes of all the permutations of integer numbers from 1 to N. He wants to get such permutation P having minimum H(P). If more than one permutation satisfies the condition, you should give the lexicographically smallest one.

The first line contains an integer T which indicates the number of test cases.
The following T lines each contain an integer N (1 ≤ N ≤ 100000).

The first line contains an integer T which indicates the number of test cases.
The following T lines each contain an integer N (1 ≤ N ≤ 100000).

3
1
2
3

1
1 2
1 3 2

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
using namespace std;

#define MAXN 1005
bool vis[MAXN];
int a[MAXN], ant[MAXN];
int n;

int UU()
{
int dp[MAXN], ans = 1;
for(int i = 1; i <= n; i++) dp[i] = 1;
for(int i = 1; i <= n; i++)
{
int MAX = 0;
for(int j = i-1; j >= 1; j--)
{
if(a[i] > a[j] && dp[j] > MAX) MAX = dp[j];
}
dp[i] = MAX + 1;
if(dp[i] > ans) ans = dp[i];
}
return ans;
}

int DD()
{
int dp[MAXN], ans = 1;
for(int i = 1; i <= n; i++) dp[i] = 1;
for(int i = 1; i <= n; i++)
{
int MAX = 0;
for(int j = i-1; j >= 1; j--)
{
if(a[i] < a[j] && dp[j] > MAX) MAX = dp[j];
}
dp[i] = MAX + 1;
if(dp[i] > ans) ans = dp[i];
}
return ans;
}

int mmm = 99999;

void dfs(int x, int num)
{
//if(tar) return;
a[num] = x;
if(num == n)
{
int MAX = UU();
int MIN = DD();
//printf("MAX=%d MIN=%d\n", MAX, MIN);
int tp = max(MAX, MIN);
if(tp < mmm)
{
mmm = tp;
for(int i = 1; i <= n; i++)
{
ant[i] = a[i];
}
}
return ;
}
for(int i = 1; i <= n; i++)
{
if(vis[i]) continue;
vis[i] = true;
dfs(i, num+1);
vis[i] = false;
}
}

int main()
{
int i, j, t;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
/*memset(vis, false, sizeof(vis));
mmm = 99999;
for(i = 1; i <= n; i++)
{
vis[i] = true;
dfs(i, 1);
vis[i] = false;
}
for(i = 1; i <= n; i++)
{
printf("%d ", ant[i]);
}
printf("\n------------------\n");*/

if(n == 1) {printf("1\n");continue;}
if(n == 2) {printf("1 2\n");continue;}
if(n == 3) {printf("1 3 2\n"); continue;}
/*if(n == 4) {printf("2 1 4 3\n"); continue;}
if(n == 5) {printf("1 2 5 4 3\n"); continue;}
if(n == 6) {printf("1 3 2 6 5 4\n"); continue;}
if(n == 8) {printf("2 1 5 4 3 8 7 6\n"); continue;}
if(n%2 == 1)
{
printf("1");
for(i = 2; i <= (n+1)/2-3; i++)
{
printf(" %d", i);
}
printf(" %d %d %d", (n+1)/2, (n+1)/2-1, (n+1)/2-2);
for(i = n; i >= (n+1)/2+1; i--)
{
printf(" %d", i);
}
printf("\n");
}
else
{
printf("1");
for(i = 2; i <= n/2+1-4; i++)
{
printf(" %d", i);
}
printf(" %d %d %d %d", n/2+1, n/2, n/2-1, n/2-2);
for(i = n; i >= n/2+2; i--)
{
printf(" %d", i);
}
printf("\n");
}*/
int l, kuai, sheng, tp;
l = sqrt(n*1.0);
bool tar = true;
if(l == sqrt(n*1.0))
{
sheng = 0;
kuai = n / l;
tar = false;
///printf("goto L\n");
goto L;
}

if(l != sqrt(n*1.0)) l++;
kuai = n / l;
sheng = n - kuai*l;
if(sheng == 0 && l != sqrt(n*1.0))
{
sheng = l;
kuai--;
}
//tp = l - kuai;
//tp = min(tp, sheng)-1;

//printf("l=%d kuai=%d sheng=%d\n", l, kuai, sheng);

if(l - kuai >= 2)
{
printf("1");
for(i = sheng; i > 1; i--)
printf(" %d", i);
}
else
{
printf("%d", sheng);
for(i = sheng-1; i >= 1; i--)
printf(" %d", i);
}
/*for(i = 1; i <= tp; i++)
{
printf("%d ", i);
}
if(sheng-tp==0) goto L;
for(i = sheng; i > sheng-tp; i--)
{
printf("%d ", i);
}*/
L:
int sum = sheng;
for(i = 1; i <= kuai; i++)
{
for(j = 0; j < l; j++)
{
if(tar) printf(" ");
tar = true;
printf("%d", sum+l-j);
}
sum += l;
}
printf("\n");
}

return 0;
}

1. 学者有很多种，要看他想要表达什么、用心是什么。龙应台对大陆的喊话，从来不谈台湾存在的问题，从来不谈大陆媳妇、大陆学生在台湾的困境；讨论腐败，她怎么不批评陈水扁？宣扬民主，她怎么不为陆媳、陆生站台？打着文化旗号，行政客之实，鼓吹她自己的那一套的丑恶嘴脸，应