2019-08-09 纪中NOIP模拟赛B组

柔光的暖阳◎ 2021-11-02 06:20 354阅读 0赞

**T1 \[JZOJ1035\] 粉刷匠**

**题目描述**

windy有N条木板需要被粉刷。

每条木板被分为M个格子。

每个格子要被刷成红色或蓝色。

windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。

每个格子最多只能被粉刷一次。

如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？

一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

**数据范围**

$1 \\leq N,M \\leq 50$，$0 \\leq T \\leq 2500$

**分析**

**　　**没错，这就是个DP

设 $f\[i\]\[j\]$ 表示前 $i$ 条木板粉刷 $j$ 次最多粉刷正确的格子数，$h\[i\]\[j\]$ 表示第 $i$ 行粉刷 $j$ 次最多粉刷正确的格子数

显然 $f\[i\]\[j\]= \\mathop\{max\}\\limits\_\{0 \\leq k \\leq m\} \\\{ f\[i-1\]\[j-k\]+h\[i\]\[k\] \\\}$

然后考虑怎么预处理出 $h$ 数组

由于直接从 $h\[i\]\[j-1\]$ 转移到 $h\[i\]\[j\]$ 是很困难的，所以可以加一维 $k$ 表示刷完第 $i$ 条木板的前 $k$ 个格子

每新一次粉刷的颜色应为粉刷区间内格子最多的颜色

于是状态转移方程为 $$h\[i\]\[j\]\[k\]= \\mathop\{max\}\\limits\_\{j-1 \\leq l < k\} \\\{ h\[i\]\[j-1\]\[l\]+max(b\[i\]\[k\]-b\[i\]\[l\],k-l-(b\[i\]\[k\]-b\[i\]\[l\])) \\\}$$

$b\[i\]\[j\]$ 表示第 $i$ 行前 $j$ 个格子中要粉刷成蓝色的个数，这个可以在输入的时候处理

最后在 $f$ 数组的转移时，倒序枚举 $j$ 可以降掉第一维 $i$

我还预处理了每条木板最多粉刷的次数，然后成了考场上跑的最快的代码

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    using namespace std;
    #define ll long long
    #define inf 0x3f3f3f3f
    #define N 55
    #define T 2505
    
    int n, m, t;
    int f[T], g[N][N], h[N][N][N];
    int sum[N], pre[N], blue[N][N];
    char s[N];
    
    int main() {
        scanf("%d%d%d", &n, &m, &t);
        for (int i = 1; i <= n; i++) {
            scanf("%s", s + 1);
            for (int j = 1; j <= m; j++) {
                if (s[j] == '0') blue[i][j] = blue[i][j - 1];
                else g[i][j] = 1, blue[i][j] = blue[i][j - 1] + 1;
            }
        }
        for (int i = 1; i <= n; i++) {
            sum[i] = 1;
            for (int j = 2; j <= m; j++)
                if (g[i][j] != g[i][j - 1]) sum[i]++;
            pre[i] = pre[i - 1] + sum[i];
        }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= sum[i]; j++)
                for (int l = 1; l <= m; l++)
                    for (int k = j - 1; k < l; k++)
                        h[i][j][l] = max(h[i][j][l], h[i][j - 1][k] +
                         max(blue[i][l] - blue[i][k], l - k - (blue[i][l] - blue[i][k])));
        for (int i = 1; i <= n; i++)
            for (int j = pre[i]; j; j--)
                for (int k = 1; k <= j && k <= sum[i]; k++)
                    f[j] = max(f[j], f[j - k] + h[i][k][m]);
        while (!f[t]) t--;
        printf("%d\n", f[t]);
        
        return 0;
    }

**T2 \[JZOJ1036\] 迷路**

**题目描述**

windy在有向图中迷路了。

该有向图有N个节点，windy从节点0出发，他必须恰好在T时刻到达节点N-1。

现在给出该有向图，你能告诉windy总共有多少种不同的路径吗？

注意：windy不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。

**数据范围**

$2 \\leq N \\leq 10$，$1 \\leq T \\leq 10^9$

**分析**

连续两次考矩阵乘法，想不到想不到

矩阵乘法有这么一个定理：

一个存图（边权均为 $1$）的矩阵 $m$ 自乘 $k$ 次后，$m\[i\]\[j\]$ 就表示从 $i$ 到 $j$ 走 $k$ 步的路径数

但是这题比较难搞的就是，每条边的边权可能是 $0 \\sim 9$ 中的任意值

然后有了个神奇操作——分点（或者是说把每条边拆开），这样矩阵内所有边权都为 $0$ 或 $1$，第 $i$ 个点就被分为了 $10 \\times i+j \\, (1 \\leq j \\leq 9)$

对于一条边 $(u,v,w)$，我们需要先将 $10 \\times u+1 \\sim w$ 中的所有点连接，再把 $10 \\times u+w$ 和 $10 \\times v+1$ 连起来

