Codeforces Round 992 (Div. 2) solutions (A-D)

ACM
6.4k words

Codeforces Round 992 (Div. 2) solutions (A-D)

A - Game of Division

如果两个数的差值的绝对值能被 kk 整除，也就意味着这两个数对 kk 同余。

那就变成了求所有数中是否存在对 kk 同余只有自身的数了。

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
#include <bits/stdc++.h>
using namespace std;

#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#define debug_container(container) (void)0
#endif 

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=100;

int n;
int a[maxn+5],k;

void solve(void){
    vector<int> cnt(maxn+5,0);
    vector<int> pos(maxn+5,0);
	cin>>n>>k;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        a[i]%=k;
        debug(a[i]);
        cnt[a[i]]++;
        pos[a[i]]=i;
    }

	for (int i=0;i<=maxn;i++){
        debug(i,cnt[i]);
        if (cnt[i]==1){
            cout<<"YES"<<endl;
            cout<<pos[i]<<endl;
            return ;
        }
    }
    cout<<"NO"<<endl;
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int t=1;
	cin>>t;
	while (t--)
		solve();
//		cout<<(solve()?"YES":"NO")<<endl;
	return 0;
}

B - Paint a Strip

观察发现，我们从1开始向上以最快的速度扩展，首先我们要选两个数做操作1，然后把里面包裹的全部用操作2转成1，然后继续选数做操作1……最快的无疑是选1,4做操作1，然后把1~4都转成1，然后选10做操作1（现在1~10有5个1了，完全可以把1~10都变成1），然后再1~10做操作2，然后选22做操作1……

也就是说，我们在初始状态后，在1~p都是1的情况下，我们选(p+1)*2做操作1，然后把1~(p+1)*2都用操作2变1，是最优的。这个是指数增长的，预处理一下即可。

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
#include <bits/stdc++.h>
using namespace std;

//#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#define debug_container(container) (void)0
#endif 

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=1e5;

int n;

set<P> ans;
void prepare(){
    ans.insert(P{1,1});
    ans.insert(P{4,2});
    ans.insert(P{10,3});
    int pos=10,ret=3;
    while (true){
        pos=(pos+1)*2;
        ret++;
        ans.insert(P{pos,ret});
        if (pos>maxn)
            break;
    }
}

void solve(void){
	cin>>n;
    if (n==1)
        cout<<1<<endl;
    else if (n<=4)
        cout<<2<<endl;
    else{
        auto it=ans.lower_bound(P{n,0});
        cout<<it->second<<endl;
    }
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int t=1;
	cin>>t;
    prepare();
	while (t--)
		solve();
//		cout<<(solve()?"YES":"NO")<<endl;
	return 0;
}

C - Ordered Permutations

首先最大化得分的构造方式，肯定是让1尽可能处于最少的区间中，2处于第二少的区间中，以此类推……

那1必然只能是第一个或者最后一个，2必然是除了1以外的区间中的第一个或者最后一个，以此类推。

因此我们从1到n逐个放。1放第一个或者最后一个，有2种选择；2放除了1以外的区间的第一个或者最后一个，有2种选择……只有最后的nn，只有一种选择，因此我们能构造出来的序列个数最大是 2n−12^{n-1}，这样就能输出-1的情况了。

取字典序时，非常显然，假设总共个数是 L=2n−1L=2^{n-1}， 那1放第一个的序列们的字典序，必然小于1放最后一个的序列们的字典序。也就是说，1放开头和放最后两种，一定是字典序的前半部分和后半部分。那对于k，就不断判断它是在当前字典序的前半部分还是后半部分，即可确定当前数的位置，循环这样做就行。

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
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;

#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#define debug_container(container) (void)0
#endif 

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=2e5;

ll n,k;
ll ans[maxn+5];

