SnackDown2021 Online Qualifiers题解

发表于 更新于 分类于 阅读次数： 本文字数： 5.6k 阅读时长 ≈ 5 分钟

比赛链接

LUCKYNUM

输入三个数, 若有7输出YES，否则输出NO

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

int main() {
    int T, a, b, c;
    cin >> T;
    while (T--) {
        cin >> a >> b >> c;
        if (a == 7 || b == 7 || c == 7) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

TESTSERIES

输入5个数(只能是0/1/2), 1比2多输出INDIA，反之输出ENGLAND，一样多输出DRAW

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

int T;
int c[3];

int main() {
    cin >> T;
    while (T--) {
        c[0] = c[1] = c[2] = 0;
        for (int i = 0; i < 5; ++i) {
            int x; 
            cin >> x;
            c[x]++;
        }
        if (c[1] > c[2]) {
            cout << "INDIA" << endl;
        }
        else if (c[1] == c[2]) {
            cout << "DRAW" << endl;
        }
        else {
            cout << "ENGLAND" << endl;
        }
    }
    return 0;
}

MAXDISTKT

题意

给定一个数组B, 要求输出一个数组A, 使得\(A\%B\)（对应位置取模）之后的数组的不同整数最多

题解

贪心，首先将B从小到大排序，然后\(A\%B\)应该是从小到大递增的（排除那些不能产生新数的位置）

然后将A按原位置排序输出即可

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL gcd(LL a, LL b) {
    return b == 0 ? a : gcd(b, a % b);
}
const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
//-------------------end head--------------

const int N = 2e5 + 10;

int T, n;

struct node2 {
    int val, id;
    bool operator<(const node2 &rhs) const {
        return id < rhs.id;
    }
}a[N];

struct node {
    int val, id;
    bool operator<(const node &rhs) const {
        return val < rhs.val;
    }
}b[N];

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &b[i].val);
            b[i].id = i;
        }
        sort(b + 1, b + n + 1);
        int cnt = 0;
        for (int i = 1; i <= n; ++i) {
            if (b[i].val > cnt) {
                a[i].val = b[i].val + cnt;
                cnt++;
            }
            else {
                a[i].val = b[i].val;
            }
            a[i].id = b[i].id;
        }
        sort(a + 1, a + n + 1);
        for (int i = 1; i <= n; ++i) {
            printf("%d%c", a[i].val, " \n"[i == n]);
        }
    }
    return 0;
}

MINDIFF1

题意

有一个简单无向图，你需要给每个点分配一个数字，且分配的数字是1-n的排列

定义\(D_i\)为\(i\)的满足\(C_j<C_i\)的邻居数量

你需要最小化\(D\)的极差，输出这个极差和对应的分配方案

题解

首先可以看出D的最小值是0（数字1在的那个节点），于是问题就变成了最小化D的最大值

考虑如下分配方式：将当前最大的数字放在度数最小的节点上，然后删除这个节点

正确性并不会证......

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL gcd(LL a, LL b) {
    return b == 0 ? a : gcd(b, a % b);
}
const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
//-------------------end head--------------

const int N = 3e5 + 10;

int T, d[N], n, m, x, y, mx;
int a[N];

vector<int> G[N];

int main() {
    scanf("%d", &T);
    while (T--) {
        mx = 0;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) {
            d[i] = 0;
            a[i] = 0;
            G[i].clear();
        }
        for (int i = 1; i <= m; ++i) {
            scanf("%d%d", &x, &y);
            G[x].push_back(y);
            G[y].push_back(x);
            d[x]++;
            d[y]++;
        }
        set<pair<int, int>> pq;
        for (int i = 1; i <= n; ++i) {
            pq.insert(pair<int, int>(d[i], i));
        }
        while (!pq.empty()) {
            auto u = pq.begin();
            a[u->second] = pq.size();
            pq.erase(u);
            mx = max(mx, u->first);
            for (auto i: G[u->second]) {
                if (a[i] != 0) continue;
                pair<int, int> x(d[i], i);
                pq.erase(x);
                x.first--;
                d[i]--;
                pq.insert(x);
            }
        }
        printf("%d\n", mx);
        for (int i = 1; i <= n; ++i) {
            printf("%d%c", a[i], " \n"[i == n]);
        }
    }
    return 0;
}

