[POJ 1069] | Eurce's Blog

搜索

题意：给出一个边长以三角形个数描述的正六边形，以及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月中旬的校赛了。