20250728总结

· · 个人记录

除了改题以外没干啥事，是不是废了/ll

P3643 [APIO2016] 划艇

动态规划：13 组合计数：9我用脚填的数值

神仙题目。

想到了离散化+前缀和，可惜组计没推出来，然后写了个暴力。

一个比较好想到的dp：设 f_{i,j} 表示第 i 个学校出 j 艘划艇的方案数，则 f_{i,j} = \sum\limits_{k = 0}^{i - 1}\sum\limits_{l = 1}^{j - 1}{f_{k,l}}(a_i \leq j \leq b_i)。复杂度 O(n^2b^2)。

稍加思考可以想到前缀和优化，即设 g_{i,j} = \sum\limits_{k = 1}^{j}{f_{i,k}}，则 f_{i,j} = \sum\limits_{k = 0}^{i - 1}{g_{k,j - 1}}(a_i \leq j \leq b_i)，复杂度 O(n^2b)。当然你还可以上二维前缀和，强行优化到 O(nb)，但 b 太大，这么写没什么含义。

不过 n 比较小，考虑在 n 上做文章。

首先 a_i,b_i 太大，离散化是必然的。离散化后的 b \leq 2n，结合前缀和优化可以做到 O(n^3)（这个时候因为某些原因就不能用二维前缀和了），然而递推式不能照搬，要重新推。

首先我们新 f_{i,j} 的含义为第 i 个学校出的划艇数在 j 所代表的区间内（即 [lsh_j,lsh_{j + 1})，其中 lsh 是离散化用的数组）的方案数，此时答案的构成相对复杂一些，不过总体可分为两部分：

一部分是划艇数 < lsh_j 的。对于这一部分，答案其实就是 \sum\limits_{k = 0}^{i - 1}{g_{k,j - 1}}，此时 k 是你枚举的最后一个 < lsh_j 的位置。

另一部分则是划艇数 \geq lsh_j 或不出划艇的（假设这里包括 i 本身有 m 个学校），这一部分相对难算一些，因为看上去每一个位置能取什么数都取决于上一个位置的数，难以处理。

但之前某一天里的总结写到过，这种取的数必须递增的情况可以把取的数放桶里，然后就变成了排列组合问题，此处同理。

当我们多开 m - 1 个 0 位置的桶时（减一是因为 i 自己不能为 0），此时就变成了在 lsh_{j + 1} - lsh_j + m - 1 个数中选 m 个数了，也就是 C_{len_j + m - 1}^{m}（len_j = lsh_{j + 1} - lsh_j）。

根据乘法原理，两部分合并后的答案为：

f_{i,j} = \sum\limits_{k = 0}^{i - 1}{g_{k,j - 1}} C_{len_j + m - 1}^{m}

因为 len_j 比较大，无法直接预处理组合数，所以可以令 c_i = C_{len_j + i - 1}^{i}，然后在最外层枚举 j，内层枚举 i，在内层递推计算 c_i。（同时这么做也方便计算 m。）

int main(){
    n = read();
    for(i = 1; i <= n; i++){
        a[i] = read(),b[i] = read() + 1;
        lsh[++m] = a[i],lsh[++m] = b[i];
    }
    inv[1] = 1;
    for(i = 2; i <= n; i++){
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    }
    sort(lsh + 1,lsh + m + 1);
    m = unique(lsh + 1,lsh + m + 1) - lsh - 1;
    for(i = 1; i <= n; i++){
        a[i] = lower_bound(lsh + 1,lsh + m + 1,a[i]) - lsh;
        b[i] = lower_bound(lsh + 1,lsh + m + 1,b[i]) - lsh;
    }
    c[0] = 1;
    f[0][0] = g[0][0] = 1;
    for(j = 1; j < m; j++){
        int1 len = lsh[j + 1] - lsh[j];
        for(i = 1; i <= n; i++){
            c[i] = c[i - 1] * (i + len - 1) % mod * inv[i] % mod;
        }
        for(i = 0; i <= n; i++){
            if(a[i] <= j && j < b[i]){
                int1 _m = 1;
                for(k = i - 1; k >= 0; k--){
                    f[i][j] = (f[i][j] + c[_m] * g[k][j - 1]) % mod;
                    if(a[k] <= j && j < b[k]){
                        _m++;
                    }
                }
            }
            g[i][j] = (g[i][j - 1] + f[i][j]) % mod;
        }
    }
    for(i = 1; i <= n; i++){
        ans = (ans + g[i][m - 1]) % mod;
    }
    pe(ans);
    return 0;
}

