杭电暑期训练

发表于 更新于 分类于 本文字数： 3.4k 阅读时长 ≈ 12 分钟

补点杭电暑期训练营的题目.

菜比不如去补点 CF 上的思维模拟题, 或者跟着闫总做题去. 给自己的任务: 做出签到题就是胜利. 银牌题怕是这辈子也做不出了. 8.22 就是 CCPC 的网络赛, 估计到时候要被川内其他学校薄纱.

Contest 1

1009 Assertion

题解

标签: 思维

签到题. 好像是鸽笼原理, 但不懂也能做.

代码

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

const int N = 1e5 + 5;
int T;

void solve()
{
    int n, m, d;
    cin >> n >> m >> d;
    int res = (m - 1) / n + 1;
    if (res >= d)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

1005 Cyclically Isomorphic

题解

标签: 字符串哈希 双指针

题意: 给定 \(n\) 个字符串 \(s_i\) (长度为 \(m\), 且 \(1\leqslant n\cdot m \leqslant 10^5\)), 然后给出查询 \((x,y)\), 问 \(s_x\) 是否可以经过循环右移 (字符串旋转) 得到 \(s_y\).

字符串旋转的一个小技巧: 复制字符串

例如 aab 的全部旋转得到的对象 aab, baa, aba, 其实都是 aabaab 的字串. 同时一个好的性质是它们复制得到的新串经过hash映射结果是一样的.

计算 hash: 单 hash

这道题 KMP 和后缀数组也可以做.

代码

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
#include <bits/stdc++.h>
using namespace std;
const int MOD = 666623333, N = 1e5 + 5;
int T, a[N];
char s[2 * N];

void solve()
{
    int n, m, Q;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> (s + 1);
        // Duplicate
        for (int j = m + 1; j <= m + m; j++)
            s[j] = s[j - m];
        int I, J;
        for (I = 1, J = 2; J <= m; J++)
        {
            for (int k = 0; k < m; k++)
            {
                if (s[I + k] < s[J + k]) {
                    J += k;
                    break;
                }
                if (s[I + k] > s[J + k]) {
                    int tmp = I;
                    I = J;
                    J = max(J, tmp + k);
                    break;
                }
            }
        }
        // 计算 Hash
        a[i] = 0;
        for (int j = 0; j < m; j++)
            a[i] = (31ll * a[i] + s[I + j] - 'a' + 1) % MOD;
    }
    cin >> Q;
    while (Q--)
    {
        int x, y;
        cin >> x >> y;
        if (a[x] == a[y])
            puts("Yes");
        else
            puts("No");
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

1002 City Upgrading

题解

标签: 树形dp

坑点: 数据有 \(n=1\) 的情形, 但是题目里没讲...

题意: 给定一棵 \(n\) 个节点的有权树, 选择一个节点可以覆盖其子节点, 问覆盖整棵树方案需要花费的最小值.

  • 状态表示:
    • \(f(i,0)\) 表示 \(i\) 节点未选择, \(i\) 也不被覆盖, 且 \(i\) 的子孙都被覆盖.
    • \(f(i,1)\) 表示 \(i\) 节点选择, 且 \(i\) 的子孙都被覆盖.
    • \(f(i,2)\) 表示 \(i\) 节点未选择, 但被它的子孙覆盖, 且 \(i\) 的子孙都被覆盖.
  • 属性: 最小代价
  • 状态转移:
    • \(F\): 考虑到子节点 \(k\) 更新后的 dp 值
    • \(F(i,0)=f(i,0)+f(i,2)\)
    • \(F(i,1)=\min \{f(i,0), f(k,1), f(k,2)\}\)
    • \(F(i,2)=\min \{f(i,2)+\min\{f(k,1),f(k,2)\}, f(i,0)+f(k,1)\}\)

代码

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 <cstdio>
#include <cstring>
#include <algorithm>
#define M 1000005
#define INF 100000000000000
using namespace std;
struct E
{
    int to, nx;
} edge[M << 1];
int tot, head[M];
void Addedge(int a, int b)
{
    edge[++tot].to = b;
    edge[tot].nx = head[a];
    head[a] = tot;
}
long long dp[M][3];
int fa[M];
int A[M];
inline void Add(long long &x, long long y)
{
    x += y;
    if (x >= INF)
        x = INF;
}
void dfs(int now)
{
    dp[now][0] = dp[now][1] = dp[now][2] = 0;
    dp[now][1] = A[now];
    dp[now][2] = INF;
    for (int i = head[now]; i; i = edge[i].nx)
    {
        int nxt = edge[i].to;
        if (nxt == fa[now])
            continue;
        fa[nxt] = now;
        dfs(nxt);
        dp[now][2] = min(dp[now][2] + min(dp[nxt][1], dp[nxt][2]), dp[now][0] + dp[nxt][1]);
        Add(dp[now][1], min(dp[nxt][0], min(dp[nxt][1], dp[nxt][2])));
        Add(dp[now][0], dp[nxt][2]);
    }
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n;
        scanf("%d", &n);
        memset(head, 0, sizeof(head));
        tot = 0;
        for (int i = 1; i <= n; i++)
            head[i] = 0;
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        for (int i = 1; i < n; i++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            Addedge(a, b);
            Addedge(b, a);
        }
        dfs(1);
        long long ans = min(dp[1][1], dp[1][2]);
        printf("%lld\n", ans);
    }
    return 0;
}

1010 Easy problem I

先吐槽下标题, 一点也不easy

标签: 线段树维护

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <bits/stdc++.h>

#define ll long long
#define Max 200005

using namespace std;

struct Tree
{
    ll lazy1, lazy2, lazy3, cnt, minn, sum1, sum2;
} st[Max * 4];

int T, n, m, a[Max];

inline Tree up(Tree ls, Tree rs)
{
    Tree ans;
    ans.lazy1 = ans.lazy3 = 0;
    ans.lazy2 = 1;
    ans.minn = min(ls.minn, rs.minn);
    ans.sum1 = ls.sum1 + rs.sum1;
    ans.sum2 = ls.sum2 + rs.sum2;
    ans.cnt = ls.cnt + rs.cnt;
    return ans;
}

inline void down(int node, int L, int R)
{
    int ls = node << 1, rs = node << 1 | 1;
    int mid = (L + R) >> 1;

    st[ls].lazy3 += st[node].lazy3;
    st[rs].lazy3 += st[node].lazy3;
    st[ls].sum1 -= st[node].lazy3 * st[ls].cnt;
    st[rs].sum1 -= st[node].lazy3 * st[rs].cnt;
    st[ls].minn -= st[node].lazy3;
    st[rs].minn -= st[node].lazy3;

    st[ls].lazy1 = st[node].lazy1 + st[ls].lazy1 * st[node].lazy2;
    st[rs].lazy1 = st[node].lazy1 + st[rs].lazy1 * st[node].lazy2;
    st[ls].lazy2 *= st[node].lazy2;
    st[rs].lazy2 *= st[node].lazy2;
    st[ls].sum2 = st[node].lazy1 * (mid - L + 1 - st[ls].cnt) + st[ls].sum2 * st[node].lazy2;
    st[rs].sum2 = st[node].lazy1 * (R - mid - st[rs].cnt) + st[rs].sum2 * st[node].lazy2;
    st[node].lazy1 = st[node].lazy3 = 0;
    st[node].lazy2 = 1;
    return;
}

inline void build(int node, int L, int R)
{
    if (L == R)
    {
        st[node].lazy1 = st[node].lazy3 = 0;
        st[node].lazy2 = 1;
        st[node].minn = st[node].sum1 = a[L];
        st[node].sum2 = 0;
        st[node].cnt = 1;
        return;
    }
    int mid = (L + R) >> 1;
    build(node << 1, L, mid);
    build(node << 1 | 1, mid + 1, R);
    st[node] = up(st[node << 1], st[node << 1 | 1]);
    return;
}

inline void change(int node, int l, int r, int L, int R, int k)
{
    if (L >= l && R <= r)
    {
        if (st[node].cnt)
        {
            if (L == R)
            {
                if (st[node].sum1 < k)
                {
                    st[node].sum2 = k - st[node].sum1;
                    st[node].sum1 = st[node].cnt = 0;
                    st[node].minn = 1e18;
                }
                else
                {
                    st[node].minn = st[node].sum1 = st[node].sum1 - k;
                }
            }
            else
            {
                if (st[node].minn < k)
                {
                    down(node, L, R);
                    int mid = (L + R) >> 1;
                    change(node << 1, l, r, L, mid, k);
                    change(node << 1 | 1, l, r, mid + 1, R, k);
                    st[node] = up(st[node << 1], st[node << 1 | 1]);
                }
                else
                {
                    st[node].lazy3 += k;
                    st[node].minn -= k;
                    st[node].sum1 -= 1ll * k * st[node].cnt;
                    st[node].lazy1 = k - st[node].lazy1;
                    st[node].lazy2 *= -1;
                    st[node].sum2 = 1ll * k * (R - L + 1 - st[node].cnt) - st[node].sum2;
                }
            }
        }
        else
        {
            st[node].lazy1 = k - st[node].lazy1;
            st[node].lazy2 *= -1;
            st[node].sum2 = 1ll * k * (R - L + 1) - st[node].sum2;
        }
        //        cout<<L<<" "<<R<<" "<<st[node].sum1<<" "<<st[node].sum2<<endl;
        return;
    }
    down(node, L, R);
    int mid = (L + R) >> 1;
    if (l <= mid)
        change(node << 1, l, r, L, mid, k);
    if (r > mid)
        change(node << 1 | 1, l, r, mid + 1, R, k);
    st[node] = up(st[node << 1], st[node << 1 | 1]);
    return;
}

inline Tree query(int node, int l, int r, int L, int R)
{
    if (L >= l && R <= r)
        return st[node];
    down(node, L, R);
    int mid = (L + R) >> 1;
    if (r <= mid)
        return query(node << 1, l, r, L, mid);
    if (l > mid)
        return query(node << 1 | 1, l, r, mid + 1, R);
    return up(query(node << 1, l, r, L, mid), query(node << 1 | 1, l, r, mid + 1, R));
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        build(1, 1, n);
        for (int i = 1; i <= m; i++)
        {
            int opt;
            cin >> opt;
            if (opt == 1)
            {
                int l, r, x;
                cin >> l >> r >> x;
                change(1, l, r, 1, n, x);
            }
            else
            {
                int l, r;
                cin >> l >> r;
                Tree ans = query(1, l, r, 1, n);
                cout << ans.sum1 + ans.sum2 << '\n';
            }
        }
    }
    return 0;
}

