月度归档：2014年02月

[POJ 1093]

题意：输入行长度值n，以及一篇文章，要将文章重新排版，使得”坏值”和最小。若某行只含一个单词，则坏值为500。包含多个单词的行，单词间每个长度为k的间隔，其坏值为(k-1)^2。

这题之前做CLRS时见过类似的（第二版习题15-2），当时也是想了很久才推出公式：用dp[i][j]保存到第i行结束时，打印了前j个单词的最小坏值。那么dp[i][j]=min{dp[i-1][k-1]+bd[n-sum{w[l]|k<=l<=j}][j-k]}，其中w[l]为第l个单词的长度，bd[p][q]为预处理计算出来的一行有p个空格和q个间隔时的坏值。状态转移时注意下标边界，并需要记录父状态。这里对于相同坏值的方案，要输出使各间隔长度值字典序最小的，那么每次dp使，总是使更多单词尽量在之前打印即可。输出时，首先找到最小坏值对应的行数，根据父状态一层层回退，记录每行要打印多少个单词；然后逐个单词处理输出即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define WN 1000

int n,sl,w[10000],wl,bd[81][81];
char s[10000];
int dp[WN][WN],p[WN][WN],dpi,dpj[WN],dpw[WN];

void init()
{
    int i,j,k,l;
    char c;
    sl=wl=0;
    memset(w,0,sizeof w);
    memset(s,0,sizeof s);
    memset(dp,-1,sizeof dp);
    getchar();
    while((c=getchar())!='\n')
    {
        while(c!='\n')
        {
            while(c==' ')
                c=getchar();
            if(c=='\n')
                break;
            while(c!=' '&&c!='\n')
            {
                w[wl]++;
                s[sl++]=c;
                c=getchar();
            }
            wl++;
        }
    }
}

void pnt(int wi,int si)
{
    int i;
    for(i=0;i<w[wi];i++)
        printf("%c",s[si+i]);
}

void pntw(int i)
{
    while(i--)
        printf(" ");
}

void solve()
{
    int i,j,k,l,pj,km;
    for(i=0,j=w[i];i<wl&&i+j<=n;i++,j+=w[i])
        dp[0][i]=bd[n-j][i];
    for(i=1;i<wl;i++)
    {
        for(j=i;j<wl&&dp[i-1][j-1]!=-1;j++)
        {
            for(k=j,l=w[k];k<wl&&l+k-j<=n;k++,l+=w[k])
            {
                if(dp[i][k]==-1)
                {
                    p[i][k]=j;
                    dp[i][k]=dp[i-1][j-1]+bd[n-l][k-j];
                }
                else if(dp[i-1][j-1]+bd[n-l][k-j]
                        <=dp[i][k])
                {
                    p[i][k]=j;
                    dp[i][k]=dp[i-1][j-1]+bd[n-l][k-j];
                }
            }
        }
    }
    for(i=0,j=0x7fffffff;i<wl;i++)
        if(dp[i][wl-1]!=-1)
        {
            if(dp[i][wl-1]<j)
            {
                j=dp[i][wl-1];
                dpi=i+1;
            }
        }
    dpj[dpi-1]=wl;
    for(i=dpi-1;i;i--)
        dpj[i-1]=p[i][dpj[i]-1];
    for(i=j=0;i<dpi;i++)
        for(dpw[i]=n;j<dpj[i];j++)
            dpw[i]-=w[j];
    for(i=j=pj=l=0;i<dpi;i++)
    {
        if(dpj[i]>j+1)
        {
            k=dpw[i]/(dpj[i]-j-1);
            km=(dpj[i]-j-1)-dpw[i]%(dpj[i]-j-1);
            for(;j<dpj[i]-1;j++)
            {
                pnt(j,l);
                l+=w[j];
                if(km)
                {
                    km--;
                    pntw(k);
                }
                else
                    pntw(k+1);
            }
        }
        pnt(j,l);
        l+=w[j];
        j++;
        puts("");
        pj=j;
    }
    puts("");
}

