首页 > 编程语言 >算法学习笔记(38): 2-SAT

算法学习笔记(38): 2-SAT

时间:2023-11-13 21:47:48浏览次数:59  
标签:38 覆盖 草莓 大棚 斜边 问题 算法 SAT

SAT 问题,也就是可满足性问题 Boolean Satisfiability Problem,是第一个被证明的 NPC 问题。

但是特殊的 2-SAT 我们可以通过图论的知识在线性复杂度内求解,构造出一组解。

基本的模型在 P4782 【模板】2-SAT 中有体现。

经典的标志是:AB 至少选一个,AB 要么都选,要么都不选。

简单的我们就不说了,像 P5782 [POI2001]和平委员会P6378 [PA2010] RiddleP4171 [JSOI2010] 满汉全席P5782 [POI2001] 和平委员会,都是很好的板子。

根据 伍昱 -《由对称性解 2-sat 问题》,我们可以得出:如果要输出 2-SAT 问题的一个可行解,只需要在 tarjan 缩点后所得的 DAG 上自底向上地进行选择和删除。

也就是优先选择缩点后所在连通块编号小的即可。

然而怎么会有这么板板的问题……


给定一个 0/1权有向图,给每个点赋予 ABCD 中的一个字母使得每条有向边都满足:\(w = 1 \iff (t_x, t_y) \in \{(A, D), (A, B), (B, D), (B, A), (C, D), (C, A), (C, B)\}\)

这一眼看不出来是 2-SAT,将关系画出来,大概是:

于是可以分为两组,\(a, b\) 进行 2-SAT


给定 \(n\) 对 \(m\) 维空间中的点对,求平行于坐标轴且能够覆盖每个点对中至少一个点的 \(m\) 维正方体的边长的最小值,点在正方体的边界上视为覆盖。

二分答案,好抽象,利用 2-SAT 判断。

假如当前选了某个点,那么每一维距离它 \(\gt x\) 的都不可以选,考虑排序之后,这一定是一段前缀和一段后缀,于是可以前后缀优化建图。

然而还有二选一的限制,\(\neg a \to b\) 即可。

于是总复杂度为 \(O(nk \log n)\)。


草莓城是一个个四个角坐标分别为 \(H \times W\) 的矩形,其中有

个草莓,草莓所在的点都是整点。现在要给每个草莓建一个大棚,满足大棚都处在城市内,且互不相交(指被多个大棚覆盖的区域面积为零)。要求每个大棚的形状为等腰直角三角形,对应草莓处于斜边的中点,且斜边与一条坐标轴平行、所有三角形的斜边长度相等。

请你设计一个方案使得斜边的长度最大。

是某种合法的方案。

还是二分 + 覆盖,这和上一题很类似。

但是每一个点有 \(4\) 个状态,于是成功的变成了 4-SAT NPC 问题,成功不可做。

然而可以注意到,将 \(4\) 中状态取交覆盖,发现我们只需要关注对角的二选一即可。

于是变成 \(AD\) 和 \(BC\) 两套 2-SAT 即可。

还有,我们可以 \(O(n^2)\) 建图,那么这道题就十分 naive 了。

标签:38,覆盖,草莓,大棚,斜边,问题,算法,SAT
From: https://www.cnblogs.com/jeefy/p/17830273.html

相关文章

  • 算法刷题记录-链表移除元素
    算法刷题记录-链表移除元素移除链表元素给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点。示例1:输入:head=[1,2,6,3,4,5,6],val=6输出:[1,2,3,4,5]示例2:输入:head=[],val=1输出:[]示例3:输入:hea......
  • 11.13算法
    题目二叉搜索树中第K小的元素给定一个二叉搜索树的根节点root,和一个整数k,请你设计一个算法查找其中第 k 个最小元素(从1开始计数)。示例1:输入:root=[3,1,4,null,2],k=1输出:1示例2:输入:root=[5,3,6,2,4,null,null,1],k=3输出:3提示:树中的节点数为n。......
  • 算法学习笔记(37): 矩阵
    一切线性操作都可以归为矩阵乘法--bySmallBasic本文是拿来玩耍,而不是学习的!目录线性递推超级矩阵快速幂!矩阵与邻接矩阵矩阵与线段树矩阵与FFT矩阵与期望不知道还能扯啥了矩阵的加法,要求两个矩阵大小相等,于是可以对位单点相加。\[C_{i,j}=A_{i,j}+B_{i,j}\]关于矩......
  • OAuth1.0的在http请求中的使用方式以及签名算法说明
    1、在httprequestheader的Authorization中,其格式为Authorization:"OAuthoauth_consumer_key="OAuthConsumeKey",oauth_token="OAuthToken",oauth_signature_method="HMAC-SHA256",oauth_timestamp="OAuthTimestamp",oauth_nonc......
  • 【C++】【图像处理】均值滤波和高斯滤波(低通滤波)算法解析(以.raw格式的图像为基础进行
    1voidmeanFilter(BYTE*image,intwidth,intheight,BYTE*outImg)2{3//均值滤波4intsmth[9];5inti,j,m,n;6BYTEblock[9];78//高斯卷积核初始化9smth[0]=1,smth[1]=2,smth[2]=1,10smth[3]=2,......
  • 实现冒泡排序算法
    实现冒泡排序算法#include<stdio.h> voidswap(int*xp,int*yp){   inttemp=*xp;   *xp=*yp;   *yp=temp;} voidbubbleSort(intarr[],intn){   for(inti=0;i<n-1;i++){       for(intj=0;j<n-i-1;j++){       ......
  • 算法题:约瑟夫环问题
    原题:N个人围成一圈顺序编号,从1号开始按1、2、3…顺序报数,报p者退出圈外,其余的人再从1、2、3开始报数,报p的人再退出圈外,以此类推。请按退出顺序输出每个退出人的原序号。输入格式:输入只有一行,包括一个整数N(1<=N<=3000)及一个整数p(1<=p<=5000)。输出格式:按退出顺序输出每个......
  • 文心一言 VS 讯飞星火 VS chatgpt (134)-- 算法导论11.2 6题
    六、用go语言,假设将n个关键字存储到一个大小为m且通过链接法解决冲突的散列表中,同时已知每条链的长度,包括其中最长链的长度L,请描述从散列表的所有关键字中均匀随机地选择某一元素并在O(L·(1+1/a))的期望时间内返回该关键字的过程。文心一言,代码不能运行:在这个问题中,我们需......
  • JavaSE day06【排序查找算法,Map集合,集合的嵌套,斗地主案例】测评题
    选择题题目1(多选):下列关于TreeSet集合排序的原理正确的是()选项:​ A.排序方法如果返回的是小于0,代表的是当前元素较小,需要存放在左边​ B.排序方法如果返回的是大于0,代表的是当前元素较大,需要存放在右边​ C.排序此方法如果返回的是0,代表的是当前元......
  • pip下载python软件包时报错 Could not find a version that satisfies the requiremen
    pip下载python软件包时报错,使用了国内源等各种方法,后来才知道是电脑中打开了抓包工具;打开抓包工具后一定要关闭抓包工具,这样下载软件包就下载下来了关闭抓包工具后,下载成功了......