啦啦啦~

考试

粉刷匠

这个粉刷匠不是第一天 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

2019.8.9 集训解题报告

2019.8.9 集训解题报告

考试

粉刷匠

迷路

游戏

windy数

总结