Codeforces Round 896 (Div.1 + Div.2) VP

发现问题，解决问题。

观前提示

笔者实力有限， 的是 且撒后只改到了 题，所以本题解也只有 的题解。

原比赛链接：https://codeforc.es/contest/1869

A. Make It Zero

题目简介

给出一个长度为 的序列 ，现在定义一次操作：

• 选择一个区间 ，计算 。
• 将 替换为 。

要求你在 次操作内将整个序列变为 ，并构造出方案。多测。。

数据范围：

恰当的签到题。

注意到 ，每次操作结束后 都会变成一个相同的数，所以如果 的话，我们再对 执行操作 就会全部变成 。

所以我们的第一步就是对 执行，此时 序列就会变成同一个值，这样就好操作得多了。

但是你发现如果 是奇数，那最后操作偶数区间会多出一个，但又想到 ，所以我们再对剩下的那一个数和旁边一个位置做一次操作，就会把旁边的 变成这个数，然后再对这个长度为 的区间做一次就行了。

时间复杂度 。

AC Code

// ----- Eternally question-----
// Problem: A. Make It Zero
// Contest: Codeforces - Codeforces Round 896 (Div. 2)
// URL: https://codeforces.com/contest/1869/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-09-27 20:15:05
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e2+10;
int Test,N,val[MAXN],pre[MAXN];
int K,Lst[10],Rst[10];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	while(Test--)
	{
		read(N);
		for(int i=1;i<=N;++i) read(val[i]),pre[i]=pre[i-1]^val[i];
		if(N%2==0)
		{
			K=2;write(K,'\n');
			write("1 ",N,'\n',"1 ",N,'\n');
		}
		else
		{
			K=4;write(K,'\n');
			printf("1 %d\n1 %d\n%d %d\n%d %d\n",N,N-1,N-1,N,N-1,N);
		}
	}
	return 0;
}
/*

*/

---

B. 2D Traveling

题目简介

在二维平面中有 个点，第 个点的坐标为 ，其两点间距离计算如下：

$$\mathrm{dist}(i,j)= \begin{cases} 0&,i\leq k,j\leq k\\ |x_i-x_j|+|y_i-y_j|&,\text{otherwise} \end{cases}$$

求第 个点到第 个点间的最短路径。多测。

数据范围：

考虑一个月票购买的方式，最短距离由两种情况构成：

• ；
• ，其中 ，所以 。

那我们处理出前 个点距离 最近的距离然后与直接距离相比较即可。

时间复杂度 。

AC Code

// ----- Eternally question-----
// Problem: B. 2D Traveling
// Contest: Codeforces - Codeforces Round 896 (Div. 2)
// URL: https://codeforces.com/contest/1869/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-09-27 20:21:19
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e5+10;
const ll INF=0x3f3f3f3f3f3f3f3f;
int Test,N,K,A,B;
struct Point
{ ll x,y; }a[MAXN];
ll ans;
inline ll getDist(int i,int j)
{ return std::abs(a[i].x-a[j].x)+std::abs(a[i].y-a[j].y); }
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	while(Test--)
	{
		read(N,K,A,B);
		for(int i=1;i<=N;++i) read(a[i].x,a[i].y);
		ans=getDist(A,B);
		ll ans1=INF,ans2=INF;
		if(A<=K) ans1=0;
		if(B<=K) ans2=0;
		for(int i=1;i<=K;++i)
		{
			checkMin(ans1,getDist(A,i));
			checkMin(ans2,getDist(B,i));
		}
		checkMin(ans,ans1+ans2);
		write(ans,'\n');
	}
	return 0;
}
/*

*/

---

C. Fill in the Matrix

题目简介

给定一个没有定值的 的矩阵，对于每一列，我们指定 表示 为 ，并定义整个矩阵的权值为 。

要求最大化 ，并构造出一组权值为 的矩阵。多测。

数据范围：

我们观察样例得知， 一定逼近 ，但无法准确判定，所以我们考虑首先构造。

让 尽可能大，那么 必须包含 ，这里我们钦定 。那么显然，第 列不能出现 且必须出现 ，所以我们先构造出半个矩阵：

