目录

一. 试卷

二. 专题：贪心，构造

一. 试卷

1. 资产

（1）错误思路：· 每一步都取绝对值

                           · 若下一个数为负且当前和为负时不取绝对值，若下一个数为正且当前和为负时取绝对值。反例：-5 -3 2 -1 -7 在加完前两个时遇到2不应取绝对值，应该在最后一步时再取加绝对值才能达到最大值。

（2）正确思路：由于并不知道该在何时对和取绝对值，所以用maxn和minn看最大能到多大和最小能到多小，在最后一次再取绝对值。

#include #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 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 #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  奶牛玩杂技 

思路：体重与力量值之和从大到小依次从下往上叠。