[数据结构与算法]Codeforces Round #730 div.2 A-E题解

视频讲解：TBD

A. Exciting Bets

题目大意

给定整数 $a,b(0\le a,b\le 10^{18})$ ，可以对其修改任意次数，使得 $gcd(a,b)$ 最大。求修改后的 $gcd(a,b)$ 与最小修改次数。
每次修改时，可以将 $a,b$ 都增加 $1$ ，或减少 $1$ （只有当 $a,b>0$ 时才能减少）。
若 $gcd(a,b)$ 可以无穷大，则输出 “0 0” 。
当 $x\ge 0$ 时，认为 $gcd(x,0)=x$ 。

题解

若 $a=b$ ，则 $gcd(a,b)$ 可以无穷大。反之，最大的 $gcd(a,b)$ 为 $|a?b|$ 。
证明：
设所有操作后， $a,b$ 增加了 $x$ ，变为 $a+x,b+x$ ， $gcd(a+x,b+x)=g$ ，则
$$a+x=k_1?g$$

$$b+x=k_2?g$$

$$a?b=(k_1?k_2)g$$

可得 $g$ 是 $a?b$ 的因子，最大就是 $|a?b|$ ，证毕。

若 $x\ge 0$ ，则 $x=?\frac{a+g?1}{g}??g?a$ ；
若 $x<0$ ，则 $|x|=a??\frac{a}{g}??g$ ；
最小步数为其中的较小值。

参考代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main()
{
	ll T,a,b,g,ad1,ad2;
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld%lld",&a,&b);
		if(a==b)
		{
			printf("0 0\n");
			continue;
		}
		g=abs(a-b);
		ad1=(a+g-1)/g*g-a;
		ad2=a-a/g*g;
		printf("%lld %lld\n",g,min(ad1,ad2));
	}
}

B. Customising the Track

题目大意

有 $n(1\le n\le 2?10^5)$ 个轨道，编号从 $1$ 到 $n$ 。第 $i$ 个轨道上有 $a_i$ 辆车。
你可以执行任意次修改，每次修改可以将一辆车移动到另一个轨道上。
求修改后的最小 ${\sum }_{i=1}^n{\sum }_{j==i+1}^n|a_i?a_j|$ 。

题解

观察表达式，易得 $a_i$ 尽可能平均分布时最优。
但 $sum={\sum }_{i=1}^n{a}_i$ 不一定能等分为 $n$ 份。设每个轨道上有 $ave=?\frac{sum}{n}?$ 辆车，则还剩余 $last=sum?ave?n$ 辆车。
将 $last$ 辆车放置在任意轨道中，每个轨道放置一辆，则有 $last$ 个轨道有 $ave+1$ 辆车，有 $n?last$ 个轨道有 $ave$ 辆车。
答案 $ans=last?(n?last)$

参考代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main()
{
	ll T,n,x,sum,i,last,ans;
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld",&n);
		sum=0;
		for(i=1;i<=n;i++)
		{
			scanf("%lld",&x);
			sum+=x;
		}
		last=sum-sum/n*n;
		ans=last*(n-last);
		printf("%lld\n",ans);
	}
}

C. Need for Pink Slips

题目大意

有三种奖品，分别简称为C奖品，M奖品，P奖品。每次获取奖品时，会随机从中获得一项，概率分别为 $c,m,p(0<c,m,p<1,c+m+p=1)$ 。
其中P奖品是目标奖品，玩家会不断抽奖，直到抽到了P奖品。
抽奖有软保底机制。每次抽奖后，会根据波动参数 $v(0.1\le v\le 0.9)$ 调整三种奖品的获得概率：

• 若抽到了P奖品，则直接结束。
• 否则。假设抽到的奖品的当前概率为 $a$，则：
• • 若 $a\le v$ ，则将该奖品从奖池中删除，今后不会再抽到该奖品，即获奖概率调整为 $0$ 。降低的获奖概率，将平分到奖池中的其他奖品上；
• • 若 $a>v$ ，则将该奖品的获奖概率减少 $v$ 。降低的获奖概率，将平分到奖池中的其他奖品上；

