2022牛客暑期多校训练营6（ABGIJM）

题集链接；
视频题解；

A Array

构造

题意

给定序列 aia_i ，满足 ∑1ai⩽12\sum\frac 1{a_i}\leqslant\frac 12 ，构造长度不超过1e6的序列 cic_i，满足在 c 序列首尾相接形成的序列 b 中，任意长度为 aia_i 的子串都含有数字 ii ；

思路

对于 aia_i 的限制，我们可以理解为“填充率”，即数字 i 至少占所求序列的 1ai\frac 1{a_i} ；

然后我们考虑构造，考虑序列 c 的长度为 2max⁡(ai)2\max(a_i) ，对于每一个 i ，按 aia_i 升序排列，依次构造，从起始处开始每 aia_i 位填入一个 i ，如果对应位被占，则向左找最近的空位；

在结尾处，我们考虑可能存在由于被占位造成的左移，使得c序列最后一个 i 和下一个c序列的第一个i之间的距离不满足要求，则我们在结尾处重新寻找空位插入；

由于保证有解，所以不存在数组前 aia_i 位均被占或找不到空位等情况；

代码

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

using namespace std;

int ans[1000006];

int main()
{
    int n, mxg = 0;
    pair<int, int> g[100005];
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%d", &g[i].first), g[i].second = i, mxg = max(mxg, g[i].first);
    sort(g + 1, g + n + 1);
    int c = 1;
    for (int i = 1; i <= n; i++)
    {
		int j=c;
		while(ans[j])j++,c++;
        for (; j <= 2*mxg; j += g[i].first)
        {
			while(ans[j])j--;
            ans[j] = g[i].second;
        }
		if(j-2*mxg<c)
		{
			while(j>2*mxg||ans[j])j--;
			ans[j] = g[i].second;
		}
        c++;
    }
    printf("%d\n", 2*mxg);
    for (int i = 1; i <= 2*mxg; i++)
        printf("%d ", (ans[i])?ans[i]:1);
    return 0;
}

B Eezie and Pie

树上差分

题意

在一棵以 1 为根的树中，每一个点有一个属性 did_i ，表示该点可以覆盖自己和向根方向的 did_i 个点（did_i不含自身），输出每个点可以被几个点覆盖；

思路

区间加问题，我们考虑差分来解决；

在dfs形成的每一条链上，我们对末端点的did_i 进行差分，在dfs离开该点时，将该点的差分值加到父亲上，以此统计每个点的被覆盖次数；

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> rod[2000006];
ll ans[2000006], d[2000006];
vector<pair<int, int>> tmp;//这里的.first实际上无意义

void dfs(int x, int f)
{
    tmp.push_back({x, 1});
    if ((int)tmp.size() - 1 - d[x] - 1 >= 0)
        tmp[(int)tmp.size() - 1 - d[x] - 1].second--;

    for (auto u : rod[x])
    {
        if (u == f)
            continue;
        dfs(u, x);
    }

    ans[x] = tmp[tmp.size() - 1].second;
    if (tmp.size() > 1)
    {
        tmp[tmp.size() - 2].second += tmp[tmp.size() - 1].second;
    }
    tmp.pop_back();
}
int main()
{
    int n, u, v;
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        scanf("%d%d", &u, &v);
        rod[u].push_back(v);
        rod[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &d[i]);
    }
	// tmp.push_back({0,0});
    dfs(1, 0);
    for (int i = 1; i <= n; i++)
    {
        printf("%lld ", ans[i]);
    }
    return 0;
}

G Icon Design

字符串

题意

按要求打印字符串

代码

队友代码如下

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
#include <iostream>
#include <set>
using namespace std;

