【做題記錄】多校-dp

A. Multitest Generator

考慮一個長為 \(m(m\ge 2)\) 的序列 \(b\)，我們顯然可以令 \(b_1=1,b_2=m-2\) 來使它變成 multitest。于是我們只需要判斷能否使用 \(0\) 次或 \(1\) 次操作使其變成 multitest。

首先考慮 \(0\) 次，也就是它本身就是個 multitest。設 \(f_i\) 表示 \(i\sim n\) 這段后綴中有多少個 test，若不合法則 \(f_i=0\)，可以 DP 出來。于是 \(i\) 的答案為 \(0\) 的充要條件即為 \(a_i=f_{i+1}\)。

考慮 \(1\) 次。首先如果 \(f_{i+1}\ne0\)，那么我們可以直接修改 \(a_i\) 來滿足要求。而如果 \(f_{i+1}=0\)，我們則希望通過一次修改將 \(i+1\sim n\) 這段后綴變成 \(a_i\) 個 test?？紤]如果能變成 \(x\) 個 test，則一定可以變成 \(x-1\) 個 test，于是設 \(g_i\) 表示通過一次修改能使 \(i\sim n\) 最多變成多少個 test，則有：

\[g_i=\max(g_{i+a_i+1}+1,\max_{j=i+1}^{n}\{f_j\}+1) \]

也就是分別考慮是否修改 \(a_i\)。于是若 \(g_{i+1}\ge a_i\) 那么 \(i\) 的答案為 \(1\)，否則答案為 \(2\)。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=3e5+5;
int T,n,a[maxn],f[maxn],hp[maxn],g[maxn];
il void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	f[n+1]=hp[n+1]=g[n+1]=0;
	for(int i=n;i;i--){
		f[i]=i+a[i]==n?1:i+a[i]>n||!f[i+a[i]+1]?0:f[i+a[i]+1]+1;
		hp[i]=max(hp[i+1],f[i]);
		g[i]=max(i+a[i]>n?0:g[i+a[i]+1]+1,hp[i+1]+1);
	}
	for(int i=1;i<n;i++){
		cout<<(a[i]==f[i+1]?0:f[i+1]||g[i+1]>=a[i]?1:2)<<' ';
	}
	cout<<'\n';
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
}
int main(){return asbt::main();}

B. Bitwise Slides

記 \(s_i\) 為前綴異或和數組。則對于每一時刻，都有三個數的異或和為 \(s_i\)。又因為有兩個相等，所以必然有一個值為 \(s_i\)。

設 \(dp_{i,j}\) 表示進行完第 \(i\) 次操作后那兩個相等的數值為 \(j\) 的方案數。于是有轉移：

\(j=s_{i-1}\)，\(dp_{i,j}\gets 3dp_{i-1,j}\)。
\(j=s_i\)，\(\begin{cases}dp_{i,j}\gets dp_{i-1,j}\\dp_{i,s_{i-1}}\gets2dp_{i,j}\end{cases}\)。
\(else\)，\(dp_{i,j}\gets dp_{i-1,j}\)。

發現每次 DP 值改變的只有 \(dp_{i,s_{i-1}}\)。用 map 維護即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pii pair<int,int>
#define fir first
#define sec second
using namespace std;
namespace asbt{
const int maxn=2e5+5,mod=1e9+7;
il int pls(int x,int y){
    return x+y<mod?x+y:x+y-mod;
}
il void add(int &x,int y){
    x=pls(x,y);
}
il int mns(int x,int y){
    return x<y?x-y+mod:x-y;
}
il void sub(int &x,int y){
    x=mns(x,y);
}
int T,n,a[maxn];
map<int,int> dp;
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        dp.clear();
        dp[0]=1;
        for(int i=1,x;i<=n;i++){
            cin>>x;
            a[i]=a[i-1]^x;
            dp[a[i-1]]=(dp[a[i-1]]*3ll+dp[a[i]]*2ll)%mod;
        }
        int ans=0;
        for(pii i:dp){
            add(ans,i.sec);
        }
        cout<<ans<<'\n';
    }
    return 0;
}
}
int main(){return asbt::main();}

C. Cows and Cool Sequences

考慮題目約束的實質，設那一段連續數字的開頭為 \(t\)，于是有 \(ty+\frac{y(y-1)}{2}=x\)，即 \(\frac{2x}{y}-y=2t-1\)，也就是要求 \(\frac{2x}{y}-y\) 為奇數。

考慮將每個數 \(x\) 的所有因子 \(2\) 都拆出來，也就是 \(x=2^{v(x)}\times p(x)\)，其中 \(p(x)\) 為 \(x\) 的最大的奇約數。于是我們的要求即為 \(2^{v(x)-v(y)+1}\times\frac{p(x)}{p(y)}-y\) 為奇數。首先有 \(p(y)|p(x)\)，然后對 \(y\) 的奇偶性進行分類討論：

\(y\) 為奇數，則要求 \(2^{v(x)-v(y)+1}\times\frac{p(x)}{p(y)}\) 為偶數，即 \(v(x)-v(y)+1>0\)，也就是 \(v(x)>-1\)，即 \(v(x)\) 任取。
\(y\) 為偶數，則要求 \(2^{v(x)-v(y)+1}\times\frac{p(x)}{p(y)}\) 為奇數，即 \(v(x)-v(y)+1=0\)，即 \(v(y)=v(x)+1\)。

