XCPC Notes

Appearance

发布时间：2024-07-24

#! https://zhuanlan.zhihu.com/p/710707827

状压dp ​

棋盘式 ​

P1896互不侵犯 ​

Image

cpp
#include<bits/stdc++.h>
#define int long long
const int mod=1e9+7;
using namespace std;
const int N=110,M=10;
int cnt[1<<M];//当前状态行1的个数
vector<int> state;//存储可选行
int dp[2][M*M][1<<M];//dp[i][j][k]表示第i行选了j个国王当前状态为k的方案数
int n,m;
vector<int> head[1<<M];//可以与相应行匹配的其他行
bool check(int x){//判断可选行
    for(int i=0;i<n;i++){
        if((x>>i&1)&&(x>>i+1&1))return false;
    }
    return true;
}
int count(int x){
    int res=0;
    for(int i=0;i<n;i++)res+=(x>>i&1);
    return res;
}
void solve(){
    cin>>n>>m;
    for(int i=0;i<1<<n;i++){
        if(check(i)){
            state.push_back(i);
            cnt[i]=count(i);
        }
    }
    for(int i=0;i<state.size();i++){
        for(int j=0;j<state.size();j++){
            int a=state[i],b=state[j];
            if((a&b)==0&&check(a|b))head[i].push_back(j);
        }
    }
    dp[0][0][0]=1;
    for(int i=1;i<=n+1;i++){
        for(int j=m;j>=0;j--){
            for(int a=0;a<state.size();a++){
                for(int b:head[a]){
                    int c=cnt[state[a]];
                    if(j>=c)dp[i&1][j][a]+=dp[i-1&1][j-c][b];
                    //if(dp[i&1][j][a]!=0)cout<<i<<" "<<j<<" "<<a<<" "<<b<<" "<<dp[i&1][j][a]<<"\n";
                }
            }
        }
        memset(dp[i-1&1],0,sizeof(dp[i-1&1]));
    }
    cout<<dp[n+1&1][m][0];
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}

炮兵阵地 ​

Image

cpp
#include<bits/stdc++.h>
#define int long long
const int mod=1e9+7;
using namespace std;
const int N=110,M=11;
int g[N],cnt[1<<M];
vector<int> state;
int dp[2][1<<M][1<<M];//dp[i][j][k]表示当前状态为j，上一状态为k的能放的炮兵数
int n,m;
bool check(int x){
    for(int i=0;i<m;i++){
        if((x>>i&1)&&((x>>i+1&1)|(x>>i+2&1)))return false;
    }
    return true;
}
int count(int x){
    int res=0;
    for(int i=0;i<m;i++)res+=(x>>i&1);
    return res;
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++){
            char c;
            cin>>c;
            if(c=='H')g[i]+=1<<j;
        }
    }
    for(int i=0;i<1<<m;i++){
        if(check(i)){
            state.push_back(i);
            cnt[i]=count(i);
        }
    }
    for(int i=1;i<=n+2;i++){
        for(int j=0;j<state.size();j++){
            for(int k=0;k<state.size();k++){
                for(int u=0;u<state.size();u++){
                    int a=state[j],b=state[k],c=state[u];
                    if((a&c)|(b&c)|(a&c))continue;
                    if((g[i]&a)|(g[i-1]&b))continue;
                    if(i>=2&&(g[i-2]&c))continue;
                    dp[i&1][j][k]=max(dp[i&1][j][k],dp[i-1&1][k][u]+cnt[a]);
                }
            }
        }
    }
    cout<<dp[n+2&1][0][0];//到n的话需要统计所有情况，因此可以到n+2
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}

集合式 ​

P2831愤怒的小鸟 ​

题意：
给定多个点，问至少有多少条开口向下的抛物线能将这些点完全覆盖
思路：
预处理出 $$ n^2 $$ 条抛物线，将该抛物线能覆盖到的点用状压表示，然后状态转移

cpp
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-6;
const int N=20,M=1<<20;
int f[M];
int path[N][N],n,m;
double X[N],Y[N];
int cmp(double x,double y){
    if(fabs(x-y)<eps)return 0;
    if(x>y)return 1;
    return -1;
}
void solve(){
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>X[i]>>Y[i];
    memset(path,0,sizeof path);
    for(int i=0;i<n;i++){
        path[i][i]=1<<i;
        for(int j=0;j<n;j++){
            if(!cmp(X[i],X[j]))continue;
            double a=(Y[i]/X[i]-Y[j]/X[j])/(X[i]-X[j]);
            double b=Y[i]/X[i]-a*X[i];
            //cout<<a<<" "<<b<<"\n";
            if(a>0)continue;
            int state=0;
            for(int k=0;k<n;k++){
                double x=X[k],y=Y[k];
                if(!cmp(a*x*x+b*x,y))state+=1<<k;
            }
            path[i][j]=state;
        }
    }
    memset(f,0x3f,sizeof f);
    f[0]=0;
    for(int i=0;i+1<1<<n;i++){
        int x=0;
        for(int j=0;j<n;j++){
            if(!(i>>j&1)){
                x=j;
                break;
            }
        }
        for(int j=0;j<n;j++){
            f[i|path[x][j]]=min(f[i|path[x][j]],f[i]+1);
        }
    }
    cout<<f[(1<<n)-1]<<"\n";
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}

