10.7 div2复现赛

用户头像 发布于 2025-10-07 255 次阅读 OI

10.7 div2复现赛

P14178 「FAOI-R8」Jueves

可以发现一些性质：

  1. 当 $s=t$ 时，显然答案为 0
  2. 否则，最短路一定是连接 $s$ 与 $t$ 的那条边，因为 $(a_u​ xor a_v​)+(a_u​ or a_v​)+(a_u​ and a_v​) > a_u$。

所以代码非常简单：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5;
int T,n,s,t;
int a[N];
signed main(){
	cin>>T;
	while(T--){
		cin>>n>>s>>t;
		for(int i=1;i<=n;i++) cin>>a[i];
		if(s==t) cout<<0<<endl;
		else cout<<(a[s]^a[t])+(a[s]|a[t])+(a[s]&a[t])<<endl;
	}
	return 0;
}

P14179 「FAOI-R8」喵了个喵 V

首先无视 $m$ 的取值根据题意模拟求出字典序最小的答案数组，
若此时 $m<0$，无解；$m=0$ 则刚好得出答案；
若 $m>0$，则再次按照性质从大到小尽可能地匀给当前位置，
然后就能得出答案了。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int T;
int n,d,m;
int a[N];
bool b[N];
signed main(){
	cin>>T;
	while(T--){
		int y=1;
		cin>>n>>d>>m;
		for(int i=1;i<=n;i++) cin>>b[i],a[i]=0;;
		for(int i=1;i<=n;i++){
			a[i]+=a[i-1];
			if(b[i]){
				if(a[i]%d==0){
					m-=a[i];
					continue;
				} 
				int add=d-(a[i]%d);
				a[i]+=add,m-=a[i];
				if(m<0) y=0;
			}
			else{
				if(a[i]%d!=0){
					m-=a[i];
					continue;
				} 
				a[i]++,m-=a[i];
				if(m<0) y=0;
			}
		}
		if(m>0){
			for(int i=n;i>=1;i--){
				if(!m) break;
				if(b[i]){
					if(i==n){
						a[i]+=(m-(m%d)),m=m%d;
						continue;
					}
					int cha=(a[i+1]-(a[i+1]%d))-a[i];
					if(cha<=m){
						a[i]+=cha;
						m-=cha;
					}
					else{
						a[i]+=(m-(m%d)),m=m%d;
					}
				}
				else{
					if(i==n||m<=a[i+1]-a[i]){
						if((a[i]+m)%d==0) a[i]+=m-1,m=1;
						else a[i]+=m,m=0; 
					}
					else{
						if(a[i+1]%d==0) m-=a[i+1]-a[i]-1,a[i]=a[i+1]-1;
						else m-=a[i+1]-a[i],a[i]=a[i+1];
					}
				}
				if(m<0||(a[i]>a[i+1]&&i!=n)) y=0;
			}
		}
		if(y==0||m!=0) cout<<"No\n";
		else{
			for(int i=1;i<=n;i++) cout<<a[i]<<" ";
			cout<<"\n";
		}
	}
	return 0;
}

P1651 塔

差值 DP。
设选到了第 $i$ 个木块，左塔减右塔的值为 $j$ 时，左塔最高的高度为 $dp_{i,j}$。
就可以分类讨论 $a_i$ 是不放还是放在左塔还是放在右塔。
注意到 $j$ 的值是会小于零的，所以我们给 $j$ 整体加上 $500000$ 就可以了。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int n,ans;
int a[55],dp[N],dp1[N];
signed main(){
	memset(dp,128,sizeof dp);
	memset(dp1,128,sizeof dp1);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	dp1[500000]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<N;j++){
			dp[j]=max(dp[j],dp1[j]);
			if(j-a[i]>=0) dp[j]=max(dp[j],dp1[j-a[i]]+a[i]);
			if(j+a[i]<N) dp[j]=max(dp[j],dp1[j+a[i]]);
			if(j==500000) ans=max(ans,dp[j]);
		}
		for(int j=0;j<=N;j++){
			dp1[j]=dp[j];
		}
	}
	if(ans>0) cout<<ans;
	else cout<<-1;
	return 0;
}