浙江农林大学第二十二届程序设计竞赛
目录
瓜瓜打游戏（EASY）
题目思路
简单dp，状态转移公式如下：
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * a[i];
题目代码
#include<bits/stdc++.h>
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] << ' ';
}
瓜瓜喜欢做 A + B
题目思路
最后一个颜色所占面积最大
题目代码
#include<bits/stdc++.h>
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<bits/stdc++.h>
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;
}
瓜瓜的 01 串
题目思路
思维题目，判断0和1的个数和k的个数作比较
题目代码
#include<bits/stdc++.h>
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<bits/stdc++.h>
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;
}
策策学长找py
题目思路
上一行任何一个块这一行只能在其左上方，判断一下
题目代码
#include<bits/stdc++.h>
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<bits/stdc++.h>
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;
}
其他题目题解链接
结语
“遇事不决，可问春风。春风不语，即随本心。”的意思是：对一件事犹豫不决，就问春风该如何做，春风给不出答案，就凭自己本心做出决断。“遇事不决可问春风，春风不语即随本心”一句出自网络作家“烽火戏诸侯”的《剑来》，其原文是：“遇事不决，可问春风。春风不语，遵循己心”。
