AT_abc345_d 题解

本文同步发表于 cnblogs。

是个逆天搜索。

最开始：爆搜，启动！

然后 TLE 到飞起。

赛后：我【数据删除】这么简单的吗？！

dfs 每个位置，试着把没放过的块放到以这个位置为左上角的区域里面。

好了没了，就是这么简单！

对了记得这个块可以旋转！

Posted on cnblogs too. But I didn't write English solution there.

It's such a strange DFS.

I used an exhaustive DFS, and got TLE.

But actually it's easy.

DFS every cell, and try to put a tile that we haven't used it before(this tile's top left corner is this cell).

Oh, and remember that the tile can spin.

#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
    i128 f=1;
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    x*=f;
}
void writing(i128 x)
{
    if(x>=10)writing(x/10);
    putchar(x%10+'0');
}
void write(i128 x)
{
    if(x<0)
    {
        cout<<'-';
        x=-x;
    }
    writing(x);
}
LL n,h,w,a[20],b[20];
bool vis[20][20],u[20];
void dfs(LL x,LL y)
{
    if(y>w)dfs(x+1,1);
    if(x>h)
    {
        cout<<"Yes"<<endl;
        exit(0);
    }
    if(vis[x][y])dfs(x,y+1);
    rep(i,1,2*n,1)
    {
        if(!u[(i-1)%n+1])
        {
            bool f=1;
            repn(xx,x,x+a[i],1)
            {
                repn(yy,y,y+b[i],1)
                {
                    if(xx>h||yy>w||vis[xx][yy])f=0;
                }
            }
            if(!f)continue;
            u[(i-1)%n+1]=1;
            repn(xx,x,x+a[i],1)
            {
                repn(yy,y,y+b[i],1)
                {
                    vis[xx][yy]=1;
                }
            }
            dfs(x,y+1);
            u[(i-1)%n+1]=0;
            repn(xx,x,x+a[i],1)
            {
                repn(yy,y,y+b[i],1)
                {
                    vis[xx][yy]=0;
                }
            }
        }
    }
}
int main()
{
    cin>>n>>h>>w;
    rep(i,1,n,1)cin>>a[i]>>b[i];
    rep(i,n+1,2*n,1)
    {
        a[i]=b[i-n];
        b[i]=a[i-n];
    }
    dfs(1,1);
    cout<<"No"<<endl;
    return 0;
}