10.7 div2复现赛

2025年10月7日 ooliver OI

10.7 div2复现赛

P14178 「FAOI-R8」Jueves

可以发现一些性质：

当 $s = t$ 时，显然答案为 0
否则，最短路一定是连接 $s$ 与 $t$ 的那条边，因为 $(a_{u} x o r a_{v} ) + (a_{u} o r a_{v} ) + (a_{u} a n d a_{v} ) [PARSE ERROR: Ampersand] g t; a_{u}$ 。

所以代码非常简单：

#include
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>a[i];
		if(s==t) cout

`#include
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>a[i];
		if(s==t) cout0
		else couta[s]^a[t])+(a[s]|a[t])+(a[s]&a[t])
	}
	return 0;
}`

P14179 「FAOI-R8」喵了个喵 V

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

#include
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>b[i],a[i]=0;;
		for(int i=1;i0){
			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(chaa[i+1]&&i!=n)) y=0;
			}
		}
		if(y==0||m!=0) cout

`#include
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>b[i],a[i]=0;;
		for(int i=1;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(m0) y=0;
			}
			else{
				if(a[i]%d!=0){
					m-=a[i];
					continue;
				} 
				a[i]++,m-=a[i];
				if(m0) 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
						a[i]+=cha;
						m-=cha;
					}
					else{
						a[i]+=(m-(m%d)),m=m%d;
					}
				}
				else{
					if(i==n||ma[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(m0||(a[i]>a[i+1]&&i!=n)) y=0;
			}
		}
		if(y==0||m!=0) cout"No\n";
		else{
			for(int i=1;ia[i]" ";
			cout"\n";
		}
	}
	return 0;
}`

P1651 塔

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

#include
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>a[i];
	dp1[500000]=0;
	for(int i=1;i=0) dp[j]=max(dp[j],dp1[j-a[i]]+a[i]);
			if(j+a[i]0) cout

`#include
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>a[i];
	dp1[500000]=0;
	for(int i=1;i
		for(int j=0;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]dp[j]=max(dp[j],dp1[j+a[i]]);
			if(j==500000) ans=max(ans,dp[j]);
		}
		for(int j=0;j
			dp1[j]=dp[j];
		}
	}
	if(ans>0) cout
	else cout1;
	return 0;
}`