https://ac.nowcoder.com/acm/contest/4743

C. 装备合成

 

题意：牛牛有x件材料a和y件材料b，用2件材料a和3件材料b可以合成一件装备，用4件材料a和1件材料b也可以合成一件装备。牛牛想要最大化合成的装备的数量，于是牛牛找来了你帮忙。

三分合成多少第一件装备。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int T;
ll a, b;
ll ck(ll x) {
	ll ta = a - 2 * x, tb = b - 3 * x;
	return x + max(0ll, min(ta / 4, tb));
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%lld%lld", &a, &b);
		ll L = 0, R = min(a / 2, b / 3);
		while (R - L > 2) {
			ll m1 = (L + R) / 2, m2 = (R + m1) / 2;
			if (ck(m1) > ck(m2))R = m2;
			else L = m1;
		}
		ll ans = 0;
		while (L <= R)ans = max(ans, ck(L++));
		printf("%lld\n", ans);
	}
	return 0;
}

 

D. 取石子游戏

 

题意：有一堆石子，假设当前石子数量为 kk，如果 k≥2k\geq2，那么将石子分为 ⌊k/2⌋\lfloor k/2 \rfloor和 k−⌊k/2⌋k-\lfloor k/2 \rfloor 两堆，然后选择其中任意一堆石子取走。否则当前操作的人输。

打表找规律可以发现每次都是一个区间内都输或者都赢，而这个区间的变化一定和2有关，那就猜结论好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int T;
int main() {
	scanf("%d", &T);
	while (T--) {
		ll x;
		scanf("%lld", &x);
		if (x == 1) { puts("XiaoQiao"); continue; }
		bool flg = 0;
		ll L = 2, R = 3;
		while (R < x) {
			flg ^= 1;
			L = R + 1;
			if (flg)R = L * 2 - 2;
			else R = L * 2 - 1;
		}
		puts(flg ? "XiaoQiao" : "XiaoHuiHui");
	}
	return 0;
}