WA_automat
N 人看过

偷鸡大法

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

codeforces

这里就只写第一题和第二题(偷鸡版)的题解啦!

  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;
}

也就是真实的,应满足

(偷鸡写法,仅供参考!)