百度之星初赛第三场

T1

题意：
数有多少个长度为 nn，由小写字母组成的字符串里出现了至少三次不相交的 shs。
不相交：即 shshs 只算一次。

应该只要dp每个前缀出现几次，后面两个字母以及最后三个是否产生贡献即可，转移也是简单的。。。
但我没想明白，于是倒着做了，即 26n26^n 减去没有的减去出现一次的减去出现两次的。
长度为 ii 且没出现的记为 fi,b∈{0,1,2}f_{i,b\in{\{0,1,2\}}}，其中 fi,0f_{i,0} 为后缀不为 s 或 sh， fi,1f_{i,1} 为后缀为 s 的，fi,2f_{i,2} 为后缀为 sh，转移是平凡的。
长度为 ii 且出现一次的记为 gi,b∈{0,1,2}g_{i,b\in{\{0,1,2\}}}，转移类似上述，需要注意的是 gi,2g_{i,2} 为后缀为 sh 且不在产生贡献的 shs 中，且 gi,0g_{i,0} 需要加上 fi−1,2f_{i-1,2}。
最后是出现两次的，为 ∑i=3n(fi−3,0+fi−3,1)×(gn−i,0+gn−i,1+gn−i,2)\sum\limits_{i=3}^{n}(f_{i-3,0}+f_{i-3,1})\times(g_{n-i,0}+g_{n-i,1}+g_{n-i,2})。

code\texttt{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
/**
 * @author : cyb1010
 * @date   : 2023-09-24 14:00:50
 * @file   : 1.cpp
 */
#include <bits/stdc++.h>
using namespace std;
#define fo(s) freopen(s ".in", "r", stdin), freopen(s ".out", "w", stdout)
#define fi first
#define se second
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
int n;
ll f[1000010][3], mod = 1000000007,
                  ans; // f[i][0] not 's' or 'sh' f[i][1] is 's' f[i][2] is 'sh'
ll g[1000010][3];      // g[i][0] not 's' or 'sh' g[i][1] is 's' g[i][2] is 'sh'
ll qp(ll x, ll k) {
    ll res = 1;
    while (k) {
        if (k & 1) res = res * x % mod;
        x = x * x % mod, k >>= 1;
    }
    return res;
}
int main() {
    // fo("1");
    scanf("%d", &n);
    if (n < 9) {
        printf("0\n");
        return 0;
    }
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i][0] =
            (f[i - 1][0] * 25 + f[i - 1][1] * 24 + f[i - 1][2] * 25) % mod;
        f[i][1] = (f[i - 1][0] + f[i - 1][1]) % mod;
        f[i][2] = f[i - 1][1];
    }
    ans = f[n][0] + f[n][1] + f[n][2];
    for (int i = 3; i <= n; i++) {
        g[i][0] = (g[i - 1][0] * 25 + g[i - 1][1] * 24 + g[i - 1][2] * 25
                   + f[i - 1][2])
                  % mod;
        g[i][1] = (g[i - 1][0] + g[i - 1][1]) % mod;
        g[i][2] = g[i - 1][1];
    }
    ans += g[n][0] + g[n][1] + g[n][2], ans %= mod;
    for (int i = 3; i <= n; i++) {
        ans = (ans
               + (f[i - 3][0] + f[i - 3][1])
                     * (g[n - i][0] + g[n - i][1] + g[n - i][2]))
              % mod;
    }
    printf("%lld\n", (qp(26, n) - ans + mod) % mod);
    return 0;
}

T2

题意：
统计有多少种给 n×mn\times m 网格染上 kk 个黑色，其余白色的方案使得任意相邻两行或两列要么完全一致要么完全不同。

观察到行和列的限制要么都满足要么都不满足，因此只考虑列。
枚举其中一列的黑色个数 ii，则其余列要么 n−in-i 个要么 ii 个，有方程 x×i+(m−x)×(n−i)=kx\times i+(m-x)\times(n-i)=k，解得 x=k+m×(i−n)2×i−nx=\frac{k+m\times(i-n)}{2\times i-n}，有一个特例是 i×2=ni\times 2=n ，此时若 k×2=n×mk\times 2=n\times m 则答案为 (ni)2m\binom{n}{i}2^{m}，否则为 00。其余情况下判断方程是否有解，若有则贡献为 (ni)(mx)\binom{n}{i}\binom{m}{x}，最后由于枚举的是其中一列，答案要 ÷2\div2。