Contest 2

只切了一道数学题.

做不动了. 立即推放弃

1009 String Problem

题面: 多例输入, 给定 \(n\) 长的字符串 \(s\), 选择 \(k\) 个非空, 互文, 不相交字串 \(s_i\), \(s_i\) 包含至多一种字符, 求 \(\max \{\sum \operatorname{len}(s_i)-k\}\).

样例:

1
2
3
2
etxabaxtezwkdwokdbbb
aaaaa
1
2
2
4

题解

签到题, 队友切了

将字符串拆成尽可能少的段, 每段只包含一种字符, 每段对答案贡献减一

代码

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
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
typedef pair<int, int> PII;

const int MOD = 666623333, N = 1e6 + 5;
int T = 1;
char s[N];

void solve()
{
    scanf("%s", s + 1);
    int n = strlen(s + 1);

    vector<pair<char, int>> v;
    v.push_back({s[1], 1});
    for (int i = 2; i <= n; i++)
    {
        if (s[i] == v.back().first)
            ++v.back().second;
        else
            v.push_back({s[i], 1});
    }    
    int ans = 0;
    for (auto [x, y] : v)
        ans += y - 1;
    cout << ans << endl;
}

signed main() {
    scanf("%d", &T);
    while (T--)
    {
        solve();
    }
    
    return 0;
}

