Codeforces Round 1090 (Div.4)题解

比赛链接：https://codeforces.com/contest/2218

每道题都会给出py和cpp两个版本

cpp版本是我赛时写的

A. The 67th Integer Problem#

我们只需要输出67即可

1
t = int(input())
2
for _ in range(t):
3
    print(67)

cpp

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define ld long double
5
#define debug(x) cerr << #x << ": " << x << '\n';
6
const int INF = 0x3f3f3f3f3f3f3f3f;
7
const int N=1e9;
8
void solve(){
9
    int x;cin>>x;
10
    cout<<67<<"\n";
11
}
12
signed main(){
13
    std::ios_base::sync_with_stdio(false);
14
    std::cin.tie(nullptr);
15
    int t = 1;
16
    cin>>t;
17
    while(t--){
18
        solve();
19
    }return 0;
20
}

B. The 67th 6-7 Integer Problem#

我们只需要先对数组排序再依次取前6个数的相反数即可

1
t = int(input())
2
for _ in range(t):
3
    a = list(map(int,input().split()))
4
    a.sort()
5
    ans = 0
6
    for i in range(6):
7
        ans -= a[i]
8
    print(ans + a[-1])

cpp

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define ld long double
5
#define debug(x) cerr << #x << ": " << x << '\n';
6
const int INF = 0x3f3f3f3f3f3f3f3f;
7

8
void solve(){
9
    vector<int> a(8);
10
    for(int i=1;i<=7;i++) cin>>a[i];
11
    sort(a.begin()+1,a.end());
12
    int sum=0;
13
    for(int i=1;i<=6;i++) sum-=a[i];
14
    cout<<sum+a[7]<<"\n";
15
}
16
signed main(){
17
    std::ios_base::sync_with_stdio(false);
18
    std::cin.tie(nullptr);
19
    int t = 1;
20
    cin>>t;
21
    while(t--){
22
        solve();
23
    }return 0;
24
}

C. The 67th Permutation Problem#

一道简单的构造题，通过观察不难发现，我们只需要把从小到大连续的两个大数放到一块，第三个数放从1开始的小数，这样可以取到最大，例如6 5 1 4 3 2

1
t = int(input())
2
for _ in range(t):
3
    n = int(input())
4
    cur = 1
5
    mx = n*3
6
    for i in range(n):
7
        print(f"{mx} {mx-1} {cur}",end=" ")
8
        cur += 1
9
        mx -= 2
10
    print()

cpp

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define ld long double
5
#define debug(x) cerr << #x << ": " << x << '\n';
6
const int INF = 0x3f3f3f3f3f3f3f3f;
7

8
void solve(){
9
    int n;cin>>n;
10
    int cur=1,mx=n*3;
11
    for(int i=1;i<=n;i++){
12
        cout<<mx<<" "<<mx-1<<" "<<cur<<" ";
13
        mx-=2;
14
        cur++;
15
    }
16
    cout<<"\n";
17
}
18
signed main(){
19
    std::ios_base::sync_with_stdio(false);
20
    std::cin.tie(nullptr);
21
    int t = 1;
22
    cin>>t;
23
    while(t--){
24
        solve();
25
    }return 0;
26
}

D. The 67th OEIS Problem#

本题的上限为1e18，经过观察，可行的方式为筛选出前1e4个质数，前一个质数和后一个质数相乘即可

第10001个质数大约是104729，不会超出上限。

1
import sys
2
input = sys.stdin.readline
3
N = 200010
4
heshu = [False] * N
5
zhishu = []
6
def sieve():
7
    for i in range(2,N):
8
        if not heshu[i]:
9
            zhishu.append(i)
10
            if i * i < N:
11
                for j in range(i * i, N , i):
12
                    heshu[j] = True
13
sieve()
14
t = int(input())
15
for _ in range(t):
16
    ans = []
17
    n = int(input())
18
    for i in range(n):
19
        ans.append(zhishu[i]*zhishu[i+1])
20
    print(*ans)

cpp

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int N=1e7+10;
5
int zhishu[N];
6
int heshu[N];
7
int cnt;
8
void solve(){
9
    ll n;cin>>n;
10
    for(int i=1;i<=n;i++) cout<<(ll)zhishu[i]*zhishu[i+1]<<" ";
11
}
12
int main(){
13
    for(ll i=2;i<=N;i++){
14
        if(!heshu[i]){
15
            cnt++;
16
            zhishu[cnt]=i;
17
            for(ll j=i*i;j<=N;j+=i){
18
                heshu[j]=1;
19
            }
20
        }
21
    }
22
    std::ios_base::sync_with_stdio(false);
23
    std::cin.tie(nullptr);
24
    int t = 1;
25
    cin>>t;
26
    while(t--){
27
        solve();
28
    }return 0;
29
}
30
//Onloglogn

E. The 67th XOR Problem#

首先知道a ^ a = 0 ,0 ^ a = a,我们根据题意模拟两个样例，会发现，在不断异或的情况下，前n-2个数会抵消，最后只剩下两个数异或，所以答案为数组中两个数异或最大值，时间复杂度为O(n*n),对于本题完全足够

