• 8.11学习日志 后缀数组+DLX

    DLX

    精确覆盖或者说是不重不漏问题

    抽象模型是：给定n*m矩阵的0-1矩阵，请选择k行使得这k行的每一列都有且仅有一个1

    本质：应用双向循环交叉链实现集合精确覆盖问题。

    P4929 【模板】舞蹈链（DLX）

    #include
#include
#include
#include
using namespace std;
const int mx=250501;//n*m+m<=250500
inline int Read(){
	int x=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return x;
}
int n,m;
int cnt;
int l[mx],r[mx],u[mx],d[mx],col[mx],row[mx];//每个点的左右上下指针，所在行列
int h[mx];//每行的头结点
int s[mx];//每列的节点数
int ansk[mx];//选了那些集合
void init(int m)
{//m个元素
	for(register int i=0;i<=m;i++)
    {
		r[i]=i+1;
		l[i]=i-1;
		u[i]=d[i]=i;
	}
	r[m]=0;
	l[0]=m;
	memset(h,-1,sizeof(h));
	memset(s,0,sizeof(s));
	cnt=m+1;
}//初始化
inline void link(int R,int C){//R行C列插入点
	s[C]++;
	row[cnt]=R;
	col[cnt]=C;
	u[cnt]=C;
	d[cnt]=d[C];
	u[d[C]]=cnt;
	d[C]=cnt;
	if(h[R]==-1)h[R]=r[cnt]=l[cnt]=cnt;//该行没有点，直接加入
	else{
		r[cnt]=h[R];
		l[cnt]=l[h[R]];
		r[l[h[R]]]=cnt;
		l[h[R]]=cnt;
	}
	cnt++;
	return;
}
inline void remove(int C){//删除涉及C列的集合
	r[l[C]]=r[C],l[r[C]]=l[C];
	for(int i=d[C];i!=C;i=d[i]){
		for(int j=r[i];j!=i;j=r[j]){
			u[d[j]]=u[j];
			d[u[j]]=d[j];
			s[col[j]]--;
		}
	}
}
inline void resume(int C){//恢复涉及C列的集合
	for(int i=u[C];i!=C;i=u[i]){
		for(int j=l[i];j!=i;j=l[j]){
			u[d[j]]=j;
			d[u[j]]=j;
			s[col[j]]++;
		}
	}
	r[l[C]]=C;
	l[r[C]]=C;
}
bool dance(int deep){
	if(r[0]==0){
		register int i=0;
		for(i=0;i<deep;i++)printf("%d ",ansk[i]);
		return 1;
	}
	int c=r[0];
	int i,j;
	for(i=r[0];i!=0;i=r[i])if(s[i]<s[c])c=i;
	remove(c);
	for(i=d[c];i!=c;i=d[i]){
		ansk[deep]=row[i];
		for(j=r[i];j!=i;j=r[j])remove(col[j]);
		if(dance(deep+1))return 1;
		for(j=l[i];j!=i;j=l[j])resume(col[j]);
	}
	resume(c);
	return 0;
}
int main()
{
	n=Read(),m=Read();
	register int i,j;
	int f;
	init(m);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			f=Read();
			if(f)
			link(i,j);
		}
	}
	if(!dance(0))printf("No Solution!");
	return 0;
}


    • 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

    模板当中通常需要修改的地方是link函数的使用和dance函数的记录答案部分

    for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			f=Read();
			if(f)
			link(i,j);
		}
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    bool dance(int deep){
	if(r[0]==0){
		register int i=0;
		for(i=0;i<deep;i++)printf("%d ",ansk[i]);
		return 1;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    其余部分则几乎不需要做出改动。

    类似问题：最小区间覆盖，区间有重覆盖问题（这个问题不建议用DLX的修改版本，直接写搜索就好了，或者for循环贪心就可以，和区间最小覆盖很像）。

    数独问题

    这个属于DLX应用起来很难的问题了，这里用DFS的话题目的确只有黄色水准，但是如果是DLX，估计是紫题偏难的水准。

    后缀数组——处理字符串的有力工具.pdf
    pdf 0星 超过10%的资源 51KB
    下载
    #include
#include
#include
#include
using namespace std;
#define mx 100100//其实不用这么大只要大于729*324即可 
int sum=0;
int a[10][10];//每个点的数
inline int Read(){
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return x;
}//快读好习惯 
struct DLX{
	int m,cnt;//矩阵的长，宽，点的数量
	int l[mx],r[mx],u[mx],d[mx],row[mx],col[mx];//每个点的左，右，上下，行，列信息 
	int h[mx];//每行的头结点 
	int s[mx];//每列的结点数 
	int ansk[mx];//ansk[] 装答案（选了哪几行）
	void init(int _n,int _m){
		m=_m;
		int i;
		for(i=0;i<=m;i++){
			r[i]=i+1;l[i]=i-1;u[i]=d[i]=i;
		}
		r[m]=0;//m右边是0 
		l[0]=m;//0左边是m 
		memset(h,-1,sizeof(h));
		memset(s,0,sizeof(s));
		cnt=m+1;//开始时有m个结点（0结点和各列头结点） 
	}//初始化，生成每列的头
	void link(int R,int C){
		s[C]++;
		row[cnt]=R;
		col[cnt]=C;
		u[cnt]=C;
		d[cnt]=d[C];
		u[d[C]]=cnt;
		d[C]=cnt;
		if(h[R]<0)h[R]=r[cnt]=l[cnt]=cnt;//该行没有别的点,把第一个加入的点作为该行的行头结点 
		else{
			r[cnt]=h[R];
			l[cnt]=l[h[R]];
			r[l[h[R]]]=cnt;
			l[h[R]]=cnt;
		}
		cnt++;
	}//在r行c列插入点
	void remove(int c){
		r[l[c]]=r[c],l[r[c]]=l[c];
		for(int i=d[c];i!=c;i=d[i]){
			for(int j=r[i];j!=i;j=r[j]){
				u[d[j]]=u[j];
				d[u[j]]=d[j];
				s[col[j]]--;
			}
		}
	}//删除c列和c列上有点的行
	void resume(int c){
		for(int i=u[c];i!=c;i=u[i]){
			for(int j=l[i];j!=i;j=l[j]){
				u[d[j]]=j;
				d[u[j]]=j;
				s[col[j]]++;
			}
		}
		r[l[c]]=c;
		l[r[c]]=c;
	}//恢复c列和c列上有点的行
	bool dance(int deep){
		if(r[0]==0){
			int x,y,v;
			for(int i=0;i<deep;i++){
			x=(ansk[i]-1)/9/9;
			y=(ansk[i]-1)/9%9;
			v=(ansk[i])%9;//把行信息转换成对应的点的值 
			if(v==0)v=9;//防止9的倍数%9==0 
			a[x][y]=v;
			}
			return 1;//只要找一组解 
		}
		int c=r[0];
		for(int i=r[0];i!=0;i=r[i])if(s[i]<s[c])c=i;//找到点最少的列
		remove(c);
		for(int i=d[c];i!=c;i=d[i]){
			ansk[deep]=row[i];
			for(int j=r[i];j!=i;j=r[j]) remove(col[j]);
			if(dance(deep+1)==1)return 1;//只要找一组解 
			for(int j=l[i];j!=i;j=l[j]) resume(col[j]);
		}
		resume(c); 
		return false;
	}
}dlx;
int main(){
	dlx.init(729,324);
	//729:
	//9^4种情况对应9^4行;
	//324:
	//对应数独的规则:每个格子，每行，每列，每个九宫只能填1~9各一次 
	//对于第m列：
	//若m在[1,81]表示在(m/9，m%9)填数 
	//若m在[81*1,81*2]在第1+（m-81）/9行填1+（m-81）%9 
	//若m在[81*2,81*3]在第1+（m-81*2）/9列填1+（m-81*2）%9 
	//若m在[81*3,81*4]在第1+（m-81*3）/9宫填1+（m-81*3）%9
	int x;
	int o;
	for(int i=0;i<=8;i++){
	 	for(int j=0;j<=8;j++){
	 	a[i][j]=x=Read();
		 for(int k=1;k<=9;k++){
		 	if(x!=k&&x!=0)continue;//已经填好的点就不用考虑了 
		 	o=i*9*9+j*9+k;
		 	dlx.link(o,i*9+j+1);
		 	dlx.link(o,i*9+81+k);
		 	dlx.link(o,j*9+81*2+k);
		 	dlx.link(o,81*3+(i/3*3+j/3)*9+k);//把点对应成行（集合） 
		 }
		 }
	 }
	 dlx.dance(0);
	for(int i=0;i<=8;i++){
		for(int j=0;j<=8;j++)printf("%d ",a[i][j]);
		printf("\n");
	}
	return 0;
}

    • 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

    最后来一个题目捏
    P2870 [USACO07DEC]Best Cow Line G

    题意：给定一个字符串，每次可以从前或者后方拿出一个字符，然后放到新的字符的尾部，问这样一遍操作过后，新字符串的最小字典序形态是什么，输出这个新字符串。

    思路
    1.我们发现当首尾字符不相等时显然优先把字典序小的字母挑出来
    2.但是发现当首尾一致的情况下很难判断
    比如BABB，我们如果按照相等则右方先行就会得到BBAB显然是错的，同理BBAB会让左方现行错误。

    怎么解决呢？
    我么可以前后临时建立两个指针来遍历到他们不想等的那个位置，然后把前后这两段遍历出来的子串做个字典序比较，字典序小的一方获胜。
    但是，，同志，这东西复杂度n2啊，5e5的长度复杂度铁定爆炸了

    如果对于str[L]==str[R]
    显然只要对比从L开始的后缀和截止到R的前缀就可以了
    那么考虑用一个算法来轻松获得这两个子串字典序的排名。
    考虑SA数组，将原串反转后接上原串

    对于截止到i的前缀就是rk[2*n+1-r]，对于从i开始的后缀就是rk[i]

    具体实现里我加入0作为分隔符，所以截止到i的前缀是rk[2*n+2-r]。

    我们要注意桶排序不要落下ASCII码为0的位置，要不然rk数组就出错了。

    #include 
using namespace std;
const int N = 1e6+100;
char s[N<<1];
char ans[N<<1];
int y[N<<1],x[N<<1],c[N<<1],sa[N<<1],rk[N<<1],height[N<<1];
int n,m;
void get_SA()
{
	for(int i=1;i<=n;++i)
    {
        x[i]=s[i];
        ++c[x[i]];
    }
    for(int i=1;i<=m;++i)
        c[i]+=c[i-1];
    for(int i=n;i>=1;--i)
        sa[c[x[i]]--]=i;
    for (int k=1;k<=n;k<<=1)
    {
        int num=0;
        for(int i=n-k+1;i<=n;++i)
        y[++num]=i;
        for (int i=1;i<=n;++i)
        if (sa[i]>k)
        y[++num]=sa[i]-k;
        for (int i=0;i<=m;++i)
         c[i]=0;
        for (int i=1;i<=n;++i)
        ++c[x[i]];
        for (int i=1;i<=m;++i)
        c[i]+=c[i-1];
        for (int i=n;i>=1;--i)
        sa[c[x[y[i]]]--]=y[i],y[i]=0;
        swap(x,y);
        x[sa[1]]=1;num=1;
        for (int i=2;i<=n;++i)
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) ? num : ++num;
        if (num==n) break;
        m=num;
    }
}
void get_height()
{
    int k=0;
    for (int i=1;i<=n;++i)
        rk[sa[i]]=i;
    for (int i=1;i<=n;++i)
    {
        if (rk[i]==1) continue;//第一名height为0
        if (k) --k;//h[i]>=h[i-1]+1;
        int j=sa[rk[i]-1];
        while (j+k<=n && i+k<=n && s[i+k]==s[j+k]) ++k;
        height[rk[i]]=k;//h[i]=height[rk[i]];
    }
}
void init()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        s[n*2+2-i]=s[i];
    }
    s[n+1]=(char)0;
    m=130;
    n=n*2+1;
    get_SA();
    get_height();
   /* for(int i=1;i<=n;i++)
        cout<
}
int main()
{
    init();
    n=(n-1)/2;
    int l=1,r=n;
    int cnt=0;
    while(l<r)
    {
        if(s[l]<s[r])
            ans[++cnt]=(char)s[l++];
        else if(s[l]>s[r])
            ans[++cnt]=(char)s[r--];
        else
            if(rk[l]<rk[2*n+2-r])
                ans[++cnt]=(char)s[l++];
            else
                ans[++cnt]=(char)s[r--];
    }
    ans[++cnt]=(char)s[l];
    for(int i=1;i<=cnt;i++)
    {
        cout<<ans[i];
        if(!(i%80))
            cout<<endl;
    }
}


    • 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

    获得了升级版的模板

    #include 
using namespace std;
const int N = 1e6+100;
char s[N<<1];
char ans[N<<1];
int y[N<<1],x[N<<1],c[N<<1],sa[N<<1],rk[N<<1],height[N<<1];
int n,m;
void Sort()
{
     for(int i=0;i<=m;++i)
         c[i]=0;
     for(int i=1;i<=n;++i)
        ++c[x[i]];
     for(int i=1;i<=m;++i)
        c[i]+=c[i-1];
     for(int i=n;i>=1;--i)
        sa[c[x[y[i]]]--]=y[i],y[i]=0;
}
void get_SA()
{
	for(int i=1;i<=n;++i)
    {
        x[i]=s[i];y[i]=i;
    }
    Sort();
    for(int k=1;k<=n;k<<=1)
    {
        int num=0;
        for(int i=n-k+1;i<=n;++i)
            y[++num]=i;
        for(int i=1;i<=n;++i)
            if(sa[i]>k)
            y[++num]=sa[i]-k;
        Sort();swap(x,y);x[sa[1]]=1;num=1;
        for(int i=2;i<=n;++i)
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
        if (num==n)
            break;
        m=num;
    }
}
void get_height()
{
    int k=0;
    for(int i=1;i<=n;++i)
        rk[sa[i]]=i;
    for (int i=1;i<=n;++i)
    {
        if (rk[i]==1)
            continue;//第一名height为0
        if (k) --k;//h[i]>=h[i-1]+1;
        int j=sa[rk[i]-1];
        while (j+k<=n && i+k<=n && s[i+k]==s[j+k]) ++k;
        height[rk[i]]=k;//h[i]=height[rk[i]];
    }
}
void init()
{
    cin>>s+1;
    m=130;
    n=strlen(s+1);
    get_SA();
    for(int i=1;i<=n;i++)
        cout<<sa[i]<<" ";

}
int main()
{
    init();
}


    • 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
  • 相关阅读:
    四川古力未来科技公司抖音小店：靠谱的新电商之旅
    【python入门专项练习】-N01.输入输出&&类型转换
    第七讲：利用类事件改变对象的属性(上)
    SpringMvc执行流程
    Java实现自动玩王铲铲的致富之路小程序游戏
    获取dubbo源码编译并导入idea以及启动入门项目dubbo-demo
    Java 使用 ant.jar 执行 SQL 脚本文件
    Web前端：JavaScript编程语言有哪些优势?
    Django笔记四十之运行Django环境的python脚本
    【Go电商实战04】为什么GoFrame不支持migrate功能？我还特意去问了框架作者
  • 原文地址：https://blog.csdn.net/qq_35866893/article/details/126293280