Contest 3

坐牢

1011 8-bit Zoom

标签: 模拟

题意: 给定一个 \(n\times n\) (\(1\leqslant n\leqslant 50\))的图像, 用字符串模拟, 输出放大 \(Z \%\)(\(100\leqslant Z\leqslant 200\), \(Z \bmod 25 = 0\)) 倍. 最终图像的大小为 \(\frac{nZ}{100}\times\frac{nZ}{100}\).

图像在以下两种情况下不能放大:

  • 当 \(\frac{nZ}{100}\) 不为整数时
  • 图像放大后, 有些像素点无法确定. 如果至少有两个不同的颜色映射到同一个像素点, 那么这个像素点的颜色就无法确定.

多例输入, 第一行包含 \(n\) 和 \(Z\), 然后 \(n\) 行, 每一行是长度为 \(n\) 的字符串, 每个字符都是英文小写字符, 第 \(i\) 行的第 \(j\) 个字符表示原图像中的 \((i,j)\) 像素点的颜色.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
5
2 100
ab
cd
2 200
ab
cd
2 125
aa
aa
4 125
aaab
aaaa
aaaa
aaaa
4 125
aaaa
aaaa
aaaa
aaaa
1
2
3
4
5
6
7
8
9
10
11
12
13
ab
cd
aabb
aabb
ccdd
ccdd
error
error
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa

