2024杭电钉耙编程联赛Day1||补题

1001-循环位移

$(709/3775)$

题意

将字符串 $S=S_0+S_1+S_2+...+S_{n-1}$ 循环位移 $k$ 次后得到 $S(k)=S_{k\bmod n }+...+S_{n-1}+S+0+...+S_{(k-1)\bmod n}$ 。

定义 $[A]={A(k),k\in N}$ 。给出 $T$ 组串 $A,B$ ，询问 $B$ 有多少个子串在 $[A]$ 中。

数据范围

$|A|\leq |B|$
$\sum|B|\leq 1048576$

思路

思路1：字符串哈希

记字符串 $A$ 的长度是 $n$ ，将字符串 $A$ 转变为首尾相连的样子（ $A=A+A.substr(1,n-1)$ ），并计算其中每个长度为 $n$ 的哈希值，用map存值，再对字符串 $B$ 进行哈希，同样也对长度为 $n$ 的子串计算哈希值，若有符合的则计数。

代码

代码1：字符串哈希

1
ll ha[maxn], hb[maxn];
2
ll pwr[maxn];
3

4
void solve() {
5
    string a, b;cin >> a >> b;
6
    ll n = a.size();
7
    a = a.substr(1, n - 1) + a;
8
    ll la = a.size(), lb = b.size();
9
    a = " " + a, b = " " + b;
10
    pwr[0] = 1;
11
    map<ll, bool>mp;
12
    for (ll i = 1;i <= la;i++) {
13
        ha[i] = ha[i - 1] * bas1 + a[i];
14
        pwr[i] = pwr[i - 1] * bas1;
15
        if (i - n >= 0) {
16
            ll x = ha[i] - ha[i - n] * pwr[n];
17
            mp[x] = true;
18
        }
19
    }
20
    ll ans = 0;
21
    for (ll i = 1;i <= lb;i++) {
22
        hb[i] = hb[i - 1] * bas1 + b[i];
23
        if (i - n >= 0) {
24
            ll x = hb[i] - hb[i - n] * pwr[n];
25
            if (mp.count(x)) {
26
                ans++;
27
            }
28
        }
29
    }
30
    cout << ans << endl;
31
}

1002-星星

$(991/1659)$

题意

小 $A$ 有 $n$ 次获得星星的机会，第 $i$ 次有如下5种选择：

跳过
$a_i$ 的代价获得 $1$ 颗星星
$b_i$ 的代价获得 $2$ 颗星星
$c_i$ 的代价获得 $3$ 颗星星
$d_i$ 的代价获得 $4$ 颗星星

请问若想恰好获得 $k$ 颗星星，所需要的最小代价是多少。

数据范围

$1\leq n\leq 1000$
$0\leq k\leq n\times 4$
$0\lt a_i\leq b_i\leq c_i\leq d_i\leq 10^9$

思路

基础的动态规划。记 $dp[i]$ 表示获得 $i$ 颗星星的最小代价。

代码

1
ll a[maxn], b[maxn], c[maxn], d[maxn];
2
ll dp[4 * maxn];
3

4
void solve() {
5
    ll n, k;cin >> n >> k;
6
    for (ll i = 1;i <= n;i++) {
7
        cin >> a[i] >> b[i] >> c[i] >> d[i];
8
    }
9
    fill(dp, dp + 4 * maxn, inf);
10
    dp[0] = 0;
11
    for (ll i = 1;i <= n;i++) {
12
        ll m = min(k, 4 * i);
13
        for (ll j = m;j >= 0;j--) {
14
            if (j + 1 <= m)
15
                dp[j + 1] = min(dp[j] + a[i], dp[j + 1]);
16
            if (j + 2 <= m)
17
                dp[j + 2] = min(dp[j] + b[i], dp[j + 2]);
18
            if (j + 3 <= m)
19
                dp[j + 3] = min(dp[j] + c[i], dp[j + 3]);
20
            if (j + 4 <= m)
21
                dp[j + 4] = min(dp[j] + d[i], dp[j + 4]);
22
        }
23
    }
24
    cout << dp[k] << "\n";
25
}

1008-位运算

$(918/1427)$

题意

有多少在范围 $[0,2^k)$ 中的 $a,b,c,d$ 构成的四元组 $(a,b,c,d)$ 满足 $a \\& b\oplus c | d=n$ 。

数据范围

$1\leq T\leq 10$
$1\leq k\leq 15,0\leq n\lt 2^k$

思路

记 $x=a \\& b\oplus c | d$ ， $x$ 的每一位只有1和0的可能，而每位上的数字只和 $a,b,c,d$ 对应位是 $1$ 或 $0$ 有关，枚举四个数的 $1/0$ ，统计 $x$ 是 $0$ 的组合和是 $1$ 的组合的数量。再根据 $n$ 的 $k$ 位进行统计即可。

代码

1
void solve() {
2
    ll n, k;cin >> n >> k;
3
    ll cnt[2];cnt[0] = cnt[1] = 0;
4
    for (int i = 0;i <= 1;i++) {
5
        for (int j = 0;j <= 1;j++) {
6
            for (int k = 0;k <= 1;k++) {
7
                for (ll l = 0;l <= 1;l++) {
8
                    ll x = i & j ^ k | l;
9
                    cnt[x]++;
10
                }
11
            }
12
        }
13
    }
14
    vector<int>v;
15
    ll ans = 1;
16
    for (ll i = 0;i < k;i++) {
17
        v.push_back(n & 1);
18
        ans *= cnt[n & 1];
19
        n >>= 1;
20
    }
21
    cout << ans << "\n";
22
}

