T1 袋中球的最终颜色

观察题面描述，发现这个题包含了一个很有趣的性质：

• 如果把每次拿出球看做一个运算的话，这种运算对应着“每次选出来的球相同则结果为白球，反之结果为黑球”。

这和异或运算的本质是相同的，即“相同为 0，不同为 1”。

把白球看做数字 0 ，黑球看做数字 1 ，则题面转化为如下形式：

给出 $a$ 个数字 0 和 $b$ 个数字 1 ，问他们进行异或运算的结果是 0 还是 1 。

由于异或运算具有交换律，所以我们可以通过计算所有 0 异或的结果（必然为 0 ），和所有 1 异或的结果（可能是 0 和 1 ），最终再进行合并即可。

由于所有 0 异或的结果只可能是0，且 0^x=x，所以最终答案和 $b$ 个 1 异或运算的结果相同。只和 $b$ 的奇偶有关。

code:

#include <bits/stdc++.h>
using namespace std;
long long  a, b;

int main() {
	cin >> a >> b;
	if (b % 2)
		cout << "black";
	else
		cout << "white";
	return 0;
}

T2 砍竹子1

对于这种没有思路的题，我们可以打标观察一下小数据的答案。

• 若 $n$ = 1，则答案为 1。

• 若 $n$ = 2，则答案为 2。

• 若 $n$ = 3，则答案为 3。

• 若 $n$ = 4，则答案为 4。

• 若 $n$ = 5，则答案为 2 * 3 = 6。

• 若 $n$ = 6，则答案为 3 * 3 = 9。

• 若 $n$ = 7，则答案为 2 * 2 * 3 = 12。

• 若 $n$ = 8，则答案为 2 * 3 * 3 = 18。

• $\dots$

到此我们发现，最终答案里是否只会出现 2 和 3 呢？

由此我们发现，如果对于一个数字 $n$，现在有了一种可行的方案，且这个方案的乘积表示下有 $4$，则拆分成 $2\times 2$ 是等价的，如果有 $5$，则拆分成 $2\times 3$ 更优，如果是 $6$，则拆分成 $3\times 3$ 更优……

由此证明了最优解一定是只由 $2$ 和 $3$ 组成的乘积序列的结果。

因为 3 比 2 更优，所以最终的答案序列应该尽可能放 3。

经过打表，我们可以发现以下规律：

如果 $n\bmod 3$ = 0，则答案为 $\frac{n}{3}$ 个 3 的乘积。

如果 $n\bmod 3$ = 1，则答案为 2 个 2 乘 $\frac{n-4}{3}$ 个 3。

如果 $n\bmod 3$ = 2，则答案为 1 个 2 乘 $\frac{n-2}{3}$ 个 3。

直接按照上述结论写代码即可，注意特判 $n=1$ 的情况。

事实上，这是一个广泛应用的经典贪心问题，请同学们牢记。

以下代码使用了快速幂来计算一个 3 的 $x$ 次方，感兴趣的同学可以移步学习了解。

code:

#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;

long long mi(long long a, long long b) {
	long long t = a, ans = 1;
	while (b) {
		if (b & 1)
			ans = (ans * t) % mod;
		t = (t * t) % mod;
		b >>= 1;
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	long long n, ans = 1;
	cin >> n;
	if (n == 1)
		ans = 1;
	else if (n == 2)
		ans = 2;
	else if (n % 3 == 1)
		ans = 4, n -= 4;
	else if (n % 3 == 2)
		ans = 2, n -= 2;
	ans = (ans * mi(3, n / 3)) % mod;
	cout << ans << "\n";
	return 0;
}

T3 天天的n台电脑

发现直接计算最优解是困难的，因为电池和电脑的使用都是自由变量。

但是可以判断可行性，即判断电脑坚持多长时间是可行的，所以转二分考虑。（如果电脑能运行 $x$ 分钟，那么一定可以运行 $x+1$ 分钟，以此类推具有单调性）

考虑如果有 $n$ 台电脑要坚持 $x$ 分钟，相当于一台电脑需要坚持 $n\times x$ 分钟。

……吗？

仔细想一下，如果一块电池可以让电脑使用 $a_i$ 分钟，且 $a_i>x$，则这块电池在时间内最多贡献 $x$ 分钟的时间。

那么如果 $a_i<x$，这块电池能完整贡献 $a_i$ 的时间吗？答案是肯定的，留给同学自证。

所以如果目标是让 $n$ 台电脑坚持 $x$ 分钟，则所有电池的贡献总和 $sum$ 为两类电池相加，对于每一块 $a_i\le x$ 的电池，贡献为 $a_i$，否则贡献为 $x$。

以上可以通过比较 $sum$ 和 $n\times x$ 的大小来计算答案。

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
int n,sum[N],a[N],tot;
int check(int x){
    int id = lower_bound(a+1,a+1+tot,x)-a;
    id--;
    int tmp = sum[id];
    if(tmp>=(n-tot+id)*x){
        return 1;
    }
    else{
        return 0;
    }
}
signed main(){
    cin>>n;
    while(scanf("%lld",&a[++tot])!=-1);
    sort(a+1,a+1+tot);
    for(int i = 1; i<=tot; i++){
        sum[i] = sum[i-1]+a[i];
    }
    int l = 0, r = sum[tot]/n;
    while(l<=r){
        int mid = (l+r)>>1;
        int tmp = check(mid);
        if(tmp) l=mid+1;
        else r=mid-1;
    }
    cout<<r;
    return 0;
}

T4 熙晨打怪兽

如果两种伤害都是刀砍的话，每一回合选择伤害最高的方法即可。

但是难处理的问题是由于毒杀的存在，所以我们难以判断毒杀的伤害和刀砍的伤害谁更高，这是因为毒杀的伤害和接下来剩余的轮数有关。

在已知轮数的情况下，以上答案是好计算的，又由于答案具有单调性（能坚持 $x$ 轮的怪兽肯定能坚持 $x-1$ 轮）。

转为判断怪兽是否能在 $x$ 轮后死亡，即要让 $x$ 轮的总伤害最大。

则对于第 $i$ 轮发出的伤害为 $k$ 的毒杀，可以转化成 $(n-x)\times k$ 伤害大小的刀砍伤害。

这样就可以每次贪心选择最大的一组伤害而得到答案了。

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, hp, kni[N], ven[N];
int check (int x){
	int tmp = 0;
	for (int i = 1; i <= min(x, n); i++){
		tmp += max (kni[i], ven[i] * (x - i));
	}
	return tmp >= hp;
}
signed main(){
	cin >> n >> hp;
	for(int i = 1; i <= n; i++) {
		cin >> kni[i] >> ven[i];
	}
	int l = 1, r = hp + 1;
	while (l <= r) {
		int mid = l + r >> 1;
		if (check(mid)) {
			r = mid - 1;
		} else{
			l = mid + 1;
		}
	}
	cout << l;
	return 0; 
}