2022/8/8 Competition thinking + state pressure dp

​

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

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

  可以想一下,The coordinates of each number are unique and are a permutation,Then we can construct the arrangement according to the coordinates,用b[i]Maintain coordinates,遍历a数组,If the coordinates and values ​​are found to be equal,Then find the first number that is not equal to the subscript,Then swap the coordinates of the two,It can be found that the two numbers after the exchange must meet the conditions,So output after traversingb数组就可以了,NOThe case is that the entire array is 1个值的时候,cArrays are maintainedaThe value of the array after sorting and deduplication,dThe array maintains the subscript of each number,Actually this array is a bit far-fetched,因为a中会有重复的,所以dThe array maintains the last occurrencea[i]The subscript of the last occurrence,But that's enough,The purpose of finding numbers is achieved

#include <bits/stdc++.h>
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<<c[ma]<<" "<<ma<<" "<<d[]<<endl;
                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)

It can be found that the two operations do not affect each other,That is, as long as you find that you can operate it, just operate it,So this question needs to be concerned about the operation of deleting two numbers,这个操作vectorIt can be done elegantly,To make thinking more concise,从0到n-2扫一遍之后,如果还剩下2个或多个数,Then look at it1And the last one can't,You can continue watching2And the penultimate can't,直到不符合条件

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=998244353;
const int N = 2e5+5;
ll n,x;
vector<ll>v;
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(y<v.size()-1&&v.size()>0){
        //cout<<y<<" sss "<<v.size()-1<<endl;
        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<<y<<" "<<v.size()<<endl;
    }
    if(v.size()>1){
        ll l=0,r=v.size()-1;
        while(l<r){
            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)

After reading the meaning of the question, base on it1个字母,2letters are equal or unequal,3one or more letters are all equal or unequal 分类讨论就行

#include <bits/stdc++.h>
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 And check the auxiliary jump interval

The key point of this question is how to skip those knights that have already been visited,令s[i]为从iStart the first unvisited knight,一开始s[i]=i,当i被访问后,s[i]也就变成i+1了,when we visitedfindd(i+1)jump like this;At first I tried array jumping but it was still too violent,用vectorTwo points are still very violent,Finally, you can also look at the problem solution and find out and check the set

CF356A - little_carl 的博客 - 洛谷博客

#include <bits/stdc++.h>
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 - 洛谷 | 位运算

Think of using materials and not using them1和0,然后枚举nThe binary is fine,This question isn't actually a pressuredp,Just used pressuredpThe bit operation in the operation is nothing more than

#include <bits/stdc++.h>
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<<n);s++){
        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

This is also a sort of ranking problem,So the approach is similar,But it's important to note that the answer is no longer found in an all-selected permutation,Because using all of them is not necessarily the best,So update the maximum value in time,In addition, it is only necessary to judge whether the strings are connected end to end,As a blue question, it is not difficult,After all, you can do it yourself,,,

#include <bits/stdc++.h>
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<<i-1][i]=strlen(ch[i]+1);
    for(int s=0;s<(1<<n);s++)
    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<<j-1)][j]=max(dp[s|(1<<j-1)][j],dp[s][i]+(ll)strlen(ch[j]+1));
        ans=max(ans,dp[s|(1<<j-1)][j]);
        //cout<<dp[s|(1<<j-1)][j]<<" "<<dp[s][i]<<" "<<s<<" "<<j<<" "<<i<<endl;
    }
    printf("%lld\n",ans);
    system("pause");
    return 0;
}

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

I feel like this topic is an enhanced version of the formation of troops,But I also forgot to write about the formation,You should write the formation first,,,

This blog speaks clearly,将dpThe situation is very clear,f[i][j][k]表示已经放了i行,有jA pawn is placed in the column,有k列放了2个棋子,Discuss separatelyiPlace a pawn on the line,With two pieces and no piece

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

#include <bits/stdc++.h>
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++){
        //No chess pieces
        f[i][j][k]=f[i-1][j][k];
        //Put a pawn
        //Put in a column with pieces
        if(k>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j+1][k-1]*(j+1)%mod)%mod;
        //Placed in the column without pawns
        if(j>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*(m-(j-1)-k)%mod)%mod;
        //Place two pieces
        //Put on a column with pawns and a column without pawns
        if(k>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]*j*(m-j-(k-1))%mod)%mod;
        //Placed in the column without pawns
        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;
}