题解

主要是放大的逻辑不太好写. 例如 aaab 放大 1.25 倍的这个案例. 主要恶心的是这个小数.

避免小数的出现, 我们把图像放大到 \(Z / 25\) 倍, 然后以 \(4\) 为步长去读取即可.

例如 a 放大两倍就变成

1
2
3
4
aaaaaaaa
aaaaaaaa
...
aaaaaaaa

以4为步长, 那么

1
2
aa
aa

怎么判断放大后某一个像素点存在至少两个不同的颜色?

例如

1
2
aaab
aaaa

放大倍率为 125%, 它就不合法. 为什么(?)

1
2
3
4
5
aaaa aaaa aaaa aaab bbbb
aaaa aaaa aaaa aaab bbbb
aaaa aaaa aaaa aaab bbbb
aaaa aaaa aaaa aaab bbbb
...

步长为 4 读取, a a a a b, 你会发现第四个像素点有两种颜色! 我们要做的就是把这种情况作为异常处理.

代码

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
#include <cstdio>

const int N = 55;
int T = 1;

char a[N][N], b[N * 8][N * 8];

void solve()
{
    int n, Z;
    scanf("%d%d", &n, &Z);
    if (n * Z / 25 % 4)
    {
        puts("error");
        return;
    }
    else
    {
        for (int i = 0; i < n; i++)
            scanf("%s", a[i]);
        int rate = Z / 25;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                int xl = i * rate, xr = xl + rate;
                int yl = j * rate, yr = yl + rate;
                char w = a[i][j];
                for (int A = xl; A < xr; A++)
                    for (int B = yl; B < yr; B++)
                        b[A][B] = w;
            }
        
        int m = n * rate;
        for (int i = 0; i < m; i += 4)
            for (int j = 0; j < m; j += 4)
            {
                char w = b[i][j];
                for (int A = i; A < i + 4; A++)
                    for (int B = j; B < j + 4; B++)
                        if (b[A][B] != w)
                        {
                            puts("error");
                            return;
                        }
            }
        for (int i = 0; i < m; i += 4)
        {
            for (int j = 0; j < m; j += 4)
                putchar(b[i][j]);
            puts("");
        }
    }
}

signed main() {
    scanf("%d", &T);
    while (T--)
    {
        solve();
    }
    
    return 0;
}

1005 Out of Control

标签: 排序 前缀和 离散化

挺有实际意义的一个问题

题意: 多例输入 \(T\leqslant 100\), \(n\) 个($ 1n $)整数 \(x_i(1\leqslant x_i \leqslant 10^9)\), 维护栈单调递增, 输出栈长固定时所有单调栈的数量, 结果对 \(10^9+7\) 取模.

