Atcoder Regular Contest 138

以前的号没了，新号一场上绿

一些仅供参考的图表

A - Larger Score

第一题挂了3次

Method

注意到一些明显的性质：

  • 问题=把a1...ka_{1...k}中的任意一个数换为一个比它大的ak+1...na_{k+1...n}的最小代价
  • 交换aia_i和aja_j需要∣i−j∣\mid i-j \mid次
  • 如果不存在ak+1,k+1,...,n＞min⁡(a1,a2,..ak)a_{k+1,k+1,...,n}＞\min(a_1,a_2,..a_k)则答案不存在，输出-1

于是，我们可以用pair数组存a[k+1,n]a[k+1,n]的值和位置，再以数值为关键字排序

此时可以O(n−k)O(n-k)从后往前遍历出每个数和比它大的数最早出现的位置，设这个答案为pos1,pos2,...,posn−kpos_1,pos_2,...,pos_{n-k}

遍历11~kk，对于每个aia_i可以O(logn)O(log n)二分出第一个比它大的数值，再去pospos数组中查询答案

时间复杂度为O(n+nlogn+n+nlogn)→O(nlogn)O(n+nlogn+n+nlogn) \rightarrow O(nlogn) 是可以AC的

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
/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#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 fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 4e5 + 10;

// bool st;
int n, k;
int a[N];
pii b[N];
int pos[N];
int mi = INF;
bool f = false;
// bool en;

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (i > k)
        {
            b[i - k] = {a[i], i};
            if (a[i] > mi)
            {
                f = true;
            }
        }
        else
            mi = min(mi, a[i]);
    }
    if (!f)
    {
        cout << "-1" << endl;
        return 0;
    }
    sort(b + 1, b + n - k + 1);
    int res = INF;
    pos[n - k + 1] = INF;
    for (int i = n - k; i >= 1; i--)
    {
        pos[i] = pos[i + 1];
        pos[i] = min(pos[i], b[i].sec);
    }
    for (int i = 1; i <= k; i++)
    {
        int l = 1, r = n - k + 1;
        while (l < r)
        {
            int mid = (l + r) >> 1;
            if (b[mid].fir > a[i])
                r = mid;
            else
                l = mid + 1;
        }
        res = min(res, pos[r] - i);
    }
    cout << res << endl;
    return 0;
}
一道不错的A题

B - 01 Generation

Method

个人觉得比A题简单

考虑倒推，检查是否可以从结果推回空串。可以贪心，当可以从尾部删的时候，优先从尾部删，否则翻转并删掉开头的数。如果当前的状态下队首为00且队尾为11则不可能

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: B - 01 Generation
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2022 Spring（AtCoder Regular Contest 138）
// URL: https://atcoder.jp/contests/arc138/tasks/arc138_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// 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 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 fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

// bool st;
int n;
int a[N];
deque<int> q;
// bool en;

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        q.pb(a[i]);
    }
    int f = 0;
    int cnt = 0;
    while (!q.empty())
    {
        cnt++;
        while (!q.empty() && ((!q.back() && (!(f & 1))) || (q.back() && (f & 1))))
        {
            q.pop_back();
        }
        if (!q.empty() && ((q.front() == 0 && f % 2 == 0) || (q.front() == 1 && f % 2 == 1)))
        {
            q.pop_front();
            f++;
        }
        if (cnt > n)//也可以在大于n次操作后输出No，跑的会稍微慢一点
        {
            No;
            return 0;
        }
    }
    Yes;
    return 0;
}

C - Rotate and Play Game

C题比D题难一点qwq

Method

有趣的性质：

  • Snuke一定可以拿到最大的n2\frac{n}{2}个数

  • 感性理解一下，上述条件成立

证明

参考官方题解

wtcl，不会证明qwq

然后就可以做到O(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
// Problem: C - Rotate and Play Game
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2022 Spring（AtCoder Regular Contest 138）
// URL: https://atcoder.jp/contests/arc138/tasks/arc138_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// 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 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 fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

// bool st;
int n;
pii a[N];
int pos[N];
// bool en;

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].fir;
        a[i].sec = i;
    }
    sort(a + 1, a + n + 1);//排序取前n/2大
    int res = 0;
    for (int i = n / 2 + 1; i <= n; i++)
    {
        pos[i - n / 2] = a[i].sec;
        res += a[i].fir;
    }
    sort(pos + 1, pos + n / 2 + 1);
    int ans = 0;
    int l = 0;
    for (int i = 1; i <= n / 2; i++)//查答案
    {
        if ((pos[i] - ans) / 2 < i - l)
        {
            ans = pos[i];
            l = i;
        }
    }
    cout << ans << ' ' << res << endl;
    return 0;
}

D.Differ by K bits

Method

观察下列性质:

  • 当kk是22的倍数时，不存在解法
  • 当n=kn=k且k≠1k\neq 1，不存在解法
  • 否则一定存在一种方案

可以通过xorxor枚举出一个数的下一个，在用一个map记录

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
// Problem: D - Differ by K bits
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2022 Spring（AtCoder Regular Contest 138）
// URL: https://atcoder.jp/contests/arc138/tasks/arc138_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// 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 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 fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 1e5 + 10;

// bool st;
int n, k;
map<int, bool> mp;
vector<int> t;
// bool en;

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n >> k;
    if (k % 2 == 0 || (k != 1 && n == k))
    {
        No;
        return 0;
    }
    int st = 0;
    Yes;
    cout << st << ' ';
    mp[0] = true;
    for (int i = 1; i < (1 << n); i++)
        if (__builtin_popcount(i) == k)
            t.pb(i);
    for (int i = 1; i < (1 << n); i++)
    {
        for (auto x : t)
        {
            if (mp[st ^ x])
                continue;
            st = st ^ x;
            mp[st] = true;
            cout << st << ' ';
            break;
        }
    }
    return 0;
}

后面就不会了qwq