1012-并

$(241/1229)$

题意

给出在二维平面上的 $n$ 个矩形，随机选择 $k$ 个不同的矩形 $(k\in [1,n])$ ，求这 $k$ 个矩形所有覆盖部分的并集的面积的期望。

数据范围

$1\leq n\leq 2\times 10^3$
$1\leq x_{i,1}\lt x_{i,2} \leq 10^9$
$1\leq y_{i,1}\lt y_{i,2} \leq 10^9$

思路

将横纵坐标离散化之后可以将这 $n$ 个矩形覆盖的部分分割成不重叠的若干个小矩形，每个小矩形设置权值，代表被原来的 $n$ 个矩形覆盖的次数。设某个小矩形的覆盖次数是 $m$ ，则在选择 $k$ 个矩形时，这个小矩形的贡献是： $\frac{\binom{k}{n}-\binom{k}{n-m}}{\binom{k}{n}}$ （全集-选除该矩形以外的部分），预处理离散后的矩形以及被覆盖 $m$ 次的所有矩形的总面积，枚举计数即可。

代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef double ld;
5
const int maxn = 2050;
6
const int mo998 = 998244353;
7

8
struct Rec {
9
    ll x1, y1, x2, y2;
10
}a[maxn];
11

12
ll X[maxn * 2], Y[maxn * 2];
13

14
ll fact[maxn], invfact[maxn]; // 阶乘,阶乘逆元
15

16
ll qpow(ll a, ll b) {
17
    ll res = 1;
18
    while (b) {
19
        if (b & 1)res = res * a % mo998;
20
        b >>= 1;
21
        a = a * a % mo998;
22
    }
23
    return res;
24
}
25

26
ll inv(ll x) {
27
    return qpow(x, mo998 - 2);
28
}
29

30
void init() {
31
    // 预处理阶乘,阶乘逆元
32
    fact[0] = invfact[0] = 1ll;
33
    for (int i = 1;i < maxn;i++) {
34
        fact[i] = fact[i - 1] * i % mo998;
35
        invfact[i] = invfact[i - 1] * inv(i) % mo998;
36
    }
37
}
38

39
ll C(int n, int k) {
40
    // n选k的方案数
41
    if (k > n)return 0ll;
42
    ll res = fact[n] * invfact[k] % mo998 * invfact[n - k] % mo998;
43
    return res;
44
}
45

46
ll Stot[maxn], rec[2 * maxn][2 * maxn];
47

48
void solve() {
49
    int n;cin >> n;
50
    for (int i = 1;i <= n;i++) {
51
        ll x1, y1, x2, y2;
52
        cin >> x1 >> y1 >> x2 >> y2;
53
        a[i] = { x1,y1,x2,y2 };
54
        X[i] = x1, X[i + n] = x2;
55
        Y[i] = y1, Y[i + n] = y2;
56
    }
57
    sort(X + 1, X + 1 + 2 * n);
58
    sort(Y + 1, Y + 1 + 2 * n);
59
    int t1 = unique(X + 1, X + 1 + 2 * n) - X - 1;
60
    int t2 = unique(Y + 1, Y + 1 + 2 * n) - Y - 1;
61
    for (int i = 1;i <= n;i++) {
62
        auto [x1, y1, x2, y2] = a[i];
63
        x1 = lower_bound(X + 1, X + 1 + t1, x1) - X; // 值x1在X[]中的位置
64
        x2 = lower_bound(X + 1, X + 1 + t1, x2) - X;
65
        y1 = lower_bound(Y + 1, Y + 1 + t2, y1) - Y;
66
        y2 = lower_bound(Y + 1, Y + 1 + t2, y2) - Y;
67
        // 差分计数
68
        rec[x1][y1]++, rec[x2][y1]--;
69
        rec[x1][y2]--, rec[x2][y2]++;
70
    }
71
    for (int i = 1;i <= t1;i++) {
72
        for (int j = 1;j <= t2;j++) {
73
            rec[i][j] += rec[i - 1][j] + rec[i][j - 1] - rec[i - 1][j - 1];
74
        }
75
    }
76
    for (int i = 1;i < t1;i++) {
77
        for (int j = 1;j < t2;j++) {
78
            // 覆盖rec[i][j]次的矩形的面积
79
            Stot[rec[i][j]] += (X[i + 1] - X[i]) * (Y[j + 1] - Y[j]) % mo998;
80
            Stot[rec[i][j]] %= mo998;
81
        }
82
    }
83

84

85
    for (int k = 1;k <= n;k++) {
86
        ll ans = 0, Cnk = C(n, k);
87
        ll iCnk = inv(Cnk);
88
        for (int i = 1;i <= n;i++) {
89
            ll Si = Stot[i];
90
            ans += (Cnk - C(n - i, k) + mo998) % mo998 * iCnk % mo998 * Si % mo998;
91
            ans %= mo998;
92
        }
93
        cout << ans << "\n";
94
    }
95
}
96

97
int main() {
98
    ios::sync_with_stdio(false);
99
    cin.tie(0);
100
    init();
101
    int t = 1;
102
    // cin >> t;cin.tie(0);
103
    while (t--)
104
        solve();
105

106
    return 0;
107
}