比赛题单：2024“钉耙编程”中国大学生算法设计超级联赛（1）

(1001)HDU7433.循环位移

字符串

题意

给定两个字符串 A,B 。
定义 [A] 为字符串 A 的循环位移任意次可以得到的所有字符串的集合。
求 B 包含 [A] 中元素的个数。

解题思路

利用字符串Hash快速匹配。
将 [A] 中所有元素的Hash记录到一个set：计算 A+A 的Hash前缀和，以快速得到所有长度为 |A| 的子串的Hash值，并加入set中。
枚举 B 的所有长度为 |A| 的子串，计算Hash值，判断是否在set中，计数。

参考程序

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve()
{
    string a,b;
    cin >> a >> b;
    ll n=a.length(),m=b.length();
    set<pll> st;
    strHash sa(a+a);
    FORLL(i,1,n)
        st.insert(sa.findz(i,i+n-1));
    strHash sb(b);
    ll ans = 0 ;
    FORLL(i,1,m-n+1)
        if(st.count(sb.findz(i,i+n-1))) ans++;
    cout << ans << endl;
}

(1002)HDU7434.星星

背包DP

题意

小A要进行n次选择，每次可以选择一项：

  1. 不执行操作
  2. 付出ai点代价得到1颗星星
  3. 付出bi点代价得到2颗星星
  4. 付出ci点代价得到3颗星星
  5. 付出di点代价得到4颗星星

求恰好得到k颗星星的最小代价。

解题思路

一眼顶针鉴定为背包DP的分组背包问题。

$dpx表示选x个物品的最低cost。在第i组时，从大到小遍历作出选择后有j个星星。遍历这一步的选择（l个星星），从dp{j-l}更新到dp_j$ ，这样更新保证了一次操作只生效一项。

参考程序

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve()
{
    ll n,k;cin >> n >> k;
    vector<array<ll,5>> cost(n,{0,0,0,0,0});
    vector<ll> dp(k+1,INF); dp[0]=0; //选i个物品的最低cost
    FORLL(i,0,n-1) cin >> cost[i][1] >> cost[i][2] >> cost[i][3] >> cost[i][4];
    FORLL(i,0,n-1){ //第i步
        FORLL_rev(j,k,1){ //选择后的个数
            FORLL(l,0,4){ //这一步选择l个
                if(j-l>=0) chmin(dp[j],dp[j-l]+cost[i][l]);
            }
        }
    }
    cout << dp[k] << endl;
}

(1008)HDU7440.位运算

题意

给定整数n,k，求满足 ((a⊗b)⊕c)⊖d=n 的四元组 (a,b,c,d)，0≤a,b,c,d<2k 的个数。

其中，⊗ 表示按位与，⊕ 表示按位异或，⊖ 表示按位或。

解题思路

转为二进制，按位考虑。

若 n 的某一位上是 0 ， d 在这一位上必须为 0 ，c 在这一位上由 a,b 决定（控制这一位为 0），a,b 在这一位上任选，即 1×1×2×2=4 种可能。

若 n 的某一位上是 1 ：

  1. 若 d 在这一位上为 0 ，则 c 在这一位上由 a,b 决定（控制这一位为 1），a,b 在这一位上任选，即 1×1×2×2=4 种可能。
  2. 若 d 在这一位上为 1 ，则 a,b,c 在这一位上任选，即 1×2×2×2=8 种可能。

综上，n 的一位上是 1 时有 12 种可能，是 0 时有 4 种可能。

答案为 4k×3cnt1 。

参考程序

cpp
1
2
3
4
5
6
7
8
9
10
11
void solve()
{
    ll n,k;
    cin >> n >> k;
    ll cnt1=0;
    while(n){
        if(n%2) cnt1++;
        n/=2;
    }
    cout << qcpow(2,k*2)*qcpow(3,cnt1) << endl;
}

(1012)HDU7444.并

题意

给定 n 个矩形，对 k=1→n 分别求随机取 k 个矩形的面积并的期望。

解题思路

平面可以被矩形边界分割成若干个小区域，考虑每个区域对答案的贡献。

因为要求期望，被“相同数量矩形覆盖”的小区域 对答案的贡献是相同的，因此按照 覆盖矩形数量 将这些小区域分组，统计出恰好被 i 个矩形覆盖的区域的面积 Si。

我的求法就是从左到右扫描，在每条竖线的位置，更新 i 个矩形覆盖的y轴长度 yvali ，到下一条竖线再乘经过的x轴长度，得到这一部分的面积（类似于积分？），加入 Si

然后考虑贡献的权重。
从 n 个矩形中随机选取 k 个，对于被 i 个矩形覆盖的区域，只要选取的 k 个矩形中，存在这 i 个矩形之一，那么这个面积就会被计入。
在上述条件下的贡献权重是 $val{k,i}=\frac{C{n}^{k}-C{n-i}^{k}}{C{n}^{k}}，即从n个矩形中选取k个方案数，减去从n-i个矩形中选取k$ 个方案数。

最后答案$ansk是\sum\limits{i=1}^{n}val_{k,i}\times S_i$ 。

参考程序

cpp
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
void prepare(){
    Prepare_Combination(5005);
    MOD = 998244353;
}
ll getval(ll n,ll i,ll j){
    ll ret=C[n][i],sb;
    if(i>n-j) sb=0;
    else sb = C[n-j][i];
    return sub(ret,sb);
}
void solve()
{
    ll n;cin >> n;
    ll xx1,xx2,yy1,yy2;
    vector<tuple<ll,ll,ll,ll>> xlines;
    vector<ll> ylines;
    // xline:(y,x1,x2,flag) # 横线 flag:0上边界1下边界
    // yline:(x) # 竖线x坐标
    FORLL(i,1,n)
    {
        cin >> xx1 >> yy1 >> xx2 >> yy2;
        xlines.emplace_back(yy1,xx1,xx2,0);
        xlines.emplace_back(yy2,xx1,xx2,1);
        ylines.emplace_back(xx1);
        ylines.emplace_back(xx2);
    }
    SORT(xlines); SORT(ylines);

    map<ll,ll> S,yval;
    ll prex=0;
    // S[i]:重叠i次部分的面积
    for(auto xx:ylines)
    {
        ll difx = xx-prex;
        for(auto [pl,val]:yval)
        {
            // S[pl]+=difx*val;
            addto(S[pl],mul(difx,val));
        }
        yval.clear();
        ll cur = 0, prey = 0;
        for(auto [yy,xx1,xx2,flag]:xlines)
        {
            if(xx1<=xx&&xx<xx2)
            {
                yval[cur]+=yy-prey;
                if(flag==0) cur++;
                else cur--;
                prey=yy;
            }
        }
        prex = xx;
    }
    // for(auto x:S) cout << x.first << ' ' << x.second << endl;

    FORLL(i,1,n){
        ll ans = 0;
        FORLL(j,1,n){
            ll val = getval(n,i,j);
            ans = add(ans,mul(val,S[j]));
        }
        divto(ans,C[n][i]);
        cout << ans << endl;
    }
}