IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 第46届ICPC东亚洲区域赛(昆明)B Blocks题解 -> 正文阅读

[数据结构与算法]第46届ICPC东亚洲区域赛(昆明)B Blocks题解

  • 特此声明:该文章中的代码和解法均来自博主cup-pyy,我只是对其代码添加了详细注解,以及部分思路的详细化,原文链接见:这里

二维平面转为一维

注意我们最多含有22个坐标,但是实际上只会有21*21个格子
如何判断二维平面中的格子数量全部染黑?一维情况状态压缩十分容易,二维的情况将若干个一维拼接即可

        bitset<500> t;
        //二维平面转换为一维
        //虽然22个坐标
        // 21 * 21个格子看看是否都能染满
        lop(i, 0, n)
        {
            r[i].a.x = lower_bound(xs + 1, xs + cntx + 1, r[i].a.x) - xs;
            r[i].a.y = lower_bound(ys + 1, ys + cnty + 1, r[i].a.y) - ys;
            r[i].b.x = lower_bound(xs + 1, xs + cntx + 1, r[i].b.x) - xs;
            r[i].b.y = lower_bound(ys + 1, ys + cnty + 1, r[i].b.y) - ys;
            mask[i].reset();//
            t.reset();
            //标记一个格子被染黑,表示这个格子的左下角被染黑
            t = (1 << (r[i].b.y - r[i].a.y)) - 1;
            //[r[i].a.y, r[i].b.y - 1]全部为1
            //转换为下标为0开始
            //[r[i].a.y - 1, r[i].b.y - 2]全部都是1
            t <<= r[i].a.y - 1;
            //对于区间[r[i].a.y - 1, ]
            //r[i].b.y - r[i].a.y = len
            //(1 << len) - 1先初始先赋值[0, len - 1]全是1
            //然后区间同时加上,为[r[i].a.y - 1, r[i].a.y - 1 + len - 1]

            //大矩形一行的状态为[0, cnty - 1]
            //所以往上移动一行为 << (1 * (cnty - 1))
            lop(j, r[i].a.x - 1, r[i].b.x - 1)
            {
                //区间[r[i].a.x, b[i].b.x - 1]
                //0-index为[r[i].a.x - 1, b[i].b.x - 2]
                mask[i] |= (t << (j * (cnty - 1)));
            }
        }

期望dp方程化简

cnt为状态i1的数量

  • f [ k ] = 1 + 1 n ∑ i = 0 n f [ k ∣ ( 1 < < i ) ] f[k]=1+\cfrac{1}{n}\sum_{i=0}^{n}f[k\mid(1<<i)] f[k]=1+n1?i=0n?f[k(1<<i)] 1 1 1表示固定的染色步数花费
  • f [ k ] = 1 + c n t n f [ k ] + 1 n ∑ ( k & ( 1 < < i ) ) = = 0 f [ k ∣ ( 1 < < i ) ] f[k]=1+\cfrac{cnt}{n}f[k]+\cfrac{1}{n}\sum_{(k\&(1<<i))==0}f[k|(1<<i)] f[k]=1+ncnt?f[k]+n1?(k&(1<<i))==0?f[k(1<<i)]
  • n ? c n t n f [ k ] = 1 + 1 n ∑ ( k & ( 1 < < i ) ) = = 0 f [ k ∣ ( 1 < < i ) ] \cfrac{n-cnt}{n}f[k]=1+\cfrac{1}{n}\sum_{(k\&(1<<i))==0}f[k|(1<<i)] nn?cnt?f[k]=1+n1?(k&(1<<i))==0?f[k(1<<i)]
  • f [ k ] = ( 1 + 1 n ∑ ( k & ( 1 < < i ) ) = = 0 f [ k ∣ ( 1 < < i ) ] ) × n n ? c n t f[k]=(1+\cfrac{1}{n}\sum_{(k\&(1<<i))==0}f[k|(1<<i)])\times\cfrac{n}{n-cnt} f[k]=(1+n1?(k&(1<<i))==0?f[k(1<<i)])×n?cntn?

完整的注释代码

#include <bits/stdc++.h>
using namespace std;
#define el '\n'
#define pb push_back
#define x first
#define y second
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)

typedef long long LL;
typedef pair<int, int> PII;

struct read
{
    static const int M = 1 << 21;
    char buf[M], *S = buf, *P = buf, c, f;
    inline char getc()
    {
        return (S == P && (P = (S = buf) + fread(buf, 1, 1 << 21, stdin), S == P) ? EOF : *S++);
    }
    template <typename T>
    read &operator>>(T &x)
    {
        for (c = 0; !isdigit(c); c = getc())
            f = c;
        for (x = 0; isdigit(c); c = getc())
            x = x * 10 + (c - '0');
        return x = (f ^ '-') ? x : -x, *this;
    }
} fin;

