2022/8/8 比赛思维+状压dp

​

活动地址：CSDN21天学习挑战赛

C-Constructive Problems Never Die_"蔚来杯"2022牛客暑期多校训练营7 (nowcoder.com)

  可以想一下，每个数的坐标是唯一的并且是一个排列，那我们就可以根据坐标来构造排列，用b[i]维护坐标，遍历a数组，如果发现坐标和值相等了，那就去找第一个和下标不等的数，然后交换两者的坐标，可以发现交换后的两个数是一定符合条件的，所以遍历完之后输出b数组就可以了，NO的情况就是整个数组都为1个值的时候，c数组维护的是a数组排序去重后的值，d数组维护的是每个数的下标，其实这个数组有点牵强，因为a中会有重复的，所以d数组维护的是最后出现a[i]最后一次出现时的下标，但这样也够了，达到了找数的目的

#include 
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=998244353;
const int N = 2e5+5;
ll t,n,a[100005],b[100005],c[100005],d[100005];
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        for(int i=1;i<=n;i++) a[i]=b[i]=c[i]=d[i]=0;
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]),b[i]=i,c[i]=a[i],d[a[i]]=i;
        sort(c+1,c+n+1);
        ll m=unique(c+1,c+n+1)-c-1,flag=1;
        for(int i=1;i<=n;i++){
            if(a[i]==b[i]){
                ll ma=1;
                while(a[i]==c[ma]&&ma<=m) ma++;
                if(ma>m){flag=0;break;}
                //cout<
                swap(b[i],b[d[c[ma]]]);
            }
        }
        if(flag) printf("YES\n");
        else {printf("NO\n");continue;}
        for(int i=1;i<=n;i++) printf("%lld ",b[i]);
        printf("\n");
    }
    system("pause");
    return 0;
}

F-Candies_"蔚来杯"2022牛客暑期多校训练营7 (nowcoder.com)

可以发现两种操作互不影响，即只要发现可以操作尽管操作就行，所以这题需要在意的就只是删除两个数的操作了，这个操作vector就可以优雅的完成，为了思路更加简洁，从0到n-2扫一遍之后，如果还剩下2个或多个数，那么就在看看1和最后一个可不可以，可以就继续看2和倒数第二个可不可以，直到不符合条件

#include 
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=998244353;
const int N = 2e5+5;
ll n,x;
vectorv;
int main(){
    scanf("%lld%lld",&n,&x);
    for(int i=1;i<=n;i++){
        ll y;scanf("%lld",&y);
        v.push_back(y);
    }
    ll y=0,ans=0;
    while(ysize()-1&&v.size()>0){
        //cout<
        if(v[y]==v[y+1]||v[y]+v[y+1]==x){
            ans++;
            v.erase(v.begin()+y);
            v.erase(v.begin()+y);
            y=max(0LL,y-1);
        }
        else y++;
        //cout<
    }
    if(v.size()>1){
        ll l=0,r=v.size()-1;
        while(l
            if(v[l]==v[r]||v[l]+v[r]==x){ans++;l++,r--;}
            else break;
        }
    }
    printf("%lld\n",ans);
    system("pause");
    return 0;
}

G-Regular Expression_"蔚来杯"2022牛客暑期多校训练营7 (nowcoder.com)

读懂题意之后根据1个字母，2个字母相等或不等，3个或多个字母全相等或不等 分类讨论就行

#include 
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=998244353;
const int N = 2e5+5;
ll q;
char s[200005];
int main(){
    scanf("%lld",&q);
    while(q--){
        scanf("%s",s+1);
        ll n=strlen(s+1),flag=1;
        for(int i=2;i<=n;i++)
            if(s[i]!=s[i-1]){flag=0;break;}
        if(n==1) printf("1 2\n");
        else if(n==2){
            if(flag) printf("2 8\n");
            else printf("2 6\n");
        }
        else{
            if(flag) printf("2 4\n");
            else printf("2 2\n");
        }
    }
    system("pause");
    return 0;
}

356A - Knight Tournament 并查集辅助跳跃区间

这题关键点就是如何跳过那些已经被访问过的骑士，令s[i]为从i开始第一个没被访问的骑士，一开始s[i]=i，当i被访问后，s[i]也就变成i+1了，我们访问的时候就findd(i+1)这样跳；一开始试的用数组跳但还是太暴力了，用vector二分也还是很暴力，最后看题解发现并查集也可以

CF356A - little_carl 的博客 - 洛谷博客

