2019.8.9 集训解题报告
浏览 338 | 评论 0 | 字数 5989
Snowflake_Pink
2019年08月09日
  • 啦啦啦~


    考试

    粉刷匠

    这个粉刷匠不是第一天 A 组的粉刷匠,不会用 $dp$ 的喔死磕半个多小时才把方程列出来,应该是:

    $$ f[i][j][k]=max \{ f[i][j-1][k] + val, f[i][j-1][k-1] + val \} $$

    我不知道是不是对的,最后收集答案时使用 $dfs$ 枚举,只加了一个最优化剪枝。


    好的,是错的。QAQ

    今天这道提高 B 组的 T1 在洛谷的难度是:这让我的心态有了一点 小小 的变化 qwq

    这题预处理一下就可以转换成一个背包问题,因为我不会,所以我也不知道 $dalao$ 们是怎么想出来的,只能原样照搬 qwq

    首先设计状态:

    • $f[i][k]$ :表示前 $i$ 条木板一共粉刷 $k$ 次后的最大合法格子数
    • $w[i][j][k]$ :表示在第 $i$ 条木板上涂完前 $j$ 个格子后用了 $k$ 次粉刷的最大合法格子数

    那么只需要预处理出 $w[i][j][k]$ ,就可以像背包问题一样转移 $f[i][j]$ 了。

    对于 $f[i][j]$ 的转移,是显而易见的(在处理出 $w[i][j][k]$ 以后):

    $$ f[i][j] = max \{ f[i][j], f[i-1][j]+w[i][m][k] \} $$

    其中:

    • $m$ 是固定的,表示一行多少个
    • $k$ 是不一定的,因为不知道刷多少次,所以要枚举一遍

    对于 $w[i][j][k]$ 的预处理,在枚举 $i$ 、$j$ 、$k$ ,更新出最大值。对于计算更新后作出的贡献,可以加一个前缀和来方便计算。

    设 $sum[i][j]$ 等于第 $i$ 行,前 $j$ 个蓝色格子(蓝色是 1 ,方便加)的个数。

    那么对于一个区间中的红色格子:

    $$ red[l,r]=sum[i][r]-sum[i][l] $$

    对于一个区间的蓝色格子:

    $$ blue[l,r]=(r-l)-(sum[i][r]-sum[i][l]) $$

    那么对于 $w[i][j][k]$ 的处理:

    $$ w[i][j][k]=max \{ w[i][j][k], w[i][l][k-1]+max \{ sum[i][j]-sum[i][l], (j-l)-(sum[i][j]-sum[i][l] \} \} $$

    然后就完成了~~

    $Test's$ $Code$:0%

    #include <iostream>
    #include <cstdio>
    #include <cmath>
    
    using namespace std;
    const int MAXN = 50 + 5;
    const int MAXM = 50 + 5;
    const int MAXT = 25e2 + 5;
    
    int n, m, T, ans;
    int f[MAXN][MAXM][MAXT], col[MAXN][MAXM][MAXT];
    int g[MAXN][MAXM], s[MAXN], Max[MAXN];
    
    void dfs (int i, int k, int cnt) {
        if (i > n) {
            ans = max (ans, cnt);
            return;
        }
        if (cnt + s[i] <= ans) {
            return;
        }
        if (i == n) {
            dfs (i + 1, 0, cnt + f[i][m][k]);
            return;
        }
        
        for (int j = 0; j <= k; j++) {
            dfs (i + 1, k - j, cnt + f[i][m][j]);
        }
        return;
    }
    
    int main() {
        scanf ("%d%d%d", &n, &m, &T);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char ch;
                cin >> ch;
                g[i][j] = ch - '0';
            }
        }
        
        for (int k = 1; k <= T; k++) {
            for (int i = 1; i <= n; i++) {
                if (k == 1) {
                    f[i][1][k] = 1;
                    col[i][1][k] =    g[i][1];
                }
                for (int j = k + 1; j <= m; j++) {
                    int x = f[i][j - 1][k] + (g[i][j] == (col[i][j - 1][k]) ? 1 : 0);
                    int y = f[i][j - 1][k - 1] + (g[i][j] == (1 - col[i][j][k - 1]) ? 1 : 0);
                    if (x > y) {
                        f[i][j][k] = x;
                        col[i][j][k] = col [i][j - 1][k];
                    }
                    else {
                        f[i][j][k] = y;
                        col[i][j][k] = 1 - col[i][j - 1][k - 1];
                    }
                }
            }
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cout <<i<<" "<<j<<endl;
                for (int k = 1; k <= T; k++) {
                    cout <<f[i][j][k]<<" ";
                }
                cout <<endl;
            }
            cout <<endl;
        }
        
        for (int i = 1; i <= n; i++) {
            for (int k = 1; k <= T; k++) {
                Max[i] = max (Max[i], f[i][m][k]);
            }
        }
        
        for (int i = n; i >= 1; i--) {
            s[i] = s[i + 1] + Max[i];
        }
        
        dfs (1, T, 0);
        
        printf ("%d\n", ans);
        return 0;
    }

    $Fixed$ $Code$:100%

    #include <iostream>
    #include <cstdio>
    
    using namespace std;
    const int MAXN = 50 + 5;
    const int MAXM = 50 + 5;
    const int MAXT = 25e2 + 5;
    
    int n, m, t, a[MAXN][MAXM];
    int f[MAXN][MAXT], w[MAXN][MAXM][MAXT], sum[MAXN][MAXM];
    
    int main() {
        scanf ("%d%d%d", &n, &m, &t);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char ch;
                cin >>ch;
                a[i][j] = ch - '0';
                sum[i][j] = sum [i][j - 1] + a[i][j];
            }
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = 1; k <= m; k++) {
                    for(int l = k - 1; l <= j - 1; l++) {
                        w[i][j][k] = max (w[i][j][k], w[i][l][k - 1] + max (sum[i][j] - sum[i][l], (j - l) - (sum[i][j] - sum[i][l])));
                    }
                }
            }
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= t; j++) {
                for (int k = 0; k <= min (j, m); k++) {
                    f[i][j] = max (f[i][j], f[i - 1][j - k] + w[i][m][k]);
                }
            }
        }
        
        printf ("%d\n", f[n][t]);
        return 0;
    }

    迷路

    什么倍增 + $Floyd$ + 矩阵快速幂???

    等我学完矩阵快速幂再说 QAQ

    游戏

    这道题又是被几天前那个小学生巨佬讲解的 qwq,我要自闭了.....

    题目要一个字符串还原,可以发现每一个数字都是会回到起点的,也就是一个循环,要想要他们都同时回到原处,就是求这些循环长度的最小公倍数。


    网上很多都说了类似的一段话:

    对于所有的环长 $L_i$ ,一定有 $\sum\limits_{i=1}^{n} L_i = n$。 ---网络

    样例不就是 $3+3+3+2+2+1=14 \neq 6$ 吗?


    好的,我太菜了,写完才反应过来,对于样例,有 (1,2,3)(4,5)(6) 这三组环。意思不是每个数的循环 qwq

    emm,这样,问题就转化成:在 $n$ 的所有正整数拆分中,有多少个不相同的最小公倍数。

    最小公倍数是可以转化为各个质因子的乘积的,这样,只要枚举质因子及其的幂,就一定可以枚举出不一样的最小公倍数。因为质因子可以取很多个,所以这就可以转换为完全背包问题。

    先设一个二维的状态:$f[i][j]$ 表示前 $i$ 个质数的和为 $j$ 的情况数。

    这样就可以很轻松的得出转移方程:

    $$ f[i][j] = \sum\limits_{k=0}^{j-p_i^k \geq 0} f[i-1][j-p_i^k] $$

    然后就可以倒一下循环的顺序就可以把二维降为一维,还有记得最后再循环一遍统计答案。

    还有一点需要注意,对于 $n$ 的 “拆分”,其实 “拆分" 的各数之和小于 $n$ 也没有关系,因为可以用 1 补。

    $Test's$ $Code$:30% ($\frac{12}{1000}$ 的打表还有 30 分,数据太感动(shui)了)

    #include <iostream>
    #include <cstdio>
    
    using namespace std;
    const int MAXN = 1e3 + 5;
    
    int n, a[MAXN];
    
    int main() {
        scanf ("%d", &n);
        a[1] = 1;
        a[2] = 2;
        a[3] = 3;
        a[4] = 4;
        a[5] = 6;
        a[6] = 6;
        a[7] = 9;
        a[8] = 11;
        a[9] = 14;
        a[10] = 16;
        a[11] = 20;
        a[12] = 23;
        printf ("%d\n", a[n]);
        return 0;
    }

    $Fixed$ $Code$:100%

    #include <iostream>
    #include <cstdio>
    
    using namespace std;
    const int MAXN = 1e3 + 5;
    
    int n, p[MAXN], cnt;
    long long f[MAXN], ans;
    int main() {
        scanf ("%d", &n);
        
        p[++cnt] = 2;
        for (int i = 3; i <= n; i += 2) {
            int flag = true;
            for (int j = 1; j <= cnt; j++) {
                if (i % p[j] == 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                p[++cnt] = i;
            }
        }
        
        f[0] = 1;
        for (int i = 1; i <= cnt; i++) {
            for (int j = n; j >= p[i]; j--) {
                int temp = p[i];
                while (temp <= j) {
                    f[j] += f[j - temp];
                    temp *= p[i];
                }
            }
        }
        
        for (int i = 0; i <= n; i++) {
            ans += f[i];
        }
        printf ("%lld\n", ans);
        return 0;
    }

    windy数

    听 $dalao$ 们说都是数位 $dp$ 的模板题,但是数位 $dp$ 喔不会啊 qwq

    似乎差不多就是把每位分开来模拟 $dp$。


    总结

    失败的一天,没有订完题。QAQ

    本文作者:Snowflake_Pink
    本文链接:https://snowflake.pink/archives/77/
    最后修改时间:2020-04-14 08:59:38
    本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!
    评论
    评论会由可爱的 AI 来审核鸭~
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论