偷鸡大法
为了备战蓝桥杯和快速升到蓝名,最近一直在打
这里就只写第一题和第二题(偷鸡版)的题解啦!
( 题) ( 题)
In Berland, there are two types of coins, having denominations of
Your task is to determine whether it is possible to represent
题目大意
输入
一个整数
下面
输出
有非负整数解时,输出
样例
输入
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;
}
题目大意
一开始有一个人位于
三种操作如下:
- 腿长
- 从
走到 - 从
走到
他最少需要多少时间
题解
一开始我以为本质是最小化
但我们可以用这个方法偷鸡一波。
最小化的值一定位于这个极值点附近,在数据范围内并不会偏移很多。我们假设极值点为
现在,样例的最大个数
我们可以得出如下的代码:
#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;
}
也就是真实的
(偷鸡写法,仅供参考!)