开锁

思路分析

对每个数字，比较是加过去步数少，还是减过去步数少即可。

参考代码

#include <bits/stdc++.h>
using namespace std;

int n, s, i;
string a, b;
int main() {
	cin >> n >> a >> b;
	for (int i = 0; i < n; i++) s += min((a[i] - b[i] + 10) % 10, (b[i] - a[i] + 10) % 10);
	cout << s << endl;
}

加减二叉树

思路分析

所有n都不大于2^k。考虑到n等于2^k时，一直往左走最后一步往右走。n等于2^k-1时一直往左走。n等于2^k-d时，分d是奇数偶数讨论最后一步的走法（奇左偶右），前面k-1步一直往左走，令减去的值刚好等于d/2向下取整。

参考代码

#include <bits/stdc++.h.h>

using namespace std;

int main() {
	long long n, k, a, d, b, i;
	scanf("%lld%lld", &n, &k);
	a = 1LL<<k;
	d = a - n;
	b = d / 2;
	for(i = 0; i < k; i++) {
		if((1LL<<i) & b)printf("%lld -\n",(1LL<<i));
		else {
			if(i == k - 1) {
				if(d & 1) printf("%lld +\n",(1LL<<i));
				else printf("%lld +\n",(1LL<<i)+1LL);
			}
			else printf("%lld +\n",(1LL<<i));
		}
	}
	return 0;
}

走斜线

思路分析

要到达目的地花费的最小步数是x和y的最大值，如果k小于这个值就一定到不了。如果k溢出了，那么在整个k步里，最多只会走两条直线。分别是如下三种情况（令x<=y）：0条直线（y-x）是偶数且（k-x）是偶数；1条直线（y-x）是奇数；2条直线（y-x）是偶数且（k-x）是奇数。

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
	int T;
	long long x, y, k, t, ans;
	scanf("%d", &T);
	while(T--) {
		scanf("%lld%lld%lld",&x,&y,&k);
		if(x > y) {
			t = x;
			x = y; 
			y = t;
		}
		if(y > k) {
			puts("-1");
			continue;
		}
		ans = k;
		if((y - x) % 2) ans--;
		else if((k - x) % 2) ans -= 2;
		printf("%lld\n", ans);
	}
	return 0;
}

得分最大

思路分析

双方都要使自己的得分尽可能比对方多，就有两种策略：使自己得分越多越好；使对方得分越少越好。所以贪心比较当前自己盒子里分值最大的彩球和对方盒子里分值最大的彩球，如果自己的分比较多，就从自己盒子里拿（自己得分越多越好），否则从对方盒子里拿（对方得分越少越好）。

参考代码

#include <bits/stdc++.h>
using namespace std;

int a[100015],b[100015];

bool _cmp(int i, int j){return i > j;}

int main() {	
	int n;
	long long ans;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
	sort(a + 1, a + 1 + n, _cmp);
	sort(b + 1, b + 1 + n, _cmp);
	ans = 0;
	int i = 1;
	int j = 1;
	while(i <= n || j <= n) {
		if(a[i] > b[j]) ans += a[i++];
		else j++;
		if(b[j] > a[i]) ans -= b[j++];
		else i++;
	}
	printf("%lld", ans);
	return 0;
}