code\texttt{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
/**
 * @author : cyb1010
 * @date   : 2023-09-24 14:52:30
 * @file   : 2.cpp
 */
#include <bits/stdc++.h>
using namespace std;
#define fo(s) freopen(s ".in", "r", stdin), freopen(s ".out", "w", stdout)
#define fi first
#define se second
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
const int N = 10000000;
ll n, m, k, jc[N + 10], inj[N + 10], mod = 998244353, ans;
ll qp(ll x, ll k) {
    ll res = 1;
    while (k) {
        if (k & 1) res = res * x % mod;
        x = x * x % mod, k >>= 1;
    }
    return res;
}
ll c(ll x, ll y) { return jc[x] * inj[y] % mod * inj[x - y] % mod; }
int main() {
    // fo("2");
    scanf("%lld%lld%lld", &n, &m, &k), jc[0] = 1;
    for (int i = 1; i <= N; i++) jc[i] = jc[i - 1] * i % mod;
    inj[N] = qp(jc[N], mod - 2);
    for (int i = N; i; i--) inj[i - 1] = inj[i] * i % mod;
    for (int i = 0; i <= n; i++) {
        // x*i+(m-x)*(n-i)=k
        // 2*x*i+m*n-x*n-m*i=k
        // x*(2*i-n)=k+m*i-m*n
        if (i << 1 == n) {
            if (k << 1 == n * m) ans = (ans + c(n, i) * qp(2, m)) % mod;
            continue;
        }
        ll u = k + m * i - m * n, d = 2 * i - n;
        if (u % d) continue;
        ll x = u / d;
        if (x >= 0 && x <= m) ans = (ans + c(n, i) * c(m, x)) % mod;
    }
    printf("%lld\n", ans * 499122177 % mod);
    return 0;
}

T3

题意：
定义 f(x)=∏i=1xix−i+1f(x)=\prod\limits_{i=1}^{x}i^{x-i+1}，输出 f(n) (1≤n≤107)f(n)\ (1\le n\le 10^7) 分解质因数的结果。

收到 cspcsp 初赛启发，写个奇怪的筛子过了。

code\texttt{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
/**
 * @author : cyb1010
 * @date   : 2023-09-24 14:35:44
 * @file   : 3.cpp
 */
#include <bits/stdc++.h>
using namespace std;
namespace FastIO {
const std::size_t buf_size = 1 << 18;
char I[buf_size], *p1, *p2, O[buf_size], s[128];
int p, q, f;
inline char gc() {
    return p1 == p2 && (p2 = (p1 = I) + fread(I, 1, sizeof(I), stdin), p1 == p2)
               ? EOF
               : *p1++;
}
inline void pc(char c) { O[p++] = c; }
inline void flush() { fwrite(O, 1, p, stdout), p = 0; }
void chkf() {
    if (p >= buf_size >> 1) flush();
}
struct AutoFlush {
    ~AutoFlush() { flush(); }
} auto_flush;

template <typename T>
void rd(T &x) {
    char c = gc();
    x = 0, f = c == '-';
    while (!isdigit(c)) c = gc(), c == '-' ? f = 1 : 0;
    while (isdigit(c)) x = x * 10 + c - '0', c = gc();
    f ? x = -x : 1;
}
template <typename T>
void wr(T x) {
    if (x < 0) x = -x, pc('-');
    do s[++q] = (x % 10) | 48;
    while (x /= 10);
    do pc(s[q]);
    while (--q);
    chkf();
}
template <typename T>
void wr(T x, char c) {
    wr(x), pc(c);
}
} // namespace FastIO
using FastIO::rd;
using FastIO::wr;
using FastIO::pc;
#define fo(s) freopen(s ".in", "r", stdin), freopen(s ".out", "w", stdout)
#define fi first
#define se second
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
int n, tot, d[20];
ll tmp;
bool np[10000010];
int main() {
    // fo("3");
    rd(n);
    pc('f'), pc('('), wr(n, ')'), pc('=');
    if (n == 1) {
        wr(1, '\n');
        return 0;
    }
    for (int i = 2; i <= n; i++)
        if (!np[i]) {
            i > 2 && (pc('*'), 1), wr(i);
            if (i == n) continue;
            pc('^'), tmp = 0;
            for (int j = i, x = i, t = 0; j <= n; j += i, x = i, t = 0) {
                np[j] = true;
                while (j % x == 0) x *= i, t++;
                tmp += t * (n - j + 1);
            }
            wr(tmp);
        }
    return 0;
}

T4

题意：
小 UU 会 mm 种炼金术，能在 cic_i 时间内将 aia_i 金属变成 bib_i 金属(1≤ai,bi≤400)(1\le a_i,b_i\le 400)。 现在他又两串长度为 n(1≤n≤105)n(1\le n\le 10^5) 的项链 pp 和 q (1≤pi,qi≤400)q\ (1\le p_i,q_i\le 400)，要将两者变成一样（循环同构）的，输出 nn 种匹配方式（即 p1p_1 对应 q1q_1，q2q_2 等等 nn 种）的最小花费时间的平均值。

首先，将确定的两个金属变成一样的是简单的，floydfloyd 之后再简单 dpdp 即可。
其次，平均值，即总时间 ÷n\div n，即每一个 pip_i 变成每一个 pip_i 的总时间，观察到 pip_i 很小，因此做个桶 bucjbuc_j 统计多少个 pip_i 和多少 qiq_i 等于 jj 即可。

code\texttt{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
/**
 * @author : cyb1010
 * @date   : 2023-09-24 15:19:22
 * @file   : 4.cpp
 */
#include <bits/stdc++.h>
using namespace std;
#define fo(s) freopen(s ".in", "r", stdin), freopen(s ".out", "w", stdout)
#define fi first
#define se second
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
int n, m, cns[410], cnt[410];

int f[410][410], t[410][410];
void floyd() {
    memset(f, 0x3f, sizeof(f));
    memset(t, 0x3f, sizeof(t));
    while (m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        f[a][b] = min(f[a][b], c);
    }
    for (int i = 1; i <= 400; i++) f[i][i] = 0;
    for (int k = 1; k <= 400; k++)
        for (int i = 1; i <= 400; i++)
            for (int j = 1; j <= 400; j++)
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
    for (int i = 1; i <= 400; i++)
        for (int j = 1; j <= 400; j++)
            for (int k = 1; k <= 400; k++)
                t[i][j] = min(t[i][j], f[i][k] + f[j][k]);
}
int main() {
    // fo("4");
    scanf("%d%d", &n, &m);
    for (int i = 1, s; i <= n; i++) scanf("%d", &s), cns[s]++;
    for (int i = 1, t; i <= n; i++) scanf("%d", &t), cnt[t]++;
    floyd();
    ll ans = 0;
    for (int i = 1; i <= 400; i++)
        for (int j = 1; j <= 400; j++) {
            ans += t[i][j] * cns[i] * cnt[j];
        }
    printf("%.2lf\n", ans * 1. / n);
    return 0;
}

T5

题意：
有 nn 个石头，每个有颜色 aia_i，求所有相邻两个石头最小距离 ≤k\le k 的颜色的 xorxor 和。

签到题，按题意模拟即可。

code\texttt{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
/**
 * @author : cyb1010
 * @date   : 2023-09-24 14:21:01
 * @file   : 5.cpp
 */
#include <bits/stdc++.h>
using namespace std;
#define fo(s) freopen(s ".in", "r", stdin), freopen(s ".out", "w", stdout)
#define fi first
#define se second
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
int n, k, a[50010], id[50010], ans;
unordered_set<int> s;
bool cmp(int x, int y) { return a[x] == a[y] ? x < y : a[x] < a[y]; }
int main() {
    // fo("5");
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]), id[i] = i;
    }
    sort(id + 1, id + 1 + n, cmp);
    for (int _ = 2, i = id[2]; _ <= n; i = id[++_]) {
        if (a[i] == a[id[_ - 1]] && i - id[_ - 1] <= k
            && s.find(a[i]) == s.end())
            ans ^= a[i], s.insert(a[i]);
    }
    cout << ans << endl;
    return 0;
}

T6

题意：
小 UU 在打隔膜，要打 nn 关，第 ii 关有 mim_i 个血量为 aia_i 的怪，他可以放技能在 00 秒内打掉 kk 滴血，也可以在 11 秒内打掉 11 滴血，技能有 cdcd，在他普攻打死一个怪后 cdcd 会好，输出最小时间。

考虑dp。fi,j∈{0,1}f_{i,j\in{\{0,1\}}} 表示打完 ii 层技能 cdcd 是否好了的最小时间。
考虑转移，若 ai>ka_i>k，则必然先放技能再打普攻，fi,0=fi,1=min⁡(fi−1,1,fi−1,0+k)+(ai−k)×mif_{i,0}=f_{i,1}=\min(f_{i-1,1},f_{i-1,0}+k)+(a_i-k)\times m_i
若 ai≤ka_i\le k，则要考虑奇偶性，也是简单的，详见代码。

code\texttt{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
/**
 * @author : cyb1010
 * @date   : 2023-09-24 15:23:43
 * @file   : 6.cpp
 */
#include <bits/stdc++.h>
using namespace std;
#define fo(s) freopen(s ".in", "r", stdin), freopen(s ".out", "w", stdout)
#define fi first
#define se second
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
int n, a[100010], m[100010], k;
ll f[100010][2];
int main() {
    // fo("6");
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i], &m[i]);
        if (a[i] > k) {
            f[i][1] = f[i][0] =
                min(f[i - 1][0] + a[i] + 1ll * (a[i] - k) * (m[i] - 1),
                    f[i - 1][1] + 1ll * (a[i] - k) * m[i]);
            continue;
        }
        if (m[i] & 1) {
            f[i][0] = f[i][1] = f[i - 1][0] + (m[i] + 1ll >> 1) * a[i];
            f[i][0] = min(f[i][0], f[i - 1][1] + 1ll * (m[i] >> 1) * a[i]);
            f[i][1] = min(f[i][1], f[i - 1][1] + (m[i] + 1ll >> 1) * a[i]);
        } else {
            f[i][0] = f[i - 1][0] + 1ll * (m[i] >> 1) * a[i],
            f[i][1] = f[i][0] + a[i];
            f[i][0] = min(f[i][0], f[i - 1][1] + 1ll * (m[i] >> 1) * a[i]);
            f[i][1] = min(f[i][1], f[i - 1][1] + 1ll * (m[i] >> 1) * a[i]);
        }
    }
    printf("%lld\n", min(f[n][0], f[n][1]));
    return 0;
}

