Codeforces Round #768 (Div. 2)

By xiaruize

A. Min Max Swap

Method

对于1≤i≤n1\leq i\leq n,若ai>bia_i>b_i,则swap(ai,bi)swap(a_i,b_i)

###Code

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
// Problem: A. Min Max Swap
// Contest: Codeforces - Codeforces Round #768 (Div. 2)
// URL: https://codeforces.com/contest/1631/problem/0
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// TestType: single
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define ull unsigned long long

#define MOD 1000000007

#define ALL(a) (a).begin(), (a).end()

#define pb push_back

#define mk make_pair

#define pii pair<int, int>

#define pis pair<int, string>

#define sec second

#define ll long long

#define fir first

#define sz(a) int((a).size())

#define double long double

#define INF 0x3f3f3f3f

#define debug(c, x) cerr << c << ':' << x << endl;

const int N = 1e4 + 10;

// bool st;
int t;
int n;
int a[N], b[N];
int mx, smx;
// bool en;

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    for (int i = 1; i <= n; i++)
        if (a[i] < b[i])
            swap(a[i], b[i]);
    int mxa = -INF, mxb = -INF;
    for (int i = 1; i <= n; i++)
    {
        mxa = max(mxa, a[i]);
        mxb = max(mxb, b[i]);
    }
    cout << mxa * mxb << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

B. Fun with Even Subarrays

Method

∵\because数组的最后一位不可能被别的数代替 ∴\therefore最后一定统一为ana_n

暴力从后往前处理即可

复杂度O(n)/O(log n)

Code

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
// Problem: F. Flipping Range
// Contest: Codeforces - Codeforces Round #768 (Div. 2)
// URL: https://codeforces.com/contest/1631/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// TestType: single
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define MOD 1000000007
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define ll long long
#define fir first
#define sz(a) int((a).size())
#define double long double
#define INF 0x3f3f3f3f
#define debug(c, x) cerr << c << ':' << x << endl;
const int N = 2e5 + 10;

// bool st;
int t;
int n;
int a[N];
// bool en;

void solve()
{
    int ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int num = a[n];
    for (int i = n; i >= 1; i--)
    {
        while (a[i] == num)
            i--;
        if (i < 1)
            break;
        ans++;
        i = n - 2 * (n - i) + 1;
        cerr << t << ' ' << i << endl;
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

C. And Matching

Method

定义f(x)f(x)为x在二进制下取反的结果

构造:

1.k=0k=0

​ 让(x,f(x))一组

 ∵x and f(x)=0\ \because x \ and\ f(x)=0

 ∴∑i=1n/2ai and bi=0=k\ \therefore \sum^{n/2}_{i=1}{a_i \ and \ b_i}=0=k

2.0<k<n−10< k <n-1

​ 除了0,k,f(x),n−10,k,f(x),n-1,其它数按11操作

​ ∵0 and f(k)=0k and (n−1)=k∴∑i=1n/2ai and bi=k\because 0\ and\ f(k)=0\\ k\ and \ (n-1)=k \\ \therefore \sum^{n/2}_{i=1}{a_i\ and \ b_i}=k

  1. k=n−1k=n-1

    ∵(n−1) and (n−2)=n−2(n−3) and 1=10 and 2=0\because (n-1)\ and \ (n-2)=n-2\\ (n-3)\ and \ 1=1 \\0\ and \ 2=0

    ∴∑i=1n/2ai and bi=n−1\therefore \sum^{n/2}_{i=1}{a_i\ and \ b_i}=n-1

Code

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
// Problem: C. And Matching
// Contest: Codeforces - Codeforces Round #768 (Div. 2)
// URL: https://codeforces.com/contest/1631/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// TestType: single
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define MOD 1000000007
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define ll long long
#define fir first
#define sz(a) int((a).size())
#define double long double
#define INF 0x3f3f3f3f
#define debug(c, x) cerr << c << ':' << x << endl;
const int N = 1e5 + 10;

// bool st;
int t;
int n, k;
int a[N];
// bool en;

void solve()
{
    cin >> n >> k;
    int m = n;
    if (k == 3 && n == 4)
    {
        cout << "-1" << endl;
        return;
    }
    for (int i = 0; i < n; i++)
        a[i] = i;
    while (n)
    {
        if (k >= n / 2)
        {
            swap(a[n / 2], a[0]);
            k -= n / 2;
        }
        n /= 2;
    }
    for (int i = 0; i < m / 2; i++)
        cout << a[i] << ' ' << a[m - i - 1] << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

​