偷鸡大法

为了备战蓝桥杯和快速升到蓝名，最近一直在打。碰巧昨晚回宿舍的时间还算比较早，就火速注册打了一把，不过确实是没想到第二题那么恶心人，搞得第三题都没时间认真写了（这个天不洗澡受不了，写完第二题怕没热水就去洗澡了）。

这里就只写第一题和第二题（偷鸡版）的题解啦！

1. （题）
2. （题）

In Berland, there are two types of coins, having denominations ofandburles.

Your task is to determine whether it is possible to representburles in coins, i.e. whether there exist non-negative integersandsuch that.

题目大意

是否有非负整数解。

输入

一个整数，表示有个样例。
下面行，每行两个整数和。

输出

有非负整数解时，输出，否则输出。

题目链接

样例

输入

4
5 3
6 1
7 4
8 8

输出

YES
YES
NO
YES

题解

其实不难看出，当为偶数，肯定有非负数解。
那当为奇数时，只要为奇数（由于），必定能被表示出来。

代码实现：

#include<iostream>
using namespace std;
typedef long long LL;
LL t, n, k;
int main(void) {
	cin >> t;
	while (t--) {
		cin >> n >> k;
		if (n % 2) {
			if (k % 2 == 0) cout << "NO" << endl;
			else cout << "YES" << endl;
		}
		else cout << "YES" << endl;
	}
	return 0;
}

原题链接

题目大意

一开始有一个人位于位置，他一开始的腿长为，他现在想走到，他可以进行三种操作，每次操作消耗单位时间。

三种操作如下：

1. 腿长
2. 从走到
3. 从走到

他最少需要多少时间

题解

一开始我以为本质是最小化，最后发现好像不是这样的，他必须恰好跳到终点处。

但我们可以用这个方法偷鸡一波。

最小化的值一定位于这个极值点附近，在数据范围内并不会偏移很多。我们假设极值点为，上述函数为，则：

现在，样例的最大个数，并且，众所周知，最多可以跑大约次。

我们可以得出如下的代码：

#include<iostream>
#include<cmath>
using namespace std;
int t, a, b;
int main(void) {
	cin >> t;
	while (t--) {
		int ans = 0x3f3f3f3f;
		cin >> a >> b;
		if (a > b) swap(a, b);
		int m = sqrt(a + b);
		for (int i = m - 1e5; i <= m + 1e5; ++i) {
			int tmp = i <= 0 ? 1 : i;
			ans = min(ans, (int)(tmp - 1 + ceil((double)a / tmp) + ceil((double)b / tmp)));
		}
		cout << ans << endl;
	}
	return 0;
}

也就是真实的，应满足

（偷鸡写法，仅供参考！）