「赛后总结」USACO 2021 December Contest

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

第一次打 USACO，只打到了 Silver

Bronze

Problem 1. Lonely Photo

Description

给定一个长度为 nn 的字符串 ss，ss 仅由 G 和 H 组成，求有多少个长度不小于 33 的子串只包含一个 G 或 H。

3≤n≤5×1053\le n \le 5\times 10^5

Solution

考虑对于每一个位置 ii，有多少个以 ii 结尾的合法的子串，不难发现子串的开头是一段连续的，所以只需要预处理一下 ii 前面第一个与 sis_i 相同的位置 preipre_i 和第一个与 sis_i 不同的位置 lstilst_i

然后只需要分类讨论一下以 ii 为结尾的子串中出现一次的字符是 G 还是 H。

  • si=si−1s_i=s_{i-1} 或 si−1≠si−2s_{i-1}\neq s_{i-2} 时，也就是只出现一次的字符不是 sis_i，那么我们需要找到上一个与 sis_i 不同的字符 sjs_j，和 sjs_j 前面第一个与 sjs_j 相同的字符，中间都是合法的。
  • 否则，也就是只出现一次的字符是 sis_i，那么直接找到上一个与 sis_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
#include <bits/stdc++.h>
#define ll long long
#define db double
#define gc getchar
#define pc putchar

using namespace std;

namespace IO
{
    template <typename T>
    void read(T &x)
    {
        x = 0; bool f = 0; char c = gc();
        while(!isdigit(c)) f |= c == '-', c = gc();
        while(isdigit(c)) x = x * 10 + c - '0', c = gc();
        if(f) x = -x;
    }

    template <typename T>
    void write(T x)
    {
        if(x < 0) pc('-'), x = -x;
        if(x > 9) write(x / 10);
        pc('0' + x % 10);
    }
}
using namespace IO;

const int N = 5e5 + 5;

int n, pre[N], lst[N];
char s[N];
ll ans;

int main()
{
    read(n);
    scanf("%s", s + 1);
    int x = 0, y = 0;
    pre[n + 1] = n;
    for(int i = 1; i <= n; i++)
    {
        if(s[i] == 'G')
        {
            pre[i] = x;
            lst[i] = y ? y : n + 1;
            x = i;
        }
        else
        {
            pre[i] = y;
            lst[i] = x ? x : n + 1; 
            y = i;
        }
    }
    for(int i = 3; i <= n; i++)
    {
        if(s[i - 1] == s[i] || s[i - 2] != s[i - 1]) ans += max(min(lst[i], i - 2) - pre[lst[i]], 0);
        else ans += max(i - pre[i] - 2, 0);
    }
    write(ans), pc('\n');
    return 0;
}
// A.S.

Problem 2. Air Cownditioning

Description

给定两个长为 nn 的序列 a,ba,b，每次操作可以将 aa 序列中连续的一段就、 +1+1 或 −1-1，求最少需要操作多少次。

1≤n≤1051\le n \le 10^5

Solution

直接做差，然后就转化成典中典了

就是有正有负，通过手玩不难发现每次操作不可能同时操作正负，分成两边单独操作一样是最优的

所以只需要指针扫一遍找出每个正、负区间，然后跑一遍单调栈即可。

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
#include <bits/stdc++.h>
#define ll long long
#define db double
#define gc getchar
#define pc putchar

using namespace std;

namespace IO
{
    template <typename T>
    void read(T &x)
    {
        x = 0; bool f = 0; char c = gc();
        while(!isdigit(c)) f |= c == '-', c = gc();
        while(isdigit(c)) x = x * 10 + c - '0', c = gc();
        if(f) x = -x;
    }

    template <typename T>
    void write(T x)
    {
        if(x < 0) pc('-'), x = -x;
        if(x > 9) write(x / 10);
        pc('0' + x % 10);
    }
}
using namespace IO;

const int N = 1e6 + 5;

int n, a[N];
int stk[N], top;
ll ans;

int main()
{
    read(n);
    for(int i = 1; i <= n; i++) read(a[i]);
    for(int i = 1, b; i <= n; i++) read(b), a[i] = b - a[i];
    for(int l = 1, r; l <= n; l = r + 1)
    {
        r = l + 1;
        while(r <= n && a[r] * a[r - 1] > 0) r++;
        r--;
        top = 0;
        for(int i = l; i <= r; i++)
        {
            a[i] = abs(a[i]);
            if(a[i] > stk[top]) ans += a[i] - stk[top];
            while(top && stk[top] > a[i]) top--;
            stk[++top] = a[i];
        }
    }
    write(ans), pc('\n');
    return 0;
}
// A.S.

Problem 3. Walking Home

Description

给定一个 n×nn\times n 的矩阵，. 可以通过，H 不可以通过，只能向右或向下走，求在至多转向 kk 次的前提下从左上角走到右下角有多少种方案。

2≤n≤50,1≤k≤32\le n \le 50,1\le k\le 3