#include 
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=998244353;
const int N = 2e5+5;
ll n,m,ans[300005],s[300005];
ll findd(ll x){return x==s[x]?x:s[x]=findd(s[x]);}
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n+1;i++) s[i]=i;
    for(int i=1;i<=m;i++){
        ll l,r,x;
        scanf("%lld%lld%lld",&l,&r,&x);
        for(int j=findd(l);j<=r;j=findd(j+1)){
            if(j!=x){
                ans[j]=x;
                s[j]=j+1;
            }
        }
    }
    for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
    system("pause");
    return 0;
}

P7859 [COCI2015-2016#2] GEPPETTO - 洛谷 | 位运算

把用材料和不用看成1和0，然后枚举n的二进制就可以了，这题其实不是状压dp，只是用到了状压dp中的位运算的操作罢了

#include 
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=998244353;
const int N = 2e5+5;
ll n,m,x[405],y[405],a[25];
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++) scanf("%lld%lld",&x[i],&y[i]);
    ll ans=0;
    for(int s=0;s<(1<
        for(int i=1;i<=n;i++) 
            if(s>>(i-1)&1) a[i]=1;
            else a[i]=0;
        ll flag=1;
        for(int i=1;i<=m;i++){
            if(a[x[i]]&&a[y[i]]){flag=0;break;}
        }
        if(flag) ans++;
    }
    printf("%lld\n",ans);
    system("pause");
    return 0;
}

P1278 单词游戏 - 洛谷 | 状压dp

这也算是排列问题的一种，所以做法也类似，但是需要注意的是答案不再是从全被选上的排列中找了，因为全部用上不一定是最优的，所以要及时更新最大值，另外字符串之间要首尾相接只需要判断一下就可以了，作为蓝题还是不算难的，毕竟可以自己做出来，，，

#include 
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=998244353;
const int N = 2e5+5;
ll n,dp[100006][20];
char ch[20][110];
int main(){
    scanf("%lld",&n);
    ll ans=0;
    for(int i=1;i<=n;i++) scanf("%s",ch[i]+1);
    for(int i=1;i<=n;i++) dp[1<-1][i]=strlen(ch[i]+1);
    for(int s=0;s<(1<
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++){
        if(s>>(j-1)&1) continue;
        if(ch[i][strlen(ch[i]+1)]!=ch[j][1]||i==j) continue;
        dp[s|(1<-1)][j]=max(dp[s|(1<-1)][j],dp[s][i]+(ll)strlen(ch[j]+1));
        ans=max(ans,dp[s|(1<-1)][j]);
        //cout<
    }
    printf("%lld\n",ans);
    system("pause");
    return 0;
}

P2051 [AHOI2009] 中国象棋 - 洛谷 | 状态dp

感觉这题像是排兵布阵的强化版，但是排兵布阵我也忘了咋写了，应该先写排兵布阵的，，，

这个博客讲的很清楚，将dp的情况分的很清楚，f[i][j][k]表示已经放了i行，有j列放了一个棋子，有k列放了2个棋子，分别讨论第i行放一个棋子，放两个棋子和不放棋子的情况

题解 P2051 【[AHOI2009]中国象棋】 - 顾z 的博客 - 洛谷博客

#include 
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=9999973;
const int N = 2e5+5;
ll n,m,ans;
ll f[105][105][105];
ll C(ll x){
    return x*(x-1LL)/2%mod;
}
int main(){
    scanf("%lld%lld",&n,&m);
    f[0][0][0]=1;
    for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++)
    for(int k=0;k<=m-j;k++){
        //不放棋子
        f[i][j][k]=f[i-1][j][k];
        //放一个棋子
        //放在一个有棋子的列
        if(k>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j+1][k-1]*(j+1)%mod)%mod;
        //放在没有棋子的列
        if(j>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*(m-(j-1)-k)%mod)%mod;
        //放两个棋子
        //放在一个有棋子的列和一个没有棋子的列
        if(k>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]*j*(m-j-(k-1))%mod)%mod;
        //放在没有棋子的列
        if(j>=2) f[i][j][k]=(f[i][j][k]+f[i-1][j-2][k]*C(m-(j-2)-k)%mod)%mod;
        if(k>=2) f[i][j][k]=(f[i][j][k]+f[i-1][j+2][k-2]*C(j+2)%mod)%mod;
    }
    for(int i=0;i<=m;i++)
    for(int j=0;j<=m;j++)
    ans=(ans+f[n][i][j])%mod;
    printf("%lld\n", ans);
    system("pause");
    return 0;
}