$$\begin{bmatrix} ? & 0 & 1 & 2 & 3 & \cdots \\ ? & ? & 0 & 1 & 2 & \cdots \\ ? & ? & ? & 0 & 1 & \cdots \\ & & \vdots & & \ddots\\ \end{bmatrix}$$

然后你发现第一行除了 都填了，所以 。按照这个思路，我们将第 行视作第 行向右平移了一个单位：

$$\begin{bmatrix} m & 0 & 1 & 2 & 3 & \cdots \\ m-1 & m & 0 & 1 & 2 & \cdots \\ m-2 & m-1 & m & 0 & 1 & \cdots \\ & & \vdots & & \ddots\\ \end{bmatrix}$$

但这个平移操作是一个以 为模数的循环节，之后就会变成所有 ，但 了。所以考虑我们令 ，之后不再扩展，而是一视同仁。此时 。

但我们注意到可能会存在 的情况，这个时候连一次循环都跑不满，以 为例：

$$\begin{bmatrix} 6 & 0 & 1 & 2 & 3 & 4 & 5 \\ 5 & 6 & 0 & 1 & 2 & 3 & 4 \\ 4 & 5 & 6 & 0 & 1 & 2 & 3 \\ \end{bmatrix}$$

此时 ，。

但你发现这个时候的 甚至比上面精心构造的还要大点，所以我们甚至不需要管。

至于证明我还真不会，纯考场想的。时间复杂度 。哦可能要特判一下 或者 的情况。

AC Code

// ----- Eternally question-----
// Problem: C. Fill in the Matrix
// Contest: Codeforces - Codeforces Round 896 (Div. 2)
// URL: https://codeforces.com/contest/1869/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-09-27 20:28:39
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e5+10;
int Test,N,M;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	while(Test--)
	{
		read(N,M);
		if(N>=M)
		{
			if(M==1) puts("0");
			else write(std::min(N,M),'\n');
			for(int i=1;i<=M-1;++i,puts(""))
				for(int j=1;j<=M;++j) write((M-i+j-1+M)%M,' ');
			for(int i=M;i<=N;++i,puts(""))
				for(int j=1;j<=M;++j) write(j%M,' ');
		}
		else
		{
			write(std::min(N,M)+1,'\n');
			for(int i=1;i<=N;++i,puts(""))
				for(int j=1;j<=M;++j) write((M-i+j-1+M)%M,' ');
		}
	}
	return 0;
}
/*

*/

---

D. Candy Party

Easy Version Hard Version

题目简介

现在有 个人，每个人手中有一个数 ，现在，每一个人执行一次操作如下：

• 选择另外一个人（不能是自己），然后选择一个 ，执行 以及 ，相当于将自己 给第 个人。
• 需要注意的是 必须时刻满足。
• 每一个人必须给另外一个人，且每一个人必须且仅能从另外一个人接受一次 。

求最终是否能够让所有人的数相等。多测。

数据范围：

考虑到有很多个必须，所以我们发现所有操作结束后，每个人都会变成 的形式。

设目标数 ，显然 非整数时不成立，所以我们有 ，也就是 ，那么后者只会有不超过 中取值，我们暴力预处理。

然后我们记录一个操作的二元组为 ，那么显然， 次操作后所有 一定为 ，所有操作的 都必须被抵消。

所以每次操作我们视作 。最后判断是否全部为 即可。

时间复杂度 。

AC Code