P3043 [USACO12JAN] Bovine Alliance G

哇好水的蓝题（（（

你个fvv，四十多分钟才想出来

首先 m < n，所以很有可能存在图不联通的情况；同时发现对于每个连通块答案是相互独立的，所以先考虑单个连通块的情况。

假设一个连通块有 x 个点，y 条边。

各部分答案相乘即可。

void add_edge(int1 x,int1 y){
    nex[++bs] = hea[x],hea[x] = bs,to[bs] = y,in[y]++;
    return ;
}
int1 dfs(int1 x){
    already++;
    int1 cnt = in[x];
    vis[x] = 1;
    for(int1 i = hea[x]; i; i = nex[i]){
        int1 y = to[i];
        if(!vis[y]){
            cnt += dfs(y);
        }
    }
    return cnt;
}
int main(){
    n = read(),m = read();
    for(i = 1; i <= m; i++){
        int1 x = read(),y = read();
        add_edge(x,y),add_edge(y,x);
    }
    ans = 1;
    for(i = 1; i <= n; i++){
        if(!vis[i]){
            int1 y = dfs(i) >> 1;
            int1 x = already - last;
            if(x < y){
                putchar('0');
                return 0;
            }else if(x == y){
                ans = (ans << 1) % mod;
            }else{
                ans = ans * x % mod;
            }
            last = already;
        }
    }
    pe(ans);
    return 0;
}

P4160 [SCOI2009] 生日快乐

初看不好做，然而实际上因为 n 很小，且必须切 n - 1 刀，所以可以直接爆搜乱切（（（

double cut(double x,double y,int1 n){
    if(n == 1){
        return max(x,y) / min(x,y);
    }
    double ans = INF;
    double _x = x / n,_y = y / n;
    for(int1 i = 1,j = n - 1; i < n; i++,j--){//枚举两边切的份数
        ans = min(ans,max(cut(x,_y * i,i),cut(x,_y * j,j)));
        ans = min(ans,max(cut(_x * i,y,i),cut(_x * j,y,j)));
    }
    return ans;
}
int main(){
    x = read(),y = read(),n = read();
    printf("%.6lf\n",cut(x,y,n));
    return 0;
}

P9751 [CSP-J 2023] 旅游巴士

这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？这是绿？

这我场切个己卯啊/ll

发现 k 不大，以及因为有时间是 k 的倍数的硬性要求，所以可以尝试用分层图的思路跑最短路，人话就是 dis_{i,j} 记录在第 i 个点 t \bmod k = j 时用时 t 的最小值。

但问题来了：a_i 怎么处理？

死盯样例可以发现我们可以在起点等 k 的倍数的时间，碰到 a_i 时若 t < a_i 就把边权暂且看作 1 + \left\lceil \frac{a_i - t}{k}\right\rceil\times k。然后缔结斯特拉结束。

int main(){
    n = read(),m = read(),k = read();
    for(i = 1; i <= m; i++){
        int1 x = read(),y = read(),z = read();
        add_edge(x,y,z);
    }
    for(i = 1; i <= n; i++){
        for(j = 0; j < k; j++){
            dis[i][j] = INF;
        }
    }
    dis[1][0] = 0;
    q.push(make_pair(0,1));
    while(!q.empty()){
        int1 now = q.top().second,bzd = q.top().first;
        q.pop();
        if(!vis[now][bzd % k]){
            vis[now][bzd % k] = 1;
            for(i = hea[now]; i; i = nex[i]){
                int1 y = to[i],w = bzd + 1 + max(0,(t[i] - bzd + k - 1) / k * k);
                if(dis[y][w % k] > w){
                    dis[y][w % k] = w;
                    q.push(make_pair(w,y));
                }
            }
        }
    }
    if(dis[n][0] == INF){
        pe(-1);
    }else{
        pe(dis[n][0]);
    }
    return 0;
}