Codeforces Round #730 (Div. 2) 题解

2024-02-27 15:56:39

Codeforces Round #730 (Div. 2) 题解

Problem A Exciting Bets

本题有$t$组数据。

给出两个数$a,b$，进行一次操作可以同时将两个数增加或减少$1$，设经过$k$次操作后的两个数为$a',b'$。

求出让$gcd(a',b')$最大值，并求出此最大值条件下最下操作次数$k$。

注意：如果最大值可以无限大，请输出$"0\ 0 "$

对于$100%$数据，$1 \leq t \leq 5 \times 10^3,0 \leq a,b \leq 10^{18}$。

当且仅当$a=b$时，最大值可以无限大，输出$"0\ 0 "$。

下面证明，本题的最大值为$|a-b|$,不妨设$0 \leq a\leq b \leq 10^{18}$:

$\max_d \{ gcd(a\pm d,b\pm d)\}=\max_d \{ gcd(b-a,a\pm d)\}=b-a$。
当且仅当$a\pm d=k(b-a),k\in N$时成立。

所以$|d|_{min}=\min\{a \% (b-a),(b-a)-a\%(b-a)\}$

时间复杂度为$O(t)$

# include <bits/stdc++.h>
# define int long long
using namespace std;
signed main()
{
	int t; cin>>t;
	for (int i=1;i<=t;i++) {
		int a,b; scanf("%lld%lld",&a,&b);
		if (a==b) {printf("0 0\n"); continue;}
		if (a>b) swap(a,b);
		printf("%lld %lld\n",b-a,min(b-a-a%(b-a),a%(b-a)));
	}
	return 0;
}

Problem B Customising the Track

本题有$t$组数据。

初始有$n$个元素的数组$a_n$，可以任意分配数字，但必须保证新数组各元素和与原数组各元素的和相等，使得$\sum_{i=1}^{n}\sum_{j=i+1}^n |a_i-a_j|$最小。求出该最小值。

对于$100%$数据，$1 \leq t \leq 10^4,0 \leq a_i \leq 10^{9},1 \leq n,\sum n \leq 2\times 10^5$。

最优情况下，数组会变为$(\sum_{i-1}^{n} a_i) \% n$个$\lfloor \frac{\sum_{i-1}^{n} a_i}{n} \rfloor +1$，$n-(\sum_{i-1}^{n} a_i) \% n$个$\lfloor \frac{\sum_{i-1}^{n} a_i}{n} \rfloor $组成的数组。

此时有最小值：$(\sum_{i-1}^{n} a_i) \% n \times (n-(\sum_{i-1}^{n} a_i))$。

时间复杂度为$O(\sum n + t)$

# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N=2e5+10;
int n,a[N];
signed main()
{
	int T; scanf("%lld",&T);
	while (T--){
		int n; scanf("%lld",&n);
		int sum=0;
		for (int i=1;i<=n;i++) {
			int t; scanf("%lld",&t);
			sum+=t;
		}
		sum=sum%n;
		printf("%lld\n",sum*(n-sum));	
	}
	return 0;
}

Problem C Need for Pink Slips

本题有$t$组数据。

有编号为$1,2,3$的三张卡片，初始摸到的概率分别为$c,m,p$，给定一个参数$v$。

若摸到编号为$3$的卡片则停止，否则设摸到卡片当前概率为$a$。

若$a\leq v$则将概率$a$平均分给剩下的卡片，并将该卡片从卡池中拿走。

若$a>v$则将从该卡片中抽取的概率$v$，平均分给剩下的卡片。

求摸到卡片$3$的次数的期望值，精确到$10^{-6}$。

对于$100\%$的数据，$1 \leq t \leq 10,0 < c,m,p < 1,c+m+p=1,0.1 \leq v \leq 0.9$ 。

注意到本题中，$0.1\leq v \leq 0.9$，说明最多操作的次数是很有限的。

结合本题的概率期望模型，可以采用在概率树上$dfs$解决，回溯时统计答案。

细节方面，注意$a\leq v$的判定并将应当抽出卡池的卡片抽走，防止可能造成的精度误差。

时间复杂度为$O(2^k)$

# include <bits/stdc++.h>
using namespace std;
const double eps=1e-12;
double c,m,p,v,ans;
void dfs(int dep,double cc,double mm,double pp,double pel,bool fcc,bool fmm) {
	if (abs(cc)<eps) fcc=false;
	if (abs(mm)<eps) fmm=false;
	if (fcc) {
		if (cc<=v) {
			if (fmm) dfs(dep+1,0,mm+cc/2.0,pp+cc/2.0,pel*cc,0,fmm);
			else dfs(dep+1,0,0,pp+cc,pel*cc,0,0);
		}
		else {
			if (fmm) dfs(dep+1,cc-v,mm+v/2.0,pp+v/2.0,pel*cc,fcc,fmm);
			else dfs(dep+1,cc-v,0,pp+v,pel*cc,fcc,0);
		}
	}
	if (fmm) {
		if (mm<=v) {
			if (fcc) dfs(dep+1,cc+mm/2.0,0,pp+mm/2.0,pel*mm,fcc,0);
			else dfs(dep+1,0,0,pp+mm,pel*mm,0,0);
		}
		else {
			if (fcc) dfs(dep+1,cc+v/2.0,mm-v,pp+v/2.0,pel*mm,fcc,fmm);
			else dfs(dep+1,0,mm-v,pp+v,pel*mm,fcc,fmm);
		}
	}
	ans=ans+pp*dep*pel;
}
int main()
{
	int T; scanf("%d",&T);
	while (T--) {
		ans=0;
		cin>>c>>m>>p>>v;
		dfs(1,c,m,p,1.0,1,1);
		printf("%.9lf\n",ans); 
	}

	return 0;
}