于是原矩阵就转化为了一个 $0/1$ 矩阵，后面也就很简单了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    using namespace std;
    #define ll long long
    #define inf 0x3f3f3f3f
    #define N 105
    
    int n, t;
    char s[N];
    const int mod = 2009;
    
    struct Mat {
        int m[N][N];
        Mat() {memset(m, 0, sizeof m);}
    } x;
    
    Mat mul(Mat a, Mat b) {
        Mat c;
        for (int i = 0; i < 10 * n; i++)
        for (int j = 0; j < 10 * n; j++)
        for (int k = 0; k < 10 * n; k++)
            c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j] % mod) % mod;
        return c;
    }
    
    Mat mpow(Mat a, int b) {
        Mat c;
        for (int i = 0; i < 10 * n; i++) c.m[i][i] = 1;
        while (b) {
            if (b & 1) c = mul(c, a);
            a = mul(a, a);
            b >>= 1;
        }
        return c;
    }
    
    void add(int u, int v, int w) {
        if (!w) return;
        for (int i = 1; i < w; i++)
            x.m[10 * u + i][10 * u + i + 1] = 1;
        x.m[10 * u + w][10 * v + 1] = 1;
    }
    
    int main() {
        scanf("%d%d", &n, &t);
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            for (int j = 0; j < n; j++)
                add(i, j, s[j] - '0');
        }
        x = mpow(x, t);
        printf("%d\n", x.m[1][10 * (n - 1) + 1]);
        
        return 0;
    }

**T3 \[JZOJ1038\] 游戏**

**题目描述**

windy学会了一种游戏。

对于1到N这N个数字，都有唯一且不同的1到N的数字与之对应。

最开始windy把数字按顺序1，2，3，……，N写一排在纸上，然后再在这一排下面写上它们对应的数字，然后又在新的一排下面写上它们对应的数字。

如此反复，直到序列再次变为1，2，3，……，N。

如：1 2 3 4 5 6 对应的关系为 1->2 2->3 3->1 4->5 5->4 6->6，windy的操作如下

1 2 3 4 5 6

2 3 1 5 4 6

3 1 2 4 5 6

1 2 3 5 4 6

2 3 1 4 5 6

3 1 2 5 4 6

1 2 3 4 5 6

这时，我们就有若干排1到N的排列，上例中有7排。

现在windy想知道，对于所有可能的对应关系，有多少种可能的排数。

**数据范围**

$1 \\leq N \\leq 10^3$

**分析**

没错，这又是个DP

对于一个 $1$ 到 $N$ 的数列，如果其中的数被分为了若干部分，每一部分中的所有数同时进行循环，那么最后数列回到了原来的排列顺序，那么显然循环次数就是每部分包含的数的个数的最小公倍数（似乎有个高端名称叫非同构循环子群的数目）

所以题目就转化为，将 $n$ 分为若干数之和，求这些数的最小公倍数

将分出来的这些数进行质因数分解，可以发现每个质数只有其最高次项才对最小公倍数产生贡献

又因为 $1$ 对最小公倍数不产生贡献，所以可以在这些数中任意加减 $1$，也就是其他数字只需要满足和小于等于 $n$

于是问题又转化为了质数幂之和不大于 $n$ 时不同质数幂之积的个数

这就是个多重背包问题

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    using namespace std;
    #define ll long long
    #define inf 0x3f3f3f3f
    #define N 1005
    
    int n, cnt;
    int book[N], p[N];
    ll ans, f[N];
    
    void Prime() {
        for (int i = 2; i <= n; i++)
            if (!book[i]) {
                p[++cnt] = i;
                for (int j = 2; i * j <= n; j++)
                    book[i * j] = 1;
            }
    }
    
    int main() {
        scanf("%d", &n);
        Prime();
        f[0] = 1;
        for (int i = 1; i <= cnt; i++)
            for (int j = n; j >= p[i]; j--)
                for (int k = p[i]; k <= j; k *= p[i])
                    f[j] += f[j - k];
        for (int i = 0; i <= n; i++) ans += f[i];
        printf("%lld\n", ans);
        
        return 0;
    }

**T4 \[JZOJ1039\] windy数**

**题目描述**

windy定义了一种windy数。

不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。

windy想知道，在A和B之间，包括A和B，总共有多少个windy数？

**数据范围**

$1 \\leq A,B \\leq 2 \\times 10^9$

**分析**

没错，这双是个DP，一天四题三DP，我佛了

不到一个月前才刚写这题，数位DP经典题啊

就设 $f\[i\]\[j\]$ 表示最高位为第 $i$ 位且该位为 $j$ 时windy数的个数

先预处理 $f$ 数组，再统计位数小于原数最高位的windy数个数

然后从高位向低位依次统计，注意windy数的限制条件

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    using namespace std;
    #define ll long long
    #define inf 0x3f3f3f3f
    #define N 15
    
    int a, b;
    int f[N][N], s[N];
    
    int count(int x) {
        int sum = 0, len = 0;
        memset(s, 0, sizeof s);
        while (x) s[++len] = x % 10, x /= 10;
        for (int i = 1; i < len; i++)
            for (int j = 1; j <= 9; j++)
                sum += f[i][j];
        for (int i = 1; i < s[len]; i++)
            sum += f[len][i];
        for (int i = len - 1; i; i--) {
            for (int j = 0; j < s[i]; j++)
                if (abs(j - s[i + 1]) >= 2)
                    sum += f[i][j];
            if (abs(s[i] - s[i + 1]) < 2) break;
        }
        return sum;
    }
    
    int main() {
        scanf("%d%d", &a, &b);
        for (int i = 0; i <= 9; i++) f[1][i] = 1;
        for (int i = 2; i <= 10; i++)
            for (int j = 0; j <= 9; j++)
                for (int k = 0; k <= 9; k++)
                    if (abs(j - k) >= 2)
                        f[i][j] += f[i - 1][k];
        printf("%d\n", count(b + 1) - count(a));
        
        return 0;
    }

转载于:https://www.cnblogs.com/Pedesis/p/11326704.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211102/590a55641f1241df813c7f9f7c3430d7.png