TESTSERIES

题意

给你三个串S1，S2，X，问你有多少对<P,Q>满足P是S1的前缀且Q是S2的前缀且P+Q是X的子串（P，Q可以为空串）

题解

考虑枚举P和Q的断点，显然Q用exkmp就可以搞定，那P是S1的前缀和X的后缀相匹配，可以按S1+#+X做kmp，但并不是只有nxt[i]满足条件，nxt[nxt[i]], nxt[nxt[nxt[i]]]...都是可以的，暴力跳nxt肯定会超时，还有一个问题是这样可能会导致重复计算，可以将每个P的长度对应的Q的长度记录下来然后最后统一对nxt取最大值

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/*
 * @Author: tusikalanse
 * @Date: 2021-10-21 09:06:48
 * @LastEditTime: 2021-10-21 10:04:41
 * @LastEditors: tusikalanse
 * @Description: 
 */
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int N = 3e6 + 10;
string s1, s2, x;
int nxt1[N], extend[N], T;
int nxt2[N];
int ans[N];

void getnext(string &t, int nxt[]) {
  int len = t.size(), po, i = 0, j;
  nxt[0] = len;
  while(t[i] == t[i + 1] && i + 1  < len) 
    ++i;
  nxt[1] = i;
  po = 1;
  for(i = 2; i < len; ++i) {
    if(nxt[i - po] + i < po + nxt[po])
      nxt[i] = nxt[i - po];
    else {
      j = po + nxt[po] - i;
      if(j < 0) j = 0;
      while(i + j < len && t[j] == t[i + j])
        ++j;
      nxt[i] = j;
      po = i;
    }
  }
}

void exkmp(string &s, string &t, int nxt[]) {
  int len = s.size(), po, i = 0, j, l2 = t.size();
  getnext(t, nxt);
  while(t[i] == s[i] && i < len && i < l2) 
    ++i;
  extend[0] = i;
  po = 0;
  for(i = 1; i < len; ++i) {
    if(nxt[i - po] + i < po + extend[po])
      extend[i] = nxt[i - po];
    else {
      j = po + extend[po] - i;
      if(j < 0) j = 0;
      while(i + j < len && j < l2 && t[j] == s[i + j])
        ++j;
      extend[i] = j;
      po = i;
    }
  }
}

void kmp(string& s1, string& s2, int nxt[]) {
  string s = s2 + '#' + s1;
  int n = s.size(), i = 0, j = -1;
  nxt[0] = -1;
  while (i < n) {
    if (j == -1 || s[i] == s[j]) 
      nxt[++i] = ++j;
    else
      j = nxt[j];
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
    cin >> T;
    while (T--) {
        cin >> s1 >> s2 >> x;
    int total = x.size() + s1.size() + s2.size() + 10;

    memset(nxt1, 0, total * sizeof(int));
    memset(nxt2, 0, total * sizeof(int));
    memset(extend, 0, total * sizeof(int));
    memset(ans, 0, total * sizeof(int));
    exkmp(x, s2, nxt2);
    kmp(x, s1, nxt1);

    for (int i = 0; i <= x.size(); ++i) {
      int r = extend[i], l = nxt1[s1.size() + 1 + i];
      ans[l] = max(ans[l], r + 1);
    }

    for (int i = s1.size(); i; --i) {
      ans[nxt1[i]] = max(ans[nxt1[i]], ans[i]);
    }

    LL res = 0;
    for (int i = 0; i <= s1.size(); ++i) {
      res += ans[i];
    }
    cout << res << endl;
    }

  return 0;
}