• C. Build Permutation(构造,思维)


    原题链接

    A 00-indexed array aa of size nn is called good if for all valid indices ii (0≤i≤n−10≤i≤n−1), ai+iai+i is a perfect square††.

    Given an integer nn. Find a permutation‡‡ pp of [0,1,2,…,n−1][0,1,2,…,n−1] that is good or determine that no such permutation exists.

    †† An integer xx is said to be a perfect square if there exists an integer yy such that x=y2x=y2.

    ‡‡ An array bb is a permutation of an array aa if bb consists of the elements of aa in arbitrary order. For example, [4,2,3,4][4,2,3,4] is a permutation of [3,2,4,4][3,2,4,4] while [1,2,2][1,2,2] is not a permutation of [1,2,3][1,2,3].

    Input

    The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases.

    The only line of each test case contains a single integer nn (1≤n≤1051≤n≤105) — the length of the permutation pp.

    It is guaranteed that the sum of nn over all test cases does not exceed 105105.

    Output

    For each test case, output nn distinct integers p0,p1,…,pn−1p0,p1,…,pn−1 (0≤pi≤n−10≤pi≤n−1) — the permutation pp — if the answer exists, and −1−1 otherwise.

    Example

    input

    Copy

    3
    3
    4
    7
    

    output

    Copy

    1 0 2 
    0 3 2 1 
    1 0 2 6 5 4 3 
    

    Note

    In the first test case, we have n=3n=3. The array p=[1,0,2]p=[1,0,2] is good since 1+0=121+0=12, 0+1=120+1=12, and 2+2=222+2=22

    In the second test case, we have n=4n=4. The array p=[0,3,2,1]p=[0,3,2,1] is good since 0+0=020+0=02, 3+1=223+1=22, 2+2=222+2=22, and 1+3=221+3=22.

    思路:

    1,构造题,比赛时应该冷静的发现数据之间的关系

    2,从后往前看,eg。n==18    在8+17==25,所以从i=8开始,17 16 15 。。。。8     i从8到17,而a【i】从17到8,位置上加1,a【i】上减1,总体和仍未某个数的平方

    代码:

    1. #include
    2. using namespace std;
    3. #define int long long
    4. #define vec vector
    5. #define pi 3.1415926
    6. #define rep(i,l,r) for(int i=l;i<=r;++i)
    7. const int maxj=2e5+100,mod=998244353,inf=0x7f7f7f7f7f7f7f;
    8. int a[maxj],vis[maxj];
    9. void solve(){
    10. int n;cin>>n;
    11. for(int i=0;i//赋值
    12. a[i]=i;
    13. }
    14. vectorint,2>>ve;
    15. int las=n-1;
    16. while(las>=0){
    17. int s=ceil(sqrt((double)las));
    18. s=s*s;
    19. int pre=s-las;//找配套的数
    20. ve.push_back({pre,las});
    21. las=pre-1;//从前边接着找合适的距离
    22. }
    23. for(auto [p,q]:ve){
    24. for(int i=p;i<=q;++i){
    25. a[i]=p+q-i;//合的数仍为平方数
    26. }
    27. }
    28. for(int i=0;i
    29. cout<' ';
    30. }cout<<'\n';
    31. }
    32. signed main(){
    33. ios::sync_with_stdio(0);
    34. cin.tie(0);
    35. cout.tie(0);
    36. int t;
    37. t=1;
    38. cin>>t;
    39. while(t--)solve();
    40. return 0;
    41. }

  • 相关阅读:
    Vue3中runtime-dom的实现-详细步骤
    [答疑]校长出轨主任流程的业务建模
    112. 路径总和
    c++1237. 找出给定方程的正整数解,四种解法(二分+有限状态机)
    又一个新指标可以写,氧化平衡评分,源自膳食以及生活方式
    创新的Sui项目在CoinDCX的Unfold 2023黑客松中获奖
    理解Spring Bean的创建过程和生命周期
    【王道】计算机网络数据链路层(二)
    GPIO实验:ARM汇编代码实现LED灯亮灭控制
    Go 基本数据类型和 string 类型介绍
  • 原文地址:https://blog.csdn.net/m0_63054077/article/details/126206779