T7

如果没读错的话，是动态加关键点，查询到给定一点最远的关键点的欧几里得距离，查询的点每次给出。因为不太会所以没写，好像只有两个人过了。

T8

题意：
有 n (n=2k,1≤k≤20)n\ (n=2^k,1\le k\le20) 个人打淘汰赛，胜者晋级。有个赌鬼，在第 ii 个人身上赌了 bib_i 元，若第 ii 个人赢一场则会得回 bib_i 元，若第 ii 人夺冠会额外奖励 ai×bia_i\times b_i 元，aia_i 开始给出。动态修改 bib_i，查询最小收益。

首先贪心策略是让 bib_i 小的多赢，但是夺冠奖励会影响结果。于是可以线段树维护一个人赢到最后的答案，同时另用一个线段树维护区间最小收益。修改第 ii 人时，注意到与他在同一轮相遇的对手答案的变化量是一样的，于是只要修改 log⁡n\log n 段区间就行了，而这些对手又恰好对应线段树上的一个节点，因此只要修改 O(log⁡(n))O(\log(n)) 个节点的值即可。

code\texttt{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
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
/**
 * @author : cyb1010
 * @date   : 2023-09-24 16:11:31
 * @file   : 8.cpp
 */
#include <bits/stdc++.h>
using namespace std;
namespace FastIO {
const std::size_t buf_size = 1 << 18;
char I[buf_size], *p1, *p2, O[buf_size], s[128];
int p, q, f;
inline char gc() {
    return p1 == p2 && (p2 = (p1 = I) + fread(I, 1, sizeof(I), stdin), p1 == p2)
               ? EOF
               : *p1++;
}
inline void pc(char c) { O[p++] = c; }
inline void flush() { fwrite(O, 1, p, stdout), p = 0; }
void chkf() {
    if (p >= buf_size >> 1) flush();
}
struct AutoFlush {
    ~AutoFlush() { flush(); }
} auto_flush;

template <typename T>
void rd(T &x) {
    char c = gc();
    x = 0, f = c == '-';
    while (!isdigit(c)) c = gc(), c == '-' ? f = 1 : 0;
    while (isdigit(c)) x = x * 10 + c - '0', c = gc();
    f ? x = -x : 1;
}
template <typename T>
void wr(T x) {
    if (x < 0) x = -x, pc('-');
    do s[++q] = (x % 10) | 48;
    while (x /= 10);
    do pc(s[q]);
    while (--q);
    chkf();
}
template <typename T>
void wr(T x, char c) {
    wr(x), pc(c);
}
} // namespace FastIO
using FastIO::rd;
using FastIO::wr;
#define fo(s) freopen(s ".in", "r", stdin), freopen(s ".out", "w", stdout)
#define fi first
#define se second
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
int n, q, b[1100010], mn[2100010], a[1100010];
ll s[2100010], ans[2100010], tag[2100010];
void add(int p, int l, int r, int ll, int rr, long long k) {
    if (l > rr || r < ll) return;
    if (l >= ll && r <= rr) return ans[p] += k, tag[p] += k, void();
    int mid = l + r >> 1;
    add(p << 1, l, mid, ll, rr, k), add(p << 1 | 1, mid + 1, r, ll, rr, k);
    ans[p] = min(ans[p << 1], ans[p << 1 | 1]) + tag[p];
}
int build(int p, int l, int r) {
    if (l == r) return s[p] = mn[p] = b[l];
    int mid = l + r >> 1;
    mn[p] = min(build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r));
    return s[p] = s[p << 1] + s[p << 1 | 1] + mn[p], mn[p];
}
ll qry(int p, int l, int r, int x) {
    if (l == r) return b[x];
    int mid = l + r >> 1;
    if (x <= mid) return b[x] + s[p << 1 | 1] + qry(p << 1, l, mid, x);
    return b[x] + s[p << 1] + qry(p << 1 | 1, mid + 1, r, x);
}