Problem D RPD and Rap Sheet

本题为交互题，有$t$组数据。

定义对$k$进制数运算符 $A\oplus_{k} B = C$,使得每个$k$进制位$i$满足$C_i = (A_i+B_i) \% k$。

计算机会给出一个自适应密码，初始为$x$，要求猜出当前密码。

设当前密码为$a$,输入计算机猜测的密码为$b$。

若当前猜对，则返回$1$，本次处理结束。

若当前猜错，则返回$0$，自适应密码将更改为$c$，并满足$a \oplus_{k}c = b$。

要求在$n$次尝试之内猜出密码，并提交给计算机。

对于$100\%$的数据， $1 \leq t \leq 10^4,1 \leq n,\sum n \leq 2\times 10^5,2 \leq k \leq 100$。

本题有$Easy \ Version$，当且仅当$k=2$时。

$k=2$时，$\oplus_{k=2} \Leftrightarrow \oplus$，考虑性质$a \oplus b=c \Leftrightarrow a \oplus c = b$。（两边同时亦或上$a$得证）

设第$i$个询问输入到计算机中的数字为$q_i$，需要满足当$i-1$是初始密码时，$i$是当前密码。

$q_1=0.$
$q_i=(i-2) \oplus(i-1) , i\geq 2.$

当$i-1$为初始密码时，当前密码为$(i-1)\oplus 0 \oplus(0 \oplus1)...(i-3)\oplus(i-2) = (i-1)\oplus(i-2)=q_i$

由于初始密码为$[0,n-1]$中一个数字，则可以在$n$次询问之内解决问题。

# include <bits/stdc++.h>
using namespace std;
int q(int x) {
	if (x==1) return 0;
	else return (x-1)^(x-2);
}
void fun(int n) {
	int s=0;
	for (int i=1;i<=n;i++) {
		printf("%d\n",q(i));fflush(stdout);
		int r; scanf("%d",&r); 
		if (r==1) return;
	}
}
int main()
{
	int T; scanf("%d",&T);
	while (T--) {
		int n,k; scanf("%d%d",&n,&k);
		fun(n);	
	}
	return 0;
}

$2 \leq k \leq 100$时，考虑更一般情况。$a \oplus_{k}c = b$ 若已知$k$进制数$a,b$，尝试求出$c$。

$A\oplus_{k} C = B$,使得每个$k$进制位$i$满足$B_i = (A_i+C_i) \% k$,则$C_i = (A_i-B_i) \% k$。

定义对$k$进制数运算符 $A\odot_{k} B = C$,使得每个$k$进制位$i$满足$C_i = (A_i-B_i) \% k$。

两个引理：

引理1：$(a \odot_k b)\odot_k(a \odot_k c)=c \odot_k b$
引理2：$(b \odot_k a)\odot_k(c \odot_k a)=b \odot_k c$

构造$q_i$函数：

$q_1=0.$
$q_i=(i-2)\odot_k(i-1),i \ is \ even.$
$q_i=(i-1) \odot_k (i-2), i \ is \ odd.$

当$x$为初始密码时，当前密码：

$x \odot_k (i-1) , i \ is \ even.$
$(i-1) \odot_k x , i \ is \ odd.$

证明：

$i \ is \ even.$

假设当前密码为$x \odot_k (i-1) , i \ is \ even.$成立，则$i+1$时，

密码为:$(i \odot_k i-1)\odot_k(x \odot_k i-1)=i \odot_k x$。
$i \ is \ odd.$

假设当前密码为$(i-1) \odot_k x , i \ is \ odd.$成立，则$i+1$时，

密码为:$((i-1) \odot_k i)\odot_k((i-1) \odot_k x)=x \odot_k i$。

所以，当$i=x$时，当前答案为：

$x \odot_k (x-1) , x \ is \ even.$
$(x-1) \odot_k x , x \ is \ odd.$

等于$q_{x+1}$。

# include <bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=22;
int a[M],b[M],c[M];
int k;
int f(int x,int y) {
	int z=0,p=1;
	while (x>0||y>0) {
		int a=x%k; x=x/k;
		int b=y%k; y=y/k;
		int c=(a-b+k)%k;
		z=z+p*c;
		p=p*k;
	}
	return z;
}
int q(int i) {
	if (i==1) return 0;
	if (i%2==0) return f(i-2,i-1);
	else return f(i-1,i-2);
}
void fun(int n) {
	for (int i=1;i<=n;i++) {
		int r; printf("%d\n",q(i)); fflush(stdout);
		scanf("%d",&r); if (r==1) return;
	}
}
int main()
{
	int T; scanf("%d",&T);
	while (T--) {
		int n; scanf("%d%d",&n,&k);
		fun(n);
	}
	return 0;
}

码农公寓

Codeforces Round #730 (Div. 2) 题解

Problem A Exciting Bets

Problem B Customising the Track

Problem C Need for Pink Slips

Problem D RPD and Rap Sheet

相关文章