im钱包下载中心|dlx
作者： im钱包下载中心
2024-03-07 18:14:35
DLX算法 - 木子川 - 博客园
DLX算法 - 木子川 - 博客园
会员
周边
新闻
博问
AI培训
云市场
所有博客
当前博客
我的博客
我的园子
账号设置
简洁模式 ...
退出登录
注册
登录
木子川
联系
管理
DLX算法
理解DLX算法之前首先了解精确覆盖问题和重复覆盖问题
精确覆盖问题
何为精确覆盖问题
在一个全集X中若干子集的集合为S，精确覆盖（Exactcover）是指，S的子集S*，满足X中的每一个元素在S*中恰好出现一次。
定义
满足以下条件的集合为一个精确覆盖： S*中任意两个集合没有交集，即X中的元素在S*中出现最多一次 S*中集合的全集为X，即X中的元素在S*中出现最少一次 合二为一，即X中的元素在S*中出现恰好一次。
举例
令={N,O,E,P}是集合X={1,2,3,4}的一个子集，并满足： N={} O={1,3} E={2,4} P={2,3}. 其中一个子集{O,E}是X的一个精确覆盖,因为O={1,3}而E={2,4}的并集恰好是X={1,2,3,4}。同理，{N,O,E}也是X.的一个精确覆盖。空集并不影响结论。
精确覆盖问题的表示方式
一般的，我们用一个集合s包含s中的元素的单向关系表示精确覆盖问题。常用的有以下两种方法：
矩阵表示法
包含关系可以用一个关系矩阵表示。.矩阵每行表示S的一个子集，每列表示X中的一个元素。矩阵行列交点元素为1表示对应的元素在对应的集合中，不在则为0。
通过这种矩阵表示法，求一个精确覆盖转化为求矩阵的若干个行的集合，使每列有且仅有一个1。同时，该问题也是精确覆盖的典型例题之一。
下表为其中一个例子：
S*={B,D,F}便是一个精确覆盖。
图论表示法
可将精确覆盖问题转化为一个二分图，左侧为集合，右侧为元素，左侧集合若与右侧元素有包含关系则连边，通过将左侧节点与其所有边保留与否求解一个右侧的每一个节点恰好有一条边的匹配。
重复覆盖问题
即选取一个01矩阵中的几行，使这几行组成的新矩阵的每一列至少有一个1，也就是说每一列上可以有多个1。 该问题在精确覆盖问题上减少了一个约束条件。
Dancing Links X 算法
历史
算法大师Donald E.Knuth（《计算机程序设计艺术》的作者）提出了DLX（Dancing Links X）算法。实际上，他把上面求解的过程称为X算法，而他提出的舞蹈链（Dancing Links）实际上并不是一种算法，而是一种数据结构。一种非常巧妙的数据结构，他的数据结构在缓存和回溯的过程中效率惊人，不需要额外的空间，以及近乎线性的时间。而在整个求解过程中，指针在数据之间跳跃着，就像精巧设计的舞蹈一样，故Donald E.Knuth把它称为Dancing Links（中文译名舞蹈链）。
算法思想
Dancing Links的核心是基于双向链的方便操作（移除、恢复加入）
我们用例子来说明
假设双向链的三个连续的元素，A1、A2、A3，每个元素有两个分量Left和Right，分别指向左边和右边的元素。由定义可知
A1.Right=A2，A2.Right=A3
A2.Left=A1，A3.Left=A2
在这个双向链中，可以由任一个元素得到其他两个元素，A1.Right.Right=A3，A3.Left.Left=A1等等
现在把A2这个元素从双向链中移除（不是删除）出去，那么执行下面的操作就可以了
A1.Right=A3，A3.Left=A1
那么就直接连接起A1和A3。A2从双向链中移除出去了。但仅仅是从双向链中移除了，A2这个实体还在，并没有删除。只是在双向链中遍历的话，遍历不到A2了。
那么A2这个实体中的两个分量Left和Right指向谁？由于实体还在，而且没有修改A2分量的操作，那么A2的两个分量指向没有发生变化，也就是在移除前的指向。即A2.Left=A1和A2.Right=A3
如果此时发现，需要把A2这个元素重新加入到双向链中的原来的位置，也就是A1和A3的中间。由于A2的两个分量没有发生变化，仍然指向A1和A3。那么只要修改A1的Right分量和A3的Left就行了。也就是下面的操作
A1.Right=A2，A3.Left=A2
仔细想想，上面两个操作（移除和恢复加入）对应了什么？是不是对应了之前的算法过程中的关键的两步？
移除操作对应着缓存数据、恢复加入操作对应着回溯数据。而美妙的是，这两个操作不再占用新的空间，时间上也是极快速的
在很多实际运用中，把双向链的首尾相连，构成循环双向链
Dancing Links用的数据结构是交叉十字循环双向链
而Dancing Links中的每个元素不仅是横向循环双向链中的一份子，又是纵向循环双向链的一份子。
因为精确覆盖问题的矩阵往往是稀疏矩阵（矩阵中，0的个数多于1），Dancing Links仅仅记录矩阵中值是1的元素。
Dancing Links中的每个元素有6个分量
分别：Left指向左边的元素、Right指向右边的元素、Up指向上边的元素、Down指向下边的元素、Col指向列标元素、Row指示当前元素所在的行
Dancing Links还要准备一些辅助元素（为什么需要这些辅助元素？没有太多的道理，大师认为这能解决问题，实际上是解决了问题）
Ans（）：Ans数组，在求解的过程中保留当前的答案，以供最后输出答案用。
Head元素：求解的辅助元素，在求解的过程中，当判断出Head.Right=Head（也可以是Head.Left=Head）时，求解结束，输出答案。Head元素只有两个分量有用。其余的分量对求解没啥用
C元素：辅助元素，称列标元素，每列有一个列标元素。本文开始的题目的列标元素分别是C1、C2、C3、C4、C5、C6、C7。每一列的元素的Col分量都指向所在列的列标元素。列标元素的Col分量指向自己（也可以是没有）。在初始化的状态下，Head.Right=C1、C1.Right=C2、……、C7.Right=Head、Head.Left=C7等等。列标元素的分量Row=0，表示是处在第0行。
下图就是根据题目构建好的交叉十字循环双向链（构建的过程后面的详述）
就上图解释一下
每个绿色方块是一个元素，其中Head和C1、C2、……、C7是辅助元素。橙色框中的元素是原矩阵中1的元素，给他们标上号（从1到16）
左侧的红色，标示的是行号，辅助元素所在的行是0行，其余元素所在的行从1到6
每两个元素之间有一个双向箭头连线，表示双向链中相邻两个元素的关系（水平的是左右关系、垂直的是上下关系）
单向的箭头并不是表示单向关系，而因为是循环双向链，左侧的单向箭头和右侧的单向箭头（上边的和下边的）组成了一个双向箭头，例如元素14左侧的单向箭头和元素16右侧的单项箭头组成一个双向箭头，表示14.Left=16、16.Right=14；同理，元素14下边的单项箭头和元素C4上边的单向箭头组成一个双向箭头，表示14.Down=C4、C4.Up=14
接下来，利用图来解释Dancing Links是如何求解精确覆盖问题
1、首先判断Head.Right=Head？若是，求解结束，输出解；若不是，求解还没结束，到步骤2（也可以判断Head.Left=Head？）
2、获取Head.Right元素，即元素C1，并标示元素C1（标示元素C1，指的是标示C1、和C1所在列的所有元素、以及该元素所在行的元素，并从双向链中移除这些元素）。如下图中的紫色部分。
如上图可知，行2和行4中的一个必是答案的一部分（其他行中没有元素能覆盖列C1），先假设选择的是行2
3、选择行2（在答案栈中压入2），标示该行中的其他元素（元素5和元素6）所在的列首元素，即标示元素C4和标示元素C7，下图中的橙色部分。
注意的是，即使元素5在步骤2中就从双向链中移除，但是元素5的Col分量还是指向元素C4的，这里体现了双向链的强大作用。
把上图中的紫色部分和橙色部分移除的话，剩下的绿色部分就如下图所示
一下子空了好多，是不是转换为一个少了很多元素的精确覆盖问题？，利用递归的思想，很快就能写出求解的过程来。我们继续完成求解过程
4、获取Head.Right元素，即元素C2，并标示元素C2。如下图中的紫色部分。
如图，列C2只有元素7覆盖，故答案只能选择行3
5、选择行3（在答案栈中压入3），标示该行中的其他元素（元素8和元素9）所在的列首元素，即标示元素C3和标示元素C6，下图中的橙色部分。
把上图中的紫色部分和橙色部分移除的话，剩下的绿色部分就如下图所示
6、获取Head.Right元素，即元素C5，元素C5中的垂直双向链中没有其他元素，也就是没有元素覆盖列C5。说明当前求解失败。要回溯到之前的分叉选择步骤（步骤2）。那要回标列首元素（把列首元素、所在列的元素，以及对应行其余的元素。并恢复这些元素到双向链中），回标列首元素的顺序是标示元素的顺序的反过来。从前文可知，顺序是回标列首C6、回标列首C3、回标列首C2、回标列首C7、回标列首C4。表面上看起来比较复杂，实际上利用递归，是一件很简单的事。并把答案栈恢复到步骤2（清空的状态）的时候。又回到下图所示
7、由于之前选择行2导致无解，因此这次选择行4（再无解就整个问题就无解了）。选择行4（在答案栈中压入4），标示该行中的其他元素（元素11）所在的列首元素，即标示元素C4，下图中的橙色部分。
把上图中的紫色部分和橙色部分移除的话，剩下的绿色部分就如下图所示
8、获取Head.Right元素，即元素C2，并标示元素C2。如下图中的紫色部分。
如图，行3和行5都可以选择
9、选择行3（在答案栈中压入3），标示该行中的其他元素（元素8和元素9）所在的列首元素，即标示元素C3和标示元素C6，下图中的橙色部分。
把上图中的紫色部分和橙色部分移除的话，剩下的绿色部分就如下图所示
10、获取Head.Right元素，即元素C5，元素C5中的垂直双向链中没有其他元素，也就是没有元素覆盖列C5。说明当前求解失败。要回溯到之前的分叉选择步骤（步骤8）。从前文可知，回标列首C6、回标列首C3。并把答案栈恢复到步骤8（答案栈中只有4）的时候。又回到下图所示
11、由于之前选择行3导致无解，因此这次选择行5（在答案栈中压入5），标示该行中的其他元素（元素13）所在的列首元素，即标示元素C7，下图中的橙色部分。
把上图中的紫色部分和橙色部分移除的话，剩下的绿色部分就如下图所示
12、获取Head.Right元素，即元素C3，并标示元素C3。如下图中的紫色部分。
13、如上图，列C3只有元素1覆盖，故答案只能选择行3（在答案栈压入1）。标示该行中的其他元素（元素2和元素3）所在的列首元素，即标示元素C5和标示元素C6，下图中的橙色部分。
把上图中的紫色部分和橙色部分移除的话，剩下的绿色部分就如下图所示
14、因为Head.Right=Head。故，整个过程求解结束。输出答案，答案栈中的答案分别是4、5、1。表示该问题的解是第4、5、1行覆盖所有的列。如下图所示（蓝色的部分）
从以上的14步来看，可以把Dancing Links的求解过程表述如下
1、Dancing函数的入口
2、判断Head.Right=Head？，若是，输出答案，返回True，退出函数。
3、获得Head.Right的元素C
4、标示元素C
5、获得元素C所在列的一个元素
6、标示该元素同行的其余元素所在的列首元素
7、获得一个简化的问题，递归调用Daning函数，若返回的True，则返回True，退出函数。
8、若返回的是False，则回标该元素同行的其余元素所在的列首元素，回标的顺序和之前标示的顺序相反
9、获得元素C所在列的下一个元素，若有，跳转到步骤6
10、若没有，回标元素C，返回False，退出函数。
之前的文章的表述，为了表述简单，采用面向对象的思路，说每个元素有6个分量，分别是Left、Right、Up、Down、Col、Row分量。
但在实际的编码中，用数组也能实现相同的作用。例如：用Left（）表示所有元素的Left分量，Left（1）表示元素1的Left分量
在前文中，元素分为Head元素、列首元素（C1、C2等）、普通元素。在编码中，三种元素统一成一种元素。如上题，0表示Head元素，1表示元素C1、2表示元素C2、……、7表示元素C7，从8开始表示普通元素。这是统一后，编码的简便性。利用数组的下标来表示元素，宛若指针一般。
精确覆盖例题：Sudoku ZOJ - 3122 链接：https://zoj.pintia.cn/problem-sets/91827364500/problems/91827367537
代码：
1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 #include
11 #include
12 #include
13 #include
14 #include
15 #define mod 1000000007
16 #define eps 1e-6
17 #define ll long long
18 #define INF 0x3f3f3f3f
19 using namespace std;
20
21 const int maxn=18000;
22 //ans用来记录答案的编号
23 int ans[maxn];
24 struct DLX
25 {
26
27 //左右上下，四个数组
28 int left[maxn],right[maxn],up[maxn],down[maxn];
29 //列数组，头数组,loc代表这个数在数独中的位置和数值
30 int col[maxn],head[maxn],loc[maxn][3];
31 //num数组保存每列有几个数，id为编号
32 int num[1030],id;
33 //创建有m列的矩阵
34 void init(int n)
35 {
36 for(int i=0;i<=n;i++)
37 {
38 up[i]=down[i]=i;
39 left[i]=i-1;
40 right[i]=i+1;
41 }
42 left[0]=n; right[n]=0;
43 id=n;
44 memset(num,0,sizeof(num));
45 memset(head,-1,sizeof(head));
46 }
47 //插入位于x,y的数，并对其上下左右，列和编号初始化，对px,py,pz存入loc数组
48 void Link(int x,int y,int px,int py,int k)
49 {
50 ++id;
51 down[id]=y;
52 up[id]=up[y];
53 down[up[y]]=id;
54 up[y]=id;
55 loc[id][0]=px,loc[id][1]=py,loc[id][2]=k;//存放数的位置和数
56 col[id]=y;
57 num[y]++;//此列1的数量加一
58 if(head[x]==-1)
59 {
60 head[x]=left[id]=right[id]=id;
61 }
62 else
63 {
64 int a=head[x];
65 int b=right[a];
66 left[id]=a; right[a]=id;
67 right[id]=b; left[b]=id;
68 head[x]=id;
69 }
70 }
71 //移除c列和c列上数所在的每一行，
72 void Remove(int c)
73 {
74 left[right[c]]=left[c];
75 right[left[c]]=right[c];
76 for(int i=down[c];i!=c;i=down[i])
77 for(int j=right[i];j!=i;j=right[j])
78 {
79 up[down[j]]=up[j];
80 down[up[j]]=down[j];
81 num[col[j]]--;
82 }
83 }
84 //恢复c列和c列上数所在的每一行，
85 void Resume(int c)
86 {
87 for(int i=up[c];i!=c;i=up[i])
88 for(int j=right[i];j!=i;j=right[j])
89 {
90 num[col[j]]++;
91 up[down[j]]=j;
92 down[up[j]]=j;
93 }
94 left[right[c]]=c;
95 right[left[c]]=c;
96 }
97 bool dfs(int step)
98 {
99 //如果走到第256步时已走完所有的数独中的数，所以退出
100 if(step==256) return true;
101 //如果头指向第0列，说明所有列已删除
102 if(right[0]==0) return false;
103 int c=right[0];
104 //用循环是c优先指向列中数少的列
105 for(int i=right[0];i;i=right[i])
106 {
107 if(num[i] 108 { 109 c=i; 110 } 111 } 112 //删除第c列 113 Remove(c); 114 for(int i=down[c];i!=c;i=down[i]) 115 { 116 //记录每此循环选的编号 117 ans[step]=i; 118 //遍历i所在的行，并删除j所在的列 119 for(int j=right[i];j!=i;j=right[j]) Remove(col[j]); 120 //如果循环下去有解，则返回true 121 if(dfs(step+1)) return true; 122 //遍历i所在的行，并恢复j所在的列 123 for(int j=left[i];j!=i;j=left[j]) Resume(col[j]); 124 } 125 //恢复第c列 126 Resume(c); 127 //所有操作完成后仍无解，则返回false 128 return false; 129 } 130 }dlx; 131 int main() 132 { 133 //str数组存放输入的数据 134 char str[260]; 135 int kase=0; 136 while(cin>>str) 137 { 138 //换行 139 if(kase) 140 { 141 cout< 142 } 143 kase++; 144 for(int i=1;i<=15;i++) 145 { 146 cin>>str+i*16; 147 } 148 dlx.init(256*4); 149 int r=0,js=0;//r代表行 150 for(int x=0;x<16;x++) 151 { for(int y=0;y<16;y++) 152 { 153 char ch=str[js]; 154 js++; 155 int s=(x/4)*4+y/4;//宫 156 int a,b,c,d;//a表示约束一，b表示约束二，c表示约束三,d表示约束四 157 if(ch=='-') 158 { 159 //此位置上可能是1到16， 160 for(int i=1;i<=16;i++) 161 { 162 a=x*16+y+1; 163 b=x*16+i+256; 164 c=y*16+i+256+256; 165 d=s*16+i+256+256+256; 166 ++r; 167 dlx.Link(r,a,x,y,i); 168 dlx.Link(r,b,x,y,i); 169 dlx.Link(r,c,x,y,i); 170 dlx.Link(r,d,x,y,i); 171 } 172 } 173 else 174 { 175 int i=ch-64; 176 a=x*16+y+1; 177 b=x*16+i+256; 178 c=y*16+i+256+256; 179 d=s*16+i+256+256+256; 180 ++r; 181 dlx.Link(r,a,x,y,i); 182 dlx.Link(r,b,x,y,i); 183 dlx.Link(r,c,x,y,i); 184 dlx.Link(r,d,x,y,i); 185 } 186 } 187 } 188 dlx.dfs(0); 189 char res[16][16]; 190 for(int i=0;i<256;i++)//将答案存放到一个数独数组中 191 { 192 int a=ans[i]; 193 int x=dlx.loc[a][0],y=dlx.loc[a][1],k=dlx.loc[a][2]-1; 194 res[x][y]=k+'A'; 195 } 196 for(int i=0;i<16;i++) 197 { 198 for(int j=0;j<16;j++) 199 { 200 printf("%c",res[i][j]); 201 } 202 printf("\n"); 203 } 204 } 205 206 } 重复覆盖例题：Airport HDU - 5046 链接：https://vjudge.net/problem/HDU-5046 代码： 1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #define mod 998244353 16 #define eps 1e-6 17 #define ll long long 18 #define INF 0x3f3f3f3f 19 using namespace std; 20 21 const int maxn=4010; 22 int k; 23 struct 24 { 25 //左右上下，四个数组 26 int left[maxn],right[maxn],up[maxn],down[maxn]; 27 //头数组，列数组 28 int head[65],col[maxn]; 29 //num数组保存每列有几个数，id为编号 30 int num[65],id; 31 //创建有m列的矩阵 32 void init(int m) 33 { 34 for(int i=0;i<=m;i++) 35 { 36 left[i]=i-1; 37 right[i]=i+1; 38 up[i]=down[i]=i; 39 col[i]=i; 40 } 41 id=m; 42 left[0]=m; 43 right[m]=0; 44 memset(head,-1,sizeof(head)); 45 memset(num,0,sizeof(num)); 46 } 47 //插入位于x,y的数，并对其上下左右，列和编号初始化 48 void link(int x,int y) 49 { 50 id++; 51 down[id]=down[y]; 52 up[down[y]]=id; 53 up[id]=y; 54 down[y]=id; 55 num[y]++; 56 col[id]=y; 57 if(head[x]==-1) 58 { 59 head[x]=left[id]=right[id]=id; 60 } 61 else 62 { 63 right[id]=right[head[x]]; 64 left[right[head[x]]]=id; 65 left[id]=head[x]; 66 right[head[x]]=id; 67 } 68 } 69 //只移除c所在的一列和c所在列上数所在的每一行 70 void remove(int c) 71 { 72 for(int i=down[c];i!=c;i=down[i]) 73 { 74 left[right[i]]=left[i]; 75 right[left[i]]=right[i]; 76 } 77 } 78 //恢复c所在的一列和c所在列上数所在的每一行 79 void reback(int c) 80 { 81 for(int i=up[c];i!=c;i=up[i]) 82 { 83 left[right[i]]=right[left[i]]=i; 84 } 85 } 86 bool bj[maxn]; 87 //计算还需要多少步 88 int A() 89 { 90 int ans=0; 91 for(int c=right[0];c!=0;c=right[c]) 92 { 93 bj[c]=true; 94 } 95 for(int c=right[0];c!=0;c=right[c]) 96 { 97 if(bj[c]) 98 { 99 ans++; 100 bj[c]=false; 101 for(int i=down[c];i!=c;i=down[i]) 102 { 103 for(int j=right[i];j!=i;j=right[j]) 104 { 105 bj[col[j]]=false; 106 } 107 } 108 } 109 } 110 return ans; 111 } 112 //核心函数，step表示步数 113 bool danc(int step) 114 { 115 //如果还要走的步数加上已走的步数，比现有的答案多，则不需要走了，因此退出 116 if(A()+step>k)//剪枝 117 { 118 return false; 119 } 120 //如果头指向第0列，说明所有列已删除 121 if(right[0]==0) 122 { 123 return step<=k; 124 } 125 int c=right[0]; 126 //用循环是c优先指向列中数少的列 127 for(int i=c;i!=0;i=right[i]) 128 { 129 if(num[i] 130 { 131 c=i; 132 } 133 } 134 //遍历c列中的数 135 for(int i=down[c];i!=c;i=down[i]) 136 { 137 //删除i列 138 remove(i); 139 //遍历i所在的行，并删除j所在的列 140 for(int j=right[i];j!=i;j=right[j]) 141 { 142 remove(j); 143 } 144 //如果循环下去有解，则返回true 145 if(danc(step+1)) 146 { 147 return true; 148 } 149 //遍历i所在的行，并恢复j所在的列 150 for(int j=left[i];j!=i;j=left[j]) 151 { 152 reback(j); 153 } 154 //恢复i列 155 reback(i); 156 } 157 //所有操作完成后仍无解，则返回false 158 return false; 159 } 160 }dlx; 161 struct node//小岛信息 162 { 163 ll x,y; 164 }no[65]; 165 ll dis(node a,node b)//计算距离 166 { 167 ll dx=a.x-b.x; 168 if(dx<0) 169 { 170 dx=-dx; 171 } 172 ll dy=a.y-b.y; 173 if(dy<0) 174 { 175 dy=-dy; 176 } 177 return dx+dy; 178 } 179 int main() 180 { 181 int t,ans=0;; 182 scanf("%d",&t); 183 while(t--) 184 { 185 ans++; 186 int n; 187 ll x[65],y[65]; 188 scanf("%d %d",&n,&k); 189 for(int i=1;i<=n;i++) 190 { 191 scanf("%lld %lld",&no[i].x,&no[i].y); 192 } 193 ll le=0,rig=100000000000LL; 194 //二分法一步一步缩小距离 195 while(rig-le>0) 196 { 197 dlx.init(n); 198 ll mid=(rig+le)/2; 199 for(int i=1;i<=n;i++) 200 { 201 for(int j=1;j<=n;j++) 202 { 203 if(dis(no[i],no[j])<=mid)//岛之间的距离比航距小时 204 { 205 dlx.link(i,j); 206 } 207 } 208 } 209 if(dlx.danc(0))//如果当前航距需要的最少飞机的数量比k小为true 210 { 211 rig=mid; 212 } 213 else 214 { 215 le=mid+1; 216 } 217 } 218 printf("Case #%d: %lld\n",ans,le); 219 } 220 } posted @ 2019-09-05 21:08 木子川 阅读(4284) 评论(0) 编辑 收藏 举报 会员力量，点亮园子希望 刷新页面返回顶部 Copyright © 2024 木子川 Powered by .NET 8.0 on Kubernetes 算法竞赛学习笔记——DLX - 知乎切换模式写文章登录/注册算法竞赛学习笔记——DLX因幡巡单推人现居江苏的大学生前言笔者最近在学数据结构这门课，课内讲到了十字链表，不禁让笔者想起了DLX。那么我们就来学习一下DLX吧。正文双向十字循环链表在讲DLX算法之前，我们先引入一种数据结构：双向循环十字链表。 让我们想想一个稀疏矩阵，如果我们打算把它保存下来，我们可能会使用一个二维数组来代表此矩阵——但是考虑到这是个稀疏矩阵，当矩阵中非0元的个数\lt\lt矩阵大小时，我们实际上浪费了很多空间。因此我们考虑使用十字链表，即把矩阵中的每个非0元用链表来储存。对于行和列，我们设置两个“哨兵”链表，可以方便看是否到头。 画的略丑，见谅 可以看出，对于每个元素，我们维护的是它下方和右边的元素。这样对行、列的遍历都是很方便的。在此基础上，我们把它改成双向循环十字链表，即首先把所有边都变成双向的，维护每个节点上下左右的四个节点，然后“循环”指的是到末尾时指针指回链头，即这样： 按照这个思路，双向十字链表很好实现。不过在这里我们只维护列的哨兵。插入操作插入任何一个节点时，因为我们在输入此矩阵时是有序的，我们保证这个节点是在最后面的。那么对于列，我们只需要把这个节点的上指针指向最后一个元素，下指针指向哨兵即可。如何快速查询这一列的最后一个元素呢？这就是循环链表的好处了——哨兵的上一个元素就是。对于行，由于我们没有维护行哨兵，每行的头节点我们需要单独维护。精确覆盖问题DLX是用来解决什么问题的呢？参见下图。 引用自oiwiki 这种问题可以被转化为下列问题： 引用自oiwiki移除操作考虑到要选择若干行使得每一列恰好有一个1，我们需要在矩阵中支持的操作包括移除某一列及其相关行——如果我们选定某一行，那么如果这一行中的第k个元素是1，那么第k列中所有为1的元素的所在的行均不能选，我们引用董晓老师https://www.bilibili.com/video/BV1eX4y1p7Lu/?spm_id_from=333.337.search-card.all.click&vd_source=d9b89a11011b83051a736249d783bb8a中的视频截图， 如图 首先我们选择一列，在这一列中我们能且仅能选一个1，那么假设我们在这一行中选择了某一个1，那么这一行中的第k个元素如果是1，那么在第k列肯定是不能选其他行与这一列的交点的。我们就需要从链表中移除选择的第k列以及所有的相关行。具体来说，我们一直向下遍历此列，并且删除每一行就行。 删除每一个节点的方法？让其他节点忽视它即可，即让它上下左右的节点的指针都跳过它即可。注意在这里我们并不是把节点给delete掉了，我们在这里并未破坏行和列的结构，只是删除了它们与整个矩阵的连接，使它们成为了“孤岛”，具体原因是因为等下我们还需要恢复这些结构，如果破坏得过多是很难恢复的。 从哪里开始删除呢？这就是我们最开始设置哨兵的作用了。我们从哨兵开始完成此过程。恢复操作恢复操作即是移除的逆操作。DLX算法DLX算法由大名鼎鼎的Donald E. Knuth提出。具体来说，就是依靠上述数据结构进行回溯——其实就是很简单的深搜。对于每一个当前矩阵，我们选择任意一列，首先删除这一列及其相关行（读者可以想象为什么），在这一列中枚举所有可选的1，在它们的行中存在1的列进行上述的删除操作。在删除过后的子矩阵上重复此算法，如果我们最后得到一个空矩阵则说明可以，否则如果出现全0列那说明存在错误，那就回溯。 听起来时间复杂度很不好计算，不过据计算DLX算法的时间复杂度很好，是O(c^n)的。其中c是一个接近1的常数，c是矩阵中1的个数。据说DLX算法能轻松解决4阶数独，十分的高效，十分的迅速。不过笔者还没有实验，不知道真假。代码#include using namespace std; int n,m,cnt; const int Max=5501;//注意这里，哨兵也算节点 int u[Max],d[Max],l[Max],r[Max]; int row[Max],col[Max]; int h[Max],s[Max];//每行的头节点和每列节点数 int ans[Max]; void init(){ for(int i=0;i<=m;i++){ u[i]=d[i]=i; l[i]=i-1;r[i]=i+1; } l[0]=m;r[m]=0;cnt=m; } void add(int x,int y){ row[++cnt]=x;col[cnt]=y;s[y]++; u[cnt]=u[y];d[u[y]]=cnt; d[cnt]=y; u[y]=cnt; if(h[x]==0){ h[x]=r[cnt]=cnt=l[cnt]=cnt; }else{ l[cnt]=l[h[x]]; r[l[h[x]]]=cnt; r[cnt]=h[x]; l[h[x]]=cnt; } } void remove(int y){ r[l[y]]=r[y];l[r[y]]=l[y]; for(int i=d[y];i!=y;i=d[i]){ for(int j=r[i];j!=i;j=r[j]){ d[u[j]]=d[j];u[d[j]]=u[j];s[col[j]]--; } } } void recover(int y){ r[l[y]]=y;l[r[y]]=y; for(int i=u[y];i!=y;i=u[i]){ for(int j=l[i];j!=i;j=l[j]){ d[u[j]]=j;u[d[j]]=j;s[col[j]]++; } } } void print(){ for(int i=r[0];i;i=r[i]){ // for(int j=d[i];j!=u) } } bool dance(int dep){ //cout< if(r[0]==0){ for(int i=1;i cout< } return true; } int y=r[0]; for(int i=r[0];i;i=r[i]){ if(s[i] y=i; } } remove(y); for(int i=d[y];i!=y;i=d[i]){ ans[dep]=row[i]; for(int j=r[i];j!=i;j=r[j]){ remove(col[j]); } if(dance(dep+1)){ return true; } for(int j=l[i];j!=i;j=l[j]){//注意这里，考虑到我们之前的删除顺序，每个节点左边的节点是“有误”的，因此需要从右往左进行恢复，从而完全按照最开始的顺序。 recover(col[j]); } } recover(y); return false; } int main(){ cin>>n>>m; init(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ int tmp;cin>>tmp; if(tmp){ add(i,j); } } } if(!dance(1)){ cout<<"No Solution!"; } } 后记读者们可能会问笔者，这个算法有什么用呢？这确实是个问题。笔者以为真正的能力并不仅仅在于理解什么是DLX算法本身，更多是在于怎么把一个问题转化成为上述的精确覆盖问题。这也如《算法竞赛进阶指南》上提到DLX算法时说的那句话：“算法思维能力的训练远比学习几个能直接拿来解决问题的数据结构重要”。本文使用 Zhihu On VSCode 创作并发布发布于 2023-10-26 17:57・IP 属地江苏赞同 23 条评论分享喜欢收藏申请 RabbitMQ - 死信队列(Dead-Letter-Exchange ) - 知乎首发于MQ切换模式写文章登录/注册RabbitMQ - 死信队列(Dead-Letter-Exchange )Balmy消息和队列都可以设置过期消失时间吗,但归处可以不同,消息过期消失,没有了就是没有了,但是队列是可以留下痕迹去往死信队列说白了,死信队列就是一个"接盘侠" 凡是:被拒绝过期以及超过标准(到达最大长度)死信队列都会敞开怀抱,收纳他们进入正题DLX，全称为Dead-Letter-Exchange , 可以称之为死信交换机，也有人称之为死信邮箱。当消息在一个队列中变成死信(dead message)之后，它能被重新发送到另一个交换机中，这个交换机就是DLX ，绑定DLX的队列就称之为死信队列。消息变成死信，可能是由于以下的原因：消息被拒绝消息过期队列达到最大长度DLX也是一个正常的交换机，和一般的交换机没有区别，它能在任何的队列上被指定，实际上就是设置某一个队列的属性。当这个队列中存在死信时，Rabbitmq就会自动地将这个消息重新发布到设置的DLX上去，进而被路由到另一个队列，即死信队列。要想使用死信队列，只需要在定义队列的时候设置队列参数x-dead-letter-exchange指定交换机即可。第一种 过期进入死信队列创建死信队列 过期消息绑定死信队列这里需要注意的是,已经申明的队列增加新的参数不会采取覆盖,需要web端手动删除在创建,所以要想清楚了再创建DLX 死信交换机 DLK死信路由key过期后转移到死信队列第二种 操作最大长度进入死信队列比如这个队列现在只能容纳两条信息,那么多出来的,就自动的进入死信队列了创建死信队列 操作队列,超出最大长度进入死信队列然后过期和最大数的条件是可以并存的超出最大条数全部过期进入死信队列剩下一种移到后面的案例专门说发布于 2021-04-19 18:08RabbitMQ赞同 5添加评论分享喜欢收藏申请转载文章被以下专栏收录MQ消息中间件 - 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25int ok = 0; for (int state = 0; state < 1 << n; ++state) { // 枚举每行是否被选 for (int i = 1; i <= n; ++i) if ((1 << i - 1) & state) for (int j = 1; j <= m; ++j) a[i][j] = 1; int flag = 1; for (int j = 1; j <= m; ++j) for (int i = 1, bo = 0; i <= n; ++i) if (a[i][j]) { if (bo) flag = 0; else bo = 1; } if (!flag) continue; else { ok = 1; for (int i = 1; i <= n; ++i) if ((1 << i - 1) & state) printf("%d ", i); puts(""); } memset(a, 0, sizeof(a)); } if (!ok) puts("No solution."); 暴力 2考虑到 01 矩阵的特殊性质，每一行都可以看做一个 位二进制数。因此原问题转化为给定 个 位二进制数，要求选择一些数，使得任意两个数的与都为 0，且所有数的或为 。tmp 表示的是截至目前被选中的二进制数的或。因为每一行都有选或者不选两种状态，所以枚举行的时间复杂度为 ；而每次计算 tmp 都需要 的时间复杂度。所以总的复杂度为 。实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18int ok = 0; for (int i = 1; i <= n; ++i) for (int j = m; j >= 1; --j) num[i] = num[i] << 1 | a[i][j]; for (int state = 0; state < 1 << n; ++state) { int tmp = 0; for (int i = 1; i <= n; ++i) if ((1 << i - 1) & state) { if (tmp & num[i]) break; tmp |= num[i]; } if (tmp == (1 << m) - 1) { ok = 1; for (int i = 1; i <= n; ++i) if ((1 << i - 1) & state) printf("%d ", i); puts(""); } } if (!ok) puts("No solution."); 重复覆盖问题重复覆盖问题与精确覆盖问题类似，但没有对元素相似性的限制。下文介绍的 X 算法 原本针对精确覆盖问题，但经过一些修改和优化（已标注在其中）同样可以高效地解决重复覆盖问题。X 算法Donald E. Knuth 提出了 X 算法 (Algorithm X)，其思想与刚才的暴力差不多，但是方便优化。过程继续以上文中中提到的例子为载体，得到一个这样的 01 矩阵：此时第一行有 个 ，第二行有 个 ，第三行有 个 ，第四行有 个 ，第五行有 个 ，第六行有 个 。选择第一行，将它删除，并将所有 所在的列打上标记； 选择所有被标记的列，将它们删除，并将这些列中含 的行打上标记（重复覆盖问题无需打标记）； 选择所有被标记的行，将它们删除； 这表示这一行已被选择，且这一行的所有 所在的列不能有其他 了。 于是得到一个新的小 01 矩阵： 此时第一行（原来的第二行）有 个 ，第二行（原来的第四行）有 个 ，第三行（原来的第五行）有 个 。选择第一行（原来的第二行），将它删除，并将所有 所在的列打上标记； 选择所有被标记的列，将它们删除，并将这些列中含 的行打上标记； 选择所有被标记的行，将它们删除； 这样就得到了一个空矩阵。但是上次删除的行 1 0 1 1 不是全 的，说明选择有误； 回溯到步骤 4，考虑选择第二行（原来的第四行），将它删除，并将所有 所在的列打上标记； 选择所有被标记的列，将它们删除，并将这些列中含 的行打上标记； 选择所有被标记的行，将它们删除； 于是我们得到了这样的一个矩阵： 此时第一行（原来的第五行）有 个 ，将它们全部删除，得到一个空矩阵： 上一次删除的时候，删除的是全 的行，因此成功，算法结束。 答案即为被删除的三行：。强烈建议自己模拟一遍矩阵删除、还原与回溯的过程后，再接着阅读下文。通过上述步骤，可将 X 算法的流程概括如下：对于现在的矩阵 ，选择并标记一行 ，将 添加至 中；如果尝试了所有的 却无解，则算法结束，输出无解；标记与 相关的行 和 （相关的行和列与 X 算法 中第 2 步定义相同，下同）；删除所有标记的行和列，得到新矩阵 ；如果 为空，且 为全 ，则算法结束，输出被删除的行组成的集合 ； 如果 为空，且 不全为 ，则恢复与 相关的行 以及列 ，跳转至步骤 1； 如果 不为空，则跳转至步骤 1。不难看出，X 算法需要大量的「删除行」、「删除列」和「恢复行」、「恢复列」的操作。一个朴素的想法是，使用一个二维数组存放矩阵，再用四个数组分别存放每一行与之相邻的行编号，每次删除和恢复仅需更新四个数组中的元素。但由于一般问题的矩阵中 0 的数量远多于 1 的数量，这样做的空间复杂度难以接受。Donald E. Knuth 想到了用双向十字链表来维护这些操作。而在双向十字链表上不断跳跃的过程被形象地比喻成「跳跃」，因此被用来优化 X 算法的双向十字链表也被称为「Dancing Links」。Dancing Links 优化的 X 算法预编译命令1#define IT(i, A, x) for (i = A[x]; i != x; i = A[i]) 定义双向十字链表中存在四个指针域，分别指向上、下、左、右的元素；且每个元素 在整个双向十字链表系中都对应着一个格子，因此还要表示 所在的列和所在的行，如图所示：大型的双向链表则更为复杂：每一行都有一个行首指示，每一列都有一个列指示。行首指示为 first[]，列指示是我们新建的 个哨兵结点。值得注意的是，行首指示并非是链表中的哨兵结点。它是虚拟的，类似于邻接表中的 first[] 数组，直接指向 这一行中的首元素。同时，每一列都有一个 siz[] 表示这一列的元素个数。特殊地， 号结点无右结点等价于这个 Dancing Links 为空。1 2 3 4constexpr int MS = 1e5 + 5; int n, m, idx, first[MS], siz[MS]; int L[MS], R[MS], U[MS], D[MS]; int col[MS], row[MS]; 过程remove 操作remove(c) 表示在 Dancing Links 中删除第 列以及与其相关的行和列。先将 删除，此时： 左侧的结点的右结点应为 的右结点。 右侧的结点的左结点应为 的左结点。即 L[R[c]] = L[c], R[L[c]] = R[c];。然后顺着这一列往下走，把走过的每一行都删掉。如何删掉每一行呢？枚举当前行的指针 ，此时： 上方的结点的下结点应为 的下结点。 下方的结点的上结点应为 的上结点。注意要修改每一列的元素个数。即 U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]];。remove 函数的代码实现如下：实现 1 2 3 4 5 6 7 8 9void remove(const int &c) { int i, j; L[R[c]] = L[c], R[L[c]] = R[c]; // 顺着这一列从上往下遍历 IT(i, D, c) // 顺着这一行从左往右遍历 IT(j, R, i) U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]]; } recover 操作recover(c) 表示在 Dancing Links 中还原第 列以及与其相关的行和列。recover(c) 即 remove(c) 的逆操作，这里不再赘述。值得注意的是， recover(c) 的所有操作的顺序与 remove(c) 的操作恰好相反。recover(c) 的代码实现如下：实现 1 2 3 4 5void recover(const int &c) { int i, j; IT(i, U, c) IT(j, L, i) U[D[j]] = D[U[j]] = j, ++siz[col[j]]; L[R[c]] = R[L[c]] = c; } build 操作build(r, c) 表示新建一个大小为 ，即有 行， 列的 Dancing Links。新建 个结点作为列指示。第 个点的左结点为 ，右结点为 ，上结点为 ，下结点为 。特殊地， 结点的左结点为 ， 结点的右结点为 。于是我们得到了一个环状双向链表：这样就初始化了一个 Dancing Links。build(r, c) 的代码实现如下：实现 1 2 3 4 5 6 7 8 9 10void build(const int &r, const int &c) { n = r, m = c; for (int i = 0; i <= c; ++i) { L[i] = i - 1, R[i] = i + 1; U[i] = D[i] = i; } L[0] = c, R[c] = 0, idx = c; memset(first, 0, sizeof(first)); memset(siz, 0, sizeof(siz)); } insert 操作insert(r, c) 表示在第 行，第 列插入一个结点。插入操作分为两种情况：如果第 行没有元素，那么直接插入一个元素，并使 first[r] 指向这个元素。 这可以通过 first[r] = L[idx] = R[idx] = idx; 来实现。如果第 行有元素，那么将这个新元素用一种特殊的方式与 和 连接起来。 设这个新元素为 ，然后： 把 插入到 的正下方，此时： 下方的结点为原来 的下结点； 下方的结点（即原来 的下结点）的上结点为 ; 的上结点为 ； 的下结点为 。 注意记录 的所在列和所在行，以及更新这一列的元素个数。 1 2col[++idx] = c, row[idx] = r, ++siz[c]; U[idx] = c, D[idx] = D[c], U[D[c]] = idx, D[c] = idx; 强烈建议读者完全掌握这几步的顺序后再继续阅读本文。把 插入到 的正右方，此时： 右侧的结点为原来 的右结点；原来 右侧的结点的左结点为 ； 的左结点为 ； 的右结点为 。 1 2L[idx] = first[r], R[idx] = R[first[r]]; L[R[first[r]]] = idx, R[first[r]] = idx; 强烈建议读者完全掌握这几步的顺序后再继续阅读本文。insert(r, c) 这个操作可以通过图片来辅助理解：留心曲线箭头的方向。insert(r, c) 的代码实现如下：实现 1 2 3 4 5 6 7 8 9 10void insert(const int &r, const int &c) { row[++idx] = r, col[idx] = c, ++siz[c]; U[idx] = c, D[idx] = D[c], U[D[c]] = idx, D[c] = idx; if (!first[r]) first[r] = L[idx] = R[idx] = idx; else { L[idx] = first[r], R[idx] = R[first[r]]; L[R[first[r]]] = idx, R[first[r]] = idx; } } dance 操作dance() 即为递归地删除以及还原各个行列的过程。如果 号结点没有右结点，那么矩阵为空，记录答案并返回；选择列元素个数最少的一列，并删掉这一列；遍历这一列所有有 的行，枚举它是否被选择；递归调用 dance()，如果可行，则返回；如果不可行，则恢复被选择的行；如果无解，则返回。dance() 的代码实现如下：实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17bool dance(int dep) { int i, j, c = R[0]; if (!R[0]) { ans = dep; return 1; } IT(i, R, 0) if (siz[i] < siz[c]) c = i; remove(c); IT(i, D, c) { stk[dep] = row[i]; IT(j, R, i) remove(col[j]); if (dance(dep + 1)) return 1; IT(j, L, i) recover(col[j]); } recover(c); return 0; } 其中 stk[] 用来记录答案。注意我们每次优先选择列元素个数最少的一列进行删除，这样能保证程序具有一定的启发性，使搜索树分支最少。对于重复覆盖问题，在搜索时可以用估价函数（与 A* 中类似）进行剪枝：若当前最好情况下所选行数超过目前最优解，则可以直接返回。模板模板代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90#include <bits/stdc++.h> const int N = 500 + 10; int n, m, idx, ans; int first[N], siz[N], stk[N]; int read() { // 快读 int x = 0, f = 0, ch; while (!isdigit(ch = getchar())) f |= ch == '-'; while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); return f ? -x : x; } struct DLX { static const int MAXSIZE = 1e5 + 10; int n, m, tot, first[MAXSIZE + 10], siz[MAXSIZE + 10]; int L[MAXSIZE + 10], R[MAXSIZE + 10], U[MAXSIZE + 10], D[MAXSIZE + 10]; int col[MAXSIZE + 10], row[MAXSIZE + 10]; void build(const int &r, const int &c) { // 进行build操作 n = r, m = c; for (int i = 0; i <= c; ++i) { L[i] = i - 1, R[i] = i + 1; U[i] = D[i] = i; } L[0] = c, R[c] = 0, tot = c; memset(first, 0, sizeof(first)); memset(siz, 0, sizeof(siz)); } void insert(const int &r, const int &c) { // 进行insert操作 col[++tot] = c, row[tot] = r, ++siz[c]; D[tot] = D[c], U[D[c]] = tot, U[tot] = c, D[c] = tot; if (!first[r]) first[r] = L[tot] = R[tot] = tot; else { R[tot] = R[first[r]], L[R[first[r]]] = tot; L[tot] = first[r], R[first[r]] = tot; } } void remove(const int &c) { // 进行remove操作 int i, j; L[R[c]] = L[c], R[L[c]] = R[c]; for (i = D[c]; i != c; i = D[i]) for (j = R[i]; j != i; j = R[j]) U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]]; } void recover(const int &c) { // 进行recover操作 int i, j; for (i = U[c]; i != c; i = U[i]) for (j = L[i]; j != i; j = L[j]) U[D[j]] = D[U[j]] = j, ++siz[col[j]]; L[R[c]] = R[L[c]] = c; } bool dance(int dep) { // dance if (!R[0]) { ans = dep; return 1; } int i, j, c = R[0]; for (i = R[0]; i != 0; i = R[i]) if (siz[i] < siz[c]) c = i; remove(c); for (i = D[c]; i != c; i = D[i]) { stk[dep] = row[i]; for (j = R[i]; j != i; j = R[j]) remove(col[j]); if (dance(dep + 1)) return 1; for (j = L[i]; j != i; j = L[j]) recover(col[j]); } recover(c); return 0; } } solver; int main() { n = read(), m = read(); solver.build(n, m); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { int x = read(); if (x) solver.insert(i, j); } solver.dance(1); if (ans) for (int i = 1; i < ans; ++i) printf("%d ", stk[i]); else puts("No Solution!"); return 0; } 性质DLX 递归及回溯的次数与矩阵中 的个数有关，与矩阵的 等参数无关。因此，它的时间复杂度是 指数级 的，理论复杂度大概在 左右，其中 为某个非常接近于 的常数， 为矩阵中 的个数。但实际情况下 DLX 表现良好，一般能解决大部分的问题。建模DLX 的难点，不全在于链表的建立，而在于建模。请确保已经完全掌握 DLX 模板后再继续阅读本文。我们每拿到一个题，应该考虑行和列所表示的意义：行表示决策，因为每行对应着一个集合，也就对应着选/不选；列表示状态，因为第 列对应着某个条件 。对于某一行而言，由于不同的列的值不尽相同，我们 由不同的状态，定义了一个决策。例题 1 P1784 数独解题思路 先考虑决策是什么。 在这一题中，每一个决策可以用形如 的有序三元组表示。 注意到「宫」并不是决策的参数，因为它 可以被每个确定的 表示。 因此有 行。 再考虑状态是什么。 我们思考一下 这个决将会造成什么影响。记 所在的宫为 。 第 行用了一个 （用 列表示）；第 列用了一个 （用 列表示）；第 宫用了一个 （用 列表示）； 中填入了一个数（用 列表示）。 因此有 列，共 个 。 至此，我们成功地将 的数独问题转化成了一个 有 行， 列，共 个 的精确覆盖问题。参考代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113#include <bits/stdc++.h> const int N = 1e6 + 10; int ans[10][10], stk[N]; int read() { int x = 0, f = 0, ch; while (!isdigit(ch = getchar())) f |= ch == '-'; while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); return f ? -x : x; } // 快读 struct DLX { static const int MAXSIZE = 1e5 + 10; int n, m, tot, first[MAXSIZE + 10], siz[MAXSIZE + 10]; int L[MAXSIZE + 10], R[MAXSIZE + 10], U[MAXSIZE + 10], D[MAXSIZE + 10]; int col[MAXSIZE + 10], row[MAXSIZE + 10]; void build(const int &r, const int &c) { // 进行build操作 n = r, m = c; for (int i = 0; i <= c; ++i) { L[i] = i - 1, R[i] = i + 1; U[i] = D[i] = i; } L[0] = c, R[c] = 0, tot = c; memset(first, 0, sizeof(first)); memset(siz, 0, sizeof(siz)); } void insert(const int &r, const int &c) { // 进行insert操作 col[++tot] = c, row[tot] = r, ++siz[c]; D[tot] = D[c], U[D[c]] = tot, U[tot] = c, D[c] = tot; if (!first[r]) first[r] = L[tot] = R[tot] = tot; else { R[tot] = R[first[r]], L[R[first[r]]] = tot; L[tot] = first[r], R[first[r]] = tot; } } void remove(const int &c) { // 进行remove操作 int i, j; L[R[c]] = L[c], R[L[c]] = R[c]; for (i = D[c]; i != c; i = D[i]) for (j = R[i]; j != i; j = R[j]) U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]]; } void recover(const int &c) { // 进行recover操作 int i, j; for (i = U[c]; i != c; i = U[i]) for (j = L[i]; j != i; j = L[j]) U[D[j]] = D[U[j]] = j, ++siz[col[j]]; L[R[c]] = R[L[c]] = c; } bool dance(int dep) { // dance int i, j, c = R[0]; if (!R[0]) { for (i = 1; i < dep; ++i) { int x = (stk[i] - 1) / 9 / 9 + 1; int y = (stk[i] - 1) / 9 % 9 + 1; int v = (stk[i] - 1) % 9 + 1; ans[x][y] = v; } return 1; } for (i = R[0]; i != 0; i = R[i]) if (siz[i] < siz[c]) c = i; remove(c); for (i = D[c]; i != c; i = D[i]) { stk[dep] = row[i]; for (j = R[i]; j != i; j = R[j]) remove(col[j]); if (dance(dep + 1)) return 1; for (j = L[i]; j != i; j = L[j]) recover(col[j]); } recover(c); return 0; } } solver; int GetId(int row, int col, int num) { return (row - 1) * 9 * 9 + (col - 1) * 9 + num; } void Insert(int row, int col, int num) { int dx = (row - 1) / 3 + 1; int dy = (col - 1) / 3 + 1; int room = (dx - 1) * 3 + dy; int id = GetId(row, col, num); int f1 = (row - 1) * 9 + num; // task 1 int f2 = 81 + (col - 1) * 9 + num; // task 2 int f3 = 81 * 2 + (room - 1) * 9 + num; // task 3 int f4 = 81 * 3 + (row - 1) * 9 + col; // task 4 solver.insert(id, f1); solver.insert(id, f2); solver.insert(id, f3); solver.insert(id, f4); } int main() { solver.build(729, 324); for (int i = 1; i <= 9; ++i) for (int j = 1; j <= 9; ++j) { ans[i][j] = read(); for (int v = 1; v <= 9; ++v) { if (ans[i][j] && ans[i][j] != v) continue; Insert(i, j, v); } } solver.dance(1); for (int i = 1; i <= 9; ++i, putchar('\n')) for (int j = 1; j <= 9; ++j, putchar(' ')) printf("%d", ans[i][j]); return 0; } 例题 2 靶形数独解题思路 这一题与 数独 的模型构建 一模一样，主要区别在于答案的更新。 这一题可以开一个权值数组，每次找到一组数独的解时， 每个位置上的数乘上对应的权值计入答案即可。参考代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122#include <bits/stdc++.h> const int oo = 0x3f3f3f3f; const int N = 1e5 + 10; const int e[] = {6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 6, 6, 7, 8, 8, 8, 8, 8, 7, 6, 6, 7, 8, 9, 9, 9, 8, 7, 6, 6, 7, 8, 9, 10, 9, 8, 7, 6, 6, 7, 8, 9, 9, 9, 8, 7, 6, 6, 7, 8, 8, 8, 8, 8, 7, 6, 6, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6}; int ans = -oo, a[10][10], stk[N]; int read() { int x = 0, f = 0, ch; while (!isdigit(ch = getchar())) f |= ch == '-'; while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); return f ? -x : x; } int GetWeight(int row, int col, int num) { // 求数乘上对应的权值 return num * e[(row - 1) * 9 + (col - 1)]; } struct DLX { static const int MAXSIZE = 1e5 + 10; int n, m, tot, first[MAXSIZE + 10], siz[MAXSIZE + 10]; int L[MAXSIZE + 10], R[MAXSIZE + 10], U[MAXSIZE + 10], D[MAXSIZE + 10]; int col[MAXSIZE + 10], row[MAXSIZE + 10]; void build(const int &r, const int &c) { // 进行build操作 n = r, m = c; for (int i = 0; i <= c; ++i) { L[i] = i - 1, R[i] = i + 1; U[i] = D[i] = i; } L[0] = c, R[c] = 0, tot = c; memset(first, 0, sizeof(first)); memset(siz, 0, sizeof(siz)); } void insert(const int &r, const int &c) { // 进行insert操作 col[++tot] = c, row[tot] = r, ++siz[c]; D[tot] = D[c], U[D[c]] = tot, U[tot] = c, D[c] = tot; if (!first[r]) first[r] = L[tot] = R[tot] = tot; else { R[tot] = R[first[r]], L[R[first[r]]] = tot; L[tot] = first[r], R[first[r]] = tot; } } void remove(const int &c) { // 进行remove操作 int i, j; L[R[c]] = L[c], R[L[c]] = R[c]; for (i = D[c]; i != c; i = D[i]) for (j = R[i]; j != i; j = R[j]) U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]]; } void recover(const int &c) { // 进行recover操作 int i, j; for (i = U[c]; i != c; i = U[i]) for (j = L[i]; j != i; j = L[j]) U[D[j]] = D[U[j]] = j, ++siz[col[j]]; L[R[c]] = R[L[c]] = c; } void dance(int dep) { // dance int i, j, c = R[0]; if (!R[0]) { int cur_ans = 0; for (i = 1; i < dep; ++i) { int cur_row = (stk[i] - 1) / 9 / 9 + 1; int cur_col = (stk[i] - 1) / 9 % 9 + 1; int cur_num = (stk[i] - 1) % 9 + 1; cur_ans += GetWeight(cur_row, cur_col, cur_num); } ans = std::max(ans, cur_ans); return; } for (i = R[0]; i != 0; i = R[i]) if (siz[i] < siz[c]) c = i; remove(c); for (i = D[c]; i != c; i = D[i]) { stk[dep] = row[i]; for (j = R[i]; j != i; j = R[j]) remove(col[j]); dance(dep + 1); for (j = L[i]; j != i; j = L[j]) recover(col[j]); } recover(c); } } solver; int GetId(int row, int col, int num) { return (row - 1) * 9 * 9 + (col - 1) * 9 + num; } void Insert(int row, int col, int num) { int dx = (row - 1) / 3 + 1; // r int dy = (col - 1) / 3 + 1; // c int room = (dx - 1) * 3 + dy; // room int id = GetId(row, col, num); int f1 = (row - 1) * 9 + num; // task 1 int f2 = 81 + (col - 1) * 9 + num; // task 2 int f3 = 81 * 2 + (room - 1) * 9 + num; // task 3 int f4 = 81 * 3 + (row - 1) * 9 + col; // task 4 solver.insert(id, f1); solver.insert(id, f2); solver.insert(id, f3); solver.insert(id, f4); } int main() { solver.build(729, 324); for (int i = 1; i <= 9; ++i) for (int j = 1; j <= 9; ++j) { a[i][j] = read(); for (int v = 1; v <= 9; ++v) { if (a[i][j] && v != a[i][j]) continue; Insert(i, j, v); } } solver.dance(1); printf("%d", ans == -oo ? -1 : ans); return 0; } 例题 3 「NOI2005」智慧珠游戏解题思路 定义：题中给我们的智慧珠的形态，称为这个智慧珠的标准形态。 显然，我们可以通过改变两个参数 （表示顺时针旋转 的次数）和 （是否水平翻转）来改变这个智慧珠的形态。 仍然，我们先考虑决策是什么。 在这一题中，每一个决策可以用形如 的有序五元组表示。 表示第 个智慧珠的标准形态的左上角的位置，序号为 ，经过了 次顺时针转 。 巧合的是，我们可以令 时不水平翻转， 时水平翻转，从而达到简化代码的目的。 因此有 行。 需要注意的是，因为一些不合法的填充，如 ， 所以 在实际操作中，空的智慧珠棋盘也只需要建出 行。 再考虑状态是什么。 这一题的状态比较简单。 我们思考一下， 这个决策会造成什么影响。 某些格子被占了（用 列表示）；第 个智慧珠被用了（用 列表示）。 因此有 列，共 个 。 至此，我们成功地将智慧珠游戏转化成了一个 有 行， 列，共 个 的精确覆盖问题。参考代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148#include <bits/stdc++.h> int numcol, numrow; int dfn[3000], tx[2], nxt[2], num[50][50], vis[50]; char ans[50][50]; const int f[2] = {-1, 1}; const int table[12][5][2] = { // directions of shapes {{0, 0}, {1, 0}, {0, 1}}, // A {{0, 0}, {0, 1}, {0, 2}, {0, 3}}, // B {{0, 0}, {1, 0}, {0, 1}, {0, 2}}, // C {{0, 0}, {1, 0}, {0, 1}, {1, 1}}, // D {{0, 0}, {1, 0}, {2, 0}, {2, 1}, {2, 2}}, // E {{0, 0}, {0, 1}, {1, 1}, {0, 2}, {0, 3}}, // F {{0, 0}, {1, 0}, {0, 1}, {0, 2}, {1, 2}}, // G {{0, 0}, {1, 0}, {0, 1}, {1, 1}, {0, 2}}, // H {{0, 0}, {0, 1}, {0, 2}, {1, 2}, {1, 3}}, // I {{0, 0}, {-1, 1}, {0, 1}, {1, 1}, {0, 2}}, // J {{0, 0}, {1, 0}, {1, 1}, {2, 1}, {2, 2}}, // K {{0, 0}, {1, 0}, {0, 1}, {0, 2}, {0, 3}}, // L }; const int len[12] = {3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5}; const int getx[] = {0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14}; const int gety[] = {0, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1, 2, 3, 4, 5, 6, 7, 8, 9}; struct DLX { static const int MS = 1e5 + 10; int n, m, tot, first[MS], siz[MS]; int L[MS], R[MS], U[MS], D[MS]; int col[MS], row[MS]; void build(const int &r, const int &c) { n = r, m = c; for (int i = 0; i <= c; ++i) { L[i] = i - 1, R[i] = i + 1; U[i] = D[i] = i; } L[0] = c, R[c] = 0, tot = c; memset(first, 0, sizeof(first)); memset(siz, 0, sizeof(siz)); } void insert(const int &r, const int &c) { // insert col[++tot] = c, row[tot] = r, ++siz[c]; D[tot] = D[c], U[D[c]] = tot, U[tot] = c, D[c] = tot; if (!first[r]) first[r] = L[tot] = R[tot] = tot; else R[tot] = R[first[r]], L[R[first[r]]] = tot, L[tot] = first[r], R[first[r]] = tot; // ! } void remove(const int &c) { // remove int i, j; L[R[c]] = L[c], R[L[c]] = R[c]; for (i = D[c]; i != c; i = D[i]) for (j = R[i]; j != i; j = R[j]) U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]]; } void recover(const int &c) { // recover int i, j; for (i = U[c]; i != c; i = U[i]) for (j = L[i]; j != i; j = L[j]) U[D[j]] = D[U[j]] = j, ++siz[col[j]]; L[R[c]] = R[L[c]] = c; } bool dance() { // dance if (!R[0]) return 1; int i, j, c = R[0]; for (i = R[0]; i != 0; i = R[i]) if (siz[i] < siz[c]) c = i; remove(c); for (i = D[c]; i != c; i = D[i]) { if (col[i] <= 55) ans[getx[col[i]]][gety[col[i]]] = dfn[row[i]] + 'A'; for (j = R[i]; j != i; j = R[j]) { remove(col[j]); if (col[j] <= 55) ans[getx[col[j]]][gety[col[j]]] = dfn[row[j]] + 'A'; } if (dance()) return 1; for (j = L[i]; j != i; j = L[j]) recover(col[j]); } recover(c); return 0; } } solver; int main() { for (int i = 1; i <= 10; ++i) scanf("%s", ans[i] + 1); for (int i = 1; i <= 10; ++i) for (int j = 1; j <= i; ++j) { if (ans[i][j] != '.') vis[ans[i][j] - 'A'] = 1; num[i][j] = ++numcol; } solver.build(2730, numcol + 12); /*******build*******/ for (int id = 0, op; id < 12; ++id) { // every block for (++numcol, op = 0; op <= 1; ++op) { for (int dx = 0; dx <= 1; ++dx) { for (int dy = 0; dy <= 1; ++dy) { for (tx[0] = 1; tx[0] <= 10; ++tx[0]) { for (tx[1] = 1; tx[1] <= tx[0]; ++tx[1]) { bool flag = 1; for (int k = 0; k < len[id]; ++k) { nxt[op] = tx[op] + f[dx] * table[id][k][0]; nxt[op ^ 1] = tx[op ^ 1] + f[dy] * table[id][k][1]; if (vis[id]) { if (ans[nxt[0]][nxt[1]] != id + 'A') { flag = 0; break; } } else if (ans[nxt[0]][nxt[1]] != '.') { flag = 0; break; } } if (!flag) continue; dfn[++numrow] = id; solver.insert(numrow, numcol); for (int k = 0; k < len[id]; ++k) { nxt[op] = tx[op] + f[dx] * table[id][k][0]; nxt[op ^ 1] = tx[op ^ 1] + f[dy] * table[id][k][1]; solver.insert(numrow, num[nxt[0]][nxt[1]]); } } } } } } } /********end********/ if (!solver.dance()) puts("No solution"); else for (int i = 1; i <= 10; ++i, puts("")) for (int j = 1; j <= i; ++j) putchar(ans[i][j]); return 0; } 习题SUDOKU - Sudoku「kuangbin 带你飞」专题三 Dancing Links外部链接夜深人静写算法（九）- Dancing Links X（跳舞链）_WhereIsHeroFrom 的博客》跳跃的舞者，舞蹈链（Dancing Links）算法——求解精确覆盖问题 - 万仓一黍DLX 算法一览 - zhangjianjunab搜索：DLX 算法 - 静听风吟。《算法竞赛入门经典 - 训练指南》注释（两岸用语差异）台灣：直行（column）、橫列（row） ↩本页面最近更新：2024/2/5 00:05:06，更新历史发现错误？想一起完善？ 在 GitHub 上编辑此页！本页面贡献者：LeverImmy, 383494, CCXXXI, dkz051, EarthMessenger, Enter-tainer, Great-designer, iamtwz, Ir1d, kenlig, Konano, ksyx, L1nkzz, NachtgeistW, opsiff, ouuan, SamZhangQingChuan, StudyingFather, W-RJ本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用Copyright © 2016 - 2024 OI Wiki Team Made with Material for MkDocs 最近更新：7ff011ae, 2024-03- 本质就是该消息不会再被任何消费端消费（但你可以自定义某消费者单独处理这些死信）。2 DLX产生场景消息被拒绝(basic.reject/basic.nack)，且requeue = false消息因TTL过期队列达到最大长度，先入队的消息会被删除3 死信的处理过程DLX亦为一个普通的Exchange，它能在任何队列上被指定，实际上就是设置某个队列的属性当某队列中有死信时，RabbitMQ会自动地将该消息重新发布到设置的Exchange，进而被路由到另一个队列可以监听这个队列中的消息做相应的处理。该特性可以弥补RabbitMQ 3.0以前支持的immediate参数的功能4 DLX的配置4.1 设置DLX的exchange和queue并绑定Exchange:dlx.exchangeQueue: dlx.queueRoutingKey:#4.2 正常声明交换机、队列、绑定只不过需要在队列加上一个参数：arguments.put(" x-dead-letter-exchange"，"dlx.exchange");复制这样消息在发生DLX产生条件时，消息即可直接路由到DLX。5 代码实战自定义Con Pro Con 启动Con,查看管控台 现在,让我们停止Con,并启动Pro,由于没有Con,TTL为10s的消息将送往死信队列 10s后 实际环境我们还需要对死信队列进行一个监听和处理，当然具体的处理逻辑和业务相关，这里只是简单演示死信队列是否生效。本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。 原始发表：2020-08-05 ，如有侵权请联系 cloudcommunity@tencent.com 删除前往查看rabbitmq本文分享自 作者个人站点/博客 前往查看如有侵权，请联系 cloudcommunity@tencent.com 删除。本文参与 腾讯云自媒体分享计划 ，欢迎热爱写作的你一起参与！rabbitmq评论登录后参与评论0 条评论热度最新登录 后参与评论推荐阅读LV.关注文章0获赞0目录1 什么是DLX？2 DLX产生场景3 死信的处理过程4 DLX的配置4.1 设置DLX的exchange和queue并绑定4.2 正常声明交换机、队列、绑定5 代码实战领券社区专栏文章阅读清单互动问答技术沙龙技术视频团队主页腾讯云TI平台活动自媒体分享计划邀请作者入驻自荐上首页技术竞赛资源技术周刊社区标签开发者手册开发者实验室关于社区规范免责声明联系我们友情链接腾讯云开发者扫码关注腾讯云开发者领取腾讯云代金券热门产品域名注册云服务器区块链服务消息队列网络加速云数据库域名解析云存储视频直播热门推荐人脸识别腾讯会议企业云CDN加速视频通话图像分析MySQL 数据库SSL 证书语音识别更多推荐数据安全负载均衡短信文字识别云点播商标注册小程序开发网站监控数据迁移Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档Copyright © 2013 - 2024 Tencent Cloud.All Rights Reserved. 腾讯云 版权所有登录 后参与评论00 pnpm dlx | pnpm中文文档 | pnpm中文网 跳到主要内容pnpm 中文网中文文档博客常见问题性能对比社区更多博客常见问题社区性能对比英文官网 Sponsor UsOpen CollectiveGitHub SponsorsCrypto Donations搜索简介用法CLI 命令管理依赖项Patch dependencies审查依赖项运行脚本pnpm runpnpm testpnpm execpnpm dlxpnpm createpnpm startManage environments杂项配置功能特性小窍门进阶CLI 命令运行脚本pnpm dlx本页总览pnpm dlxFetches a package from the registry without installing it as a dependency, hotloads it, and runs whatever default command binary it exposes. For example, to use create-react-app anywhere to bootstrap a react app without needing to install it under another project, you can run: pnpm dlx create-react-app ./my-app This will fetch create-react-app from the registry and run it with the given arguments. You may also specify which exact version of the package you'd like to use: pnpm dlx create-react-app@next ./my-app Options --package The package to install before running the command. Example: pnpm --package=@pnpm/meta-updater dlx meta-updater --helppnpm --package=@pnpm/meta-updater@0 dlx meta-updater --help Multiple packages can be provided for installation: pnpm --package=yo --package=generator-webapp dlx yo webapp --skip-install --shell-mode, -c Runs the command inside of a shell. Uses /bin/sh on UNIX and \cmd.exe on Windows. Example: pnpm --package cowsay --package lolcatjs -c dlx 'echo "hi pnpm" | cowsay | lolcatjs' --silent, -s Only the output of the executed command is printed.编辑此页上一页pnpm exec下一页pnpm createOptions--package 这个模型，泰裤辣!——ThreeZero DLX坦克威震天测评 - 知乎首发于dracos的玩具空间切换模式写文章登录/注册这个模型，泰裤辣!——ThreeZero DLX坦克威震天测评dracos玩具话题下的优秀答主如果说《变形金刚1》中的威震天是真人世电影宇宙的战力巅峰，那在我心中《变形金刚2》的威震天则是当之无愧的颜值巅峰。全身厚重的铠甲，较之第一部更加凌乱破碎的机械感，更为野蛮凶恶的面部细节刻画，以及更畸形的身躯，无处不体现着这位霸天虎王者的凶残与强大。它的载具也从第一部中造型张狂的赛博坦喷气式战机变成了更具力量感和机械感的赛博坦飞行坦克。可谓是人形载具各方面的颜值都进行了一次大升级，再加之其手刃擎天柱的光辉战绩（虽然是三个打一个还被反杀的下饭局），这个版本的威震天给我留下了最为深刻的印象，当听到“威震天”三个字的时候，脑海中第一个浮现的也是它的身影。也许正是因为坦克威的造型和颜值十分受人欢迎，在玩具发行的层面上，坦克威的待遇也一直不错。前有官方电影系出品的领袖级和航海家级模具，后有dmk、官方ss线和它的一系列ko放大。其玩具发行量仅次拥有元老身份的变一飞机威，比起只有两个官方模具，只能靠第三方撑起来的油罐威震天和骑士威震天而言实在是好了太多。而在去年年底，threezero公司也不甘示弱地公布了他们家出品的dlx坦克威合金可动人偶。这是dlx系列真人世五部曲的第四款产品。然而众所周知地，dlx系列前三款的二柱子、天火和骑士柱在还原度和产品质量上都出现了许多令人无语的问题，不是身材比例做崩了就是手腕容易断裂，涂装和细节上也是愈发偷工减料，完全对不起它一千三四百的高昂定价。然而这款dlx坦克威似乎是个例外，早在官图时期我便被它经验的颜值和远超几款前作的还原度给震惊了。因而也是较早入手了这款，然而在入手后把玩了一番后发现，还是那种熟悉的爱恨交加，哭笑不得，只能说还得是你啊30。究竟是什么情况呢？且听我慢慢道来~首先仍然是从包装看起。这款坦克威仍然延续了dlx系列的开窗式设计。不同于前几款汽车人的红色背景，身为霸天虎领袖的威总这次毫不犹豫地选择了虎子最爱的紫色，显得邪气满满。封绘上的威总耀武扬威，一副不可一世的反派雄风，满满的压迫感即便在封绘图上仍然那么明显，在这块30确实做得没话说。一开盒，一股浓浓的油漆味扑面而来。这款坦克威给我的第一印象就是：很黄很暴力！很暴力自然是因为它张狂的造型和沉重的重量，这款坦克威明显比dlx几款前作妖重得多，可能只有天火这个庞然大物能超越它了。很黄则是它的颜色。这家伙全身都涂了一层黄色的渍洗液一样的东西，机体呈现的不是银色而是金色。再佐以全身大量的锈渍，一眼看过去真的是黄得出奇。有些人也许会认为既然变二坦克威在沙漠的戏份居多，因而加这么一层沙漠色滤镜无可厚非，但是我在自习观察了电影后发现老威即便在沙漠中也应该是银闪闪的，即便加了滤镜后也没有dlx这么金。不过这个孰优孰劣还是见仁见智了。配件方面这次比较少，只有两个不同的替换手型和一把大炮。不得不说老威武器少、双手畸形的这个设定可是给厂家省了不少钱。武器配件的还原度自然是没问题的，两个张开的造型手看上去十分张狂，手炮十分庞大造型感满满。这些放到后面介绍。这款坦克威虽然涂装迷惑了一点，但除此之外在还原度上是真的没话说。我只有一句话用以形容：泰裤辣！尤其是这机械感满满的美背，略微佝偻的身形下破碎的钢铁纠结扭曲构成肌肉十足的背部线条，真的是极端破碎极端细致，两个巨大的喷气口凸显着它的强大，身材上虽然头屑驼背但仍然不失宽肩细腰的美型，得益于老威全身金属色的涂装，乍一眼看上去真的好像全金属的模型一样，这只钢铁的怪兽身上无处不充斥着力量和恐怖。这款威震天的头雕细节也极尽还原。老威满脸横肉的面部细节、凶神恶煞的面部表情都得到了神还原。不过问题自然也是有的，首先还是这令人无语的涂装，老威脸上的锈渍做得有点过多了，显得满脸麻子不如你改名威麻子算嘞；除此之外，这款老威的下巴居然不可动。这可是即便官方mpm08都能做出来的东西，下巴加一个分件真有这么难吗？这就是30每次都让我哭笑不得的地方，就是它明明能做得很好，但是却总是贴心地替手艺人们留下生存空间。不过总体而言这个脑袋在dlx系列里面也算上乘之作了，想想它的死敌擎天柱那个唐氏综合征一般的脑袋，简直高下立判。眼灯自然能够打开，通过按压额头的按钮实现。眼灯一开神韵拉满，老威顿时活了过来，隔着屏幕仿佛都能听到它那低沉的咆哮声。不过要注意这次电池的更换需要同时拆掉额头和天灵盖，这导致了天灵盖有点松，讲真这里完全没有分件的必要，为什么就不把额头的分件匀一块给下巴呢……尺寸方面，这个老威的大小有点尴尬。比起同系列的擎天柱只高了半个脑袋。虽然我不信那张饭制的盗版比例图，但是在电影中老威真的绝对不只这么小。这张照片还是我把老威尽可能拉直、擎天柱则是微微屈膝后才有的效果。不知道在比例尺这块30是怎么想的再拿ut油罐威、黑曼巴坦克威与梦工厂坦克威一一对比。这款dlx坦克威甚至只达到了mpm比例的梦工厂威震天的身高。其实在我看来黑曼巴太大，梦工厂太小，ut油罐威才是我心目中变二变三老威的完美比例。同事一对比也能看出来，dlx坦克威是真的很黄……配件方面，首先自然是标志性的手炮。到这里我有的吐槽了。连ss都做得出来的手刀变形，你dlx居然做不到，你比ss还牛逼。是的你没看错，这个手炮上的刀刃是一体的，不可变形不可拆卸。最搞笑的是30还不是为了省成本才搞得一体化，这个手刀其实是有分件的但是被粘住了。你说你真要省成本做个插拔能死啊……我真的是无语死了家人们谁懂啊！要知道，老威在电影中收起手刀开炮的场面还是很多的，30这么一搞让我这种还原党顿时感觉强迫症拉满。手炮自然也是没有灯的。不过据说dlx后续的变七系列，无论是擎天柱大黄蜂还是天灾幻影的手炮都会加灯了，可怜的老威只能成为时代的眼泪了。不过抛开这些槽点单轮还原性，这个手炮还是可圈可点的。刀刃部分十分尖锐，擎天柱有没有感觉到心窝子一凉？手炮的替换方式则是简单粗暴的插拔。老威的右手拆下来后神还原电影结尾被擎天柱一刀断臂的惨状。要是有个被打破的脑壳替换就更好了，不知道未来有没有手艺人会做。替换上手炮后的老威霸气度又提升了一大档次，随便一摆都是电影截图级别的精致。手型总共只有四个，跟擎天柱比少了不止一个档次。由于老威的畸形爪子做不出太多动作，所以厂家也很贴心地减少了替换手型的数量。可动手自然是不可能的，这辈子都不可能的。改造又不会改，只能搞点造型手维持一下站尸这个样子。换上了张开的造型手，这动作张力还是十分完美的。不过我个人还是喜欢老威装上大炮的样子，这才是我心中老威应有的形象。再来看看细节部分。自从dlx骑士柱开了一个恶劣的先河后，dlx在印刷塞星文的道路上是一去不复返了。这次老威全身的塞星文也都是印刷上去的。在骑士柱身上这些可能显得还凑合，但是一到了老威身上真的感觉违和感满满。韩信带净化，不愧是你30。老威身上其他的细节还是十分到位的。这满满的机械感，我顿时感觉我又能行了。赞美之词已经不能表达我对这种机械感的喜爱，尤其是这美背，这美背啊啊——一双美腿也是细节量爆炸。坦克履带的破碎不规则感还原的一丝不苟，甚至还带有联动机构。随着膝盖的活动大腿的履带也随之转动，机械生命体的真实感爆表，这个细节真的爱了。只可惜无法通过视频的形式给大家展现。可动性方面，首先肩甲是能单独活动的，这样就能够给予肩关节更大的活动空间。不过我个人觉得右肩的尖刺型肩甲做的一般，原因就是他总是和身体产生干涉，弄得整个肩甲容易飞出去。干涉源在肩甲后面的这个刺，非常容易和身体产生干涉，无论平举还是旋转都要干涉到，搞得我也是挺难受的。不知道观众老爷们有没有解决方案。。。移开肩甲后的手臂平局可以略微超过一点一百八十度。手肘是双端关节设置，接近一百八十度的活动范围，平转无压力。接下来就是30祖传的龙虾背弯腰关节了得益于丰富的背部零件细节，老威的弯腰并不违和，虽然有些断层但也可以看成是机械的层次感，可能比不上外传柱的惊艳，不过绝对比骑士柱那个疯魔的胸腰过度好太多了。接下来是腿部。这次坦克威的胯并没有采取30前几款那样的下拉式关节。也许考虑到坦克威不需要这么大的前踢幅度吧。前踢时要将裙甲上挑，再将大腿前侧的盖板往下推，彻底避免干涉。做到这一切之后的前踢可以到达九十度，不像前作几款dlx都是接近一百八十度。屈膝关节则是将小腿肚子的盖板往后移，之后可以达到九十度左右的幅度。由于联动的存在极大干扰了老威的屈膝幅度，可谓是为了美观性放弃了一点可动性。不过我个人觉得瑕不掩瑜。毕竟坦克威的体型本身就不适合做出太多浮夸的动作。脚部接地性也是有的，挪开小腿两侧的造型件避免干涉有大概三十度不到的接地幅度。最后还有两个小细节，首先是这个坦克威的喷气口是可以拆卸的，这就为手艺人制作可发光的替换件留了充足的空间，30你真的，我哭死。然后就是安装支架的方式仍然是拔开屁股后面的塞子，这块小零件比较容易丢一定要注意。总体而言，这款坦克威在dlx同系列里算得上上乘之作了。惊艳的外观，奇高的还原度，丰富的细节和别出心裁的联动都是令人眼前一亮的闪光点。然而拉胯的涂装，总是差半口气的设计真是让人明白了什么叫“我觉得保留了一点拉胯的设计，你才知道你玩的是30”。不说了，我这个已经寄出去给手艺人重涂改造了。不过好消息是，从dlx接下来放出的变七擎天柱、猩猩队长、天灾等新品的官图和灰模来看，似乎这些问题正在逐步得到改善。无论是涂装、还原性、还是手炮加灯这样的小细节都越来越好了。尤其是天灾，那个我是真的很馋。到时候肯定也会第一时间购入给兄弟们分享的。也真心希望dlx系列能越做越好吧，毕竟对于我们这种喜欢高还原度不可变产品而又玩不起动辄四五千的dmk的玩家而言，它也是目前唯一的选择了！发布于 2023-10-25 19:23・IP 属地北京变形金刚变形金刚玩具赞同 4添加评论分享喜欢收藏申请转载文章被以下专栏收录dracos的玩具空间变形金刚玩具的把玩
DLX 基因：在发育和癌症中的作用。,Cancers - X-MOL
EN
注册
登录
首页
资讯
期刊
导师
问答
求职
发Paper
文献直达
高级搜索
期刊列表
搜索 当前位置：
X-MOL 学术
›
Cancers
›
论文详情
Our official English website, www.x-mol.net, welcomes your feedback! (Note: you will need to create a separate account there.)
DLX 基因：在发育和癌症中的作用。
Cancers
(
IF 5.2
)
Pub Date : 2021-06-15 , DOI: 10.3390/cancers13123005
Yinfei Tan
1
,
Joseph R Testa
1,
2
Affiliation Genomics Facility, Fox Chase Cancer Center, Philadelphia, PA 19111, USA. Cancer Signaling and Epigenetics Program, Fox Chase Cancer Center, Philadelphia, PA 19111, USA. 同源盒基因控制发育过程中的身体模式和细胞命运决定。同源盒基因由许多家族组成，只有其中一些家族在肿瘤发生中的可能作用得到了研究。HOX 家族基因的失调已广泛涉及癌症病因。DLX 同源盒基因属于 NK 样家族，在发育和癌症中发挥双重作用。DLX 基因是参与调节脊椎动物颅面结构发育的关键转录因子。三个 DLX 双基因在鳃弓中有重叠表达。DLX 功能的破坏对器官发生具有破坏性后果，并且与人类的某些先天性疾病有关。DLX 基因在肿瘤发生中的作用才刚刚开始出现。DLX2 通过调节 p53 功能减少细胞衰老，而 DLX4 与乳腺癌的转移有关。在人类卵巢癌细胞中，DLX5 对于调节 AKT 信号传导至关重要，从而促进细胞增殖和存活。我们之前曾将 Dlx5 作为由 Akt2 的组成型活性形式驱动的鼠 T 细胞淋巴瘤中的致癌基因。在该小鼠模型中，Dlx5 的过度表达是由与 Dlx5 基因座附近的 Tcr-β 启动子区域并列的染色体重排引起的。此外，过表达 Dlx5 的转基因小鼠，特别是在未成熟的 T 细胞中，会发展为自发性胸腺淋巴瘤。该小鼠模型中的肿瘤发生涉及 Dlx5 与 Notch1 和 Notch3 基因位点的结合以激活它们的转录。Dlx5 还与 Akt 信号合作，通过激活 Wnt 信号加速淋巴瘤的形成。我们还讨论了人类 DLX5 在几种人类恶性肿瘤中异常表达的事实。
"点击查看英文标题和摘要"
DLX Genes: Roles in Development and Cancer.
Homeobox genes control body patterning and cell-fate decisions during development. The homeobox genes consist of many families, only some of which have been investigated regarding a possible role in tumorigenesis. Dysregulation of HOX family genes have been widely implicated in cancer etiology. DLX homeobox genes, which belong to the NK-like family, exert dual roles in development and cancer. The DLX genes are the key transcription factors involved in regulating the development of craniofacial structures in vertebrates. The three DLX bigenes have overlapping expression in the branchial arches. Disruption of DLX function has destructive consequences in organogenesis and is associated with certain congenital disorders in humans. The role of DLX genes in oncogenesis is only beginning to emerge. DLX2 diminishes cellular senescence by regulating p53 function, whereas DLX4 has been associated with metastasis in breast cancer. In human ovarian cancer cells, DLX5 is essential for regulating AKT signaling, thereby promoting cell proliferation and survival. We previously implicated Dlx5 as an oncogene in murine T-cell lymphoma driven by a constitutively active form of Akt2. In this mouse model, overexpression of Dlx5 was caused by a chromosomal rearrangement that juxtaposed the Tcr-beta promoter region near the Dlx5 locus. Moreover, transgenic mice overexpressing Dlx5, specifically in immature T-cells, develop spontaneous thymic lymphomas. Oncogenesis in this mouse model involves binding of Dlx5 to the Notch1 and Notch3 gene loci to activate their transcription. Dlx5 also cooperates with Akt signaling to accelerate lymphomagenesis by activating Wnt signaling. We also discuss the fact that human DLX5 is aberrantly expressed in several human malignancies.
更新日期：2021-06-15
点击分享
查看原文
点击收藏 取消收藏
新增笔记
公开下载
阅读更多本刊最新论文
本刊介绍/投稿指南
PDF
https://www.mdpi.com/2072-6694/13/12/3005/pdf
HTML
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8232755
全部期刊列表>>
学术期刊
行业资讯
全球导师
X-MOL问答
求职广场
网址导航
关于我们
帮助中心
客服邮箱：service@x-mol.com 官方微信：X-molTeam2 邮编：100098 地址：北京市海淀区知春路56号中航科技大厦
Copyright © 2014-2024 北京衮雪科技有限公司 All Rights Reserved 京ICP备11026495号-2
京公网安备 11010802027423号
down
wechat
bug bug算法竞赛学习笔记——DLX - 知乎
RabbitMQ - 死信队列(Dead-Letter-Exchange ) - 知乎
Dancing Links - OI Wiki
ing Links - OI Wiki 跳转至 OI Wiki Dancing Links 正在初始化搜索引擎 OI-wiki/OI-wiki 简介 比赛相关 工具软件 语言基础 算法基础 搜索 动态规划 字符串 数学 数据结构 图论 计算几何 杂项 专题 关于 Hulu OI Wiki OI-wiki/OI-wiki 简介 简介 Getting Started 关于本项目 如何参与 OI Wiki 不是什么 格式手册 数学符号表 F.A.Q. 用 Docker 部署 OI Wiki 镜像站列表 致谢 比赛相关 比赛相关 比赛相关简介 赛事 赛事 OI 赛事与赛制 ICPC/CCPC 赛事与赛制 题型 题型 题型概述 交互题 学习路线 学习资源 技巧 技巧 读入、输出优化 分段打表 常见错误 常见技巧 出题 工具软件 工具软件 工具软件简介 代码编辑工具 代码编辑工具 Vim Emacs VS Code Atom Eclipse Notepad++ Kate Dev-C++ CLion Geany Xcode GUIDE Sublime Text CP Editor 评测工具 评测工具 评测工具简介 Arbiter Cena CCR Plus Lemon 命令行 编译器 WSL (Windows 10) Special Judge Testlib Testlib Testlib 简介 通用 Generator Validator Interactor Checker Polygon OJ 工具 LaTeX 入门 Git 语言基础 语言基础 语言基础简介 C++ 基础 C++ 基础 Hello, World! C++ 语法基础 变量 运算 流程控制语句 流程控制语句 分支 循环 高级数据类型 高级数据类型 数组 结构体 联合体 指针 函数 文件操作 C++ 标准库 C++ 标准库 C++ 标准库简介 STL 容器 STL 容器 STL 容器简介 迭代器 序列式容器 关联式容器 无序关联式容器 容器适配器 STL 算法 bitset string pair C++ 进阶 C++ 进阶 类 命名空间 值类别 重载运算符 引用 常值 新版 C++ 特性 Lambda 表达式 pb_ds pb_ds pb_ds 简介 堆 平衡树 编译优化 C++ 与其他常用语言的区别 Pascal 转 C++ 急救 Python 速成 Java 速成 Java 进阶 算法基础 算法基础 算法基础简介 复杂度 枚举 模拟 递归 & 分治 贪心 排序 排序 排序简介 选择排序 冒泡排序 插入排序 计数排序 基数排序 快速排序 归并排序 堆排序 桶排序 希尔排序 锦标赛排序 tim排序 排序相关 STL 排序应用 前缀和 & 差分 二分 倍增 构造 搜索 搜索 搜索部分简介 DFS（搜索） BFS（搜索） 双向搜索 启发式搜索 A* 迭代加深搜索 IDA* 回溯法 Dancing Links Dancing Links 目录 精确覆盖问题 定义 解释 问题转化 实现 暴力 1 暴力 2 重复覆盖问题 X 算法 过程 Dancing Links 优化的 X 算法 预编译命令 定义 过程 remove 操作 recover 操作 build 操作 insert 操作 dance 操作 模板 性质 建模 例题 1 P1784 数独 例题 2 靶形数独 例题 3 「NOI2005」智慧珠游戏 习题 外部链接 注释 Alpha-Beta 剪枝 优化 动态规划 动态规划 动态规划部分简介 动态规划基础 记忆化搜索 背包 DP 区间 DP DAG 上的 DP 树形 DP 状压 DP 数位 DP 插头 DP 计数 DP 动态 DP 概率 DP DP 优化 DP 优化 单调队列/单调栈优化 斜率优化 四边形不等式优化 状态设计优化 其它 DP 方法 字符串 字符串 字符串部分简介 字符串基础 标准库 字符串匹配 字符串哈希 字典树 (Trie) 前缀函数与 KMP 算法 Boyer–Moore 算法 Z 函数（扩展 KMP） 自动机 AC 自动机 后缀数组 (SA) 后缀数组 (SA) 后缀数组简介 最优原地后缀排序算法 后缀自动机 (SAM) 后缀平衡树 广义后缀自动机 后缀树 Manacher 回文树 序列自动机 最小表示法 Lyndon 分解 Main–Lorentz 算法 数学 数学 数学部分简介 符号 进位制 位运算 二进制集合操作 平衡三进制 高精度计算 快速幂 置换和排列 弧度制与坐标系 复数 数论 数论 数论基础 素数 最大公约数 数论分块 欧拉函数 筛法 Meissel–Lehmer 算法 分解质因数 裴蜀定理 类欧几里德算法 欧拉定理 & 费马小定理 乘法逆元 线性同余方程 中国剩余定理 升幂引理 威尔逊定理 卢卡斯定理 同余方程 二次剩余 原根 离散对数 剩余 莫比乌斯反演 杜教筛 Powerful Number 筛 Min_25 筛 洲阁筛 连分数 Stern–Brocot 树与 Farey 序列 二次域 循环连分数 Pell 方程 多项式与生成函数 多项式与生成函数 多项式与生成函数简介 代数基本定理 快速傅里叶变换 快速数论变换 快速沃尔什变换 Chirp Z 变换 多项式牛顿迭代 多项式多点求值|快速插值 多项式初等函数 常系数齐次线性递推 多项式平移|连续点值平移 符号化方法 普通生成函数 指数生成函数 狄利克雷生成函数 组合数学 组合数学 排列组合 抽屉原理 容斥原理 康托展开 斐波那契数列 错位排列 卡特兰数 斯特林数 贝尔数 伯努利数 Entringer Number Eulerian Number 分拆数 范德蒙德卷积 图论计数 线性代数 线性代数 线性代数简介 向量 内积和外积 矩阵 初等变换 行列式 线性空间 线性基 线性映射 特征多项式 对角化 Jordan标准型 线性规划 线性规划 线性规划简介 单纯形算法 群论 群论 群论简介 置换群 概率论 概率论 基本概念 条件概率与独立性 随机变量 随机变量的数字特征 概率不等式 博弈论 博弈论 博弈论简介 公平组合游戏 非公平组合游戏 反常游戏 数值算法 数值算法 插值 数值积分 高斯消元 牛顿迭代法 傅里叶-莫茨金消元法 序理论 杨氏矩阵 Schreier–Sims 算法 Berlekamp–Massey 算法 数据结构 数据结构 数据结构部分简介 栈 队列 链表 哈希表 并查集 并查集 并查集 并查集复杂度 堆 堆 堆简介 二叉堆 配对堆 左偏树 块状数据结构 块状数据结构 分块思想 块状数组 块状链表 树分块 Sqrt Tree 单调栈 单调队列 ST 表 树状数组 线段树 李超线段树 区间最值操作 & 区间历史最值 划分树 二叉搜索树 & 平衡树 二叉搜索树 & 平衡树 二叉搜索树 & 平衡树 Treap Splay 树 WBLT Size Balanced Tree AVL 树 B 树 B+ 树 替罪羊树 Leafy Tree 笛卡尔树 红黑树 左偏红黑树 AA 树 2-3 树 2-3-4 树 跳表 可持久化数据结构 可持久化数据结构 可持久化数据结构简介 可持久化线段树 可持久化块状数组 可持久化平衡树 可持久化字典树 可持久化可并堆 树套树 树套树 线段树套线段树 平衡树套线段树 线段树套平衡树 树状数组套权值线段树 分块套树状数组 K-D Tree 动态树 动态树 Link Cut Tree 全局平衡二叉树 Euler Tour Tree Top Tree 析合树 PQ 树 手指树 霍夫曼树 图论 图论 图论部分简介 图论相关概念 图的存储 DFS（图论） BFS（图论） 树上问题 树上问题 树基础 树的直径 最近公共祖先 树的重心 树链剖分 树上启发式合并 虚树 树分治 动态树分治 AHU 算法 树哈希 树上随机游走 矩阵树定理 有向无环图 拓扑排序 最小生成树 斯坦纳树 最小树形图 最小直径生成树 最短路 拆点 差分约束 k 短路 同余最短路 连通性相关 连通性相关 强连通分量 双连通分量 割点和桥 圆方树 点/边连通度 环计数问题 2-SAT 欧拉图 哈密顿图 二分图 最小环 平面图 图的着色 网络流 网络流 网络流简介 最大流 最小割 费用流 上下界网络流 Stoer–Wagner 算法 图的匹配 图的匹配 图匹配 增广路 二分图最大匹配 二分图最大权匹配 一般图最大匹配 一般图最大权匹配 Prüfer 序列 LGV 引理 弦图 最大团搜索算法 支配树 图上随机游走 计算几何 计算几何 计算几何部分简介 二维计算几何基础 三维计算几何基础 距离 Pick 定理 三角剖分 凸包 扫描线 旋转卡壳 半平面交 平面最近点对 随机增量法 反演变换 计算几何杂项 杂项 杂项 杂项简介 离散化 双指针 离线算法 离线算法 离线算法简介 CDQ 分治 整体二分 莫队算法 莫队算法 莫队算法简介 普通莫队算法 带修改莫队 树上莫队 回滚莫队 二维莫队 莫队二次离线 莫队配合 bitset 分数规划 随机化 随机化 随机函数 随机化技巧 爬山算法 模拟退火 悬线法 计算理论基础 字节顺序 约瑟夫问题 格雷码 表达式求值 在一台机器上规划任务 主元素问题 Garsia–Wachs 算法 15-puzzle Kahan 求和 珂朵莉树/颜色段均摊 专题 专题 RMQ 并查集应用 括号序列 线段树与离线询问 关于 Hulu 关于 Hulu 关于 Hulu 目录 精确覆盖问题 定义 解释 问题转化 实现 暴力 1 暴力 2 重复覆盖问题 X 算法 过程 Dancing Links 优化的 X 算法 预编译命令 定义 过程 remove 操作 recover 操作 build 操作 insert 操作 dance 操作 模板 性质 建模 例题 1 P1784 数独 例题 2 靶形数独 例题 3 「NOI2005」智慧珠游戏 习题 外部链接 注释 Dancing Links本页面将介绍精确覆盖问题、重复覆盖问题，解决这两个问题的算法「X 算法」，以及用来优化 X 算法的双向十字链表 Dancing Link。本页也将介绍如何在建模的配合下使用 DLX 解决一些搜索题。精确覆盖问题定义精确覆盖问题（英文：Exact Cover Problem）是指给定许多集合 以及一个集合 ，求满足以下条件的无序多元组 ：解释例如，若给出则 为一组合法解。问题转化将 中的所有数离散化，可以得到这么一个模型：给定一个 01 矩阵，你可以选择一些行（row），使得最终每列（column）1都恰好有一个 1。 举个例子，我们对上文中的例子进行建模，可以得到这么一个矩阵：其中第 行表示着 ，而这一行的每个数依次表示 。实现暴力 1一种方法是枚举选择哪些行，最后检查这个方案是否合法。因为每一行都有选或者不选两种状态，所以枚举行的时间复杂度是 的；而每次检查都需要 的时间复杂度。所以总的复杂度是 。实现 1RabbitMQ高级特性-死信队列(DLX,Dead-Letter-Exchange)-腾讯云开发者社区-腾讯云
itMQ高级特性-死信队列(DLX,Dead-Letter-Exchange)-腾讯云开发者社区-腾讯云JavaEdgeRabbitMQ高级特性-死信队列(DLX,Dead-Letter-Exchange)关注作者腾讯云开发者社区文档建议反馈控制台首页学习活动专区工具TVP最新优惠活动文章/答案/技术大牛搜索搜索关闭发布登录/注册首页学习活动专区工具TVP最新优惠活动返回腾讯云官网JavaEdge首页学习活动专区工具TVP最新优惠活动返回腾讯云官网社区首页 >专栏 >RabbitMQ高级特性-死信队列(DLX,Dead-Letter-Exchange)RabbitMQ高级特性-死信队列(DLX,Dead-Letter-Exchange)JavaEdge关注发布于 2021-02-22 16:07:251.9K0发布于 2021-02-22 16:07:25举报文章被收录于专栏：JavaEdgeJavaEdge1 什么是DLX？利用DLX，当消息在一个队列中变成死信后，它能被重新发布到另一个Exchange中，这个Exchange就是DLX。pnpm dlx | pnpm中文文档 | pnpm中文网
这个模型，泰裤辣!——ThreeZero DLX坦克威震天测评 - 知乎
DLX_百度百科
百度百科 网页新闻贴吧知道网盘图片视频地图文库资讯采购百科百度首页登录注册进入词条全站搜索帮助首页秒懂百科特色百科知识专题加入百科百科团队权威合作下载百科APP个人中心收藏查看我的收藏0有用+10DLX播报讨论上传视频多元未饱和型指令集结构DLX是一种多元未饱和型指令集结构，DLX 代表中级车、加长轴距版本、内饰改款、尊贵车豪华版车型。中文名DLXDLX代表中级车、加长轴距版本G Lk5最低配车型GLXk5较高的配置车型目录1DLX简介2汽车类DLX的用意3DLX的英文翻译意DLX简介播报编辑DLX是一种多元未饱和型指令集结构。称之为多元未饱和型结构，是因为它不仅体现了当今多种机器（AMD29K、DEC station 3100、HP850、IBM 801、Intel i860、MIPS M/120A、MIPS M/1000、Motorola 88k、RISC I、SGI4D/60、SPARC station 1、Sun 4/110、Sun 4/260等）指令集结构的共同特点，而且它还将会体现未来一些机器的指令集结构的特点。这些机器的指令集结构设计思想都和DLX指令集结构的设计思想十分相似，它们都强调：具有一个简单的Load/Store指令集；注重指令流水效率；简化指令的译码；高效支持编译器。在计算机科学中，DLX是Dancing Links的缩写，该算法由Donald Knuth提出，有效地利用与Algorithm X。汽车类DLX的用意播报编辑DLX 代表中级车、加长轴距版本、内饰改款、尊贵车豪华版车型（欧系车命名方式）以起亚K5 2012款 2.0L AT DLX为例：GL：k5最低配车型GLX：k5较高的配置车型全部车型配置等级是：GL、GLS、DLX、DLX2、Premium（由低往高） [1]DLX的英文翻译意播报编辑abbr.deluxe 豪华的，高级的;DLX常放于专辑后。 [2]新手上路成长任务编辑入门编辑规则本人编辑我有疑问内容质疑在线客服官方贴吧意见反馈投诉建议举报不良信息未通过词条申诉投诉侵权信息封禁查询与解封©2024 Baidu 使用百度前必读 | 百科协议 | 隐私政策 | 百度百科合作平台 | 京ICP证030173号 京公网安备110000020000
DLX 基因：在发育和癌症中的作用。,Cancers - X-MOL