Square Destroyer

C++(g++ 7.5.0) 解法, 执行用时: 17ms, 内存消耗: 420K, 提交时间: 2022-08-09 21:50:58

#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T&x){
    x=0; char temp=getchar(); bool f=false;
    while(!isdigit(temp)){if(temp=='-') f=true; temp=getchar();}
    while(isdigit(temp)){x=(x<<1)+(x<<3)+temp-'0'; temp=getchar();}
    if(f) x=-x;
}
template <typename T>
void print(T x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
const int MAXN = 65;
int T,n,m,k,ans;
bitset<MAXN> square[MAXN]; int cnt;
vector<int> edge[MAXN];
bitset<MAXN> ori; 
inline bitset<MAXN> GetSquare(int x,int l,int id){
    bitset<MAXN> res; res.reset();
    for(int i=0;i<l;i++){
        int U=x+i,D=U+l*(2*n+1),L=(x+n)+i*(2*n+1),R=L+l;
        res[U]=res[D]=res[L]=res[R]=1;
        edge[id].push_back(U),edge[id].push_back(D),edge[id].push_back(L),edge[id].push_back(R);
    }
    return res;
}
inline void Prework(){
    cnt=0,ori.set();
    for(int i=1;i<=55;i++) square[i].reset(),edge[i].clear();
    for(int l=1;l<=n;l++)
        for(int i=1;i<=n+1-l;i++)
            for(int j=1;j<=n-l+1;j++)
                ++cnt,square[cnt]=GetSquare(j+(i-1)*(2*n+1),l,cnt);
}
inline bool Check(bitset<MAXN> now,bitset<MAXN> squ){return (now&squ)==squ;}
inline bool Check(bitset<MAXN> now,int id){return now[id]==1;}
inline void Del(bitset<MAXN> &now,bitset<MAXN> squ){now&=(~squ);}
inline void Del(bitset<MAXN> &now,int id){now[id]=0;}
inline void Ins(bitset<MAXN> &now,int id){now[id]=1;}
inline int Evaluate(bitset<MAXN> now,int turn){
    int res=0;
    for(int i=turn;i<=cnt;i++)
        if(Check(now,square[i])) res++,Del(now,square[i]); 
    return res;
}
bool tag;
int lim;
bitset<MAXN> now;
void IDAstar(int step,int turn){
    int g=Evaluate(now,turn);
    if(g+step>lim) return;
    if(g==0||tag) return tag=true,void();
    while(!Check(now,square[turn])) turn++;
    for(int i=0,tmp=edge[turn].size();i<tmp;i++)
        if(Check(now,edge[turn][i])){
            Del(now,edge[turn][i]);
            IDAstar(step+1,turn+1);
            Ins(now,edge[turn][i]);
            if(tag) return;
        }
}
int main(){
    read(T);
    while(T--){
        read(n),read(k);
        m=2*n*(n+1),Prework();
        for(int i=1,temp;i<=k;i++) read(temp),ori[temp]=0;

        tag=false,lim=0,now=ori;
        while(true){
            IDAstar(0,1);
            if(tag){ans=lim; break;}
            lim++;
        }
        print(ans),puts("");
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 54ms, 内存消耗: 380K, 提交时间: 2020-08-22 15:52:41

#include<bits/stdc++.h>

using namespace std;

int n,m,k;
vector<int>square[60];
bool st[65];

bool check(int x) {
    vector<int> &sq=square[x];
    for(int i=0;i<sq.size();i++) if(st[sq[i]]) return false;
    return true;
}
int f() {
    int res=0;
    bool temp[65];
    memcpy(temp,st,sizeof st);
    for(int i=0;i<m;i++)
        if(check(i)) {
            res++;
            vector<int> &sq=square[i];
            for(int j=0;j<sq.size();j++) st[sq[j]]=true;
        }
    memcpy(st,temp,sizeof temp);
    return res;
}
bool dfs(int depth,int max_depth) {
    int t=f();
    if(t==0) return true;
    if(t+depth>max_depth) return false;
    for(int i=0;i<m;i++) {
        if(check(i)) {
            vector<int> &sq=square[i];
            for(int j=0;j<sq.size();j++) {
                st[sq[j]]=true;
                if(dfs(depth+1,max_depth)) return true;
                st[sq[j]]=false;
            }
            return false;
        }
    }
    return true;
}
int main() {
    //freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--) {
        cin>>n;
        m=0;
        int d=2*n+1;
        for(int len=1;len<=n;len++)
            for(int x=1;x+len-1<=n;x++)
                for(int y=1;y+len-1<=n;y++) {
                    vector<int> &sq=square[m];
                    sq.clear();
                    for(int i=0;i<len;i++) {
                        sq.push_back(y+(x-1)*d+i);
                        sq.push_back(y+(x-1+len)*d+i);
                        sq.push_back(y+(x-1)*d+n+d*i);
                        sq.push_back(y+(x-1)*d+n+d*i+len);
                    }
                    m++;
                }
        cin>>k;
        memset(st,false,sizeof st);
        for(int i=1;i<=k;i++) {
            int num;
            cin>>num;
            st[num]=true;
        }
        for(int i=0;;i++) {
            if(dfs(0,i)) {
                cout<<i<<endl;
                break;
            }
        }
    } 
    return 0;
}

C++ 解法, 执行用时: 42ms, 内存消耗: 420K, 提交时间: 2022-02-05 14:06:06

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int t,ts,tts,base,n,k,ans,exi[65],tmp[65],t_st;
vector<int>sk[65],se[65];
int cal(){
    int res=0;
    for(int i=1;i<=ts;i++)tmp[i]=exi[i];
    for(int i=1;i<=ts;i++)if(!tmp[i]){
        res++;
        for(int j=0;j<se[i].size();j++)for(int l=0;l<sk[se[i][j]].size();l++)tmp[sk[se[i][j]][l]]--;
    }
    return res;
}
bool dfs(int sum,int lim){
    if(sum+cal()>lim)return 0;
    int tmp=1;
    while(exi[tmp]<0&&tmp<=ts)tmp++;
    if(tmp>ts){ans=min(ans,sum);return 1;}
    for(int i=0;i<se[tmp].size();i++){
        int sti=se[tmp][i];
        for(int j=0;j<sk[sti].size();j++)exi[sk[sti][j]]--;
        if(dfs(sum+1,lim))return 1;
        for(int j=0;j<sk[sti].size();j++)exi[sk[sti][j]]++;
    }
    return 0;
}
int main(){
	cin>>t;
    while(t--){
    	cin>>n>>k;
        ts=0,tts=2*n*(n+1),base=2*n+1;
        for(int i=1;i<65;i++)sk[i].clear(),se[i].clear();
        for(int sz=1;sz<=n;sz++)for(int i=1;(i-1)/base+sz<=n;i+=base)for(int j=i;j-i+sz<=n;j++){
            ts++;
            for(int l=j;l-j<sz;l++)se[ts].pb(l),se[ts].pb(l+sz*base),sk[l].pb(ts),sk[l+sz*base].pb(ts);
            for(int l=j+n;(l-j-sz)/base<sz;l+=base)se[ts].pb(l),se[ts].pb(l+sz),sk[l].pb(ts),sk[l+sz].pb(ts);
        }
        memset(exi,0,sizeof(exi));
        for(int i=1;i<=k;i++){cin>>t_st;for(int j=0;j<sk[t_st].size();j++)exi[sk[t_st][j]]--;tts--;}
        ans=tts;
        for(int maxd=0;;maxd++)if(dfs(0,maxd)){cout<<ans<<"\n";break;}
    }
}

详情