比赛链接：传送门

Summary

终于又上蓝了，这一场的题目都比较简单，最后两题还是有可能A掉的，不过比赛的时候基本没看最后两题。感觉第三题比第二题简单一点点。。。

Problems

B Primal Sport

先N\sqrt 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
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 1e6 + 10;

int A[Maxn], Max[Maxn];
int N, Prime[Maxn], Vis[Maxn];

int main()
{
#ifdef hk_cnyali
    freopen("B.in", "r", stdin);
    freopen("B.out", "w", stdout);
#endif
    scanf("%d", &N);
    int Cnt = 0;
    Vis[1] = 1;
    for (int i = 2; i <= N; ++i)
    {
        if (!Vis[i]) Prime[++Cnt] = i;
        for (int j = 1; j <= Cnt && i * Prime[j] <= N; ++j)
        {
            Vis[i * Prime[j]] = 1;
            if (!(i % Prime[j])) break;
        }
    }

    int tot = 0;
    for (int i = 1; i <= Cnt; ++i)
        if (!(N % Prime[i])) A[++tot] = Prime[i];
    for (int i = 1; i <= Cnt; ++i)
        for (int j = 1; j * Prime[i] <= N; ++j)
            Max[j * Prime[i]] = Prime[i];
    int Ans = N;

    for (int i = 1; i <= tot; ++i)
    {
        int now = N - A[i] + 1;
        if (now < 3) continue;
        if (Vis[now]) Ans = min(Ans, now);
        for (int j = max(now, A[i] + 1); j <= N; ++j)
        {
            int x = j - Max[j] + 1;
            if (x <= Max[j]) x = Max[j] + 1;
            if (x <= j && x >= 3)
                Ans = min(Ans, x);
        }
    }
    cout<<Ans<<endl;
    return 0;
}

C Producing Snow

用优先队列优化一下暴力就可以了

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
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int Maxn = 1e5 + 10;

int N, M;

int A[Maxn], B[Maxn];

priority_queue <int, vector <int>, greater<int> > Q;
//priority_queue <int> Q;

main()
{
#ifdef hk_cnyali
    freopen("C.in", "r", stdin);
    freopen("C.out", "w", stdout);
#endif
    scanf("%lld", &N);
    int sum = 0;
    for (int i = 1; i <= N; ++i) scanf("%lld", &A[i]);
    for (int i = 1; i <= N; ++i) scanf("%lld", &B[i]);
    for (int i = 1; i <= N; ++i)
    {
        int Ans = 0;
        Q.push(A[i] + sum);
        sum += B[i];
        while (!Q.empty())
        {
            int x = Q.top();
            //cout<<x<<endl;
            if (x >= sum)
                break;
            Ans += (x - sum + B[i]);
            Q.pop();
        }
        Ans += Q.size() * B[i];
        cout<<Ans<<" ";
    }
    return 0;
}

D Perfect Security

考虑贪心，建一棵01Trie，存在和当前位相同的就往下走，否则走另一边，更新答案

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

using namespace std;

const int Maxn = 3e5 + 10;

int N;
int A[Maxn];

namespace Trie
{
    int son[Maxn * 30][2], Cnt[Maxn * 30];
    int root = 1, cnt = 1;

    inline void insert (int x)
    {
        int now = root;
        Cnt[root] ++;
        for (int i = 29; i >= 0; --i)
        {
            int p = (x >> i) & 1;
            if (!son[now][p]) son[now][p] = ++cnt;
            now = son[now][p];
            Cnt[now]++;
        }
    }

    inline int query (int x)
    {
        int now = root;
        int ans = 0;
        for (int i = 29; i >= 0; --i)
        {
            int p = (x >> i) & 1;
            if (!son[now][p] || !Cnt[son[now][p]]) ans += (1 << i), now = son[now][p ^ 1];
            else now = son[now][p], Cnt[now]--;
        }
        return ans;
    }
}

int main()
{
#ifdef hk_cnyali
    freopen("D.in", "r", stdin);
    freopen("D.out", "w", stdout);
#endif
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
    for (int i = 1; i <= N; ++i)
    {
        int x;
        scanf("%d", &x);
        Trie :: insert(x);
    }
    for (int i = 1; i <= N; ++i)
        printf("%d ", Trie :: query (A[i]));
    return 0;
}