要有梦想，万一过了呢

A. Exciting Bets

题意简述

$T$ 组询问，每组询问给定 $a,b$ ，每次操作可以对 $a,b$ 同时加上 $1$ 或同时减去 $1$ ，求问通过这种操作可以使 $gcd(a,b)$ 最大为多少，以及达到这个最大值所需要的最小操作次数

若 $gcd(a,b)$ 可以为无穷大，则输出0 0

$T\le 5\cdot 10^3$

$0\le a,b\le 10^{18}$

解法

显然，当 $a=b$ 时，应用以上操作可以使 $gcd(a,b)$ 达到无穷大

当 $a\ne b$ 时，不妨 $a>b$ ，根据更相减损术， $gcd(a,b)=gcd(a-b,b)$

在对 $a,b$ 同时增减的过程中 $a-b$ 的值不变，而 $b$ 是可以改变的

又因为 $gcd(x,y)\le min\{x,y\}$ ，因此 $gcd(a,b)\le a-b$

而根据更相减损术的方法，我们只需要让 $b$ 成为 $a-b$ 的倍数即可令 $gcd(a,b)=a-b$

复杂度 $O(1)$

代码

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

int T;
ll a,b;

void Work()
{
    read(a),read(b);
    if(a<b)swap(a,b);
    ll c=a-b;
    if(c==0)
    {
        printf("0 0\n");
        return;
    }
    ll s=b/c;
    printf("%lld %lld\n",c,min(b-s*c,(s+1)*c-b));
}

int main()
{
    read(T);
    while(T--)
    {
        Work();
    }
    return 0;
}

B. Customising the Track

题意简述

$T$ 组询问，每组询问给定长度为 $n$ 的序列 $\{a_n\}$

每次操作可以选定任意一个 $a_i$ ，将其减去 $v\le a_i$ ，并使任意一个 $a_j+v(i\ne j)$

通过若干次这样的操作，最小化 $\sum_{i=1}^n\sum_{j=i+1}^n|a_i-a_j|$ ，输出这个最小值

解法

显然，我们只需要让所有的 $a_i$ 尽量接近即可，由于 $sum=\sum a_i$ 不变，所以只需要令 $a_i=\lfloor\frac{sum}{n}\rfloor$ 或 $\lceil\frac{sum}{n}\rceil$ ，使得 $\sum a_i$ 仍为 $sum$ 即可

那么答案即为 $(n-sum\mod n)\cdot (sum\mod n)$

即下取整的数的个数乘上取整的数的个数

复杂度 $O(n)$

代码

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const int maxn=200000+100;
int T;
int n;
ll a[maxn];

void Work()
{
    read(n);
    ll sum=0;
    for(int i=1;i<=n;++i)
    {
        read(a[i]);
        sum+=a[i];
    }
    ll plus=sum%n;
    printf("%lld\n",(n-plus)*plus);
}

int main()
{
    read(T);
    while(T--)
    {
        Work();
    }
    return 0;
}

C. Need for Pink Slips

我是伞兵

打比赛的时候明明留意到了这个问题的，复杂度算错了

题意简述

$T$ 组询问

有三个操作C M P，定义 $c,m,p$ 为选择对应操作的概率，以及一个参数 $v$

如果选定了操作P，则操作结束

否则，在选定了操作C或操作M之一后，被选定的操作对应的概率减少 $v$ ，如果该概率已经小于 $v$ ，那么它将变为 $0$ 。与此同时，减少的概率将被等量地平分加给剩下的其他有效操作的概率，使得总概率总为 $1$ 。

概率变为 $0$ 的操作将变成无效操作，它对应的概率在之后的操作中不会参与平分减少的概率

例如：

$(c,m,p)=(0.2,0.1,0.7),v=0.1$ ，选定操作M，使得 $(c,m,p)=(0.25,Invalid,0.75)$
再选择操作C，使得 $(c,m,p)=(0.15,Invalid,0.85)$

求操作次数的期望值

$T\le10$

$0\le c,m,p\le 1,c+m+p=1$

$0.1\le v\le 0.9$

精度误差 $\epsilon\le 10^{-6}$

解法

注意到 $v\ge 0.1$ ，因此操作次数最多为 $10$ 次

