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

A - Game of Division #

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

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

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
#undef LOCAL_DEBUG
5
#ifdef LOCAL_DEBUG
6
#include "debug.h"
7
#else
8
#define debug(...) (void)0
9
#define debug_array(arr, len) (void)0
10
#define debug_container(container) (void)0
11
#endif
12

13
typedef unsigned long long ull;
14
typedef long long ll;
15
typedef pair<int,int> P;
16
const int maxn=100;
17

18
int n;
19
int a[maxn+5],k;
20

21
void solve(void){
22
    vector<int> cnt(maxn+5,0);
23
    vector<int> pos(maxn+5,0);
24
  cin>>n>>k;
25
    for (int i=1;i<=n;i++){
26
        cin>>a[i];
27
        a[i]%=k;
28
        debug(a[i]);
29
        cnt[a[i]]++;
30
        pos[a[i]]=i;
31
    }
32

33
  for (int i=0;i<=maxn;i++){
34
        debug(i,cnt[i]);
35
        if (cnt[i]==1){
36
            cout<<"YES"<<endl;
37
            cout<<pos[i]<<endl;
38
            return ;
39
        }
40
    }
41
    cout<<"NO"<<endl;
42
}
43

44
int main(){
45
  std::ios::sync_with_stdio(false);
46
  std::cin.tie(nullptr);
47
  std::cout.tie(nullptr);
48
  int t=1;
49
  cin>>t;
50
  while (t--)
51
    solve();
52
//    cout<<(solve()?"YES":"NO")<<endl;
53
  return 0;
54
}

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

4
//#undef LOCAL_DEBUG
5
#ifdef LOCAL_DEBUG
6
#include "debug.h"
7
#else
8
#define debug(...) (void)0
9
#define debug_array(arr, len) (void)0
10
#define debug_container(container) (void)0
11
#endif
12

13
typedef unsigned long long ull;
14
typedef long long ll;
15
typedef pair<int,int> P;
16
const int maxn=1e5;
17

18
int n;
19

20
set<P> ans;
21
void prepare(){
22
    ans.insert(P{1,1});
23
    ans.insert(P{4,2});
24
    ans.insert(P{10,3});
25
    int pos=10,ret=3;
26
    while (true){
27
        pos=(pos+1)*2;
28
        ret++;
29
        ans.insert(P{pos,ret});
30
        if (pos>maxn)
31
            break;
32
    }
33
}
34

35
void solve(void){
36
  cin>>n;
37
    if (n==1)
38
        cout<<1<<endl;
39
    else if (n<=4)
40
        cout<<2<<endl;
41
    else{
42
        auto it=ans.lower_bound(P{n,0});
43
        cout<<it->second<<endl;
44
    }
45
}
46

47
int main(){
48
  std::ios::sync_with_stdio(false);
49
  std::cin.tie(nullptr);
50
  std::cout.tie(nullptr);
51
  int t=1;
52
  cin>>t;
53
    prepare();
54
  while (t--)
55
    solve();
56
//    cout<<(solve()?"YES":"NO")<<endl;
57
  return 0;
58
}

C - Ordered Permutations #

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

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

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

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

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
#undef LOCAL_DEBUG
5
#ifdef LOCAL_DEBUG
6
#include "debug.h"
7
#else
8
#define debug(...) (void)0
9
#define debug_array(arr, len) (void)0
10
#define debug_container(container) (void)0
11
#endif
12

13
typedef unsigned long long ull;
14
typedef long long ll;
15
typedef pair<int,int> P;
16
const int maxn=2e5;
17

18
ll n,k;
19
ll ans[maxn+5];
20

21
bool check_low(ll &k,ll i){  // k<=2^(n-i-1)
22
    ll l=log2(k);
23
    if (l<n-i-1){
24
        return true;
25
    }
26
    else{
27
        ll tmp=(1ll<<(n-i-1));
28
        if (k>tmp){
29
            k-=tmp;
30
            return false;
31
        }
32
        else
33
            return true;
34
    }
35
}
36