1
import sys
2
input = sys.stdin.readline
3
t = int(input())
4
for _ in range(t):
5
    n = int(input())
6
    a = list(map(int,input().split()))
7
    ans = 0
8
    for i in range(n):
9
        for j in range(i+1,n):
10
            ans = max(ans,a[i]^a[j])
11
    print(ans)

cpp

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define ld long double
5
#define debug(x) cerr << #x << ": " << x << '\n';
6
const int INF = 0x3f3f3f3f3f3f3f3f;
7

8
void solve(){
9
    int n;cin>>n;
10
    vector<int> a(n+1);
11
    for(int i=1;i<=n;i++) cin>>a[i];
12
    int ans=0;
13
    for(int i=1;i<=n;i++){
14
        for(int j=i+1;j<=n;j++){
15
            ans=max(ans,a[i]^a[j]);
16
        }
17
    }
18
    cout<<ans<<"\n";
19
}
20
signed main(){
21
    std::ios_base::sync_with_stdio(false);
22
    std::cin.tie(nullptr);
23
    int t = 1;
24
    cin>>t;
25
    while(t--){
26
        solve();
27
    }return 0;
28
}

F. The 67th Tree Problem#

本题是一道构造题，我们通过观察，最简单的构造方式就是只挂一个点或者两个点，首先根节点会贡献一个奇数或者偶数节点，这个由总数x+y决定，先减去这个贡献，单个点与根节点相连，会贡献一个奇数节点，两个点与根结构相连会贡献一个奇数节点和一个偶数节点，所以偶数<=奇数节点，并且减去根贡献后，奇数偶数节点数需要大于0，不满足则输出NO，满足按以上方式构造即可

1
import sys
2
input = sys.stdin.readline
3
t = int(input())
4
for _ in range(t):
5
    x,y = map(int,input().split())
6
    sum = x + y
7
    if sum&1:
8
        y -= 1
9
    else:
10
        x -= 1
11
    if x < 0 or y < 0 or x > y:
12
        print("NO")
13
        continue
14
    print("YES")
15
    cur = 2
16
    for i in range(x):
17
        print(f"{1} {cur}")
18
        print(f"{cur} {cur+1}")
19
        cur += 2
20
    while cur <= sum:
21
        print(f"{1} {cur}")
22
        cur += 1

cpp

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define ld long double
5
#define debug(x) cerr << #x << ": " << x << '\n';
6
const int INF = 0x3f3f3f3f3f3f3f3f;
7

8
void solve(){
9
    int x,y;cin>>x>>y;
10
    int sum=x+y;
11
    if((x+y)&1) y--;
12
    else x--;
13
    if(x<0||y<0||x>y){
14
        cout<<"NO\n";
15
        return;
16
    }
17
    int cur=2;
18
    cout<<"YES\n";
19
    for(int i=1;i<=x;i++){
20
        cout<<1<<" "<<cur<<"\n";
21
        cout<<cur<<" "<<cur+1<<"\n";
22
        cur+=2;
23
    }
24

25
    while(cur<=sum){
26
        cout<<1<<" "<<cur<<"\n";
27
        cur++;
28
    }
29
}
30
signed main(){
31
    std::ios_base::sync_with_stdio(false);
32
    std::cin.tie(nullptr);
33
    int t = 1;
34
    cin>>t;
35
    while(t--){
36
        solve();
37
    }return 0;
38
}

G. The 67th Iteration of “Counting is Fun”#

预处理前缀和

cpp

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

4
#define int long long
5
#define ld long double
6
#define debug(x) cerr << #x << ": " << x << '\n';
7

8
const int INF = 0x3f3f3f3f3f3f3f3f;
9
const int mod = 676767677;
10

11
void solve() {
12
    int n, m;
13
    cin>>n>>m;
14

15
    vector<int> b(n + 2, INF);
16
    vector<int> c(n + 1, 0);
17
    for (int i = 1; i <= n; i++) {
18
        cin >> b[i];
19
        c[b[i]]++;
20
    }
21

22
    vector<int> s(n + 1, 0);
23
    s[0] = c[0];
24
    for (int i = 1; i <= n; i++) {
25
        s[i] = s[i - 1] + c[i];
26
    }
27

28
    int ans = 1;
29
    for (int i = 1; i <= n; i++) {
30
        if (b[i] == 0) continue;
31

32
        int mn = min(b[i - 1], b[i + 1]);
33
        if (mn >= b[i]) {
34
            cout << 0 << "\n";
35
            return;
36
        }
37

38
        if (mn == b[i] - 1) {
39
            ans = (ans * s[b[i] - 1]) % mod;
40
        } else {
41
            ans = (ans * (s[b[i] - 1] - s[b[i] - 2])) % mod;
42
        }
43
    }
44
    cout << (ans + mod) % mod << "\n";
45
}
46

47
signed main() {
48
    std::ios_base::sync_with_stdio(false);
49
    std::cin.tie(nullptr);
50

51
    int t = 1;
52
    cin >> t;
53
    while (t--) {
54
        solve();
55
    }
56
    return 0;
57
}

pandac的blog