浙江农林大学第二十二届程序设计竞赛部分题解

• 目录
• • 瓜瓜打游戏（EASY）
  • • 题目思路
    • 题目代码
  • 瓜瓜喜欢做 A + B
  • • 题目思路
    • 题目代码
  • 瓜瓜不想上电工课
  • • 题目思路
    • 题目代码
  • 瓜瓜的 01 串
  • • 题目思路
    • 题目代码
  • 瓜瓜上电工
  • • 题目思路
    • 题目代码
  • 策策学长找py
  • • 题目思路
    • 题目代码
  • 周周的泡泡
  • • 题目思路
    • 题目代码
  • 其他题目题解链接
• 结语

简单dp，状态转移公式如下：

dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * a[i];

#include
using namespace std;
#define ll long long
ll dp[5003][5003];
ll a[5003];
int main() {
	ll n, p;
	cin >> n >> p;
	for (int i = 1; i <= n; ++i)cin >> a[i];
	dp[0][1] = 0;
	for (int i = 1; i <= n; ++i) {
		dp[i][0] = 1;
		dp[i][1] = (dp[i - 1][1] + a[i]) % p;
	}
	dp[0][0] = 1;
	for (int i = 2; i <= n; ++i) {
		for (int j = 1; j <= i; ++j) {
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * a[i];
			dp[i][j] %= p;
		}
	}
	for (int i = 0; i <= n; ++i)cout << dp[n][i] << ' ';
}

最后一个颜色所占面积最大

#include
using namespace std;
int main() {
	int n, m, k;
	cin >> n >> m >> k;
	int a, b, c;
	while (k--) {
		scanf("%d %d %d", &a, &b, &c);
	}
	cout << n + m - 1 << " " << c << endl;
}

贪心，对a和b之差进行排序，取前k个（差值为负数则不取）

#include
using namespace std;
#define ll long long
struct node {
	int x, y, z;
}a[100005];
bool cmp(node a, node b) {
	return a.z > b.z;
}
int main() {
	int n, m;
	cin >> n >> m;
	int x, y, z;
	ll sum = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i].x);
	}for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i].y);
		a[i].z = a[i].x - a[i].y;
		sum += a[i].x;
	}
	sort(a + 1, a + n + 1, cmp);
	for (int i = 1; i <= m; i++) {
		if (a[i].z <= 0)break;
		sum -= a[i].z;
	}
	cout << sum << endl;
}

思维题目，判断0和1的个数和k的个数作比较

#include
using namespace std;
#define ll long long
ll n, k;
string s;
ll sum0, sum1;
int main() {

	cin >> n >> k >> s;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '0')sum0++;
	}
	sum1 = n - sum0;
	if (k == 0) {
		cout << sum0 << endl;
	}
	else {
		if (sum0 == sum1) {
			if (k <= sum1) {
				cout << sum1 + k;
			}
			else {
				cout << n;
			}
		}
		else if (sum0 > sum1) {
			if (k <= sum1) {
				cout << sum0 + k;
			}
			else {
				if (k >= sum0) {
					int cnt0 = k - sum0;
					int cnt1 = k - sum1;
					if ((cnt0 & 1)||(cnt1%2==0)) {
						cout << n;
					}
					else {
						cout << n - 1;
					}
				}
				else {
					int cnt1 = k - sum1;
					if (cnt1 % 2 == 0) {
						cout << n;
					}
					else {
						cout << n - 1;
					}
				}
			}
		}
		else if(sum1>sum0) {
			if (k <= sum0) {
				cout << sum1 + (k - 1);
			}
			else {
				if (k >= sum1) {
					int cnt0 = k - sum0;
					int cnt1 = k - sum1;
					if ((cnt0 & 1) || (cnt1 % 2 == 0)) {
						cout << n;
					}
					else {
						cout << n - 1;
					}
				}
				else {
					int cnt0 = k - sum0;
					if (cnt0 & 1) {
						cout << n;
					}
					else {
						cout << n - 1;
					}
				}
			}

		}
	}
}

用全排列把所有情况写出来，找最小情况

#include
using namespace std;
#define ll long long
struct node {
	int x, y;
}a[14];
int b[11] = { 0,1,2,3,4,5,6,7,8,9,10 };
int n, q;
bool check(int x, int y, int c, int d) {
	if (x == c || x == d || y == c || y == d)return true;
	return false;
}
int main() {
	cin >> n >> q;
	for (int i = 1; i <= q; ++i) {
		int c, b;
		cin >> c >> b;
		a[i].x = c;
		a[i].y = b;
	}
	ll ans = 999999999;
	do {
		int dx = 0, dy = 0;
		ll sum = 0;
		for (int i = 1; i <= q; ++i) {
			int nx = a[b[i]].x, ny = a[b[i]].y;
			if (check(dx,dy,nx,ny))++sum;
			else sum += 2;
			dx = nx;
			dy = ny;
		}
		if (sum < ans)ans = sum;
	} while (next_permutation(b + 1, b + q + 1));
	ans += 2;
	cout << ans << endl;
}

上一行任何一个块这一行只能在其左上方，判断一下

#include
using namespace std;
#define ll long long
ll n, k;
string s;
ll sum0, sum1;
int begi[10005];
int last[10005];
int main() {
	int t;
	cin >> t;
	while (t--) {
		for (int i = 1; i <= 10000; i++) {
			last[i] = -1;
			begi[i] = 100000;
		}
		int n, m, k;
		scanf("%d%d%d", &n, &m, &k);
		int x, y;
		for (int i = 1; i <= k; i++) {
			scanf("%d %d", &x, &y);
			last[x] = max(last[x], y);
			begi[x] = min(begi[x], y);
		}
		int v;
		int g;
		for (int i = 1; i <= n; i++) {
			if (last[i] != -1) {
				v = last[i];
				g = i;
				break;

			}
		}
		int ok = 1;
		for (int i = g; i <= n; i++) {
			if (begi[i] != 100000) {
				if (begi[i] < v) {
					ok = 0;
					break;
				}
				v = last[i];
			}
		}
		if (ok == 1) {
			puts("YES");
		}
		else {
			puts("NO");
		}
	}
	
}

既然是连续的，就只用枚举左端点然后二分查找右端点就行了

#include
using namespace std;
#define ll long long
ll a[200005];
ll suml[200005], sumr[200005],sum[200005];
int main() {
	ll n, h;
	cin >> n >> h;
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		suml[i] = suml[i - 1] + a[i];
	}
	for (int i = n; i >= 1; i--) {
		sum[i] = sum[i + 1] + a[i];
	}
	for (int i = 1; i <= n; i++) {
		sumr[i] = sum[n - i + 1];
	}
	ll Min = 9999999999;
	for (int i = 0; i <= n; i++) {
		int x = h - suml[i];
		if (x <= 0)break;
		ll dx = lower_bound(sumr, sumr + n-i, x)-sumr-1;
		Min = min(Min, x - sumr[dx]);
	}
	cout << Min << endl;
}

• 瓜瓜选妃 （二维差分 + 二分）