月度归档：2014年06月

[LeetCode Largest Rectangle in Histogram]

题意：给出一个长度n的数组，每个值为非负数，描述一个宽为1的立柱的高h[i]，求立柱围成区域中最大的矩形区域面积。

分析：
对于每个立柱i，求出满足h[j]到h[i-1]都不小于h[i]的最左值j，记i-j+1为lc[i]，类似地求出rc[i]，那么位置i对应的最大可行面积即为h[i]*(lc[i]+rc[i]+1)。

以求lc[i]为例，需要一个单调栈，单调栈中由底到顶依次记录扫描到i之前的上升序列d[l]及其位置di[l]，扫描到i时，初始化lc[i]=1，对于所有高度d[l]大于等于h[i]的栈顶元素，依次出栈，并将其lc[di[l]]加到lc[i]中，最后将h[i]和i入栈。

时间复杂度方面，计算lc和rc时，每个元素刚好入栈、出战各一次，因此根据平摊分析，时间复杂度是O(n)的。

int d[100000], di[100000], lc[100000], rc[100000], n, ans;

class Solution {
public:
    int largestRectangleArea(vector<int> &h) {
        n=h.size(); ans=0;
        int i, l;
        for(i=0, l=0; i<n; i++)
        {
            for(lc[i]=1; l&&h[i]<=d[l-1]; l--)
                lc[i]+=lc[di[l-1]];
            d[l]=h[i];
            di[l++]=i;
        }
        for(i=n-1, l=0; i>-1; i--)
        {
            for(rc[i]=1; l&&h[i]<=d[l-1]; l--)
                rc[i]+=rc[di[l-1]];
            d[l]=h[i];
            di[l++]=i;
        }
        for(i=0; i<n; i++)
            ans=max(ans, h[i]*(lc[i]+rc[i]-1));
        return ans;
    }
};

int d[100000], di[100000], lc[100000], rc[100000], n, ans;

class Solution {

public:

int largestRectangleArea(vector<int> &h) {

n=h.size(); ans=0;

int i, l;

for(i=0, l=0; i<n; i++)

{

for(lc[i]=1; l&&h[i]<=d[l-1]; l--)

lc[i]+=lc[di[l-1]];

d[l]=h[i];

di[l++]=i;

}

for(i=n-1, l=0; i>-1; i--)

{

for(rc[i]=1; l&&h[i]<=d[l-1]; l--)

rc[i]+=rc[di[l-1]];

d[l]=h[i];

di[l++]=i;

}

for(i=0; i<n; i++)

ans=max(ans, h[i]*(lc[i]+rc[i]-1));

return ans;

}

};

ps：最早是半年前被问到了这题。现在回头看看，写得真是惨不忍睹。现在做LeetCode又遇到这题，分析题意方面，要比之前稍好一些了吧……

[LeetCode Unique Binary Search Trees II]

1条回复

Unique Binary Search Trees II

题意：输入是n，要求枚举出包含1…n这n个整数的所有二叉搜索树（BST）。

分析：显然这题n不可能很大，考察的是如何枚举每种可能的状态。首先考虑了所有全排列的插入构建BST，发现这样得到的BST有重复。然后发现，若设n的全部BST为T(n)，当根是i时，其左子树的所有可能情况为T(i-1)，右子树的所有可能情况为T(n-i)。这样就可以按n由小到大地递推构造出各个BST了。

int vvpl=0;
vector<vector<TreeNode *>> vvp;
vector<TreeNode *> vp;
vector<TreeNode *>::iterator it1, end1, it2, end2;

TreeNode *mk(TreeNode *p, int d)
{
    if(!p)
        return 0;
    TreeNode *q=new TreeNode(p->val+d);
    q->left=mk(p->left, d);
    q->right=mk(p->right, d);
    return q;
}