// ----- Eternally question-----
// Problem: D1. Candy Party (Easy Version)
// Contest: Codeforces - Codeforces Round 896 (Div. 2)
// URL: https://codeforces.com/contest/1869/problem/D1
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-09-27 20:53:07
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
#define popcount(x) __builtin_popcountll(x)
using Pir=std::pair<int,int>;
#define fir first
#define sec second
#define Mkr std::make_pair
const int MAXN=2e5+10,MAXS=60;
const int S=40;
int Test,N,val[MAXN];
ll Sum,Popcnt[MAXS];
std::map<ll,Pir>Hash;
inline bool solve(ll tar)
{
	std::memset(Popcnt,0,sizeof(Popcnt));
	for(int i=1;i<=N;++i)
	{
		if(val[i]==tar) continue;
		ll nxt=val[i]-tar;
		if(Hash.find(nxt)==Hash.end()) return 0;
		auto p=Hash[nxt];
		++Popcnt[p.fir],--Popcnt[p.sec];
	}
	for(int i=0;i<=S;++i) if(Popcnt[i]) return 0;
	return 1;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	for(int i=0;i<=S;++i)
		for(int j=0;j<=S;++j)
		{
			if(i==j) continue;
			ll a=1ll<<i,b=1ll<<j;
			Hash[a-b]=Mkr(i,j);
		}
	while(Test--)
	{
		read(N),Sum=0;
		std::memset(Popcnt,0,sizeof(Popcnt));
		for(int i=1;i<=N;++i) read(val[i]),Sum+=val[i];
		if(Sum%N!=0){ puts("No");continue; }
		ll tar=Sum/N;bool flag=1;
		flag=solve(tar);
		puts(flag?"Yes":"No");
	}
	return 0;
}
/*

*/

题目简介

现在有 个人，每个人手中有一个数 ，现在，每一个人执行一次操作如下：

• 选择另外一个人（不能是自己），然后选择一个 ，执行 以及 ，相当于将自己 给第 个人。
• 需要注意的是 必须时刻满足。
• 每一个人最多给另外一个人一次，且每一个人最多从一个人接受一次 。

求最终是否能够让所有人的数相等。多测。

数据范围：

思路是从 扩展而来的。

考虑到每个人的操作并不是强制的，所以对于 的情况，原来有 ，现在多出了一种选择。

所有我们考虑一种合成大西瓜的形式，把每两个 合成为 个 ，合成结束后再算所有 是否为 。

时间复杂度和 一样。

AC Code

// ----- Eternally question-----
// Problem: D2. Candy Party (Hard Version)
// Contest: Codeforces - Codeforces Round 896 (Div. 2)
// URL: https://codeforces.com/contest/1869/problem/D2
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-09-27 21:53:52
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
#define popcount(x) __builtin_popcountll(x)
using Pir=std::pair<int,int>;
#define fir first
#define sec second
#define Mkr std::make_pair
const int MAXN=2e5+10,MAXS=60;
const int S=40;
int Test,N,val[MAXN];
ll Sum;
int Popcnt[MAXS],Add[MAXS],Del[MAXS];
std::map<ll,Pir>Hash;
inline bool solve(ll tar)
{
	std::memset(Popcnt,0,sizeof(Popcnt));
	std::memset(Add,0,sizeof(Add));
	std::memset(Del,0,sizeof(Del));
	for(int i=1;i<=N;++i)
	{
		if(val[i]==tar) continue;
		ll nxt=val[i]-tar;
		if(Hash.find(nxt)==Hash.end()) return 0;
		auto p=Hash[nxt];
		if(nxt<0) std::swap(p.fir,p.sec);
		if(popcount(std::abs(nxt))==1)
		{
			if(nxt>0) Add[p.sec]+=2;
			else Del[p.sec]+=2;
		}
		if(nxt<0) std::swap(p.fir,p.sec);
		++Popcnt[p.fir],--Popcnt[p.sec];
	}
	for(int i=0;i<=S;++i)
	{
		if(std::abs(Popcnt[i])&1) return 0;
		if(!Popcnt[i]) continue;
		else if(Popcnt[i]>0)
		{
			if(Del[i]<Popcnt[i]) return 0;
			Popcnt[i+1]+=Popcnt[i]>>1,Popcnt[i]=0;
		}
		else
		{
			if(Add[i]<-Popcnt[i]) return 0;
			Popcnt[i+1]+=Popcnt[i]>>1,Popcnt[i]=0;
		}
	}
	for(int i=0;i<=S;++i) if(Popcnt[i]) return 0;
	return 1;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	for(int i=0;i<=S;++i)
		for(int j=0;j<=S;++j)
		{
			if(i==j) continue;
			ll a=1ll<<i,b=1ll<<j;
			Hash[a-b]=Mkr(i,j);
		}
	while(Test--)
	{
		read(N),Sum=0;
		for(int i=1;i<=N;++i) read(val[i]),Sum+=val[i];
		if(Sum%N!=0){ puts("No");continue; }
		ll tar=Sum/N;bool flag=1;
		flag=solve(tar);
		puts(flag?"Yes":"No");
	}
	return 0;
}
/*

*/

