牛客练习赛59
C 装备合成
题意：
作者：陆小萌
牛牛有{x}x件材料{a}a和{y}y件材料{b}b，用{2}2件材料{a}a和{3}3件材料{b}b可以合成一件装备，用{4}4件材料{a}a和{1}1件材料{b}b也可以合成一件装备。牛牛想要最大化合成的装备的数量，于是牛牛找来了你帮忙。
思路：1.线性规划 O(1)
这个高中知识裸题没啥好说的画个图求两直线交点，特判一下交点不在第一象限的时候取两直线和x轴、y轴的交点的最小值即可。
坑点：线性规划得到的最佳答案为浮点值，浮点运算精度可能出现问题，然后还要考虑下取整，所以可以求计算得到的值取整上下范围的一个值，这里取1即可，不过为了保险起见开大点开个10也是没问题的。
#include
using namespace std;
typedef long long ll;
typedef pairP;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const ll maxn = 1e6 + 5;
ll a,b,res;
void f(ll m){
for(ll i=m-1;i=0&&n>=0&&(2*i+4*n)<=a&&(3*i+n)>T;
while(T--){
res=0;
cin>>a>>b;
double x=(4.0*b-1.0*a)/10.0;
f(x);
f(0);
f(min(a/2,b/3));
cout<<res<<'\n';
}
return 0;
}
2.三分法
设m个第一种装备，n个第二种装备，我们需要固定一个元素,然后对另外一个元素取三分记录最大值设m个第一种装备，n个第二种装备，我们需要固定一个元素,然后对另外一个元素取三分记录最大值设m个第一种装备，n个第二种装备，我们需要固定一个元素,然后对另外一个元素取三分记录最大值需要找到n和m的关系式，n=min(x−2m4,y−3m)需要找到n和m的关系式，n=min(\frac{x-2m}{4},y-3m)需要找到n和m的关系式，n=min(4x−2m,y−3m)
#include
using namespace std;
typedef long long ll;
typedef pairP;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const ll maxn = 1e6 + 5;
ll x,y;
ll res;
ll check(ll m){
ll n=min((x-2*m)/4,y-3*m);
res=max(res,n+m);
cout<<"m="<<m<<" n="<<n<>T;
while(T--){
res=0;
cin>>x>>y;
ll L=0,R=min(x/2,y/3);
while(R-L>10){
ll m1=L+(R-L)/3;
ll m2=R-(R-L)/3;
if(check(m1)<check(m2)){
L=m1;
}else{
R=m2;
}
}
for(int i=L;i<=R;i++){
check(i);
}
cout<<res<<'\n';
}
return 0;
}
D 取石子游戏
题意：
有n个石子，小灰灰先取，每次将石子分为x和n-x,要求x*2<=n，n不断更新为剩下的石子数量。
最后谁不能取算输。
后手赢输出"XiaoQiao"，先手赢输出"XiaoHuiHui"。
博弈论
这里要注意先取的人有优势，除非是必输局，就是两堆都是必输的情况，不然若存在有一堆可以跳到后手赢的方案，则先手必胜。
| n | 赢家 |
|---|---|
| 1 | 后 |
| 2=1+1 ~ 3=1+2 | 先手 |
| 4=2+2 ~ 6=3+3 | 后手 |
| 7=3+4 ~ 13=6+7 | 先手 |
| 14=7+7 ~ 26=13+13 | 后手 |
| 27=13+14 ~ 53=26+27 | 先手 |
观察规律可得代码
代码：#include
using namespace std;
typedef long long ll;
const int N = 1e5+5;
ll T,n;
int main(){
cin>>T;
while(T--){
cin>>n;
ll x=3;
while(n>x)x=x*4+1;
if(n>x/2)puts("XiaoHuiHui");
else puts("XiaoQiao");
}
}
作者：陆小萌