Solution

很容易想到状态

fi,j,k,df_{i,j,k,d} 表示从 (1,1)(1,1) 走到 (i,j)(i,j) 共转向 kk 次，走过来后面向 d(0右,1下)d(0右,1下) 的方案数。

转移也比较简单，对于 d=0/1d=0/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
#include <bits/stdc++.h>
#define ll long long
#define db double
#define gc getchar
#define pc putchar

using namespace std;

namespace IO
{
    template <typename T>
    void read(T &x)
    {
        x = 0; bool f = 0; char c = gc();
        while(!isdigit(c)) f |= c == '-', c = gc();
        while(isdigit(c)) x = x * 10 + c - '0', c = gc();
        if(f) x = -x;
    }

    template <typename T>
    void write(T x)
    {
        if(x < 0) pc('-'), x = -x;
        if(x > 9) write(x / 10);
        pc('0' + x % 10);
    }
}
using namespace IO;

const int N = 55;

int n, m;
char s[N][N];
int f[N][N][10][2];

void solve()
{
    memset(f, 0, sizeof(f));
    read(n), read(m);
    for(int i = 1; i <= n; i++)
        scanf("%s", s[i] + 1);
    f[1][0][0][0] = f[0][1][0][1] = 1;
    for(int i = 1; i <= n; i++)
    {
        if(s[1][i] == '.') f[1][i][0][0] = f[1][i - 1][0][0];
        if(s[i][1] == '.') f[i][1][0][1] = f[i - 1][1][0][1];
    }
    for(int i = 2; i <= n; i++)
        for(int j = 2; j <= n; j++)
        {
            if(s[i][j] == 'H') continue;
            for(int k = 0; k <= m; k++)
            {
                f[i][j][k][0] += f[i][j - 1][k][0];
                if(k) f[i][j][k][0] += f[i][j - 1][k - 1][1];
                f[i][j][k][1] += f[i - 1][j][k][1];
                if(k) f[i][j][k][1] += f[i - 1][j][k - 1][0];
            }
        }
    ll ans = 0;
    for(int i = 0; i <= m; i++)
        ans += f[n][n][i][0] + f[n][n][i][1];
    write(ans), pc('\n');
}

int main()
{
    int T; read(T);
    while(T--) solve();
    return 0;
}
// A.S.

Silver

Problem 1. Closest Cow Wins

Description

在一条数轴上，有 kk 个点有权值， pip_i 位置的权值为 tit_i，现在，对方已经占了 mm 个位置 f1,f2,…fmf_1,f_2,\dots f_m，你要占 nn 个位置（可以是小数），求最大的权值和为多少。

对于每个点，当这个点距离你占的最近位置小于对方占的最近位置时，你可以获得这个点的权值。

1≤k≤2×105,1≤m≤2×1051\le k \le 2\times 10^5,1\le m\le 2\times 10^5，所有这些 k+mk+m 个位置均是 [0,109][0,10^9] 内的不同整数。

Solution

考虑对方占的每两个位置之间

当在这个区间内放 22 个点时，是可以得到这个区间内所有点的权值的。

所以只需要计算只放 11 个点时，最多能得到多少权值。

因为在这个区间内的点距离对面占的最近位置就是到两端的最小值，所以我们可以知道要想得到任意一个点的权值需要在哪个区间占位置

画一下图发现从左到右的点需要的区间的左右端点都是递增的，所以就可以双指针乱扫了（

我们有了在每个区间内占 1/21/2 个位置能得到的权值，接下来考虑如何占位置。

这里需要反悔贪心，先把占一个的权值都加到大根堆里，然后在被选时，将占两个的权值减去占一个的权值加到大根堆里，这样在下次选到时相当于占了两个。

Problem 2. Connecting Two Barns

Description

TT 组数据，每组数据给定 nn 个点 mm 条无向边，现在至多建两条边，使得从 11 到 nn 有路径，求建边的最小权值。

建一条从 ii 到 jj 的边的权值为 (i−j)2(i-j)^2

1≤T≤20,1≤n≤105,∑(n+m)≤5×1051\le T \le 20,1\le n \le 10^5,\sum(n+m)\le 5\times 10^5

Solution

先用并查集求出每个连通块，然后只需要求出 11 和 nn 所在连通块到其他连通块的最短距离，枚举一遍求最小值即可。

在求最短距离时可以直接枚举每个点，在 11 和 nn 所在连通块内二分找最小值

但我考场上没看见最后一个数据范围，就以为 O(Tnlog⁡n)O(Tn\log n) 过不去，然后写双指针乱扫，结果还没二分快 qaq

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
90
#include <bits/stdc++.h>
#define ll long long
#define db double
#define gc getchar
#define pc putchar
#define pb push_back

using namespace std;

namespace IO
{
    template <typename T>
    void read(T &x)
    {
        x = 0; bool f = 0; char c = gc();
        while(!isdigit(c)) f |= c == '-', c = gc();
        while(isdigit(c)) x = x * 10 + c - '0', c = gc();
        if(f) x = -x;
    }