class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        int i, j, k, l;
        TreeNode *p;
        if(vvpl<=n)
        {
            if(vvpl==0)
            {
                vvp.push_back(vp);
                vvp[0].push_back(0);
                vvpl=1;
            }
            for(; vvpl<=n; vvpl++)
            {
                vvp.push_back(vp);
                for(i=1; i<=vvpl; i++)
                {
                    for(it1=vvp[i-1].begin(), end1=vvp[i-1].end(); it1!=end1; it1++)
                    {
                        for(it2=vvp[vvpl-i].begin(), end2=vvp[vvpl-i].end(); it2!=end2; it2++)
                        {
                            p=new TreeNode(i);
                            p->left=mk(*it1, 0);
                            p->right=mk(*it2, i);
                            vvp[vvpl].push_back(p);
                        }
                    }
                }
            }
        }
        return vvp[n];
    }
};

int vvpl=0;

vector<vector<TreeNode *>> vvp;

vector<TreeNode *> vp;

vector<TreeNode *>::iterator it1, end1, it2, end2;

TreeNode *mk(TreeNode *p, int d)

{

if(!p)

return 0;

TreeNode *q=new TreeNode(p->val+d);

q->left=mk(p->left, d);

q->right=mk(p->right, d);

return q;

}

class Solution {

public:

vector<TreeNode *> generateTrees(int n) {

int i, j, k, l;

TreeNode *p;

if(vvpl<=n)

{

if(vvpl==0)

{

vvp.push_back(vp);

vvp[0].push_back(0);

vvpl=1;

}

for(; vvpl<=n; vvpl++)

{

vvp.push_back(vp);

for(i=1; i<=vvpl; i++)

{

for(it1=vvp[i-1].begin(), end1=vvp[i-1].end(); it1!=end1; it1++)

{

for(it2=vvp[vvpl-i].begin(), end2=vvp[vvpl-i].end(); it2!=end2; it2++)

{

p=new TreeNode(i);

p->left=mk(*it1, 0);

p->right=mk(*it2, i);

vvp[vvpl].push_back(p);

}

return vvp[n];

}

};

ps：LeetCode上面很多这种要求构造出所有可行解的题目，这是之前做的ACM中几乎没有的。虽然题型相对陌生，但解起来也很好玩~

[LeetCode Word Ladder II]

3条回复

Word Ladder II

题意：给出一个初始字符串S和目标字符串T，以及可行的中间字符串集合dict，转换字符串时仅允许一次改变一个字符，要求从S变为T的所有最短可行序列。

分析：首先，需要枚举每个字符串可行的改变方式，并用BFS建图：建立结点编号对可达字符串的映射关系，并记录每个结点的深度。建图结束后，用深搜的方式枚举出所有可行的字符串，剪枝方案只简单记录了无效结点。最后跑出的时间是1096 ms。

vector<vector<string> > vvs;
vector<string> vs;
map<string, int> Msi;
map<int, string> Mis;
int hd[100000], el, si, ti, sl, d[100000];
char b[100000];

struct E
{
    int v, p;
}e[100000];

void adde(int u, int v)
{
    e[el].v=v; e[el].p=hd[u]; hd[u]=el++;
}

void bfs(string s, string t, unordered_set<string> &dict)
{
    int i, j, k, l, u, v;
    queue<string> Q;
    d[si]=0;
    Msi[s]=si++;
    Mis[0]=s;
    Q.push(s);
    while(!Q.empty())
    {
        s=Q.front(); Q.pop();
        u=Msi[s];
        for(i=0; i<sl; i++)
        {
            k=s[i];
            for(j='a'; j<='z'; j++)
            {
                if(j==k)
                    continue;
                s[i]=j;
                if(dict.find(s)==dict.end())
                    continue;
                if(Msi.find(s)!=Msi.end())
                {
                    v=Msi[s];
                    if(d[v]==d[u]+1)
                        adde(u, v);
                    continue;
                }
                v=Msi[s]=si++;
                d[v]=d[u]+1;
                Mis[v]=s;
                Q.push(s);
                adde(u, v);
            }
            s[i]=k;
        }
    }
}

int dfs(int u, int vsl)
{
    if(b[u]||vsl>d[ti])
        return b[u]=1;
    int l, v;
    if(vs.size()<=vsl)
        vs.push_back(Mis[u]);
    else
        vs[vsl]=Mis[u];
    if(u==ti)
    {
        vvs.push_back(vs);
        return 0;
    }
    b[u]=1;
    for(l=hd[u]; l!=-1; l=e[l].p)
    {
        v=e[l].v;
        if(!dfs(v, vsl+1))
            b[u]=0;
    }
    return b[u];
}

class Solution {
public:
    vector<vector<string>> findLadders(string s, string t, unordered_set<string> &dict) {
        dict.insert(t);
        vvs.clear();
        vs.clear();
        Msi.clear();
        Mis.clear();
        memset(hd, -1, sizeof hd);
        memset(b, 0, sizeof b);
        si=el=0;
        sl=s.length();
        bfs(s, t, dict);
        if(Msi.find(t)==Msi.end())
            return vvs;
        ti=Msi[t];
        dfs(0, 0);
        return vvs;
    }
};

100

101

vector<vector<string> > vvs;

vector<string> vs;

map<string, int> Msi;

map<int, string> Mis;

int hd[100000], el, si, ti, sl, d[100000];

char b[100000];

struct E

{

int v, p;

}e[100000];

void adde(int u, int v)

{

e[el].v=v; e[el].p=hd[u]; hd[u]=el++;

}

void bfs(string s, string t, unordered_set<string> &dict)

{

int i, j, k, l, u, v;

queue<string> Q;

d[si]=0;

Msi[s]=si++;

Mis[0]=s;

Q.push(s);

while(!Q.empty())

{

s=Q.front(); Q.pop();

u=Msi[s];

for(i=0; i<sl; i++)

{

k=s[i];

for(j='a'; j<='z'; j++)

{

if(j==k)

continue;

s[i]=j;

if(dict.find(s)==dict.end())

continue;

if(Msi.find(s)!=Msi.end())

{

v=Msi[s];

if(d[v]==d[u]+1)

adde(u, v);

continue;

}

v=Msi[s]=si++;

d[v]=d[u]+1;

Mis[v]=s;

Q.push(s);

adde(u, v);

}

s[i]=k;

}

int dfs(int u, int vsl)

{

if(b[u]||vsl>d[ti])

return b[u]=1;

int l, v;

if(vs.size()<=vsl)

vs.push_back(Mis[u]);

else

vs[vsl]=Mis[u];

if(u==ti)

{

vvs.push_back(vs);

return 0;

}

b[u]=1;

for(l=hd[u]; l!=-1; l=e[l].p)

{

v=e[l].v;

if(!dfs(v, vsl+1))

b[u]=0;

}

return b[u];

}

class Solution {

public:

vector<vector<string>> findLadders(string s, string t, unordered_set<string> &dict) {

dict.insert(t);

vvs.clear();

vs.clear();

Msi.clear();

Mis.clear();

memset(hd, -1, sizeof hd);

memset(b, 0, sizeof b);

si=el=0;

sl=s.length();

bfs(s, t, dict);

if(Msi.find(t)==Msi.end())

return vvs;

ti=Msi[t];

dfs(0, 0);

return vvs;

}

};

ps：不得不说LeetCode做题好刺激，每题都不给数据范围，并且debug非常困难，基本就是各种靠猜。这题整整交了48次才过，实在是太多的血与泪。

[HDU 4836]

发表回复

The Query on the Tree

2014年百度之星复赛的第二题，看了官方题解才会做。

个人觉得这题有意思的地方有：
（1）通过记录DFS顺序+树状数组的方式，动态更新每一棵子树的权值和；
（2）树根改变的时候，根据父子关系巧妙地不修改数据求出当前子树权值和。

#include<cstdio>
#include<cstring>

int t,n,m,el,hd[10000],y[10000],f[10000],dl[10000],dr[10000],di;
int tr[20001],yt,rt;
char s[10];

struct E
{
    int v,p;
}e[20000];

void adde(int u,int v)
{
    e[el].v=v; e[el].p=hd[u]; hd[u]=el++;
    e[el].v=u; e[el].p=hd[v]; hd[v]=el++;
}

void ins(int i,int d)
{
    while(i<di)
    {
        tr[i]+=d;
        i+=i&-i;
    }
}

int qry(int i)
{
    int d=0;
    while(i)
    {
        d+=tr[i];
        i-=i&-i;
    }
    return d;
}

void dfs(int i,int h)
{
    int j,k,l;
    f[i]=h;
    dl[i]=di++;
    for(l=hd[i];l!=-1;l=e[l].p)
    {
        j=e[l].v;
        if(j==h)
            continue;
        dfs(j,i);
    }
    dr[i]=di++;
}

void init()
{
    int i,j,k,l;
    el=0;
    di=1;
    yt=0;
    rt=0;
    memset(hd,-1,sizeof hd);
    memset(tr,0,sizeof tr);
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&j,&k);
        adde(j-1,k-1);
    }
    for(i=0;i<n;i++)
    {
        scanf("%d",y+i);
        yt+=y[i];
    }
    dfs(0,-1);
    for(i=0;i<n;i++)
        ins(dl[i],y[i]);
}

void solve()
{
    int i,j,k,l;
    printf("Case #%d:\n",++t);
    scanf("%d",&m);
    while(m--)
    {
        scanf("%s",s);
        if(s[0]=='Q')
        {
            scanf("%d",&i);
            i--;
            if(i==rt)
            {
                printf("%d\n",yt);
            }
            else
            {
                if(dl[rt]>dl[i]&&dr[rt]<dr[i])
                {
                    for(l=rt;f[l]!=i;l=f[l]);
                    printf("%d\n",yt-(qry(dr[l])-qry(dl[l]-1)));
                }
                else
                {
                    printf("%d\n",qry(dr[i])-qry(dl[i]-1));
                }
            }
        }
        else if(s[0]=='C')
        {
            scanf("%d%d",&i,&j);
            i--;
            ins(dl[i],j-y[i]);
            yt+=j-y[i];
            y[i]=j;
        }
        else
        {
            scanf("%d",&rt);
            rt--;
        }
    }
}

int main()
{
    scanf("%*d");
    while(~scanf("%d",&n))
    {
        init();
        solve();
    }
    return 0;
}

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

#include<cstdio>

#include<cstring>

int t,n,m,el,hd[10000],y[10000],f[10000],dl[10000],dr[10000],di;

int tr[20001],yt,rt;

char s[10];

struct E

{

int v,p;

}e[20000];

void adde(int u,int v)

{

e[el].v=v; e[el].p=hd[u]; hd[u]=el++;

e[el].v=u; e[el].p=hd[v]; hd[v]=el++;

}

void ins(int i,int d)

{

while(i<di)

{

tr[i]+=d;

i+=i&-i;

}

int qry(int i)

{

int d=0;

while(i)

{

d+=tr[i];

i-=i&-i;

}

return d;

}

void dfs(int i,int h)

{

int j,k,l;

f[i]=h;

dl[i]=di++;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].v;

if(j==h)

continue;

dfs(j,i);

}

dr[i]=di++;

}

void init()

{

int i,j,k,l;

el=0;

di=1;

yt=0;

rt=0;

memset(hd,-1,sizeof hd);

memset(tr,0,sizeof tr);

for(i=1;i<n;i++)

{

scanf("%d%d",&j,&k);

adde(j-1,k-1);

}

for(i=0;i<n;i++)

{

scanf("%d",y+i);

yt+=y[i];

}

dfs(0,-1);

for(i=0;i<n;i++)

ins(dl[i],y[i]);

}

void solve()

{

int i,j,k,l;

printf("Case #%d:\n",++t);

scanf("%d",&m);

while(m--)

{

scanf("%s",s);

if(s[0]=='Q')

{

scanf("%d",&i);

i--;

if(i==rt)

{

printf("%d\n",yt);

}

else

{

if(dl[rt]>dl[i]&&dr[rt]<dr[i])

{

for(l=rt;f[l]!=i;l=f[l]);

printf("%d\n",yt-(qry(dr[l])-qry(dl[l]-1)));

}

else

{

printf("%d\n",qry(dr[i])-qry(dl[i]-1));

}

else if(s[0]=='C')

{

scanf("%d%d",&i,&j);

i--;

ins(dl[i],j-y[i]);

yt+=j-y[i];

y[i]=j;

}

else

{

scanf("%d",&rt);

rt--;

}

int main()

{

scanf("%*d");

while(~scanf("%d",&n))

{

init();

solve();

}

return 0;

}

[POJ 3074]

发表回复

Sudoku

题意：求解数独问题。

思路：用DLX解。首先，需要将格盘建模为DLX用到的十字链表。数字之间的互斥关系共有4种，因此可以对”每行每个数字”、”每列每个数字”、”每九宫格每个数字”、”每个格点位置”分别建立一个链表列，也即总共是9*9+9*9+9*9+9*9=324个链表列，十字链表中每一行表示在某格点放置某数，分别与4个对应的链表列相交。

然后，就是正式的深搜了。在深搜的每一层：
1) 在十字链表表头中找出元素最少且非零的一列，将该列以及列中包含的所有行元素从十字链表中移除；
2) 枚举列中的每行（作为解的一部分），将与该行相交的所有其他列以及这些列包含的行元素在十字链表中移除，递归下一层深搜;
3) 递归返回时，需要将2)中移除的相应列和行添加回十字链表；
4) 所有行枚举完毕时，需要将1)中移除的相应列和行添加回十字链表。

注意，对链表进行增删操作时，需要以相反的顺序修改各结点。同时，也需要动态维护表头的元素数。

#include<cstdio>
#include<cstring>
#define M 10000

int s[9][9],sl;
int hd,el,tag;
char t[82],r[9][10],c[9][10],b[9][10];

struct E
{
    int l,r,u,d,c,s;
    int ri,ci,bi,v;
}e[M];

void adde(int ei,int ri,int ci,int bi,int v)
{
    e[ei].s++;
    e[el].u=ei;
    e[el].d=e[ei].d;
    e[e[ei].d].u=el;
    e[ei].d=el;
    e[el].c=ei;
    e[el].ri=ri;
    e[el].ci=ci;
    e[el].bi=bi;
    e[el].v=v;
    el++;
}

void addr(int ri,int ci,int bi,int v)
{
    int i,j,k,l;
    adde(1+ri*9+v-1,ri,ci,bi,v);
    adde(1+81+ci*9+v-1,ri,ci,bi,v);
    adde(1+81+81+bi*9+v-1,ri,ci,bi,v);
    adde(1+81+81+81+ri*9+ci,ri,ci,bi,v);
    for(i=0;i<4;i++)
    {
        j=(i+3)%4;
        k=(i+1)%4;
        e[el-4+i].l=el-4+j;
        e[el-4+i].r=el-4+k;
    }
}

void init()
{
    int i,j,k,l,tl;
    hd=el=tag=0;
    sl=81;
    memset(r,0,sizeof r);
    memset(c,0,sizeof c);
    memset(b,0,sizeof b);
    for(i=tl=0;i<9;i++)
    {
        for(j=0;j<9;j++)
        {
            if(t[tl]=='.')
                k=0;
            else
                k=t[tl]-'0';
            if(k)
                sl--;
            r[i][k]=1;
            c[j][k]=1;
            s[i][j]=k;
            l=i/3*3+j/3;
            b[l][k]=1;
            tl++;
        }
    }
    e[el].l=e[el].r=el;
    el++;
    for(i=0;i<324;i++)
    {
        e[el].l=hd;
        e[el].r=e[hd].r;
        e[e[hd].r].l=el;
        e[hd].r=el;
        e[el].u=e[el].d=e[el].c=el;
        e[el].s=0;
        el++;
    }
    for(i=0;i<9;i++)
    {
        for(j=0;j<9;j++)
        {
            if(s[i][j])
                continue;
            l=i/3*3+j/3;
            for(k=1;k<10;k++)
            {
                if(r[i][k]||c[j][k]||b[l][k])
                    continue;
                addr(i,j,l,k);
            }
        }
    }
}

void pnt()
{
    int i,j,tl;
    for(i=tl=0;i<9;i++)
        for(j=0;j<9;j++)
            t[tl++]='0'+s[i][j];
    puts(t);
}

void dfs(int si)
{
    if(si==sl)
    {
        tag=1;
        pnt();
        return;
    }
    int i,j,k,l;
    int ii,jj,kk;
    int ri,ci,bi,v;
    for(i=e[hd].r,j=0x7fffffff;i!=hd;i=e[i].r)
    {
        if(e[i].s&&e[i].s<j)
        {
            j=e[i].s;
            k=i;
        }
        if(j==1)
            break;
    }
    if(j==0x7fffffff)
        return;
    e[e[k].l].r=e[k].r;
    e[e[k].r].l=e[k].l;
    for(i=e[k].d;i!=k;i=e[i].d)
    {
        for(j=e[i].r;j!=i;j=e[j].r)
        {
            e[e[j].c].s--;
            e[e[j].u].d=e[j].d;
            e[e[j].d].u=e[j].u;
        }
    }
    for(i=e[k].d;i!=k;i=e[i].d)
    {
        ri=e[i].ri; ci=e[i].ci; bi=e[i].bi; v=e[i].v;
        for(j=e[i].r;j!=i;j=e[j].r)
        {
            kk=e[j].c;
            e[e[kk].l].r=e[kk].r;
            e[e[kk].r].l=e[kk].l;
            for(ii=e[kk].d;ii!=kk;ii=e[ii].d)
            {
                for(jj=e[ii].r;jj!=ii;jj=e[jj].r)
                {
                    e[e[jj].c].s--;
                    e[e[jj].u].d=e[jj].d;
                    e[e[jj].d].u=e[jj].u;
                }
            }
        }
        s[ri][ci]=v;
        dfs(si+1);
        if(tag)
            return;
        for(j=e[i].l;j!=i;j=e[j].l)
        {
            kk=e[j].c;
            e[e[kk].l].r=kk;
            e[e[kk].r].l=kk;
            for(ii=e[kk].u;ii!=kk;ii=e[ii].u)
            {
                for(jj=e[ii].l;jj!=ii;jj=e[jj].l)
                {
                    e[e[jj].u].d=jj;
                    e[e[jj].d].u=jj;
                    e[e[jj].c].s++;
                }
            }
        }
    }
    for(i=e[k].u;i!=k;i=e[i].u)
    {
        for(j=e[i].l;j!=i;j=e[j].l)
        {
            e[e[j].u].d=j;
            e[e[j].d].u=j;
            e[e[j].c].s++;
        }
    }
    e[e[k].l].r=k;
    e[e[k].r].l=k;
}

void solve()
{
    dfs(0);
}

int main()
{
    while(scanf("%s",t)&&t[0]!='e')
    {
        init();
        solve();
    }
    return 0;
}

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

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

#include<cstdio>

#include<cstring>

#define M 10000

int s[9][9],sl;

int hd,el,tag;

char t[82],r[9][10],c[9][10],b[9][10];

struct E

{

int l,r,u,d,c,s;

int ri,ci,bi,v;

}e[M];

void adde(int ei,int ri,int ci,int bi,int v)

{

e[ei].s++;

e[el].u=ei;

e[el].d=e[ei].d;

e[e[ei].d].u=el;

e[ei].d=el;

e[el].c=ei;

e[el].ri=ri;

e[el].ci=ci;

e[el].bi=bi;

e[el].v=v;

el++;

}

void addr(int ri,int ci,int bi,int v)

{

int i,j,k,l;

adde(1+ri*9+v-1,ri,ci,bi,v);

adde(1+81+ci*9+v-1,ri,ci,bi,v);

adde(1+81+81+bi*9+v-1,ri,ci,bi,v);

adde(1+81+81+81+ri*9+ci,ri,ci,bi,v);

for(i=0;i<4;i++)

{

j=(i+3)%4;

k=(i+1)%4;

e[el-4+i].l=el-4+j;

e[el-4+i].r=el-4+k;

}

void init()

{

int i,j,k,l,tl;

hd=el=tag=0;

sl=81;

memset(r,0,sizeof r);

memset(c,0,sizeof c);

memset(b,0,sizeof b);

for(i=tl=0;i<9;i++)

{

for(j=0;j<9;j++)

{

if(t[tl]=='.')

k=0;

else

k=t[tl]-'0';

if(k)

sl--;

r[i][k]=1;

c[j][k]=1;

s[i][j]=k;

l=i/3*3+j/3;

b[l][k]=1;

tl++;

}

e[el].l=e[el].r=el;

el++;

for(i=0;i<324;i++)

{

e[el].l=hd;

e[el].r=e[hd].r;

e[e[hd].r].l=el;

e[hd].r=el;

e[el].u=e[el].d=e[el].c=el;

e[el].s=0;

el++;

}

for(i=0;i<9;i++)

{

for(j=0;j<9;j++)

{

if(s[i][j])

continue;

l=i/3*3+j/3;

for(k=1;k<10;k++)

{

if(r[i][k]||c[j][k]||b[l][k])

continue;

addr(i,j,l,k);

}

void pnt()

{

int i,j,tl;

for(i=tl=0;i<9;i++)

for(j=0;j<9;j++)

t[tl++]='0'+s[i][j];

puts(t);

}

void dfs(int si)

{

if(si==sl)

{

tag=1;

pnt();

return;

}

int i,j,k,l;

int ii,jj,kk;

int ri,ci,bi,v;

for(i=e[hd].r,j=0x7fffffff;i!=hd;i=e[i].r)

{

if(e[i].s&&e[i].s<j)

{

j=e[i].s;

k=i;

}

if(j==1)

break;

}

if(j==0x7fffffff)

return;

e[e[k].l].r=e[k].r;

e[e[k].r].l=e[k].l;

for(i=e[k].d;i!=k;i=e[i].d)

{

for(j=e[i].r;j!=i;j=e[j].r)

{

e[e[j].c].s--;

e[e[j].u].d=e[j].d;

e[e[j].d].u=e[j].u;

}

for(i=e[k].d;i!=k;i=e[i].d)

{

ri=e[i].ri; ci=e[i].ci; bi=e[i].bi; v=e[i].v;

for(j=e[i].r;j!=i;j=e[j].r)

{

kk=e[j].c;

e[e[kk].l].r=e[kk].r;

e[e[kk].r].l=e[kk].l;

for(ii=e[kk].d;ii!=kk;ii=e[ii].d)

{

for(jj=e[ii].r;jj!=ii;jj=e[jj].r)

{

e[e[jj].c].s--;

e[e[jj].u].d=e[jj].d;

e[e[jj].d].u=e[jj].u;

}

s[ri][ci]=v;

dfs(si+1);

if(tag)

return;

for(j=e[i].l;j!=i;j=e[j].l)

{

kk=e[j].c;

e[e[kk].l].r=kk;

e[e[kk].r].l=kk;

for(ii=e[kk].u;ii!=kk;ii=e[ii].u)

{

for(jj=e[ii].l;jj!=ii;jj=e[jj].l)

{

e[e[jj].u].d=jj;

e[e[jj].d].u=jj;

e[e[jj].c].s++;

}

for(i=e[k].u;i!=k;i=e[i].u)

{

for(j=e[i].l;j!=i;j=e[j].l)

{

e[e[j].u].d=j;

e[e[j].d].u=j;

e[e[j].c].s++;

}

e[e[k].l].r=k;

e[e[k].r].l=k;

}

void solve()

{

dfs(0);

}

int main()

{

while(scanf("%s",t)&&t[0]!='e')

{

init();

solve();

}

return 0;

}

没有想出太好的优化。c++下跑了188ms。

ps：
记得最早是11年寒假时，和Arios一起留校做MCM时听他提到，当时那道建模题可以用Dancing Links解。一晃眼，3年多过去了，我这才开始读Knuth的这篇论文。

文章本身的算法不算难懂，因为深搜的优化是很多问题都要用到的。之前做题的时候，确实也有考虑过对链表进行动态调整，但发现无法根本上降低时间复杂度（依然是指数时间）后，也没有深究了。而Knuth这篇论文里介绍的DLX，通过对十字链表进行动态调整从而尽量保持搜索树最优，可以说是在通常情况下将深搜优化到了极致。

做这题数独时，在链表建模那一步想了大概一整天时间。主要是数独问题元素间的互斥情况比较复杂。一开始只用了前3种互斥关系，发现表头记录的元素数无法正确维护，每次暴力重算并加了些优化后竟然勉强过了。然后就一直在想正解。想出应该增加第4种互斥关系后，又用了很长时间才推出要移除与当前行元素互斥的所有行。最后对链表的修改要比一开始想的要复杂得多。

查了下status，Arios在5年前作出的时间是32ms，并且是1A 47ms过的。实在是很强。