ABC025D 25个整数 题解

· · 题解

ABC025D 25 个整数

思路

看完题目，首先想到的可能是暴力搜索。像 数独 这样的题目，能想到暴力是很正常的。

但是，这是道黑题，用那种低级的方法一定过不了。

所以，我们可以用 状压 dp。

怎么状压？一般来说，有两种思路。第一种是记录哪些格子被填了，另一种是记录哪些数字被填了。

对于第二种，我们发现这样记录的信息不够（因为格子与其上下左右的格子都有关系），或者说难转移。所以应该使用第一种。

因为第一种没有记录具体填什么，所以填数要有顺序，例如从小到大或从大到小。事实上，两种都可以，所以这里从从小到大的方面来考虑。

这意味着，假如对于一个状态 i，它有 p_i 个位置为 1，那么当前填的数就必当是 p_i（这 p_i 个数是 1, \dots, p_i）。

如何转移？

对于每一个状态 i(1 \le i \lt 2^{25})，设 i 在二进制中有 p_i 个 1。

如果 p_i 已经被事先填好了，位置是 mp_i（即输入时填了），那么 dp_i=dp_{(i\oplus2^{mp_i})}（假设可行）。这是因为，i\oplus 2^{mp_i} 正好是除了 p_i 没填的状态。但是，有一个问题：如果 i 中的第 mp_i 为 0 会怎么样呢（即不填这个格子）？显然，此时 i\oplus 2^{mp_i} \gt i，处理 dp_i 时 dp_{(i\oplus 2^{mp_i})} 还是 0 呢。

如果 p_i 没有被事先填好，则我们可以去枚举它的位置，并且对于所有可能的位置 m，做 dp_i+dp_{(i\oplus 2^m)}\to dp_i（假设可行）。

可行性判断？

我们讨论一下横向（左右）的判断（纵向同理）。

如果一个格子在边缘，那么它必当不会成为一个单调数列的中间。所以可以不讨论。

如果它在中间，则我们可以发现，如果它左边和右边只填了一个，那么填了的那个格子上的数会小于它自己的数，而没填的将来会填个比它大的，所以这种情况是不行的。如果它左边和右边要么都填了，要么都没填，显然它不会是单调的。

复杂度：O(2^{n}n)，此处 n=25，时间复杂度是正确的。常数大也没所谓，因为时限为 5s。

一些实现方法

本段可以跳过并直接看代码。

参考代码

#define pop(x) __builtin_popcount(x)
#define MOD (1000000007)

int dp[1 << 25]; // 存数组
int mp[30]; // 存输入地图

void add(int i, int p) // i 为当前状态，p 为当前填的数的位置
{
    int x = p % 5; // 横向判断
    int y = p / 5; // 纵向判断
    if (x && x < 4 && (i >> (p - 1) & 1 ^ i >> (p + 1) & 1)) // (p - 1) 即它左边的格子，(p + 1) 即它右边的。
    {
        return;
    }
    if (y && y < 4 && (i >> (p - 5) & 1 ^ i >> (p + 5) & 1)) // (p - 5) 为上，(p + 5) 为下。
    {
        return;
    }
    dp[i] = (dp[i] + dp[i ^ (1 << p)]) % MOD; // 记得模数
}

int main()
{
    for (int i = 1; i <= 25; i++)
    {
        int c;
        cin >> c;
        mp[c] = i; // 如果 c 为 0 也没所谓。
    }
    dp[0] = 1; // 初始化
    for (int i = 1; i < 1 << 25; i++) // dp
    {
        int p = mp[pop(i)];
        if (p)
        {
            add(i, p - 1); // 只能填这个位置。注意要 -1!!
        }
        else
        {
            for (int j = 0; j < 25; j++) // 枚举
            {
                if (i & (1 << j))
                {
                    add(i, j);
                }
            }
        }
    }
    cout << dp[(1 << 25) - 1] << endl; // 结果。也要 -1!!
    return 0;
}

update: 参考代码有点问题，却因语言特性卡过去了。现在的代码没问题了。