bool check_low(ll &k,ll i){  // k<=2^(n-i-1)
    ll l=log2(k);
    if (l<n-i-1){
        return true;
    }
    else{
        ll tmp=(1ll<<(n-i-1));
        if (k>tmp){
            k-=tmp;
            return false;
        }
        else
            return true;
    }
}

void solve(void){
	cin>>n>>k;
    if (n<41){
        if ((1LL<<(n-1ll))<k){
            cout<<-1<<endl;
            return ;
        }
    }
    int l=1,r=n;
    ll i=1;
    while (l<r){
        if (check_low(k,i)){
            ans[l]=i;
            l++;
        }
        else{
            ans[r]=i;
            r--;
        }
        i++;
    }
    ans[l]=n;
    for (int i=1;i<=n;i++)
        cout<<ans[i]<<' ';
	cout<<endl;
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int t=1;
	cin>>t;
	while (t--)
		solve();
//		cout<<(solve()?"YES":"NO")<<endl;
	return 0;
}


D - Non Prime Tree

首先猜一手不存在不能构造出来的情况（不知道这个怎么证，但是看见 2*n 时候就猜应该是有神秘结论）。

这题看着是构造，其实不构造也行，理由是知道质数的个数对于大范围内的数其实是比较少的，随便取一个数较大概率不是质数，所以直接暴力枚举即可。1不是质数，所以一个合理的方法是一条链上直接1 2 3 4 地赋值。那树的其他情况怎么办？我们列一个集合，往里面塞1到2n，首先DFS遍历一下，因为DFS遍历的缘故，所以我们第一条链肯定是1 2 3 4 …地赋值，然后切换到其他分支的时候，就继续从集合中取下一个数，判断一下和父亲节点的差值是否是质数，不是就丢掉，继续取下一个数，直到取到可以的，那它继续向下遍历的时候，下一条链大概率也是逐个递增的。对于丢掉的数，我们换一个集合保存起来，这些数可能会呈现一种相对来说部分连续的段。当前集合空了，就换成前面的保存下来的丢弃的数的集合，也就是两个集合来回切换。

（这里集合我一开始用set，狠狠TLE唐完了，赛后才发现直接queue就能过）。

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>
using namespace std;

#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#define debug_container(container) (void)0
#endif 

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=2e5;

int n;
vector<int> G[maxn+5];
queue<int> que[2];
int op;
int ans[maxn+5];

void clear(){
    for (int i=1;i<=n;i++){
        G[i].clear();
        ans[i]=0;
    }
    op=0;
    while (!que[0].empty())
        que[0].pop();
    while (!que[1].empty())
        que[1].pop();
}

bool flag[maxn*2+5];
#define isprime(x) (flag[x]==false)
void prepare(){
    int lim=maxn*2;
    flag[1]=true; 
    for (int i=2;i<=lim;i++)
        if (isprime(i)){
            for (int j=2;i*j<=lim;j++)
                flag[i*j]=true;
        }
}

bool dfs(int u,int fa){
    if (fa){
        ans[u]=-1;
        while (true){
            if (que[op].empty())
                op^1;
            else if (!isprime(abs(que[op].front()-ans[fa])))
                break;
            que[op^1].push(que[op].front());
            que[op].pop();
        }
        ans[u]=que[op].front();
        que[op].pop();
    }
    else{
        ans[u]=1;
    }
    for (int v: G[u])
        if (v!=fa){
            if (dfs(v,u)==false)
                return false;
        }
    return true;
}

void solve(void){
	cin>>n;
    clear();
    for (int i=1,u,v;i<n;i++){
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i=2;i<=2*n;i++){
        que[0].push(i);
    }
    if (dfs(1,0)){
        for (int i=1;i<=n;i++)
            cout<<ans[i]<<' ';
        cout<<endl;
    }
    else
        cout<<-1<<endl;
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int t=1;
	cin>>t;
    prepare();
	while (t--)
		solve();
//		cout<<(solve()?"YES":"NO")<<endl;
	return 0;
}