考虑深度优先搜索，由于一旦选定操作P，操作结束，因此每次的决策只有选择操作C和选择操作M，直到 $p=1$ 为止

使用深度优先搜索遍历每种情况，复杂度为 $O(2^{\frac{1}{v}})$

代码

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const double eps=1e-6;
int T;
double c,m,p,v;
double ans;

void DFS(double step,double c,double m,double p,double cur)
{
    ans+=step*cur*p;
    if(fabs(p-1)<eps)
        return;
    double dec;
    if(c>eps)
    {
        dec=min(c,v);
        if(m>eps)
            DFS(step+1,c-dec,m+dec/2,p+dec/2,cur*c);
        else
            DFS(step+1,c-dec,0,p+dec,cur*c);
    }
    if(m>eps)
    {
        dec=min(m,v);
        if(c>eps)
            DFS(step+1,c+dec/2,m-dec,p+dec/2,cur*m);
        else
            DFS(step+1,0,m-dec,p+dec,cur*m);
    }
}

void Work()
{
    scanf("%lf%lf%lf%lf",&c,&m,&p,&v);
    ans=0;
    DFS(1,c,m,p,1);
    printf("%.10f\n",ans);
}

int main()
{
    read(T);
    while(T--)
    {
        Work();
    }
    return 0;
}

Tips！

要有梦想！！！

这题写出来了不是能上大分？（

D1. RPD and Rap Sheet (Easy Version)

题意简述

这是一道交互题

定义 $a\bigoplus_K b$ 表示 $a,b$ 在 $K$ 进制下的不进位加法，显然当 $K=2$ 时， $\bigoplus_2$ 即为异或操作

$T$ 组询问

每组询问给定 $n,K$ ，要求通过不多于 $n$ 次尝试猜一个在区间 $[0,n-1]$ 内的整数密码 $x$

在每一次输出询问后，将通过标准输入流输入一个数 $r$ 。 $r=1$ 表示答案正确，进入下一组询问； $r=0$ 表示答案错误，同时 $x$ 将变为 $z$ ，满足 $x\bigoplus_K z=y$ ，其中 $y$ 是询问的数。

$T\le 10000$

$1\le n\le 2\cdot 10^5$

在简单版本中 $K=2$

解法

那就嗯猜就好了嘛，从 $0$ 一直猜到 $n-1$

但密码是一直在变的，所以我们要设法将错误查询对原始密码的影响抵消掉

（约定：以下 $\bigoplus$ 与 $\bigoplus_2$ 等价）

我们知道 $x \bigoplus x=0$ （异或自反性）

由于异或即二进制下的不进位加法，那么它也满足交换律和结合律

于是有 $x\bigoplus z=y\Rightarrow x\bigoplus y\bigoplus z \bigoplus y=z \bigoplus z \bigoplus y\Rightarrow x\bigoplus y =z$

一种简单的想法是，我们可以在每次错误查询后再使用同一个数字进行一次查询，这样就可以抵消掉错误操作的影响，但是这需要 $2n$ 次操作

考虑将抵消操作和查询操作同时进行，假设上次错误查询的数为 $y'$ ，查询前密码为 $x$ ，查询后为 $z$ ，现在想要尝试 $y$ 。

如果恰好 $y=x$ ，有

$z=x\bigoplus y'=y\bigoplus y'$

如果 $y\ne x$ ，在完成本次查询后，密码 $z'$ 满足

$z'=z\bigoplus y\bigoplus y'=x\bigoplus y'\bigoplus y\bigoplus y'=x\bigoplus y$

所以在查询时，只需要输出 $y\bigoplus y'$ 。假如 $y$ 与初始密码相等，那么 $y\bigoplus y'$ 就等于当前密码；假如 $y$ 与初始密码不相等，那么当前密码受 $y'$ 的影响也被抵消，仅受 $y$ 影响

代码

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

int T;
int n,K;

void Work()
{
    read(n),read(K);
    printf("0\n");
    fflush(stdout);
    int r;
    read(r);
    if(r==1)
        return;
    for(int i=1;i<n;++i)
    {
        printf("%d\n",i^(i-1));
        fflush(stdout);
        read(r);
        if(r==1)
            return;
    }
}

int main()
{
    read(T);
    while(T--)
    {
        Work();
    }
    return 0;
}