A 最大面积
题目
输入
输出
示例1
输入
2 2 3 2
输出
4
代码
void solve() { int a, b, c, d; cin >> a >> b >> c >> d; cout << min(a, c) * min(b, d) << endl; }
B 种树
题目
输入
输出
示例1
输入
7
0111110
输出
2
思路
注意题目说的：“一个地方可以种多棵树。”
左侧有 0 可以由右侧某个1 向左种树
右侧有 0可以由左侧某个 1 向右种树
即：字符串首尾两位 0的个数，决定了种的次数。
代码
void solve() { int n; cin >> n; string s; cin >> s; int res = 0; if (s[0] == '0') res++; if (s.back() == '0') res++; cout << res << endl; }
C 奇怪的电梯
题目
输入
输出
示例1
输入
5
10 3 2 7
10 7 1 4
10 4 2 9
10 11 1 10
9 3 7 2
输出
YES
NO
YES
NO
YES
思路
事先声明：代码很丑，但思路非常简单！！！
题目问能否从（ a − > b ），那很容易第一想法就是分情况（ a > b ， b > a ， a = = b ） （a>b，b>a，a==b）（a>b，b>a，a==b）
a==b：yes
b>a：（如上图所示）
这里需要继续分情况，在此只考虑yes的情况
b−a>k：a − > b
n−b>k：a − > n − > b
a−1>k：a − > 1 − > b
n−a>k&&b−1>k：a − > n − > 1 − > b
a > b a>ba>b：同上思路
以上情况已经列明，具体的逻辑也应该非常清晰了，不在叙述每一步之间的大小关系了（自己想。
代码
void solve() { int n, k, a, b; cin >> n >> k >> a >> b; if (a == b) { puts("YES"); return ; } if (a > b) { if (n - a > k || a - b > k || b - 1 > k) { puts("YES"); return ; } else if (a - 1 > k && n - b > k) { puts("YES"); return ; } else { puts("NO"); return ; } } else { if (a - 1 > k || b - a > k || n - b > k) { puts("YES"); return ; } else if (n - a > k && b - 1 > k) { puts("YES"); return ; } else { puts("NO"); return ; } } }
D 最大gcd
题目
输入
输出
示例1
输入
3
1 2 2
输出
2
思路
这题一眼n 2
2
暴力结束。。。T的飞起
考虑题目范围n≤1e6，并且每个数的大小a[i]≤1e6。
我们可以从原先找每两个数的gcd 取最大，转为找出每个数的约数，这样最大存在的约数并且个数大于等于2 ，那么就是答案。
我们考虑 nlogn的算法来实现，又已知 nlogn 能打出 1 ~ n 范围内的所有约数。
大概思路就是枚举每个数 i 的倍数，那么 i ∗ j 的约数就有 i。和线性筛的思路有点相似，代码大概长这样：
// 求 1 ~ n 的约数 for (int i = 1; i <= n; i++) for (int j = 1; j <= n / i; j++) a[i * j].push_back(i);
不过这题还需要有一个特判（由于我的实现方式导致的），需要对重复的数也计入答案的贡献。即代码中的：if (a[x] == 2) res = max(res, x);
因为if (a[i * j]) c[i]++;，这行代码未考虑重数的情况。
代码
int a[N], c[N]; void solve() { int n; scanf("%d", &n); int res = -1; for (int i = 1; i <= n; i++) { int x; cin >> x; a[x]++; if (a[x] == 2) res = max(res, x); } for (int i = 1; i <= N; i++) for (int j = 1; j <= N / i; j++) if (a[i * j]) c[i]++; for (int i = 1; i < N; i++) if (c[i] >= 2) res = max(res, i); cout << res << endl; }
E 一道难题
题目
输入
输出
示例1
输入
2001
输出
3
说明
1 − 2001 1−20011−2001 中，满足条件的数有：111 , 1110 , 1111 111,1110,1111111,1110,1111。
思路
题目输入的是十进制的数，但是题目要求的是由 0 00 或 1 11 组成的。
所以可以发现，满足题目的条件的十进制数，实际上与相同位数的二进制数对应。
那么可以求出不超过 n nn 的最大的二进制形式，应该对应的十进制数值。
对于每一个数，都当成一个二进制数看。然后在暴力枚举，判断符合条件即可。
代码
void solve() { string s; cin >> s; int n = 0; bool o = false; for (int i = 0; i < s.sz; i++) { if (o) { n += (1ll << (s.sz - i - 1)); continue; } if (s[i] > '1') n += (1ll << (s.sz - i - 1)), o = true; if (s[i] == '1') n += (1ll << (s.sz - i - 1)); } auto check = [=](int x){ int cnt = 0; while (x) { if (x & 1) cnt++; else cnt = 0; if (cnt == 3) return true; x >>= 1; } return false; }; int res = 0; for (int i = 1; i <= n; i++) { if (check(i)) res++; } cout << res << endl; }