37
void solve(void){
38
  cin>>n>>k;
39
    if (n<41){
40
        if ((1LL<<(n-1ll))<k){
41
            cout<<-1<<endl;
42
            return ;
43
        }
44
    }
45
    int l=1,r=n;
46
    ll i=1;
47
    while (l<r){
48
        if (check_low(k,i)){
49
            ans[l]=i;
50
            l++;
51
        }
52
        else{
53
            ans[r]=i;
54
            r--;
55
        }
56
        i++;
57
    }
58
    ans[l]=n;
59
    for (int i=1;i<=n;i++)
60
        cout<<ans[i]<<' ';
61
  cout<<endl;
62
}
63

64
int main(){
65
  std::ios::sync_with_stdio(false);
66
  std::cin.tie(nullptr);
67
  std::cout.tie(nullptr);
68
  int t=1;
69
  cin>>t;
70
  while (t--)
71
    solve();
72
//    cout<<(solve()?"YES":"NO")<<endl;
73
  return 0;
74
}

D - Non Prime Tree #

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

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

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

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
#undef LOCAL_DEBUG
5
#ifdef LOCAL_DEBUG
6
#include "debug.h"
7
#else
8
#define debug(...) (void)0
9
#define debug_array(arr, len) (void)0
10
#define debug_container(container) (void)0
11
#endif
12

13
typedef unsigned long long ull;
14
typedef long long ll;
15
typedef pair<int,int> P;
16
const int maxn=2e5;
17

18
int n;
19
vector<int> G[maxn+5];
20
queue<int> que[2];
21
int op;
22
int ans[maxn+5];
23

24
void clear(){
25
    for (int i=1;i<=n;i++){
26
        G[i].clear();
27
        ans[i]=0;
28
    }
29
    op=0;
30
    while (!que[0].empty())
31
        que[0].pop();
32
    while (!que[1].empty())
33
        que[1].pop();
34
}
35

36
bool flag[maxn*2+5];
37
#define isprime(x) (flag[x]==false)
38
void prepare(){
39
    int lim=maxn*2;
40
    flag[1]=true;
41
    for (int i=2;i<=lim;i++)
42
        if (isprime(i)){
43
            for (int j=2;i*j<=lim;j++)
44
                flag[i*j]=true;
45
        }
46
}
47

48
bool dfs(int u,int fa){
49
    if (fa){
50
        ans[u]=-1;
51
        while (true){
52
            if (que[op].empty())
53
                op^1;
54
            else if (!isprime(abs(que[op].front()-ans[fa])))
55
                break;
56
            que[op^1].push(que[op].front());
57
            que[op].pop();
58
        }
59
        ans[u]=que[op].front();
60
        que[op].pop();
61
    }
62
    else{
63
        ans[u]=1;
64
    }
65
    for (int v: G[u])
66
        if (v!=fa){
67
            if (dfs(v,u)==false)
68
                return false;
69
        }
70
    return true;
71
}
72

73
void solve(void){
74
  cin>>n;
75
    clear();
76
    for (int i=1,u,v;i<n;i++){
77
        cin>>u>>v;
78
        G[u].push_back(v);
79
        G[v].push_back(u);
80
    }
81
    for (int i=2;i<=2*n;i++){
82
        que[0].push(i);
83
    }
84
    if (dfs(1,0)){
85
        for (int i=1;i<=n;i++)
86
            cout<<ans[i]<<' ';
87
        cout<<endl;
88
    }
89
    else
90
        cout<<-1<<endl;
91
}
92

93
int main(){
94
  std::ios::sync_with_stdio(false);
95
  std::cin.tie(nullptr);
96
  std::cout.tie(nullptr);
97
  int t=1;
98
  cin>>t;
99
    prepare();
100
  while (t--)
101
    solve();
102
//    cout<<(solve()?"YES":"NO")<<endl;
103
  return 0;
104
}

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

A - Game of Division#

B - Paint a Strip#

C - Ordered Permutations#

D - Non Prime Tree#

A - Game of Division #

B - Paint a Strip #

C - Ordered Permutations #

D - Non Prime Tree #