constexpr int N = 23, M = 2e6 + 10, B = 10, md = 998244353;
const double PI = acos(-1), eps = 1e-8;

int T, n, m;
int w, h, cntx, cnty;
int f[1 << B];
int xs[N], ys[N];

int fpow(int a, int b)
{
    LL res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % md;
        b >>= 1;
        a = 1LL * a * a % md;
    }
    return res;
}

struct Rect
{
    PII a, b;
} r[15];

int inv[N];
int k;
bitset<500> mask[10], state;
//mask表示覆盖的二维格子的一维形式

void dfs(int u, int s)
{
    if(u == n)
    {//0-idx,边界
        f[s] = (state.count() == k) ? 0 : - 1;
        //计算1的数量是否为k,即是否全部染黑了
        return;
    }
    bitset<500> bk = state;//递归保留现场
    //不取第u个
    dfs(u + 1, s);
    state = bk;//还原
    state |= mask[u];
    //取第u个
    dfs(u + 1, s | (1 << u));
    return ;
}

int main()
{
    rep(i, 1, 19)
    {
        inv[i] = fpow(i, md - 2);
    }
    fin >> T;
    while (T--)
    {
        fin >> n >> w >> h;
        cntx = cnty = 0;
        lop(i, 0, n)
        {
            fin >> r[i].a.x >> r[i].a.y >> r[i].b.x >> r[i].b.y;
            if (r[i].a.x > w)
                r[i].a.x = w;
            if (r[i].a.y > h)
                r[i].a.y = h;
            if (r[i].b.x > w)
                r[i].b.x = w;
            if (r[i].b.y > h)
                r[i].b.y = h;
            xs[++cntx] = r[i].a.x;
            xs[++cntx] = r[i].b.x;
            ys[++cnty] = r[i].a.y;
            ys[++cnty] = r[i].b.y;
        }
        sort(xs + 1, xs + cntx + 1);
        sort(ys + 1, ys + cnty + 1);
        cntx = unique(xs + 1, xs + cntx + 1) - (xs + 1);
        cnty = unique(ys + 1, ys + cnty + 1) - (ys + 1);
        k = (cntx - 1) * (cnty - 1);
        bitset<500> t;
        //二维平面转换为一维
        //虽然22个坐标
        // 21 * 21个格子看看是否都能染满
        lop(i, 0, n)
        {
            r[i].a.x = lower_bound(xs + 1, xs + cntx + 1, r[i].a.x) - xs;
            r[i].a.y = lower_bound(ys + 1, ys + cnty + 1, r[i].a.y) - ys;
            r[i].b.x = lower_bound(xs + 1, xs + cntx + 1, r[i].b.x) - xs;
            r[i].b.y = lower_bound(ys + 1, ys + cnty + 1, r[i].b.y) - ys;
            mask[i].reset();//
            t.reset();
            //标记一个格子被染黑,表示这个格子的左下角被染黑
            t = (1 << (r[i].b.y - r[i].a.y)) - 1;
            //[r[i].a.y, r[i].b.y - 1]全部为1
            //转换为下标为0开始
            //[r[i].a.y - 1, r[i].b.y - 2]全部都是1
            t <<= r[i].a.y - 1;
            //对于区间[r[i].a.y - 1, ]
            //r[i].b.y - r[i].a.y = len
            //(1 << len) - 1先初始先赋值[0, len - 1]全是1
            //然后区间同时加上,为[r[i].a.y - 1, r[i].a.y - 1 + len - 1]

            //大矩形一行的状态为[0, cnty - 1]
            //所以往上移动一行为 << (1 * (cnty - 1))
            lop(j, r[i].a.x - 1, r[i].b.x - 1)
            {
                //区间[r[i].a.x, b[i].b.x - 1]
                //0-index为[r[i].a.x - 1, b[i].b.x - 2]
                mask[i] |= (t << (j * (cnty - 1)));
            }
        }
        state.reset();
        dfs(0, 0);
        if(f[(1 << n) - 1] == -1)
        {
            puts("-1");
            continue;
        }
        //进行逆推期望dp过程
        dwn(i, (1 << n) - 1, 0)
        {
            if(f[i] != -1)
                continue;//f[i] == -1 是终点,期望步数为0
            int cnt = 0, res = 0;
            lop(j, 0, n)
            {
                if(i >> j & 1)
                    cnt ++; //有 cnt / n种情况会转移到自身
                else 
                    res = (res + 1LL * inv[n] * f[i | (1 << j)]) % md;
            }
            f[i] = (1LL + res) * n % md * inv[n - cnt] % md;
        }
        cout << f[0] << el;
    }
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-04-26 12:01:51  更:2022-04-26 12:02:06 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 8:50:48-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码