SAT
  • 2024-12-292-SAT!!!
    板子题卡了我一个点LuoguP4782【模板】2-SAT#include<iostream>#include<stack>#include<queue>usingnamespacestd;constintmaxn=2e6+10;structEdge{ intnxt,to;}edges[maxn];boolvis[maxn];inttot;intid;intcols;intin[maxn];in
  • 2024-12-25P4782 2—SAT
    点击查看代码#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,m;cin>>n>>m;vector<vector<int>>g(2*n);for(inti=0;i&l
  • 2024-12-232-SAT总结
    基础部分有K-Satisfiability问题,但\(k\ge2\)时那是NPC的,\(k=1\)时是trivial的,所以讨论2-Satisfiability。问题是这样的:\(n\)个bool变量,\(m\)个限制条件,每个限制会给出对于两个bool变量之间关系的描述,如\(a_i\lora_j\)为真。求一组可行解。显然我们可以暴搜,这里不说了。我们
  • 2024-12-07SAT问题(Boolean satisfiability problem)(布尔可满足性问题)
    1.组成SAT问题的三要素m个逻辑变元(variable)的集合:\(x_1,x_2,…,x_m\)文字(literal)的集合:一个文字就是一个逻辑变元或其非。这样,全部基本式为:\(x_1,\overline{x_1},x_2,\overline{x_2}…,x_m,\overline{x_m}\)n个子句(clause)的集合:\(C_1,C_2,…,C_n\),其中
  • 2024-11-26[复习] 种类并查集
    [复习]种类并查集种类并查集也可叫做扩展域并查集。前言自从两年多前刚学并查集时过了食物链后,就再也没有写过种类并查集。今天回顾一下。例题1食物链P2024[NOI2001]食物链。题目大意:有\(n\)个动物,每个动物属于\(A,B,C\)种中的一种,\(A\)吃\(B\),\(B\)吃\(C\),\(
  • 2024-12-02Win11家庭版系统安装组策略
    因为在Win11家庭版中是没有组策略器的,所以我们需要手动安装,如下是所有操作:1.在桌面新建一个TXT文本文件;2.在文本中输入以下代码:@echooffpushd"%~dp0"dir/bC:\Windows\servicing\Packages\Microsoft-Windows-GroupPolicy-ClientExtensions-Package~3*.mum>List.txt
  • 2024-11-25Swing布局
    1.流式布局(FlowLayout)   按照水平方向依次排列组件,排满一行后继续换行排列;排列方向从左到右,或者从右到左,这取决于容器的componentOrientation属性;   参数:FlowLayout.LEFT左对齐FlowLayout.CENTER居中对齐FlowLayout.RIGHT右对齐FlowLayout.LEA
  • 2024-10-01CMPT 477 / 777 Formal Verification Programming
    CMPT477/777FormalVerificationProgrammingAssignment1Thisassignmentisdueby11:59pmPTonWednesdayOct2,2024.PleasesubmitittoCanvas.Latepolicy:Supposeyoucangetn(outof100)pointsbasedonyourcodeandreportIfyousubmitbefor
  • 2024-09-262-SAT 学习笔记
    2-SAT学习笔记本文同载于本人的洛谷文章。参考资料算法2-SAT用于解决什么样的问题?问题给定\(n\)个大小为2的集合,每个集合要选其中一个元素,不能同时选,有\(m\)个条件\((a,b)\)代表元素\(a,b\)不能同时选,构造方案或判定无解。例子有3个集合:\(\{a,\nega\},\{b,
  • 2024-09-23ECE598HZ: Advanced Topics in Machine Learning
    ECE598HZ:AdvancedTopicsinMachineLearningandFormalMethodsFall2024Homework1DueSep2311:59pmCTTypesetyoursolutionsusingLATEX,createasinglezip fileincludingyoursolutions(ina singlePDF file), your code, andinstructionstorun
  • 2024-09-23关于 2-SAT 的方案构造
    基本思想是按某种顺序为每一对未确定的\((a,\nega)\)确定一个合法的点并将其后代加入方案。如果本次选择了\(a\),其合法等价于之后选到的\(a\)的后代不会同时包含某个点对\((b,\negb)\)。其可以细分为:①之后选到的\(a\)的后代不包含先前已被加入到方案的点的反面,这里所说
  • 2024-09-112-SAT
    将每个限制条件改写为「若\(A\)则\(B\)」的形式。从\(A\rightarrowB\)连一条有向边,跑\(\rmSCC\)缩点。若\(i\)和\(i'\)在同一联通块,则无解。否则有解。具体的方案是,令每个点\(c\)(所在联通块)小的为真。P6378[PA2010]Riddle前后缀优化建图,记\(pre_{a_i}\)表示
  • 2024-09-032-SAT 学习笔记
    一、简介k-SAT(satisfiability)解决这样一类问题:给定\(n\)个布尔变量和\(m\)条限制,每条限制形如\(x_1=0/1\or\cdots\orx_n=0/1\),求是否有解并给出构造。当\(k\gt2\)时,该问题为NP完全问题。二、算法流程在学习本算法前,请确保你对有向图强连通分量有一定了解。例
  • 2024-08-22[NOI2017] 游戏
    先来讲一下到底什么叫K-SAT先来看看2-SAT的准确定义那么对于k-SAT,不是说每个集合就有\(k\)个元素了(每个集合仍然只有两个元素,因为布尔变量的取值只有\(0\)和\(1\)),而是说给出的限制条件涉及\(k\)个元素,比如3-SAT那么对于这道题目,如果不考虑\(\text{x}\)的话,就是一个裸的2-SAT
  • 2024-08-18D46 2-SAT+线段树优化+二分 [ARC069F] Flags
    视频链接: [ARC069F]Flags-洛谷|计算机科学教育新生态(luogu.com.cn)//D462-SAT+线段树优化+二分O(nlognlogv)#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;#definemid((l+r)>>1)#definels(u<<1)#definer
  • 2024-08-17D45 2-SAT+二分 UVA1146 Now or later
    视频链接: D402-SATPOJ3683PriestJohn'sBusiestDay-董晓-博客园(cnblogs.com)UVA1146Noworlater-洛谷|计算机科学教育新生态(luogu.com.cn)//2-SAT+二分O(n*n*logt)#include<iostream>#include<cstring>#include<algorithm>#include<vec
  • 2024-08-162-sat 模板
    2-Sat\[\begin{align*}&\LARGE\color{Red}大意:\\&有n个数a_i,m个约束条件都需要满足\\&条件形如(i,a,j,b)\quada_i=a\\text{or}\a_j=b\\\\\\&\LARGE\color{Red}思路:\\&让a_i表示0,a_{i+n}表示1\\&转换条件表达式成:\\&a_i=a\\\te
  • 2024-08-15【2-sat】P5782 [POI2001] 和平委员会
    P5782[POI2001]和平委员会大意:n个集合每个集合有两个点i,i+1一共2n个点每个集合选一个点到另一个空集S里面有m个约束条件i和j不能在一起求可行的集合S思路:2-sat对ij而言建图(i,j邻居)和(j,i的邻居),邻居就是他们所属的集合的另一个点然后判断同同一个集
  • 2024-08-15【2-sat】P4171 [JSOI2010] 满汉全席
    P4171[JSOI2010]满汉全席-洛谷大意:n个点m个条件形如m1,h32,满足n个条件思路:2-sat让m=0,h=1,然后转换为imjh的建图,注意傻逼题目的数字可能是多位数不能直接x[1]-'0'#include<cstdio>#include<stack>#include<iostream>#include<cstring>#include<cma
  • 2024-08-13D42 2-SAT+二进制枚举 P3825 [NOI2017] 游戏
    视频链接: P3825[NOI2017]游戏-洛谷|计算机科学教育新生态(luogu.com.cn)//2-SAT+二进制枚举O(2^8*(n+m))#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;constintN=100005;inthead[N],to[N<<1],ne[N<<1],idx;
  • 2024-08-12[算法] 2-SAT简记
    真的是简记2-SAT$2-SAT$用于求解一个变量只有两种情况的适应性问题(就是有没有解以及输出一种方案);其实可以类比二分图最大匹配(但其实两者的差别还是很大的);算法流程对于每一个变量,我们都有两种情况,$true$和$false$;而题目中给我们的,是形如{$A=true/false$或
  • 2024-08-102-SAT 学习笔记
    2-SAT用于求解布尔方程组,其中每个方程最多含有两个变量,方程的形式为\((a∨b)=1\),即式子\(a\)为真或式子\(b\)为真。求解的方法是根据逻辑关系式建图,然后求强联通子图,每一个强联通子图的答案都是一样的。建图:这里以模版题为例:题意:给定若干个需要满足的条件,其形式为\(a,1
  • 2024-08-06D39 2-SAT P3209 [HNOI2010] 平面图判定
    视频链接:D392-SATP3209[HNOI2010]平面图判定_哔哩哔哩_bilibili   图论(十三)——平面图和对偶图_图论(十三)——平面图和对偶图-CSDN博客P3209[HNOI2010]平面图判定-洛谷|计算机科学教育新生态(luogu.com.cn)#include<iostream>#include<cstring>#incl
  • 2024-08-02D35【模板】2-SAT
    视频链接:D35【模板】2-SAT_哔哩哔哩_bilibili   D14强连通分量Tarjan算法-董晓-博客园(cnblogs.com)P4782【模板】2-SAT-洛谷|计算机科学教育新生态(luogu.com.cn)//2-SAT+tarjanO(n+m)#include<iostream>#include<cstring>#include<algorithm