题解归档 - cf2233B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2233B
• 本地来源：problems/cf2233B/idea.md
• 题目链接：https://codeforces.com/contest/2233/problem/B
• 原始标题：cf2233B - Different Distances

思路

cf2233B - Different Distances

pattern:
construct four permutation blocks

construction:
Output four blocks of length n:

1. 1,2,...,n
2. 1,2,...,n
3. n,1,2,...,n-1
4. 1,2,...,n

proof:
For x<n, its positions are x, n+x, 2n+x+1, 3n+x, so the consecutive
distances are n, n+1, and n-1.

For x=n, its positions are n, 2n, 2n+1, 4n, so the consecutive
distances are n, 1, and 2n-1.

In both cases the three distances are pairwise distinct for n>=2.

check:
A local validator enumerates positions of every value and checks the counts and
three distinct gaps for all 2<=n<=200.

代码

来源：problems/cf2233B/solution.cpp

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        vector<int> ans;
        for(int i=1;i<=n;i++) ans.push_back(i);
        for(int i=1;i<=n;i++) ans.push_back(i);
        ans.push_back(n);
        for(int i=1;i<n;i++) ans.push_back(i);
        for(int i=1;i<=n;i++) ans.push_back(i);
        for(int i=0;i<(int)ans.size();i++){
            if(i) cout<<" ";
            cout<<ans[i];
        }
        cout<<"\n";
    }
    return 0;
}