【CF1017C】The Phone Number(构造)

题意:要求构造一个1-n的排列,使得它的LIS+LDS最小

n<=1e5

思路:一个百度之星时候从LYY处听来的结论:1-n随机排列的LIS期望是根号级别的

考虑将LIS与LDS都构造成根号级别

分块,块内增(减),块间减(增)

 #include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef vector<int> VI;
#define fi first
#define se second
#define MP make_pair
#define N 110000
#define MOD 1000000007
#define eps 1e-8
#define pi acos(-1) int a[N]; int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} void swap(int &x,int &y)
{
int t=x;x=y;y=t;
} int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
int n;
scanf("%d",&n);
int block=sqrt(n);
int m=n/block;
int now=n;
int s=;
int st=n-block+;
for(int i=;i<=m;i++)
{
for(int j=;j<=block;j++) a[++s]=st++;
st=st-*block;
}
if(n%block)
{
st=;
for(int i=;i<=n%block;i++) a[++s]=st++;
} for(int i=;i<=n;i++) printf("%d ",a[i]);
return ;
}
上一篇:Python3 数字Number(六)


下一篇:BZOJ 3000: Big Number (数学)