2024CCPConline部分题目

D

题目链接：2024CCPCOnline

看s与t均小于100，故往dp的方向想。

设$dp[i][l][r]$为s枚举到第 i 位时，以t 中（l，r）为子序列在解码中出现的次数。

则有转移方程：

$$dp[i][l][r]=dp[i][l][r]+dp[i-1][l][k]*dp[i-1][k+1][r]$$

还需要考虑$s[i]$在（l，r）中出现的情况，即$t[k+1]==s[i]$时：

$$dp[i][l][r]=dp[i][l][r]+dp[i-1][l][k]*dp[i-1][k+2][r]$$

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const int N=1e2+5;
ll dp[N][N][N];//枚举到第n位时，T的（l，r）序列在解码中出现的次数，求dp[n][1][m]
const int MOD=998244353;
void solve(){
    string s,t;
    cin>>s>>t;
    int n=s.size();
    int m=t.size();
    s=' '+s;
    t=' '+t;
    for(int i=0;i<=n;i++){
        for(int l=1;l<=m+1;l++){
            for(int r=0;r<l;r++){
                dp[i][l][r]=1;
            }
        }
    }
    ll index;
    for(int i=1;i<=n;i++){
        for(int l=1;l<=m;l++){
            for(int r=l;r<=m;r++){
                for(int k=l-1;k<=r;k++){
                    dp[i][l][r]=(dp[i][l][r]+dp[i-1][l][k]*dp[i-1][k+1][r])%MOD;
                    //cout<<dp[i-1][l][k]<<' '<<dp[i-1][k+1][r]<<endl;
                }
                for(int k=l-1;k<r;k++){
                    if(s[i]==t[k+1]){
                        dp[i][l][r]=(dp[i][l][r]+dp[i-1][l][k]*dp[i-1][k+2][r])%MOD;
                        //cout<<dp[i-1][l][k]<<' '<<dp[i-1][k+1][r]<<endl;
                    }
                }
            }
        }
    } 
    cout<<dp[n][1][m];
}
int main(){ 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

J

题目链接：2024CCPCOnline

看到维护两个sum的异或值，想到线性基。

两数列中对应值的互换本质上是$sum \oplus a[i] \oplus b[i]$，故可对$a[i] \oplus b[i]$建立线性基。

这里需要强调一下线性基的性质：$d[i]$若不为0，第 i+1位必为1。

故有基本思路：

若(sum1>>i)&1与(sum2>>i)&1均为0，则continue

若(sum1>>i)&1与(sum2>>i)&1均为1，则sum1^d[i] , sum2^d[i]

若(sum1>>i)&1与(sum2>>i)&1不相等时，需要考虑前一位的。

1. 若为$\begin{matrix}1 & 1\\\ 0 &0\end{matrix}$需对 i 位进行处理，这样会使大的变小，小的变大
2. 若为$\begin{matrix}1 & 0\\\ 0 &1\end{matrix}$我们对 i 位不处理

3. 若为$\begin{matrix}1 & 0\\\ 1 &1\end{matrix}$或$\begin{matrix}0 & 1 \\\ 0 & 0\end{matrix}$我们不确定是否需要处理，那就都算一遍，取min，且不论取不取，大小关系已确定，后面的位处理时只需要无脑让大的变小即可、

   代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const int N=1e6+5;
ll a[N];
ll b[N];
int n;
ll d[35];
void print(int i,ll sum1,ll sum2){
    cout<<i<<' '<<sum1<<' '<<sum2<<endl;
}
void ins(ll x){
	for(int i=33;i>=0;i--){
		if(!(x&(1ll<<i)))continue;
		if(d[i])x^=d[i];//eliminate the 1 on the i-th bit of x
		else{d[i]=x;break;}//successfully inserted, jump out.
	}
}
ll dfs(int i,ll sum1,ll sum2){
    //print(i,sum1,sum2);
    if(i==-1)return max(sum1,sum2);
    int x1=(sum1>>i)&1;
    int x2=(sum2>>i)&1;
    if(x1==x2&&x1==0)return dfs(i-1,sum1,sum2);
    else if(x1==x2&&x1==1)return dfs(i-1,sum1^d[i],sum2^d[i]);
    else {
        if((sum1>sum2&&x1==1)||(sum2>sum1)&&x2==1)return dfs(i-1,sum1^d[i],sum2^d[i]);
        else return dfs(i-1,sum1,sum2);
    }
}
void solve(){
    fill(d,d+34,0);
    ll sum1=0,sum2=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum1^=a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        sum2^=b[i];
    }
    for(int i=1;i<=n;i++)ins(a[i]^b[i]);
    for(int i=33;i>=0;i--){
        int x1=(sum1>>i)&1;
        int x2=(sum2>>i)&1;
        if(x1==x2&&x1==0)continue;
        else if(x1==x2&&x1==1){
            sum1^=d[i];
            sum2^=d[i];
        }
        else {
            int y1=(sum1>>(i+1))&1;
            int y2=(sum2>>(i+1))&1;
            if(y1!=y2){
                if((y1==1&&x1==1)||(y2==1&&x2==1)){
                    cout<<dfs(i-1,sum1^d[i],sum2^d[i])<<endl;
                    return;
                }
                else {
                    cout<<dfs(i-1,sum1,sum2)<<endl;
                    return;
                }
            }
            else {
                ll ans=min(dfs(i-1,sum1,sum2),dfs(i-1,sum1^d[i],sum2^d[i]));
                cout<<ans<<endl;
                return;
            }
        }
    }
    cout<<max(sum1,sum2)<<endl;
}
int main(){ 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}