int main() {
   int n;
   cin >> n;

   set<pair<int, int>> s;

   // N

   int L = n + 1, U = n;

   for (int i = 1; i <= 2 * n + 3; i++) {
      s.insert({L + i, U + i});
      s.insert({L + 1, U + i});
      s.insert({L + 2 * n + 3, U + i});
   }

   // F

   L += 2 * n + 3 + n + 1;

   for (int i = 1; i <= 2 * n + 3; i++) {
      s.insert({L + 1, U + i});
      s.insert({L + i, U + 1});
      s.insert({L + i, U + n + 2});
   }

   // L

   L += 2 * n + 3 + n + 1;

   for (int i = 1; i <= 2 * n + 3; i++) {
      s.insert({L + 1, U + i});
      s.insert({L + i, U + 2 * n + 3});
   }

   // S
   L += 2 * n + 3 + n + 1;

   for (int i = 1; i <= 2 * n + 3; i++) {
      s.insert({L + i, U + 1});
      s.insert({L + i, U + n + 2});
      s.insert({L + i, U + 2 * n + 3});
      if (i <= n + 2) {
         s.insert({L + 1, U + i});
      }
      if (i >= n + 2) {
         s.insert({L + 2 * n + 3, U + i});
      }
   }

   for (int i = 0; i < 4 * n + 5; i++) {
      for (int j = 0; j < 13 * n + 19; j++) {
         if (i == 0 || j == 0 || i == 4 * n + 5 - 1 ||
             j == 13 * n + 19 - 1) {
            cout << '*';
         } else if (s.find({j, i}) != s.end()) {
            cout << "@";
         } else {
            cout << ".";
         }
      }
      cout << '\n';
   }

   return 0;
}

I Line

构造

题意

给定向量集 v 和数字 d ，要求生成点集 p ，要求 p 中的每个点在向量集 v 的每个方向上（共线即可）都经过恰好 d 个 p 中的点（含自身）；

思路

我们首先在 p 中构造原点，再对 p 中的每个点依次沿着 v 中的每个方向构造 d-1 个点；

为了保证不发生意外共线，我们可以将延长的距离乘一个对 v 中元素两两不同的系数，经测试，取37i,23i37^i,23^i 均可；
经测试，某些质数也会发生意外共线，具体原因待确定；

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
pair<ll, ll> vv[10];
vector<pair<pair<ll, ll>, int>> pp;
vector<pair<ll, ll>> p;
bool operator==(pair<pair<ll, ll>, int> a, pair<pair<ll, ll>, int> b)
{
    return a.first.first == b.first.first && a.first.second == b.first.second;
}
int main()
{
    int n, u, v, d;
    cin >> n >> d;
    for (int i = 0; i < n; i++)
    {
        scanf("%lld%lld", &vv[i].first, &vv[i].second);
        if (vv[i].first * vv[i].second)
        {
            int g = __gcd(abs(vv[i].first), abs(vv[i].second));
            vv[i].first /= g;
            vv[i].second /= g;
        }
        else
        {
            if (vv[i].first + vv[i].second)
            {
                if (vv[i].second)
                    vv[i] = {0, 1};
                else if (vv[i].first)
                    vv[i] = {1, 0};
            }
        }
    }
    sort(vv, vv + n);
    n = unique(vv, vv + n) - vv;
    pp.push_back({{0, 0}, -1});
    ll bas = 1;
    for (int i = 0; i < n; i++, bas *= 37)
    {
        for (int k = 0; k < pp.size(); k++)
        {
            if (pp[k].second == i)
                break;
            auto tt = pp[k].first;
            for (int j = 2; j <= d; j++)
            {
                pp.push_back(
                    {{tt.first + vv[i].first * bas * j, tt.second + vv[i].second * bas * j}, i});
            }
        }
    }

    printf("%d\n", pp.size());
    for (auto i : pp)
        printf("%lld %lld\n", (i.first), (i.second));
    return 0;
}

J Number Game

数学

题意

给定数字 A,B,C ，定义两种操作，问能否通过若干操作使得第三个位置的数字变为 x ；

思路

对于一组相同的值，进行若干次操作，这组值只会有两种不同的结果。其中第二个位置（B）的值只有可能是 B 和 A-B ；

那么对于第三个位置，其生成方式也有两种，即 先与B运算，再与A-B运算 和 先与A-B运算，再与B运算；

我们可以打表找规律：对于非负整数 k ，第三个位置的值为

(−1)k+1k+12A+(−1)kkB+(−1)kC(−1)kk2A+(−1)k+1kB+(−1)kC(-1)^{k+1}\frac {k+1}2A+(-1)^kkB+(-1)^kC\\ (-1)^{k}\frac {k}2A+(-1)^{k+1}kB+(-1)^kC

将k按奇偶讨论，换元为 2n2n 和 2n+12n+1 ，如果能求出 n 的非负整数解，即题求情况存在；