求抽中P奖品的抽奖次数期望。

题解

设 $f(c,m,p)$ 表示当前获奖概率分别为 $c,m,p$ 时的抽奖次数期望，那么根据题意，可以写出其递归方程式（详见参考代码）。
因为 $v\ge 0.1$ ，所以递归层数最多为 $d=11$ ，时间复杂度为 $O(2^d)$ ，在时限内，因此直接暴力模拟即可。
由于是浮点数运算，需要额外注意精度问题。

参考代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const double eps=1e-10;

double dfs(double c,double m,double p,double v)
{
	double newc,ret=1;
	for(int i=0;i<2;i++,swap(c,m))
	{
		if(c<eps)
			continue;
		newc=max(0.0,c-v);
		if(m<eps)
			ret+=c*dfs(newc,m,p+newc,v);
		else
			ret+=c*dfs(newc,m+(c-newc)/2,p+(c-newc)/2,v);
	}
	return ret;
}

int main()
{
	int T;
	double c,m,p,v;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%lf%lf%lf%lf",&c,&m,&p,&v);
		printf("%.10f\n",dfs(c,m,p,v));
	}
}

D1+D2. RPD and Rap Sheet

题目大意

定义 $a{\oplus }_{k}b$ 表示整数 $a$ 与 $b$ 的在 $k$ 进制下的不进位加法。特别的，当 $k=2$ 时，这一操作可以称为位运算的异或。
给定整数 $n(1\le n\le 2?10^5)$ 和 $k(2\le k\le 100)$ ，现在有一个隐藏的整数 $x(0\le x\le n?1)$ ，你需要在最多 $n$ 次交互内，猜出这个整数。
猜测时，输出猜测的整数 $y(0\le y\le 2?10^7)$ ，系统会视情况返回不同的整数 $r$ ：

• 若 $x=y$ ，则 $r=1$ ；
• 若 $ x \neq y$ ，则 $r=0$ ，且 $x$ 会变成 $z$ ，满足 $x{\oplus }_{k}z=y$ ；

对于 Easy Version， $k=2$ ；
对于 Hard Version， $2\le k\le 100$ ；

题解

设 $a{?}_{k}b$ 表示 $k$ 进制下不退位的 $a?b$ ，其与 ${\oplus }_k$ 都可以通过手写加减法的形式实现。
那么如果猜测错误后， $x$ 变为 $z$ ，则可以表示为 $z=y{?}_{k}x$ 。
设第 $i$ 次猜测的输出为 $y_i$ ，猜测后的隐藏数为 $an{s}_i$ ，则具有以下式子：
$$an{s}_i=y_i{?}_{k}an{s}_{i?1}$$

初始 $an{s}_0=x$ ，可以得到通项式：
$$an{s}_i=y_i{?}_k(y_{i?1}{?}_k(y_{i?2}{?}_k...{?}_{k}x))$$

