夏令营入门组day2

目录

一. 试卷

二. 专题：贪心，构造

一. 试卷

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

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