代码

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;
typedef long long ll;
const int N = 5e4;
const ll M = 1e9 + 7;
typedef struct
{
    int x, y, z;
} ppp;
int main()
{
    ll t, a, b, c, x;
    cin >> t;
    while (t--)
    {
        cin >> a >> b >> c >> x;
        if (c == x)
        {
            printf("Yes\n");
            continue;
        }
        if (2 * b - a)
        {
            if ((x + c + b - a) % (a - 2 * b) == 0 && (x + c + b - a) / (a - 2 * b) >= 0)
            {
                printf("Yes\n");
                continue;
            }
            if ((x + c - b) % (2 * b - a) == 0 && (x + c - b) / (2 * b - a) >= 0)
            {
                printf("Yes\n");
                continue;
            }
            if ((x - c) % (2 * b - a) == 0 && (x - c) / (2 * b - a) >= 0)
            {
                printf("Yes\n");
                continue;
            }
            if ((x - c) % (a - 2 * b) == 0 && (x - c) / (a - 2 * b) >= 0)
            {
                printf("Yes\n");
                continue;
            }
            printf("No\n");
            continue;
        }
        else if (a - b - c == x || b - c == x)
        {
            printf("Yes\n");
            continue;
        }
        else
        {
            printf("No\n");
            continue;
        }
    }
}

M Game on grid

DP

题意

给定n*m的网格，一些格点上标有字母A或B ，棋子初始在(0,0)点上，每次移动只能移动到 (i+1,j) 或 (i,j+1) 。若某时刻旗子在A上，则先手赢，若在B上则后手赢，若走到 (n-1,m-1) 点仍未划分胜负，则平局；
对于给定网格，请问先手是否有必赢、必平、必输机会；

思路

我们发现，对于 (i+j)%2=0 的点，接下来一定是先手进行操作，反之为后手先；

我们调整胜负判定，将先手必输的情况调整为以B判先手胜的先手赢，平局调整为以平局为判定的先手赢
考虑DP：

有状态表示 dp[i][j]dp[i][j] 为走到 (i,j) 点时先手的输赢情况，若为1，则走到该点时，接下来一定会先手赢，若为-1，则一定会先手输，若为0则不定；

考虑状态转移方程

dp[i][j]={check(mp[i][j]) mp[i][j]!=.max⁡(dp[i+1][j],dp[i][j+1]) (i+j)%2==0min⁡(dp[i+1][j],dp[i][j+1]) (i+j)%2==1dp[i][j]=\begin{cases} check(mp[i][j])\ mp[i][j]!=.\\ \max(dp[i+1][j],dp[i][j+1])\ (i+j)\%2==0\\ \min(dp[i+1][j],dp[i][j+1])\ (i+j)\%2==1\\ \end{cases}

即先手倾向于走向先手赢，后手倾向于走向先手输；

至于将字符映射到1,0,-1的过程，则通过check函数实现；

代码

队友代码如下

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

int dp[N][N], n, m;
char s[N][N];

void solve()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%s", s[i]);

    auto dpf = [&](auto ck, int final = 1)
    {
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = m - 1; j >= 0; j--)
            {
                dp[i][j] = ck(i, j);
                if (dp[i][j] != 0)
                    continue;
                if (i == n - 1 && j == m - 1)
                    continue;
                vector<int> nxt;
                if (i < n - 1)
                    nxt.push_back(dp[i + 1][j]);
                if (j < m - 1)
                    nxt.push_back(dp[i][j + 1]);
                if ((i + j) % 2 == 0)
                {
                    dp[i][j] = *max_element(nxt.begin(), nxt.end());
                }
                else
                {
                    dp[i][j] = *min_element(nxt.begin(), nxt.end());
                }
            }
        }
        return dp[0][0] == final;
    };

    if (dpf(
            [](int i, int j) -> int
            {
                if (s[i][j] == 'B')
                    return -1;
                return s[i][j] == 'A';
            }))
        printf("yes ");
    else
        printf("no ");

    if (dpf([](int i, int j) -> int { return s[i][j] == '.' ? 0 : -1; }, 0))
        printf("yes ");
    else
        printf("no ");

    if (dpf(
            [](int i, int j) -> int
            {
                if (s[i][j] == 'A')
                    return -1;
                return s[i][j] == 'B';
            }))
        puts("yes");
    else
        puts("no");
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        solve();
    }
}
算法竞赛 > 比赛与题集
2022牛客暑期多校训练营6（ABGIJM）
https://tanyuu.github.io/2022.07-12/2022牛客暑期多校训练营6（ABGIJM）/
作者
F Juny
发布于
2022年8月8日
许可协议