牛客练习赛59

牛客练习赛59

题目链接点击就进去了

C题：合成装备，有两种合成装备的方法
牛牛有x件材料a和y件材料b，(法一：)用2件材料a和3件材料b可以合成一件装备，(法二：)用4件材料a和1件材料b也可以合成一件装备
假设合成，n件装备用法一合成，则法二最多生成min( (x-2n)/4,(y-3n) )件，枚举即可得出最佳方案，但枚举复杂度为1e5*1e9/2 肯定会被TLE ，所以，得想办法优化，它存在单调性极值所以，可以采用三分的方法来解决。
然后在三分范围内寻找答案，复杂度极大降低了。

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
	int t;
	cin>>t;
	int x,y;
	while(t--){
		cin>>x>>y;
		int l=0,r=min(x/2,y/3);
		while(r-l>10){
			int m1=l+(r-l)/3;
			int m2=r-(r-l)/3;
			if(m1+min((x-2*m1)/4,y-3*m1))>m2+min((x-2*m2)/4,y-3*m2))
				r=m2;
			else
				l=m1;
		}
		int ans=0;
		for(int i=l;i<=r;i++)
			ans=max(ans,i+min((x-2*i)/4,y-3*i));
		printf("%d\n",ans);
	}
	return 0;
}

D:

D题应该是个构造规律题吧，
观察输赢区间，即奇偶性就行了
1 1 输
2 3 赢
4 6 输
7 13 赢
14 26 输
观察可得为奇时输区间为前一个的两倍，为偶时输区间前部分为前部分两倍-1，后部分为前部分的两倍加1，然后构造出规律，写码即可

#include<bits/stdc++.h>
#define sc(x) scanf("%lld",&x);
#define pf printf
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define dep(i,e,s) for(int i=e;i>=s;i--)
using namespace std;
typedef long long int ll;
int t;
const ll maxn=1e18;
ll k;
ll b[1000],e[1000];
int main()
{
	//ios::sync_with_stido(0);
	//¼ÓËÙcin/cout
	cin>>t;
	b[1]=1;e[1]=1;
	b[2]=2;e[2]=3;
	int i=3;
	while(e[i-1]<=maxn){
		if(i&1){
			b[i]=b[i-1]*2;
			e[i]=e[i-1]*2;
		}
		else{
			b[i]=b[i-1]*2-1;
			e[i]=e[i-1]*2+1;
		}
		i++;
	}
	while(t--){
		cin>>k;
		for(i=1; ;i++){
			if(k>=b[i] && k<=e[i]){
				break;
			}
		}
		if(i&1)
			pf("XiaoQiao\n");
		else
			pf("XiaoHuiHui\n");
	}
	return 0;
}