P3869宝藏(bfs+状态压缩) ​

Image 思路：
bfs第一次到达则为最小步数
记忆化搜索，每个状态下的x,y是否被搜过

cpp
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=40,M=1<<10;
int n,m;
bool vis[N][N][M];
int dp[N][N][M];
char a[N][N];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct node{
    int x,y,step,state;
};
struct MP{
    int x,y,a,b;
};
void solve(){
    cin>>n>>m;
    int sx,sy,ex,ey;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='S')sx=i,sy=j;
            if(a[i][j]=='T')ex=i,ey=j;
        }
    }
    int k;
    cin>>k;
    vector<MP> b(k);
    for(int i=0;i<k;i++){
        cin>>b[i].x>>b[i].y>>b[i].a>>b[i].b;
    }
    queue<node> q;
    q.push({sx,sy,0,0});
    vis[sx][sy][0]=1;
    while(!q.empty()){
        auto [x,y,step,state]=q.front();
        q.pop();
        //cout<<x<<" "<<y<<"\n";
        if(x==ex&&y==ey){
            cout<<step<<"\n";
            return;
        }
        for(int i=0;i<4;i++){
            int tx=x+dx[i],ty=y+dy[i];
            if(tx<1||tx>n||ty<1||ty>m)continue;
            bool g=0;
            if(a[tx][ty]!='#')g=1;
            int ss=state;
            for(int j=0;j<k;j++){
                if(tx==b[j].a&&ty==b[j].b&&(state>>j&1))g^=1;
                if(tx==b[j].x&&ty==b[j].y)ss^=(1<<j);
            }
            if(g&&!vis[tx][ty][ss]){
                vis[tx][ty][ss]=1;
                q.push({tx,ty,step+1,ss});
            }
        }
    }

}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}

CF1995D Cases ​

题意：

  • 两个单词如果结尾字母长度相同，那么这两个单词为同一个case
  • 给定三个数 $$ n,c,k $$ 分别代表文本长度，文本出现的字母个数，单词最长长度
  • 要求将文本分割成单词，使case数量最少

  • 1≤k≤n≤218，1≤c≤18 1 \leq k \leq n \leq 2^{18} ，1 \leq c \leq 18

思路：

  • 文本的最后一个字母肯定为一种case
  • 每个长度为k的子串，必定存在一个字母被选中
  • 使用状态压缩将所有上述两种情况的掩码表示出来，如果一种方案符合题意，那么该掩码必定与上述两种情况的所有掩码都有交集
  • 没有交集的掩码即是不符合题意的
    • 一种情况是直接找两种情况的所有掩码的反码
    • 反码的子集用状压dp搜索出来
  • 从满足的掩码选一个包含1最小的即为答案
cpp
void solve(){
    int n,c,k;
    string s;
    cin>>n>>c>>k>>s;
    vector<vector<int>> sum(c,vector<int>(n+1));
    for(int i=0;i<n;i++){
        for(int j=0;j<c;j++)sum[j][i+1]=sum[j][i]+(s[i]==j+'A');
    }
    vector<bool> bms(1<<c),bad(1<<c);
    for(int i=1;i+k-1<=n;i++){
        int mask=0;
        for(int j=0;j<c;j++){
            if(sum[j][i+k-1]-sum[j][i-1]!=0)mask|=1<<j;
        }
        bms[mask]=1;
    }
    bms[(1<<s.back()-'A')]=1;
    for(int i=0;i<1<<c;i++){
        bad[i]=bms[((1<<c)-1)^i];
    }
    for(int i=(1<<c)-1;i>=0;i--){
        for(int j=0;j<c;j++){
            bad[i]=bad[i]|bad[i|(1<<j)];
        }
    }
    int ans=1e9;
    for(int i=0;i<1<<c;i++){
        if(!bad[i])ans=min(ans,(int)__builtin_popcount(i));
    }
    cout<<ans<<"\n";
}

Wenwei Lin · 2022 — 2025