void upd(int p, int l, int r, int k, int x) {
    if (l == r) {
        add(1, 1, n, k, k, 1ll * (x - b[k]) * (__lg(n) + a[k] + 1)),
            mn[p] = s[p] = x;
        return;
    }
    int mid = l + r >> 1;
    if (k <= mid) {
        tag[p << 1 | 1] -= s[p << 1], ans[p << 1 | 1] -= s[p << 1];
        upd(p << 1, l, mid, k, x);
        tag[p << 1 | 1] += s[p << 1], ans[p << 1 | 1] += s[p << 1];
    } else {
        tag[p << 1] -= s[p << 1 | 1], ans[p << 1] -= s[p << 1 | 1];
        upd(p << 1 | 1, mid + 1, r, k, x);
        tag[p << 1] += s[p << 1 | 1], ans[p << 1] += s[p << 1 | 1];
    }
    mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
    s[p] = s[p << 1] + s[p << 1 | 1] + mn[p];
    ans[p] = min(ans[p << 1], ans[p << 1 | 1]) + tag[p];
}

int main() {
    // fo("8");
    rd(n);
    for (int i = 1; i <= n; i++) rd(a[i]), a[i]--;
    for (int i = 1; i <= n; i++) rd(b[i]);
    build(1, 1, n);
    for (int i = 1; i <= n; i++)
        add(1, 1, n, i, i, qry(1, 1, n, i) + 1ll * a[i] * b[i]);
    rd(q);
    int id, d;
    while (q--) {
        rd(id), rd(d), upd(1, 1, n, id, b[id] + d), b[id] += d;
        wr(ans[1], '\n');
    }
    return 0;
}
#oi #sol
百度之星初赛第三场
https://cyb1010.github.io/2023/09/25/游记/百度之星初赛第三场/
作者
cyb1010
发布于
2023年9月25日
许可协议