---

E. Travel Plan

题目简介

给定一棵有 个结点的完全二叉树（编号从左往右），每个结点的权值为 ，有 ，记录权值序列 显然一共有 个。

定义两点间距离为两点间简单路径上的点权最大值，记为 ，定义一个权值序列的贡献为 。

求所有权值序列的贡献和。对 取模。多测。

数据范围：

可以先考虑 的情况怎么做。

我们可以钦定 表示以 为根的子树中保证 且其子树结点权值不超过 的所有路径权值和。然后你发现这就是个基于深度的状态，所以可以 做出来。

然后考虑一个结论，一棵完全二叉树可以分成 棵满二叉树，所以就可以 做了。

细节可能偏多，写 时递归加记忆化可能要好些点。

AC Code

// ----- Eternally question-----
// Problem: E. Travel Plan
// Contest: Codeforces - Codeforces Round 896 (Div. 2)
// URL: https://codeforc.es/contest/1869/problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-10-01 19:21:37
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using Pir=std::pair<ll,ll>;
#define fir first
#define sec second
#define Mkr std::make_pair
#define popcount(x) __builtin_popcountll(x)
#define ctz(x) __builtin_ctzll(x)
using Node=std::pair<ll,Pir>;
const int MAXN=70,MAXM=1e5+10;
const int Mod=998244353;
template<class T1,class T2>
inline void add(T1 &x,T2 y){ x=x+y>=Mod?x+y-Mod:x+y; }
const int S=64;
int Test,M,K;
ll res[MAXM],N,ans;
ll f[MAXN],g[MAXN],Dp[MAXN];
Node dpTree(ll x)
{
	// write(x,'\n');
	// if(x<0) return Mkr(0,Mkr(0,0));
 	if(!x) return Mkr(1,Mkr(0,0));
 	if(x==1) return Mkr(M,Mkr(K,K));
 	++x;
 	ll cx=ctz(x);
 	if(popcount(x)==1&&Dp[cx]) return Mkr(Dp[cx],Mkr(f[cx],g[cx]));
 	--x;
 	ll ri=1ll<<(S-__builtin_clzll(x));--ri;
 	ll lx=(ri-1)>>1,rx=lx,ls=ri-x,mid=(ri+1)>>2;
 	// write(x,' ',lx,' ',rx,' ',ls,' ',mid,' ',ri,'\n');
 	if(ls<=mid) rx-=ls;
 	else rx-=mid,lx-=ls-mid;
 	Node lp=dpTree(lx),rp=dpTree(rx),res;
 	res.fir=lp.fir*rp.fir%Mod;
 	res.sec.sec=(lp.sec.sec*rp.fir%Mod+rp.sec.sec*lp.fir%Mod+res.fir)%Mod*K%Mod;
 	res.fir=res.fir*M%Mod;
 	res.sec.fir=(lp.sec.sec*rp.sec.sec%Mod*K%Mod+res.sec.sec+
 					(lp.sec.fir*rp.fir%Mod+rp.sec.fir*lp.fir%Mod)%Mod*M%Mod)%Mod;
	++x;
	if(popcount(x)==1)
	{
		f[ctz(x)]=res.sec.fir,g[ctz(x)]=res.sec.sec;
		Dp[ctz(x)]=res.fir;
	}
	--x;
	return res;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);]
	read(Test);
	while(Test--)
	{
		read(N,M);
		ll ans=0;
		for(K=1;K<=M;++K)
		{
			std::memset(f,0,sizeof(f)),
			std::memset(g,0,sizeof(g));
			std::memset(Dp,0,sizeof(Dp));
			res[K]=dpTree(N).sec.fir;
		}
		for(K=M;K>=1;--K)
		{
			add(res[K],Mod-res[K-1]);
			add(ans,res[K]*K%Mod);
		}
		write(ans,'\n');
	}
	return 0;
}
/*

*/

---