int main()
{
    int i,j,k,l;
    for(i=0;i<81;i++)
    {
        bd[i][0]=500;
        for(j=1;j<=i;j++)
        {
            k=i/j;
            if(i%j==0)
                bd[i][j]=j*(k-1)*(k-1);
            else
            {
                l=i%j;
                bd[i][j]=(j-l)*(k-1)*(k-1)+l*k*k;
            }
        }
    }
    while(~scanf("%d",&n)&&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

133

134

135

136

137

138

139

140

141

142

143

144

145

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define WN 1000

int n,sl,w[10000],wl,bd[81][81];

char s[10000];

int dp[WN][WN],p[WN][WN],dpi,dpj[WN],dpw[WN];

void init()

{

int i,j,k,l;

char c;

sl=wl=0;

memset(w,0,sizeof w);

memset(s,0,sizeof s);

memset(dp,-1,sizeof dp);

getchar();

while((c=getchar())!='\n')

{

while(c!='\n')

{

while(c==' ')

c=getchar();

if(c=='\n')

break;

while(c!=' '&&c!='\n')

{

w[wl]++;

s[sl++]=c;

c=getchar();

}

wl++;

}

void pnt(int wi,int si)

{

int i;

for(i=0;i<w[wi];i++)

printf("%c",s[si+i]);

}

void pntw(int i)

{

while(i--)

printf(" ");

}

void solve()

{

int i,j,k,l,pj,km;

for(i=0,j=w[i];i<wl&&i+j<=n;i++,j+=w[i])

dp[0][i]=bd[n-j][i];

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

{

for(j=i;j<wl&&dp[i-1][j-1]!=-1;j++)

{

for(k=j,l=w[k];k<wl&&l+k-j<=n;k++,l+=w[k])

{

if(dp[i][k]==-1)

{

p[i][k]=j;

dp[i][k]=dp[i-1][j-1]+bd[n-l][k-j];

}

else if(dp[i-1][j-1]+bd[n-l][k-j]

<=dp[i][k])

{

p[i][k]=j;

dp[i][k]=dp[i-1][j-1]+bd[n-l][k-j];

}

for(i=0,j=0x7fffffff;i<wl;i++)

if(dp[i][wl-1]!=-1)

{

if(dp[i][wl-1]<j)

{

j=dp[i][wl-1];

dpi=i+1;

}

dpj[dpi-1]=wl;

for(i=dpi-1;i;i--)

dpj[i-1]=p[i][dpj[i]-1];

for(i=j=0;i<dpi;i++)

for(dpw[i]=n;j<dpj[i];j++)

dpw[i]-=w[j];

for(i=j=pj=l=0;i<dpi;i++)

{

if(dpj[i]>j+1)

{

k=dpw[i]/(dpj[i]-j-1);

km=(dpj[i]-j-1)-dpw[i]%(dpj[i]-j-1);

for(;j<dpj[i]-1;j++)

{

pnt(j,l);

l+=w[j];

if(km)

{

km--;

pntw(k);

}

else

pntw(k+1);

}

pnt(j,l);

l+=w[j];

j++;

puts("");

pj=j;

}

puts("");

}

int main()

{

int i,j,k,l;

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

{

bd[i][0]=500;

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

{

k=i/j;

if(i%j==0)

bd[i][j]=j*(k-1)*(k-1);

else

{

l=i%j;

bd[i][j]=(j-l)*(k-1)*(k-1)+l*k*k;

}

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

{

init();

solve();

}

return 0;

}

ps: 这题考察的算法貌似很有实用价值呢……不过现在的文本处理程序，恐怕是要比这复杂十倍以上的吧……

[POJ 1324]

发表回复

Holedox Moving

搜索 + 滚动hash

给出最大20*20的格盘，和一条长为l的蛇，目的是使蛇头移动到(1,1)。格盘中存在k个格子是无法通过的石头，蛇也不能碰到自己的身体，包括最尾的一格。若能到(1,1)，输出最短距离，否则输出-1。

考虑保存蛇的状态时，只保存其蛇头位置，以及指向之前蛇头的指针。由此就能搜索处理蛇的移动方案。考虑判重时，使用滚动hash，即到一个新状态时，将之前蛇头对应的hash值升位并减去之前蛇尾的部分，再加上新的蛇头值即可。

另外就是，可以考虑优先向(1,1)的方向移动，以及搜索之前先判断蛇头是否可达(1,1)。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define HM 100003
#define HC 31
#define QL 100000
#define MEM 5000000

int t,n,m,pl,hl,hd[HM],el,mmx,mmy;
int mv[4][2]={-1,0,0,-1,1,0,0,1};
char s[20][20];
int q[QL],qh,qt;

struct H
{
    int x,y,d,p,u;
}h[MEM];

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

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

inline bool chke()
{
    int i,j,k,l;
    for(l=hd[h[hl].u];l!=-1;l=e[l].p)
    {
        j=e[l].v;
        for(i=0,k=hl;i<pl;i++,j=h[j].p,k=h[k].p)
            if(h[j].x!=h[k].x||h[j].y!=h[k].y)
                break;
        if(i==pl)
            return 0;
    }
    return 1;
}

inline bool chk(int i,int j)
{
    if(i<0||i>=n||j<0||j>=m)
        return 0;
    if(s[i][j])
        return 0;
    return 1;
}

bool prechk()
{
    int i,j,k,l,x,y;
    char ss[20][20];
    memcpy(ss,s,sizeof ss);
    qh=qt=0;
    q[qh++]=0;
    s[0][0]=1;
    while(qt!=qh)
    {
        i=q[qt++];
        j=i/20;
        k=i%20;
        for(l=0;l<4;l++)
        {
            x=j+mv[l][0];
            y=k+mv[l][1];
            if(chk(x,y))
            {
                s[x][y]=1;
                q[qh++]=x*20+y;
            }
        }
    }
    i=s[h[0].x][h[0].y];
    memcpy(s,ss,sizeof ss);
    return i;
}

int bfs()
{
    int i,j,k,l,x,y;
    if(h[0].x==0&&h[0].y==0)
        return 0;
    q[qh++]=0;
    while(qt!=qh)
    {
        i=q[qt++];
        if(qt==QL)
            qt=0;
        for(j=0,k=i;j<pl;j++,k=h[k].p)
            s[h[k].x][h[k].y]=1;
        for(l=0;l<4;l++)
        {
            x=h[i].x+mv[l][0];
            y=h[i].y+mv[l][1];
            if(chk(x,y))
            {
                if(x==0&&y==0)
                    return h[i].d+1;
                h[hl].x=x;
                h[hl].y=y;
                h[hl].d=h[i].d+1;
                h[hl].p=i;
                for(j=1,k=i;j<pl;j++,k=h[k].p);
                h[hl].u=(h[i].u*HC*HC-mmx*h[k].x-mmy*h[k].y
                        +HC*x+y)%HM;
                if(h[hl].u<0)
                    h[hl].u+=HM;
                if(chke())
                {
                    adde(h[hl].u,hl);
                    q[qh++]=hl++;
                    if(qh==QL)
                        qh=0;
                }
            }
        }
        for(j=0,k=i;j<pl;j++,k=h[k].p)
            s[h[k].x][h[k].y]=0;
    }
    return -1;
}

void init()
{
    int i,j,k,l;
    hl=el=0;
    qh=qt=0;
    memset(s,0,sizeof s);
    memset(hd,-1,sizeof hd);
    for(i=0,mmy=1;i<pl*2;i++)
        mmy=(mmy*HC)%HM;
    mmx=mmy*HC%HM;
    for(hl=0;hl<pl;hl++)
    {
        scanf("%d%d",&j,&k);
        h[hl].x=j-1;
        h[hl].y=k-1;
        h[hl].p=hl+1;
    }
    h[0].d=0;
    for(i=pl-1,j=0;i>-1;i--)
    {
        j=(j*HC+h[i].x)%HM;
        j=(j*HC+h[i].y)%HM;
    }
    h[0].u=j;
    adde(j,0);
    scanf("%d",&l);
    while(l--)
    {
        scanf("%d%d",&i,&j);
        s[i-1][j-1]=1;
    }
}

void solve()
{
    if(!prechk())
        printf("Case %d: -1\n",++t);
    else
        printf("Case %d: %d\n",++t,bfs());
}

int main()
{
    while(~scanf("%d%d%d",&n,&m,&pl)&&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

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

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define HM 100003

#define HC 31

#define QL 100000

#define MEM 5000000

int t,n,m,pl,hl,hd[HM],el,mmx,mmy;

int mv[4][2]={-1,0,0,-1,1,0,0,1};

char s[20][20];

int q[QL],qh,qt;

struct H

{

int x,y,d,p,u;

}h[MEM];

struct E

{

int v,p;

}e[MEM];

inline void adde(int u,int v)

{

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

}

inline bool chke()

{

int i,j,k,l;

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

{

j=e[l].v;

for(i=0,k=hl;i<pl;i++,j=h[j].p,k=h[k].p)

if(h[j].x!=h[k].x||h[j].y!=h[k].y)

break;

if(i==pl)

return 0;

}

return 1;

}

inline bool chk(int i,int j)

{

if(i<0||i>=n||j<0||j>=m)

return 0;

if(s[i][j])

return 0;

return 1;

}

bool prechk()

{

int i,j,k,l,x,y;

char ss[20][20];

memcpy(ss,s,sizeof ss);

qh=qt=0;

q[qh++]=0;

s[0][0]=1;

while(qt!=qh)

{

i=q[qt++];

j=i/20;

k=i%20;

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

{

x=j+mv[l][0];

y=k+mv[l][1];

if(chk(x,y))

{

s[x][y]=1;

q[qh++]=x*20+y;

}

i=s[h[0].x][h[0].y];

memcpy(s,ss,sizeof ss);

return i;

}

int bfs()

{

int i,j,k,l,x,y;

if(h[0].x==0&&h[0].y==0)

return 0;

q[qh++]=0;

while(qt!=qh)

{

i=q[qt++];

if(qt==QL)

qt=0;

for(j=0,k=i;j<pl;j++,k=h[k].p)

s[h[k].x][h[k].y]=1;

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

{

x=h[i].x+mv[l][0];

y=h[i].y+mv[l][1];

if(chk(x,y))

{

if(x==0&&y==0)

return h[i].d+1;

h[hl].x=x;

h[hl].y=y;

h[hl].d=h[i].d+1;

h[hl].p=i;

for(j=1,k=i;j<pl;j++,k=h[k].p);

h[hl].u=(h[i].u*HC*HC-mmx*h[k].x-mmy*h[k].y

+HC*x+y)%HM;

if(h[hl].u<0)

h[hl].u+=HM;

if(chke())

{

adde(h[hl].u,hl);

q[qh++]=hl++;

if(qh==QL)

qh=0;

}

for(j=0,k=i;j<pl;j++,k=h[k].p)

s[h[k].x][h[k].y]=0;

}

return -1;

}

void init()

{

int i,j,k,l;

hl=el=0;

qh=qt=0;

memset(s,0,sizeof s);

memset(hd,-1,sizeof hd);

for(i=0,mmy=1;i<pl*2;i++)

mmy=(mmy*HC)%HM;

mmx=mmy*HC%HM;

for(hl=0;hl<pl;hl++)

{

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

h[hl].x=j-1;

h[hl].y=k-1;

h[hl].p=hl+1;

}

h[0].d=0;

for(i=pl-1,j=0;i>-1;i--)

{

j=(j*HC+h[i].x)%HM;

j=(j*HC+h[i].y)%HM;

}

h[0].u=j;

adde(j,0);

scanf("%d",&l);

while(l--)

{

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

s[i-1][j-1]=1;

}

void solve()

{

if(!prechk())

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

else

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

}

int main()

{

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

{

init();

solve();

}

return 0;

}

[POJ 1872]

发表回复

A Dicey Problem

广搜

题意：有一个最大10*10的格盘，上面有一个标准色子。规定如果色子朝上的一面和相邻的某盘格的数字相同，或者盘格数字为-1，那么色子可以朝该方向滚动一格。问是否存在一条路径，使色子在格盘上从初始位置出发后，还能回到初始位置。若有解则数据保证只有唯一解。最后还要输出滚动方案。

这是1999年World Finals的C题……读完题面后很容易发现数据规模不大，状态转移不多，不需要特别优化。相比起来，需要花费更多时间考虑的是数据结构的表示。

色子有6面，但其姿态可以由正面和顶面两个数字来唯一确定，总共有6*4=24种可能。盘面最多100个格子，因此搜索空间是2400。可以将盘面状态表示为：((正面值-1)*6+(顶点值-1))*100+(纵坐标-1)*10+(横坐标-1)。当从队列中取出一个状态时，先由正面和顶点值得到整个色子当前6个面的值，这里可以将6个面分别编号，然后按六进制的方式（或者每个数用3位表示，移位处理）压成一个整型，再打表处理。然后模拟4个方向的滚动，求6个面的新值，再判断在该方向上的盘面值是否允许滚动。当回到原点时，返回当前状态以便回溯输出解方案。

#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;

int r,c,r0,c0,d[3500],p[3500],t[10][10];
int mv[4][2]={-1,0,1,0,0,-1,0,1};
char s[21];
int a[6],b[6],id0;
int id[35]={0,2540,3790,5065,6315,0,8835,0,11370,12605,0,
    15140,16405,17645,0,0,21450,22690,23950,25230,
    0,0,28985,30265,31520,0,34025,35310,0,37815,0,
    40335,41605,42850,44120};

void rot(int l)
{
    if(l==0)
    {
        b[0]=a[3]; b[1]=a[0]; b[2]=a[1];
        b[3]=a[2]; b[4]=a[4]; b[5]=a[5];
    }
    if(l==1)
    {
        b[0]=a[1]; b[1]=a[2]; b[2]=a[3];
        b[3]=a[0]; b[4]=a[4]; b[5]=a[5];
    }
    if(l==2)
    {
        b[0]=a[0]; b[1]=a[4]; b[2]=a[2];
        b[3]=a[5]; b[4]=a[3]; b[5]=a[1];
    }
    if(l==3)
    {
        b[0]=a[0]; b[1]=a[5]; b[2]=a[2];
        b[3]=a[4]; b[4]=a[1]; b[5]=a[3];
    }
}

void dec(int j)
{
    int i;
    for(i=5;i>-1;i--)
    {
        a[i]=j%6+1;
        j/=6;
    }
}

int chk(int i,int j,int k)
{
    if(i<0||i>=r||j<0||j>=c)
        return 0;
    if(!(t[i][j]==-1||t[i][j]==a[1]))
        return 0;
    if(d[i=(k*100+i*10+j)])
        return 0;
    return i;
}

void init()
{
    int i,j,k,l;
    scanf("%d%d%d%d%d%d",&r,&c,&r0,&c0,&i,&j);
    memset(d,0,sizeof d);
    memset(p,0,sizeof p);
    id0=(j-1)*6+i-1;
    for(i=0;i<r;i++)
        for(j=0;j<c;j++)
            scanf("%d",&t[i][j]);
}

int bfs()
{
    int i,j,k,l,ri,ci;
    queue<int>Q;
    Q.push(id0*100+(r0-1)*10+c0-1);
    while(!Q.empty())
    {
        i=Q.front(); Q.pop();
        j=i%100;
        ri=j/10; ci=j%10;
        dec(id[i/100]);
        for(l=0;l<4;l++)
        {
            rot(l);
            j=(b[0]-1)*6+b[1]-1;
            if(k=chk(ri+mv[l][0],ci+mv[l][1],j))
            {
                d[k]=d[i]+1;
                p[k]=i;
                if(ri+mv[l][0]==r0-1&&ci+mv[l][1]==c0-1)
                    return k;
                Q.push(k);
            }
        }
    }
    return 0;
}

void dfs(int i)
{
    int j,k,l=d[i]%9,ri,ci;
    j=i%100;
    ri=j/10+1;
    ci=j%10+1;
    if(ri==r0&&ci==c0)
        return;
    dfs(p[i]);
    if(l==0)
        printf("  ");
    printf("(%d,%d),",ri,ci);
    if(l==8)
        puts("");
}

void solve()
{
    int i=bfs();
    puts(s);
    if(!i)
    {
        puts("  No Solution Possible");
        return;
    }
    printf("  (%d,%d),",r0,c0);
    dfs(p[i]);
    if(d[i]%9==0)
        printf("  ");
    printf("(%d,%d)\n",r0,c0);
}

int main()
{
    while(~scanf("%s",s)&&strcmp(s,"END"))
    {
        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

#include<queue>

#include<cstdio>

#include<cstring>

using namespace std;

int r,c,r0,c0,d[3500],p[3500],t[10][10];

int mv[4][2]={-1,0,1,0,0,-1,0,1};

char s[21];

int a[6],b[6],id0;

int id[35]={0,2540,3790,5065,6315,0,8835,0,11370,12605,0,

15140,16405,17645,0,0,21450,22690,23950,25230,

0,0,28985,30265,31520,0,34025,35310,0,37815,0,

40335,41605,42850,44120};

void rot(int l)

{

if(l==0)

{

b[0]=a[3]; b[1]=a[0]; b[2]=a[1];

b[3]=a[2]; b[4]=a[4]; b[5]=a[5];

}

if(l==1)

{

b[0]=a[1]; b[1]=a[2]; b[2]=a[3];

b[3]=a[0]; b[4]=a[4]; b[5]=a[5];

}

if(l==2)

{

b[0]=a[0]; b[1]=a[4]; b[2]=a[2];

b[3]=a[5]; b[4]=a[3]; b[5]=a[1];

}

if(l==3)

{

b[0]=a[0]; b[1]=a[5]; b[2]=a[2];

b[3]=a[4]; b[4]=a[1]; b[5]=a[3];

}

void dec(int j)

{

int i;

for(i=5;i>-1;i--)

{

a[i]=j%6+1;

j/=6;

}

int chk(int i,int j,int k)

{

if(i<0||i>=r||j<0||j>=c)

return 0;

if(!(t[i][j]==-1||t[i][j]==a[1]))

return 0;

if(d[i=(k*100+i*10+j)])

return 0;

return i;

}

void init()

{

int i,j,k,l;

scanf("%d%d%d%d%d%d",&r,&c,&r0,&c0,&i,&j);

memset(d,0,sizeof d);

memset(p,0,sizeof p);

id0=(j-1)*6+i-1;

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

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

scanf("%d",&t[i][j]);

}

int bfs()

{

int i,j,k,l,ri,ci;

queue<int>Q;

Q.push(id0*100+(r0-1)*10+c0-1);

while(!Q.empty())

{

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

j=i%100;

ri=j/10; ci=j%10;

dec(id[i/100]);

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

{

rot(l);

j=(b[0]-1)*6+b[1]-1;

if(k=chk(ri+mv[l][0],ci+mv[l][1],j))

{

d[k]=d[i]+1;

p[k]=i;

if(ri+mv[l][0]==r0-1&&ci+mv[l][1]==c0-1)

return k;

Q.push(k);

}

return 0;

}

void dfs(int i)

{

int j,k,l=d[i]%9,ri,ci;

j=i%100;

ri=j/10+1;

ci=j%10+1;

if(ri==r0&&ci==c0)

return;

dfs(p[i]);

if(l==0)

printf(" ");

printf("(%d,%d),",ri,ci);

if(l==8)

puts("");

}

void solve()

{

int i=bfs();

puts(s);

if(!i)

{

puts(" No Solution Possible");

return;

}

printf(" (%d,%d),",r0,c0);

dfs(p[i]);

if(d[i]%9==0)

printf(" ");

printf("(%d,%d)\n",r0,c0);

}

int main()

{

while(~scanf("%s",s)&&strcmp(s,"END"))

{

init();

solve();

}

return 0;

}

一开始考虑时，直接用了全部六个面的值和坐标来作为状态，这样d和p数组的大小都是6^6*10*10=4665600，正常来说这也不是一个太大的值。但是这题test cases非常多。每次都memset的话，就超时了。因此只能在不丢失信息的情况下尽量压缩状态。

[POJ 1069]

发表回复

The Bermuda Triangle

搜索

题意：给出一个边长以三角形个数描述的正六边形，以及n种正三角形，问该六边形能否刚好由这些三角形完全覆盖。

放假都没做题，有点手生。由于提示是搜索题，首先考虑问题建模。可以将每个小三角形的覆盖情况用1bit表示，那么六边形的每行就可以用一个位向量来描述。用作覆盖的三角形只会是正置或倒置。于是，问题就转化成了由上到下由左到右地依次尝试用各种三角形进行填充。

需要注意的是，正六边形是对称的，可以分解成6个正三角形或3个菱形，直接判断后者的完全覆盖情况即可。对于此题数据，只分解成正三角形会WA，分解成菱形可以AC。另外，如果是原来的正六边形，一行最多会有25*4-1=99个小三角形，就无法用64位的LL来表示了。而菱形的话，一行最多为25*2=50位，还是可以的，写起来也较易实现。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long

int s,n,t[10],ans;
ll b[25];

void init()
{
    int i,j,l;
    ans=0;
    memset(b,0,sizeof b);
    for(l=0;n--;)
    {
        scanf("%d",&j);
        for(i=0;i<l&&t[i]!=j;i++);
        if(i==l)
            t[l++]=j;
    }
    n=l;
    sort(t,t+n);
}

bool chk1(int i,int j,int k)
{
    if(i+k>s||j+k*2-2>s*2)
        return 0;
    int ii,jj;
    ll c,d;
    c=(1LL<<(k*2-1))-1;
    for(ii=i;ii<i+k;ii++)
    {
        d=c<<(j+(ii-i)*2);
        if(b[ii]&d)
            return 0;
        c>>=2;
    }
    return 1;
}

bool chk2(int i,int j,int k)
{
    if(i+k>s||j+k*2-2>s*2)
        return 0;
    int ii,jj;
    ll c=1,d;
    for(ii=i;ii<i+k;ii++)
    {
        d=c<<j;
        if(b[ii]&d)
            return 0;
        c=(c<<2)+3;
    }
    return 1;
}

void set1(int i,int j,int k,int e)
{
    int ii,jj;
    ll c,d;
    c=(1LL<<(k*2-1))-1;
    for(ii=i;ii<i+k;ii++)
    {
        if(e)
        {
            d=c<<(j+(ii-i)*2);
            b[ii]|=d;
        }
        else
        {
            d=~(c<<(j+(ii-i)*2));
            b[ii]&=d;
        }
        c>>=2;
    }
}

void set2(int i,int j,int k,int e)
{
    int ii,jj;
    ll c=1,d;
    for(ii=i;ii<i+k;ii++)
    {
        if(e)
        {
            d=c<<j;
            b[ii]|=d;
        }
        else
        {
            d=~(c<<j);
            b[ii]&=d;
        }
        c=(c<<2)+3;
    }
}

void dfs(int i,int j)
{
    if(i==s)
    {
        ans=1;
        return;
    }
    int ii=i,jj=j+1,k,l;
    if(jj==s*2)
    {
        ii++;
        jj=0;
    }
    if(b[i]&(1LL<<j))
        dfs(ii,jj);
    else if(j&1)
    {
        for(l=0;l<n&&!ans;l++)
        {
            if(chk1(i,j,t[l]))
            {
                set1(i,j,t[l],1);
                dfs(ii,jj);
                set1(i,j,t[l],0);
            }
        }
    }
    else
    {
        for(l=0;l<n&&!ans;l++)
        {
            if(chk2(i,j,t[l]))
            {
                set2(i,j,t[l],1);
                dfs(ii,jj);
                set2(i,j,t[l],0);
            }
        }
    }
}

void solve()
{
    dfs(0,0);
    puts(ans?"YES":"NO");
}

int main()
{
    scanf("%*d");
    while(~scanf("%d%d",&s,&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

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

int s,n,t[10],ans;

ll b[25];

void init()

{

int i,j,l;

ans=0;

memset(b,0,sizeof b);

for(l=0;n--;)

{

scanf("%d",&j);

for(i=0;i<l&&t[i]!=j;i++);

if(i==l)

t[l++]=j;

}

n=l;

sort(t,t+n);

}

bool chk1(int i,int j,int k)

{

if(i+k>s||j+k*2-2>s*2)

return 0;

int ii,jj;

ll c,d;

c=(1LL<<(k*2-1))-1;

for(ii=i;ii<i+k;ii++)

{

d=c<<(j+(ii-i)*2);

if(b[ii]&d)

return 0;

c>>=2;

}

return 1;

}

bool chk2(int i,int j,int k)

{

if(i+k>s||j+k*2-2>s*2)

return 0;

int ii,jj;

ll c=1,d;

for(ii=i;ii<i+k;ii++)

{

d=c<<j;

if(b[ii]&d)

return 0;

c=(c<<2)+3;

}

return 1;

}

void set1(int i,int j,int k,int e)

{

int ii,jj;

ll c,d;

c=(1LL<<(k*2-1))-1;

for(ii=i;ii<i+k;ii++)

{

if(e)

{

d=c<<(j+(ii-i)*2);

b[ii]|=d;

}

else

{

d=~(c<<(j+(ii-i)*2));

b[ii]&=d;

}

c>>=2;

}

void set2(int i,int j,int k,int e)

{

int ii,jj;

ll c=1,d;

for(ii=i;ii<i+k;ii++)

{

if(e)

{

d=c<<j;

b[ii]|=d;

}

else

{

d=~(c<<j);

b[ii]&=d;

}

c=(c<<2)+3;

}

void dfs(int i,int j)

{

if(i==s)

{

ans=1;

return;

}

int ii=i,jj=j+1,k,l;

if(jj==s*2)

{

ii++;

jj=0;

}

if(b[i]&(1LL<<j))

dfs(ii,jj);

else if(j&1)

{

for(l=0;l<n&&!ans;l++)

{

if(chk1(i,j,t[l]))

{

set1(i,j,t[l],1);

dfs(ii,jj);

set1(i,j,t[l],0);

}

else

{

for(l=0;l<n&&!ans;l++)

{

if(chk2(i,j,t[l]))

{

set2(i,j,t[l],1);

dfs(ii,jj);

set2(i,j,t[l],0);

}

void solve()

{

dfs(0,0);

puts(ans?"YES":"NO");

}

int main()

{

scanf("%*d");

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

{

init();

solve();

}

return 0;

}

ps: 这个假期过得太开心了……发生了不少好事情，希望不会是把一年的运气都一下子用光了吧…………那么接下来，就是要好好准备3月中旬的校赛了。