于是我們可以得出 \((x,y)\) 合法的充要結論：\(p(y)|p(x)\land[v(y)=0\lor v(y)=v(x)+1]\)。考慮 DP，設 \(f_i\) 表示考慮到 \(i\) 且沒有修改 \(i\)，\(1\sim i\) 合法的最小修改次數。于是有轉移：

\[f_i=\min_{1\le j<i\land p(a_i)|p(a_j)\land[v(a_i)=v(a_j)+i-j\lor v(a_i)\le i-j-1]}\{f_j+i-j-1\} \]

答案即為 \(\min_{i=1}^{n}\{f_i+n-i\}\)。

Code

#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=5e3+5,inf=1e9;
int n,a[maxn],b[maxn],f[maxn];
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        while(a[i]%2==0){
            a[i]>>=1,b[i]++;
        }
    }
    f[1]=0;
    for(int i=2;i<=n;i++){
        f[i]=i-1;
        for(int j=1;j<i;j++){
            if(a[j]%a[i]==0&&(b[i]==b[j]+i-j||b[i]<=i-j-1)){
                f[i]=min(f[i],f[j]+i-j-1);
            }
        }
    }
    int ans=inf;
    for(int i=1;i<=n;i++){
        ans=min(ans,f[i]+n-i);
    }
    cout<<ans;
	return 0;
}
}
signed main(){return asbt::main();}

D. Reality Show

首先考慮如果已知選了哪些選手，怎么算利潤。考慮從下往上合并，每次將下面一層的合并到上面一層。然而題目要求的順序是單調不增的，很難這樣處理，考慮反過來，按照編號從大到小出處理一個單調不減的序列即可。于是可以 DP，設 \(f_{i,j,k}\) 表示考慮到了第 \(i\) 個人，此時第 \(j\) 層有 \(k\) 個人且第 \(j\) 層上面沒有人的最大利潤。于是有轉移：

加入第 \(i\) 個人：

\[f_{i,l_i,j}\gets f_{i+1,l_i,j-1}-s_i+c_{l_i} \]

合并第 \(j\) 層：

\[f_{i,j,k}+\lfloor\frac{k}{2}\rfloor\times c_{j+1}\to f_{i,j+1,\lfloor\frac{k}{2}\rfloor} \]

時空復雜度都是 \(O(n^3)\)。先將第一維滾掉，然后又是喜聞樂見的有效狀態數優化。考慮第二種轉移，因為每一層的人數最多是上一層的一半，所以有 \(k\le\frac{n}{2^{j-l_i}}\)。于是有效的狀態數是 \(O(n^2)\) 的，時間復雜度也就是 \(O(n^2)\)。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=5e3+5;
int n,m,a[maxn],b[maxn],c[maxn],f[maxn][maxn];
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
	}
	for(int i=1;i<=n+m;i++){
		cin>>c[i];
	}
	memset(f,-0x3f,sizeof(f));
	for(int i=1;i<=n+m;i++){
		f[i][0]=0;
	}
	for(int i=n;i;i--){
		for(int j=n;j;j--){
			f[a[i]][j]=max(f[a[i]][j],f[a[i]][j-1]-b[i]+c[a[i]]);
		}
		for(int j=a[i];j<n+m;j++){
			for(int k=0;k<=n>>(j-a[i]);k++){
				f[j+1][k>>1]=max(f[j+1][k>>1],f[j][k]+(k>>1)*c[j+1]);
			}
		}
	}
	cout<<f[n+m][0];
	return 0;
}
}
int main(){return asbt::main();}

E. Random Task

假設 \([x+1,2x]\) 中滿足條件的有 \(a\) 個，那么在 \([x+2,2x+2]\) 中，\(2x+2\) 和 \(x+1\) 二進制下 \(1\) 的個數是相同的，\([x+2,2x]\) 這一部分是相同的，又多了一個 \(2x+1\)，因此滿足條件的一定 \(\ge a\)。于是可以二分，將 \([mid+1,2mid]\) 中滿足條件的數量數位 DP 出來即可。

Code

#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
int m,kk,dig[67],f[67][67];
il int dfs(int pos,int sum,bool limit){
	if(!limit&&~f[pos][sum]){
		return f[pos][sum];
	}
	if(!pos){
		return sum==kk;
	}
	if(limit){
		if(dig[pos]){
			return dfs(pos-1,sum+1,1)+dfs(pos-1,sum,0);
		}else{
			return dfs(pos-1,sum,1);
		}
	}else{
		return f[pos][sum]=dfs(pos-1,sum+1,0)+dfs(pos-1,sum,0);
	}
}
il int solve(int x){
	int cnt=0;
	while(x){
		dig[++cnt]=x&1,x>>=1;
	}
	return dfs(cnt,0,1);
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>m>>kk;
	memset(f,-1,sizeof(f));
	int l=1,r=1e18;
	while(l<r){
		int mid=(l+r)>>1;
		if(solve(mid<<1)-solve(mid)>=m){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	cout<<l;
	return 0;
}
}
signed main(){return asbt::main();}

posted @ 2025-11-04 23:01 zhangxy__hp 閱讀(6) 評論(0) 收藏舉報

刷新頁面返回頂部

zhangxyhp

【做題記錄】多校-dp

A. Multitest Generator

B. Bitwise Slides

C. Cows and Cool Sequences

D. Reality Show

E. Random Task