摘要:本题属于构造算法,虽然简单但对思维提升有一定帮助
题目原地址如下:https://codeforces.com/problemset/problem/1713/C
题目截图如下:
关键词:构造算法,动态规划,*1200
简要翻译:给定一个序列a[0,1,2,.....,n-1],求其排列A[a1,a2,...an-1]使得对任意ai满足ai+i为完全平方数。
作为构造题,我们需要考察其内在结构,对n=18的情况,我们会发现从8至17的数字只需让其排列倒转即可实现完全平方的要求。也即我们可以根据完全平方数将原序列划分为多个区域,对每个区域进行考察即可。
代码如下:
1 #include <iostream> 2 using namespace std; 3 int n,input; 4 int edge;//记录边界,当需要改变完全平方数时就需要变更边界,即所得数不可大于该边界 5 int rem[10000],a[100005]; 6 int main(){ 7 for (int i=0;i<=1000;i++){//获取完全平方数 8 rem[i]=i*i; 9 } 10 cin>>n; 11 while(n){ 12 cin>>input; 13 int i=0; 14 edge=input-1; 15 for (;rem[i]<=2*input-2;i++);//确定初始的完全平方数 16 i--; 17 for (int j=input-1;j>=0;j--){//从后向前遍历,便于更新边界 18 while (rem[i]-j>edge){//边界与完全平方数的更新 19 edge=j; 20 i--; 21 } 22 if (rem[i]-j<=edge)//倒转操作 23 a[j]=rem[i]-j; 24 } 25 for (int k=0;k<=input-1;k++) 26 cout<<a[k]<<" "; 27 cout<<"\n"; 28 n--; 29 } 30 return 0; 31 }
标签:平方,边界,int,Permutation,codeforces,edge,Build,rem,input From: https://www.cnblogs.com/johnsonstar/p/16630508.html