    template <typename T>
    void write(T x)
    {
        if(x < 0) pc('-'), x = -x;
        if(x > 9) write(x / 10);
        pc('0' + x % 10);
    }
}
using namespace IO;

const int N = 1e5 + 5;

int n, m, f[N], id[N], cnt;
vector <int> vec[N];

int Find(int a)
{
    return f[a] == a ? a : f[a] = Find(f[a]);
}

int d1[N], d2[N];

void work()
{
    read(n), read(m);
    for(int i = 1; i <= n; i++) f[i] = i;
    for(int i = 1; i <= m; i++)
    {
        int u, v; read(u), read(v);
        if(Find(u) != Find(v)) f[Find(v)] = Find(u);
    }
    if(Find(1) == Find(n))
    {
        puts("0");
        return;
    }
    cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        int x = Find(i);
        if(!id[x]) id[x] = ++cnt;
        vec[id[x]].pb(i);
    }
    int S = id[Find(1)], T = id[Find(n)];
    memset(d1, 0x3f, sizeof(d1));
    memset(d2, 0x3f, sizeof(d2));
    for(int i = 1; i <= n; i++)
    {
        int x = id[Find(i)];
        int pos = lower_bound(vec[S].begin(), vec[S].end(), i) - vec[S].begin();
        d1[x] = min(d1[x], min(pos ? abs(i - vec[S][pos - 1]) : n, pos < (int)vec[S].size() ? abs(i - vec[S][pos]) : n));
        pos = lower_bound(vec[T].begin(), vec[T].end(), i) - vec[T].begin();
        d2[x] = min(d2[x], min(pos ? abs(i - vec[T][pos - 1]) : n, pos < (int)vec[T].size() ? abs(i - vec[T][pos]) : n));
    }
    ll ans = 1ll * (n - 1) * (n - 1);
    for(int i = 1; i <= cnt; i++)
        ans = min(ans, 1ll * d1[i] * d1[i] + 1ll * d2[i] * d2[i]);
    write(ans), pc('\n');
    memset(id, 0, sizeof(id));
    for(int i = 1; i <= cnt; i++) vec[i].clear();
    return;
}

signed main()
{
    int T; read(T);
    while(T--) work();
    return 0;
}
// A.S.

Problem 3. Convoluted Intervals

Description

给定 nn 个区间，第 ii 个区间为 [ai,bi][a_i,b_i]，在其中选两个区间（可以重复），对于 0≤k≤2m0\le k \le 2m 的每个 kk，求满足 ai+aj≤k≤bi+bja_i+a_j\le k \le b_i+b_j 的方案数。

1≤n≤2×105,1≤m≤5000,ai≤bi1\le n\le 2\times 10^5,1\le m\le 5000,a_i\le b_i

Solution

只要你发现 n≤2×105n\le 2\times10^5，而 m≤5000m\le 5000，这道题你就做出来一半了（

因此我们可以开个桶，然后 O(m2)O(m^2) 枚举值域，将 ai+aj=ka_i+a_j=k 和 bi+bj=kb_i+b_j=k 的方案数都求出来，注意当 ai=aja_i=a_j 时要特殊处理一下。

考虑 kk 变成 k+1k+1 有什么变化，只需要将 ai+aj=k+1a_i+a_j=k+1 的方案数加上，将 bi+bj=kb_i+b_j=k 的方案数减掉。

也相当于差分，可以在最后求个前缀和。

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
#include <bits/stdc++.h>
#define ll long long
#define db double
#define gc getchar
#define pc putchar

using namespace std;

namespace IO
{
    template <typename T>
    void read(T &x)
    {
        x = 0; bool f = 0; char c = gc();
        while(!isdigit(c)) f |= c == '-', c = gc();
        while(isdigit(c)) x = x * 10 + c - '0', c = gc();
        if(f) x = -x;
    }

    template <typename T>
    void write(T x)
    {
        if(x < 0) pc('-'), x = -x;
        if(x > 9) write(x / 10);
        pc('0' + x % 10);
    }
}
using namespace IO;

const int N = 2e5 + 5;

int n, m, a[N], b[N];
ll ca[N], cb[N];
ll l[N], r[N];

int main()
{
    read(n), read(m);
    for(int i = 1; i <= n; i++) read(a[i]), read(b[i]), ca[a[i]]++, cb[b[i]]++;
    for(int i = 0; i <= m; i++)
        for(int j = 0; j <= m; j++)
            if(i != j) l[i + j] += ca[i] * ca[j], r[i + j] += cb[i] * cb[j];
    for(int i = 0; i <= m; i++) l[i + i] += ca[i] * ca[i], r[i + i] += cb[i] * cb[i];
    ll ans = 0;
    for(int i = 0; i <= m + m; i++)
        ans += l[i], write(ans), pc('\n'), ans -= r[i];
    return 0;
}
// A.S.