好！
A.Exciting Bets
给俩数，一步操作为让他们同时+1或者-1，问最少几步操作让他们最大公约数最大，且这个数是多少
注意到俩数差不变，最大公约数必定为两数之差，找到一个最小数让他们为该数的倍数即可，直接模一下 取加减的最小值
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include<map>
#include<vector>
#include<string>
#include<math.h>
#include<time.h>
#include<set>
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
ll T;
int main() {
cin.sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
ll a, b;
while (T--)
{
cin >> a >> b;
if (b > a)swap(a, b);
ll det = a - b;
ll k = 0;
if(det!=0)
k = b % det;
cout << det << ‘ ‘ << min(k, det - k)<<‘\n‘;
}
}
B.Customising the Track
给个数列a，为每个车道上车的数量，定义拥挤值是\(\sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} \lvert a_i-a_j\rvert\)然后可以随意移动每辆车，问拥挤值最小是多少
先把所有车辆平均分配，相同部分消了，最后就是0和1，随便排列都行，其实就是0的个数乘1的个数
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include<map>
#include<vector>
#include<string>
#include<math.h>
#include<time.h>
#include<set>
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
ll T;
ll n;
int main() {
cin.sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
while (T--)
{
cin >> n;
ll a;
ll sum = 0;
for (int i = 0; i < n; i++) {
cin >> a;
sum += a;
}
sum %= n;
cout << sum * (n-sum) << ‘\n‘;
}
}
C. Need for Pink Slips
给定c，m，p三种彩票和其初始的概率，以及一个波动系数v，如果抽中p游戏立刻结束
如果当轮抽中某个彩票，且其概率为a，如果a>v则a-=v，如果a<v则a归零
a减少的值会平均分配给剩余概率不为0的彩票中去
问游戏结束轮数的数学期望
写个深搜完事了。。。比赛犯懒题都没看
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include<map>
#include<vector>
#include<string>
#include<math.h>
#include<time.h>
#include<set>
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
ll T;
double v;
double check(double a) {
if (a < 1e-7)return 0;
else return a;
}
double solve(double c, double m, double p,double pre,ll n) {
double res = 0;
res += n * pre * p;
double prec = c;
double prem = m;
if (c) {
double cc = c, mm = m,pp=p,pree=pre;
pree *= cc;
cc -= v;
cc = check(cc);
if (mm) {
mm += (prec - cc) / 2.0;
pp += (prec - cc) / 2.0;
}
else pp += prec - cc;
res += solve(cc, mm, pp, pree, n + 1);
}
if (m) {
double cc = c, mm = m, pp = p, pree = pre;
pree *= mm;
mm -= v;
mm = check(mm);
if (cc) {
cc += (prem - mm) / 2.0;
pp += (prem - mm) / 2.0;
}
else pp += prem - mm;
res += solve(cc, mm, pp, pree, n + 1);
}
return res;
}
int main() {
cin.sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
while (T--)
{
double c, m, p;
cin >> c >> m >> p>>v;
double ans;
ans = solve(c, m, p, 1, 1);
printf("%.10f\n", ans);
}
}
D. RPD and Rap Sheet
定义一种新的k位异或：先把a和b变为k进制数，每位都变成（a+b）mod k
给一个数n 密码是0到n-1 的一个数， 有n次机会猜密码 但是猜错密码 密码改变
假设猜错时密码是x 猜的数为y 则密码变成z 且 x k异或 z = y
k是2的简单版本时 就是普通异或， 这时候有传递性 直接每次猜 i-1^i就完事了
k大于2时就没有这个性质
方法如下：
定义一种新的kxor 是(a-b)modK
答案猜错会变成y kxor x
然后又有(a kxor b)kxor(a kxor c)=c kxor b (b kxor a)kxor(c kxor a)=b kxor c
所以就有了新的传递性:
偶数 i kxor i-1
奇数 i-1 kxor i
然后答案会一路变成
x-> (0 kxor 1) kxor (0 kxor x)=x kxor 1 -> 2 kxor 1 kxor (x kxor 1)=2 kxor x ->2 kxor 3 kxor (2 kxor x)=x kxor 3.....
所以答案在i为偶数时是 x kxor i-1 奇数时是 i-1 kxor i
结果照着题解抄我都犯病了 啥时候能不忘记！ 和 &的优先级啊
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include<map>
#include<vector>
#include<string>
#include<math.h>
#include<time.h>
#include<set>
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
ll T;
ll n;
ll k;
ll check(ll a) {
ll tmp;
cout << a << endl;
cin >> tmp;
return tmp;
}
ll kxor(ll a, ll b) {
ll res = 0;
ll p = 1;
while (a>0||b>0)
{
ll m = a % k;
ll n = b % k;
a /= k;
b /= k;
ll tmp = (m - n + k) % k;
res = res+tmp * p;
p = p * k;
}
return res;
}
int main() {
cin.sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
while (T--)
{
cin >> n >> k;
for (int i = 0; i < n; i++) {
ll flag = 0;
if (i == 0)flag = check(0);
else if (!(i &1))flag = check(kxor(i, i - 1));
else flag = check(kxor(i - 1, i));
if (flag)break;
}
}
}