$$an{s}_i=\{\begin{array}{ll}{y}_i{?}_k{y}_{i?1}{\oplus }_k{y}_{i?2}?...{?}_{k}x& x\%2=1\\ y_i{?}_k{y}_{i?1}{\oplus }_k{y}_{i?2}?...{\oplus }_{k}x& x\%2=0\end{array}$$

因此可以在 $[0,n?1]$ 范围内枚举 $x$ ，根据历史 $y_i$ ，求得当前应该询问的数 $y_i=an{s}_{i?1}$ 。

当 $x$ 逐个从 $0$ 枚举到 $n?1$ 进行询问时，即 $y_{i+1}$ 为 $x=i$ 时的 $an{s}_i$ ，上式也可以化简为：
$$y_{i+1}=an{s}_i=?\begin{array}{ll}0& i=0\\ (i?1){?}_{k}i& i\%2=1\\ i?(i?1)& i\%2=0\end{array}$$

就代码实现难度而言。是否进行化简区别不是特别大。

对于 Easy Version ， ${\oplus }_2$ 与 ${?}_2$ 都可以用异或进行计算。
对于 Hard Version ， ${\oplus }_k$ 与 ${?}_k$ 需要手写不进位加法与不退位减法。

参考代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int k;

int addk(int a,int b)
{
	int base,aw,bw,ret=0;
	for(base=1;base<=max(a,b);base*=k)
	{
		aw=a/base%k;
		bw=b/base%k;
		ret+=(aw+bw)%k*base;
	} 
	return ret;
}

int subk(int a,int b)
{
	int base,aw,bw,ret=0;
	for(base=1;base<=max(a,b);base*=k)
	{
		aw=a/base%k;
		bw=b/base%k;
		ret+=(aw-bw+k)%k*base;
	} 
	return ret;
}

int main()
{
	int T,n,y,i,r;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&k);
		for(i=0;i<n;i++)
		{
			if(i==0)
				y=0;
			else if(i&1)
				y=subk(i-1,i);
			else
				y=subk(i,i-1);
			printf("%d\n",y);
			fflush(stdout);
			scanf("%d",&r);
			if(r==1)
				break;
		}
	}
}

E. The Final Pursuit

题目大意

定义简单 $n$ 维超立方体可以表示为一个无向无权图，其采用以下递归方式构建：

• 获取两个简单 $n?1$ 维的超立方体，其中一个的节点编号是从 $0$ 到 $2^{n?1}?1$ 另一个的节点编号是从 $2^{n?1}$ 到 $2^n?1$ 。（简单 $0$ 维超立方体是一个点）
• 对于 $0\le i<2^{n?1}$ 中的每一个整数 $i$ ，在节点 $i$ 和节点 $i+2^{n?1}$ 之间连边。

定义置换 $n$ 维超立方体由对简单 $n$ 维超立方体的节点按任意方式重新排列得到。
置换 $n$ 维超立方体除了节点编号不同外，其结构和简单 $n$ 维超立方体相同，都具有以下性质：

• 有 $2^n$ 个节点；
• 有 $n?2^{n?1}$ 条边；
• 每个节点有 $n$ 条边；
• 没有自环或重边；

置换 $n$ 维超立方体可以用排列 $P$ 对简单 $n$ 维超立方体的节点编号置换后得到。
现在给定用无向图表示的置换 $n(1\le n\le 16)$ 维超立方体，求排列 $P$ ，并对每个节点按以下方式染色：

• 共有 $n$ 种不同的颜色，编号为 $0$ 到 $n?1$ 。对于满足 $0\le u<2^n$ 的每个节点 $u$ 和每个满足 $0\le c<n$ 的每个颜色 $c$ ，至少有一个顶点 $v$ 与 $u$ 相邻，且颜色为 $c$ 。

题解

这个问题包含两个子问题，一个是求置换 $P$ ，另一个是顶点染色。

求置换 P

根据简单 $n$ 维超立方体的定义，我们可以得到推论：

1. 当且仅当两个节点的编号只相差一个二进制位时，它们才有连边。
2. 若两个节点 $a,b$ 的编号相差两个二进制位，则它们在图的距离为 $2$ ，且恰好有 $2$ 个节点位于 $a,b$ 之间。

不妨初始设 $p_0=0$ ，对于 $0$ 号节点的每个相邻节点，均可视为新维度的拓展，标记其简单编号为 $1,2,4,...,2^{n?1}$ 。具体哪个节点对应哪个编号均可。

接下来 $i$ 从小到大贪心求解 $p_i$ 。

