阅读量:0
目录
一. 试卷
1. 资产
（1）错误思路：· 每一步都取绝对值
· 若下一个数为负且当前和为负时不取绝对值，若下一个数为正且当前和为负时取绝对值。反例：-5 -3 2 -1 -7 在加完前两个时遇到2不应取绝对值，应该在最后一步时再取加绝对值才能达到最大值。
（2）正确思路：由于并不知道该在何时对和取绝对值，所以用maxn和minn看最大能到多大和最小能到多小，在最后一次再取绝对值。
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 3e5; LL n, ans, a[N]; int main() { LL p, q, minn = 0, maxn = 0; cin >> n; for (int i = 1; i <= n; i ++) { cin >> a[i]; p = maxn + a[i]; q = minn + a[i]; maxn = max(p, q, abs(p), abs(q)); minn = min(p, q, abs(p), abs(q)); } cout << maxn; return 0; } 2. 视频游戏
正确思路：对回合数二分答案，回合数大于正确答案Boss一定死，小于正确答案一定杀不死，符合单调性。
#include<bits/stdc++.h> using namespace std; int h, n, ans, a[200005], c[200005], cd[200005]; int f(int x, int h) { x --; for (int i = 1; i <= n; i ++) h -= (x / c[i]) * a[i]; return h; } int main() { int l, r, mid; cin >> h >> n; for (int i = 1; i <= n; i ++) { cin >> a[i]; h -= a[i]; } for (int i = 1; i <= n; i ++) cin >> c[i]; l = 1, r = 5e10; // 边界一定要开得大 while (l <= r) { mid = l + (r - l) / 2; if (f(mid, h) <= 0) { ans = mid; r = mid - 1; } else l = mid + 1; } cout << ans; return 0; }二. 专题：贪心，构造
（1）USACO21OPEN Acowdemia III
思路：
（1）并不关心每棵草让哪两头牛成为朋友，只要一棵草周围有两头牛以上就可一多出一对朋友。
（2） 但这会出现特殊情况，例如 ‘ C G 和 ' G C
G C ’ C G ' 两堆草会出现重复的朋友。
（3）因此要分类讨论：· 一堆草周围牛数大于2，答案直接加一
· 一堆草周围牛数等于2，祥判断是否满足上述特例，若满足，只要上方的草加过一次，下方的草就不加。
代码：
#include<bits/stdc++.h> #define LL long long using namespace std; int n, m, ans, dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}, num[1001][1001]; char w[1001][1001]; int main() { cin >> n >> m; for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) cin >> w[i][j]; for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) for (int k = 0; k < 4; k ++) num[i][j] += (w[i + dx[k]][j + dy[k]] == 'C'); for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) if (w[i][j] == 'G') { if (num[i][j] > 2) ans ++; if (num[i][j] == 2) { if ( (w[i][j - 1] == 'C' && w[i - 1][j - 1] == 'G' && w[i - 1][j] == 'C' && num[i - 1][j - 1] == 2) || (w[i - 1][j] == 'C' && w[i][j + 1] == 'C' && w[i - 1][j + 1] == 'G' && num[i - 1][j + 1] == 2) ) continue; ans ++; } } cout << ans; return 0; }（2）USACO05NOV 奶牛玩杂技
思路：体重与力量值之和从大到小依次从下往上叠。
