好久没敲代码了，连写D1这简单题脑子都转不过来唉，属实一段时间不碰直接成菜鸡了
只写了A/B/C/D1四题，体力也快跟不上了，还剩五十分钟不大想看题了
当作康复训练吧（逃
A - Exciting Bets
题意
给你两个数字(a,b)
每次你可以让两个数都(+1)或者(-1)，但不能出现负数
使得最终的(gcd(a,b))尽可能大，并且操作次数尽可能小
输出最大的(gcd(a,b))可能值，并且输出获得这个值的最小操作数
如果(gcd(a,b))的最大值是无限大，则输出“(0 0)”
特殊的，(gcd(x,0)=x)
思路
很明显只有当(a=b)成立时，(gcd(a,b))才会接近无限大
而对于(a eq b)的情况，(gcd)的最大值也就是(|a-b|)
对于最小的操作数，只需要让(a,b)都变成(|a-b|)的倍数即可
向下移动次数即(a\%(a-b))，向上移动次数即对除数取补，即((a-b)-a%(a-b))
两者取小即可
代码
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}
void solve()
{
ll a,b;
cin>>a>>b;
if(a>b)swap(a,b);
if(a==b)
cout<<"0 0
";
else
cout<<b-a<<' '<<min(a%(b-a),(b-a)-a%(b-a))<<'
';
}
int main()
{
closeSync;
multiCase
{
solve();
}
return 0;
}
B - Customising the Track
题意
给定一个长度为(n)的数组({a})
每次可以随意选择两个位置，让其中一个(-1)，另一个(+1)，操作次数不限
要求最终(sum_{i=1}^nsum_{j=i+1}^n|a_i-a_j|)最小，并求出这个最小值
思路
可得均分所有位置的值时，答案最小
求出总和(s)，与(n)取模得到无法平均分配的值的大小(d=s\%n)
那么选择(d)个位置均分这些值
则题目中公式的值也就是此时有多少对位置的值是不同的
值为(s/n)的位置有(n-d)个，值为(s/n+1)的位置有(d)个
答案即(d*(n-d))
代码
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}
void solve()
{
int n;
cin>>n;
ll s=0;
rep(i,1,n)
{
int d;
cin>>d;
s+=d;
}
s%=n;
cout<<s*(n-s)<<'
';
}
int main()
{
closeSync;
multiCase
{
solve();
}
return 0;
}
C - Need for Pink Slips
题意
有三个字母(C/M/P)，初始时每个字母被选中的次数分别为(c,m,p (c+m+p=1))
还有一个浮动指数(v (0.1le vle 0.9))
每次会根据概率随机抽取一个字母，规则如下：
- 如果抽到字母(P)，游戏结束
- 否则，根据抽到的那个字母所对应的概率(a)，与浮动指数(v)进行比对
- 如果(ale v)，则这个字母接下来抽到的概率变为(0)，且不再会受到后续操作的影响导致概率上升（变成不可用字母），其概率将被均匀分配给剩余的可用字母
- 如果(agt v)，则这个字母接下来抽到的概率将会减(v)（(a:=a-v)），被减去的概率将被均匀分配给剩余的可用字母
问随机进行抽取游戏，最终抽到的字母个数的期望值是多少
思路
发现(0.1le vle 0.9)，这个值的精度很粗略，并且抽到(P)就会结束游戏，每次平均分配概率都会给(P)分配到，所以可以直接(dfs)模拟一遍全过程，状态数不会太多
(dfs(c,m,p,len,curp))的传参分别表示当前抽到(C/M/P)的概率、已经抽到的字母数量、处理到当前状态的概率
注意题目中给定的条件，一旦某个字母变成不可用字母，其后进行的分配概率的操作将不会考虑它
那么直接模拟，假设当前抽到字母(C)，概率就是(curp*c)，(C)的概率变成(max(c-v,0))，而减去的部分平分给剩余的可用字母，继续搜索下去
抽到字母(M)的情况同(C)
假如抽到(P)，则不会再有新的子状态产生，此时概率也就是(curp*p)，加上(P)后字母个数为(len+1)，则对答案的贡献也就是((len+1)*curp*p)
代码
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define double long double
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-14;
const double PI=acos(-1.0);
const ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}
double v,r=0;
void dfs(double c,double m,double p,int len,double curp)
{
if(c>eps) //假设抽到了C
{
double d=max(c-v,(double)0.0); //c接下来的概率
if(m>eps) //假如M是可用字母，则概率平分给M和P
dfs(d,m+(c-d)/2,p+(c-d)/2,len+1,curp*c);
else //否则概率全部给P
dfs(d,m,p+(c-d),len+1,curp*c);
}
if(m>eps) //假设抽到了M，下同
{
double d=max(m-v,(double)0.0);
if(c>eps)
dfs(c+(m-d)/2,d,p+(m-d)/2,len+1,curp*m);
else
dfs(c,d,p+(m-d),len+1,curp*m);
}
//cout<<c<<' '<<m<<' '<<p<<' '<<len<<' '<<curp<<'
';
r+=p*(len+1)*curp; //假如抽到了P，直接计算对答案的贡献
}
void solve()
{
double c,m,p;
cin>>c>>m>>p>>v;
r=0;
dfs(c,m,p,0,1.0);
cout<<fixed<<setprecision(12)<<r<<'
';
}
int main()
{
closeSync;
multiCase
{
solve();
}
return 0;
}
D1 - RPD and Rap Sheet (Easy Version)
D1. RPD and Rap Sheet (Easy Version)
题意
交互题
初始时给定两个数(n,k)
在本Version中(k=2)恒定，此值无关紧要，下文直接以异或代替
要求猜测一个位于(0)到(n-1)之间的数(x)，最多只能猜(n)次
对于每次猜测的数字(y)：
- 假如(x=y)，系统输出(1)，表示猜测成功，结束本次猜测
- 否则，系统输出(0)，并且此时(x)的值将会变成(z)，并且(z)满足(xoplus z=y)
思路
(xoplus z=y)，即(xoplus zoplus x=yoplus x)，即(z=xoplus y)
即对于每次猜测，会将待猜测的值(x)与猜测的值(y)取二进制异或，形成新的(x)值
那么初始时先猜(0)，如果成功直接退出，失败的话继续接下来的操作
由于初始(x)的值保证在(0)到(n-1)之内，最多也只能猜(n)次，所以从某种意义上来说直接枚举一遍(0)到(n-1)之间的数即可
从第二次猜测开始，每次猜测将前一次猜测所造成的影响除去
根据(aoplus boplus b=a)，所以接下来枚举(i=1)到(n-1)，每次猜测的数为(ioplus (i-1))，就可以将(i-1)造成的影响删除，变为猜测数字(i)
代码
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}
void solve()
{
int n,k,r;
scanf("%d%d",&n,&k);
printf("0
"); //先猜0
fflush(stdout);
scanf("%d",&r);
if(r==1)
return;
repp(i,1,n) //枚举一遍总能猜到
{
printf("%d
",i^(i-1)); //其后每次注意去除前一次造成的影响即可
fflush(stdout);
scanf("%d",&r);
if(r==1)
break;
}
fflush(stdout);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
solve();
return 0;
}
D2/E 无
https://blog.csdn.net/qq_36394234/article/details/118561911