• 若 $i$ 是 $2^k$ ，则其在标记 $0$ 号节点的相邻节点时已被标记过。
• 否则由于推论 $2$ ，必定可以构造两个简单编号 $b1,b2(b1,b2<i)$ ，满足其与简单节点 $i$ 距离为 $1$ ，他们之间的距离为 $2$ 。这样，只需要在输入图上寻找与 $p_{b_1}$ 和 $p_{b_2}$ 都相邻且距离为 $1$ 的点，标记其原始节点为 $i$ 即可。

寻找与 $p_{b_1}$ 和 $p_{b_2}$ 都相邻且距离为 $1$ 的点时，可以枚举 $p_{b_1}$ 的相邻点集，用二分或 set 在 $p_{b_2}$ 的相邻点集中快速检查是否存在。

顶点染色

关于顶点染色部分，推荐参考 3Blue1Brown 的 不可能的棋盘谜题 问题介绍与 Stand-up Maths 的解法 。
具体证明不再赘述，这里给出结论：

• 只有当 $n$ 为 $2$ 的整数次幂时才有解；
• 简单 $n$ 维超立方体上，一种最基础的构造方式是 $u$ 的相邻 $c$ 颜色节点的编号是 $u\oplus c$ ；

根据以上结论，我们可以尝试如下构造节点颜色：

• 设节点编号 $v$ 用二进制表示为 $b_{n?1}{b}_{n?2}...b_0$ ，那么其节点颜色为 ${\oplus }_{i=0}^{n?1}i?b_i$ 。

合理性证明：

• 对于一个节点 $u=b_{n?1}{b}_{n?2}...b_0$ 来说，其颜色为 $c={\oplus }_{i=0}^{n?1}i?b_i$ ；
• $u$ 的相邻点集可以表示为 { u ⊕ 2 0 , u ⊕ 2 1 . . . u ⊕ 2 n ? 1 } \{u\oplus 2^0,u\oplus 2^1...u\oplus 2^{n-1}\} {u⊕20,u⊕21...u⊕2n?1} ，对应的颜色集为 { c ⊕ 0 , c ⊕ 1... c ⊕ ( n ? 1 ) } \{c \oplus 0, c \oplus 1...c \oplus (n-1)\} {c⊕0,c⊕1...c⊕(n?1)} ，恰好为 $n$ 种不同颜色。

参考代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int MAXN=1<<17;
vector<int> e[MAXN];
set<int> st[MAXN];
int p[MAXN],rp[MAXN],c[MAXN];

int main()
{
	int T,n,vNum,eNum,i,j,x,y,v,b1,b2;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		vNum=1<<n;
		eNum=n<<(n-1);
		for(i=0;i<vNum;i++)
		{
			e[i].clear();
			st[i].clear();
			p[i]=rp[i]=-1;
		}
		for(i=0;i<eNum;i++)
		{
			scanf("%d%d",&x,&y);
			e[x].push_back(y);
			e[y].push_back(x);
			st[x].insert(y);
			st[y].insert(x);
		}
		p[0]=rp[0]=0;
		x=1;
		for(i=0;i<e[0].size();i++)
		{
			y=e[0][i];
			p[x]=y;
			rp[y]=x;
			x<<=1;
		}
		for(i=1;i<vNum;i++)
		{
			if(i==(i&-i))
				continue;
			b1=i^(i&-i);
			b2=i^(b1&-b1);
			for(j=0;j<e[p[b2]].size();j++)
			{
				v=e[p[b2]][j];
				if(rp[v]==-1&&st[p[b1]].count(v))
				{
					p[i]=v;
					rp[v]=i;
				}
			}
		}
		for(i=0;i<vNum;i++)
			printf("%d ",p[i]);
		puts("");
		if(n!=(n&-n))
		{
			printf("-1\n");
			continue;
		}
		for(i=0;i<vNum;i++)
		{
			c[i]=0;
			for(j=0;j<n;j++)
			{
				if(i&(1<<j))
					c[i]^=j;
			}
		}
		for(i=0;i<vNum;i++)
			printf("%d ",c[rp[i]]);
		puts("");
	}
}