样例:

1
2
3
4
5
2
3
1 2 3
3
2 3 3
1
2
3
4
5
6
3
5
5
2
2
2

题解

代码

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
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
typedef pair<int, int> PII;

const int MOD = 1e9 + 7, N = 3e3 + 5;
int T = 1;

int ans, sum;
int a[N], b[N], f[N];

inline void up(int &a, int b)
{
    a = (a + b < MOD) ? a + b : a + b - MOD;
}

void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    int m = 0;
    for (int i = 1; i <= n; i++)
        if (i == 1 || b[i] > b[i - 1])
            b[++m] = b[i];
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
        f[i] = 1;
    cout << m << endl;
    for (int i = 2; i <= n; i++)
    {
        sum = ans = 0;
        for (int j = a[i - 1]; j < a[i]; j++)
            up(sum, f[j]);
        for (int j = a[i]; j <= m; j++)
        {
            up(sum, f[j]);
            f[j] = sum;
            up(ans, sum);
        }
        cout << ans << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

Contest 4

只做了两题. 罚时有点狠的.

1012 a-b Problem

标签: 思维

题面: Alice 和 Bob 轮流取石子, Alice 先手, 石头有 \(A_i\) 和 \(B_i\) 的分数, 分别对应两个人取石子的加分. 两个人都想赢, 同时想要让分差最大. 求最后俩人的分差.

多例输入, 每个例子中, 第一行是 \(n\), 接下来 \(n\) 行每一行是 \(A_i, B_i\).

取石子是不需要按石子的顺序取的.

1
2
3
4
5
6
7
8
230
2
1 2
3 3
31
0
2 3
0 4
1
2
1
-1

题解

如果贪心取最大这是有问题的, 因为你还需要博弈考虑 Bob 的取法:

1
2
3 0
1 10000

我们可以考虑转换问题. 假如一开始石子都在 Bob 手里, 那么 Alice 取石子, 它可以获得 \(A_i + B_i\) 的分数差. 对于 Bob 来说, 他要做的是把这些可以拉大分差的石子藏起来. 这样和原问题是等价的.

于是逻辑就很简单了: 对 \(A_i + B_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
#include <stdio.h>
#include <algorithm>

struct Z
{
    int a, b;
    int operator<(Z o) const
    {
        return a + b > o.a + o.b;
    }
};
Z z[100001];

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d%d", &z[i].a, &z[i].b);
        std::sort(z, z + n);
        long long sum = 0;
        for (int i = 0; i < n; i++)
        {
            if (i & 1)
                sum -= z[i].b;
            else
                sum += z[i].a;
        }
        printf("%lld\n", sum);
    }
}

Contest 5

没空打

1012 Counting Stars

题意: 定义 \(k\) 星为 \(k+1\) 个顶点和 \(k\) 条边的连通无向图, 满足 \(k\) 条边连接着同一个点. 问: 给定一个无向图 \(n\) 顶点和 \(m\) 条边, 输出所有 \(k\) 星图(\(\forall k\in[2,n-1]\))的数量.

答案很大, 每次得到的 \(k\) 星数量 \(cnt_{i}\) 需要先对 \(10^9+7\) 取模, 然后求 \(cnt_2 \oplus cnt_3 \dots \oplus cnt_k\).

题解

计算每个节点的度, 显然 \(n\) 度的 \(k\) 星有 \(\binom{n}{k}\) 个. 我们计算每个节点对 \(k\) 图的贡献.

组合数要优先预处理. 阶乘打表. 组合数要怎么生成?

我们知道

\[\binom{n}{m} = \frac{n!}{(n-m)!m!}\]

数字大了以后不考虑除法. 因为我们已经对阶乘取过模了. 所以, 这里需要计算的是阶乘逆元. 计算逆元可以用快速幂(费马小定理). 当然你可以只计算最后一个, 之前的可以递推

\[(n-1)! n \cdot x \equiv 1 \qquad (x = (n!)^{-1})\]