Codeforces 构造专题_codeforces 构造题

D.Omkar and the Meaning of Life

求出 $p[n]$ 后，要分大于和小于的；具体见代码：

• 代码

void solve()
{
    int n;cin>>n;
    vector<int> p(n+1,0);
    int cnt = 0;
    for(int i = 2;i <= n;i ++){
        cout<<"? ";
        for(int j = 1;j < n;j ++){
            cout<<1<<" ";
        }
        cout<<i<<endl;
        cout.flush();
        int k;cin>>k;
        if(k !=0 ) cnt ++;
    }   
    p[n] = n - cnt;
    for(int d = 1;d < p[n];d ++){
        cout<<"? ";
        for(int j = 1;j < n;j ++){
            cout<<d+1<<" ";
        }
        cout<<1<<endl;
        cout.flush();
        int k;cin>>k;
        p[k] = p[n] - d;
    }
    for(int d = 1;d + p[n] <= n;d ++){
        cout<<"? ";
        for(int j = 1;j < n;j ++){
            cout<<1<<" ";
        }
        cout<<d+1<<endl;
        cout.flush();
        int k;cin>>k;
        p[k] = p[n] + d;
    }
    
    cout<<"! ";
    for(int i = 1;i <= n;i ++){
        cout<<p[i]<<" ";
    }
    cout<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

C2. k-LCM hardversion

• 题意
  
  这个其实和简单版是由联系的，难度其实就降低了。
  如果 $k==3$ 的话，很容易构造出来；如果 $n\%4==0$，n/2,n/4,n/4；否则的话，2,(n-2)/2,(n-2)/2；
  那么 $k>3$ 时，先用三个数按照上述方式构造出来 $n-(k-3)$，剩下全填 $1$就好了。
• 代码

int n,k;cin>>n>>k;
    n -= (k-3);
    if(n & 1){
        cout<<1<<" "<<(n-1)/2<<" "<<(n-1)/2<<" ";
    }
    else{
        if(n % 4 == 0){
            cout<<n/2<<" "<<n/4<<" "<<n/4<<" ";;
        }
        else{
            cout<<2<<" "<<(n-2)/2<<" "<<(n-2)/2<<" ";
        };
    }
    for(int i = 1;i <= k-3;i ++){
        cout<<"1 ";
    }
    cout<<endl;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

B. Different Rules

• 题意
  共有 $n$ 个人，两轮比赛，总排名是两轮名次加起来；现在给你一个人的第一轮名次和第二轮名次，问你两轮过后他的最好名次和最坏名次分别是多少可能？
• 思路
  这位大佬讲得好呀
• 代码

void solve()
{
    ll n;cin>>n;
    int tx,ty;cin>>tx>>ty;
    // if()
    ll huai = tx + ty - 1;
    ll hao;
    if( tx + ty < n+1) hao = 1;
    else hao = tx + ty - n + 1;
    cout<<min(n,hao)<<" "<<min(n,huai)<<endl;
}
1
2
3
4
5
6
7
8
9
10
11

D Merge Sort

• 题意

让你求一个长度为 $n$ 的全排列，然后这个全排列使用归并排序调用 $merge$ 函数的次数正好为 $k$。

• 思路

首先k一定是奇数
因为第一次单独的调用merge(0,n)
接下来分成两个子区间,若子区间有序调用0次,无序调用2次
可见 $k=1+2+2+2+2+2+2\dots +2$
知道这个就好办了,直接模拟 $merge$ 函数
若当前k还存在,那就交换 $a[mid-1]$ 和 $a[mid]$ 使得当前区间无序
但是这样左右两区间内仍然有序, $k-=2$

• 代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int n,k,a[maxn];
void merge_sort(int l,int r)
{
	if(r-l<=1)	return;
	if(k)
	{
		int mid= l+r>>1; k-=2;
		swap(a[mid-1],a[mid]);
		merge_sort(l,mid);
		merge_sort(mid,r);
	}
}

int main()
{
	cin >> n >> k;
	k--;
	if( k&1 )	{
        cout<<-1<<endl;
    }
	else
	{
		for(int i=0;i<n;i++)	a[i]=i+1;
		merge_sort(0,n);
		if( k )	{
            cout<<-1<<endl;
        }
        else
		for(int i=0;i<n;i++)	cout<<a[i]<<" ";
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

C. Slava and tanks

• 题意

• 思路

还是很简单的其实。
就奇偶奇跑一遍就可以了。

• 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6+10;
int ans[N];

int n,k;
int cnt = 1;
void merge(int l,int r)
{
    if(!k) {
        int tx = r;
        for(int i = l;i <= r;i ++){
            ans[i] = tx;tx--;
        }
        return ;
    }
    int mid = (l+r)>>1;
    k -= 2;
    merge(l,mid);
    merge(mid,r);
}
void coutn(int l,int r){
    if(r-l<=1) return;
    cnt +=2;
    int mid = l+r>>1;
    coutn(l,mid);
    coutn(mid,r);
}
int main()
{
    int n;cin>>n;

    if(n == 2){
        cout<<3<<endl;
        cout<<"2 1 2"<<endl;return 0;
    }
    if(!(n&1)){
        cout<<(3*(n/2))<<endl;
        for(int i = 1;i <= n;i += 2){
            cout<<i<<" ";
        }
        for(int i = 2;i <= n;i += 2){
            cout<<i<<" ";
        }
        for(int i = 1;i <= n;i += 2){
            cout<<i<<" ";
        }
        puts("");
    }
    else{
        cout<<(3*(n/2)+1)<<endl;
        for(int i = 2;i <= n;i += 2){
            cout<<i<<" ";
        }
        for(int i = 1;i <= n;i += 2){
            cout<<i<<" ";
        }
        for(int i = 2;i <= n;i += 2){
            cout<<i<<" ";
        }
        puts("");
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65