郑州轻工业大学2020级新生程序设计大赛题解

更新了 7- 2 的代码，之前有点小 bug
更新了 7 -10 的代码，/(ㄒoㄒ)/~~
这一次真的更新好了，可以放心观看
感谢强哥等等一系列大佬给我魔法药水这个题的思路

我好菜 /(ㄒoㄒ)/

题目地址：传送门~~~

7-1 小A与泉水

思路
位运算。在二进制下，从低位开始向上进位即可。
应该还有其他写法，没再去想了 (lll￢ω￢)
这个题好像卡输入和输出，别用 cin 和 cout

AC代码

#include <iostream>
#include <bits/stdc++.h>using namespace std;int main(int argc, char** argv) {int ncase;scanf("%d", &ncase);while(ncase--){int n;scanf("%d", &n);int res = 0;if(n == 0){printf("0\n");continue;}while(n){	// 在纸上模拟一下就OK了if(n & 1){res++;if(n != 1) n += 2; }n >>= 1;}printf("%d\n", res-1);}return 0;
}

7-2 小A的魔法

思路
二维前缀和，容斥原理

黄色部分的权值 = {(7,9)->(1,1)} - {(2,9)->(1,1)} - {{(7,2)->(1,1)}} + {{(2,2)->(1,1)}}
ps: {(7,9)->(1,1)} 表示以这两个点为顶点的矩形的权值
统计权值，计算前缀和，再通过上边公式枚举所有点就OK

这里还有一种思路：
题目给的点数比较少，选取一个敌人所在的点作为矩形的一个顶点，由这个顶点确定四个矩形，再依次找在矩形内的点数有几个。
如果暴力找点的话，时间复杂度为O(n*n)，妥妥的能过 手动狗头

AC代码

// 第一种思路的代码，第二种思路的代码自己试试吧
#include <iostream>
#include <bits/stdc++.h>using namespace std;const int maxn = 1e3;int v[maxn][maxn] = {0};int main(int argc, char** argv) {int n, w, k;cin >> n >> w >> k;int x, y;for(int i = 1; i <= n; i++){cin >> x >> y;v[x][y]++;}for(int i = 1; i < maxn; i++){	// 前缀和for(int j = 1; j < maxn; j++){v[i][j] += v[i][j-1] + v[i-1][j] - v[i-1][j-1];}} int res = 0; for(int i = 1; i < maxn; i++){	// 找最值for(int j = 1; j < maxn; j++){int xx = i - w + 1;int yy = j - k + 1;if(xx <= 0 || yy <= 0) continue;int tmp = v[i][j] - v[xx-1][j] - v[i][yy-1] + v[xx-1][yy-1];res = max(res, tmp);}}cout << res << endl;return 0;
}

7-3 小A的宝藏

思路
博弈论。

巴什博弈
每次有至多取走 m 个硬币，至少取走 1 个硬币。
共有 (m+1) * k + x 个硬币 (x 小于 m)。
A先手，B后手，取走最后一个硬币者胜。
分析： 如果 A 先手取走 x 个硬币，还剩下 (m+1) * k 个硬币。接下来 B 取走 z 个硬币，这时 A 可以通过取走 m+1-z 个硬币保证剩下的硬币为 m+1 的倍数。如此 K 轮以后，我们会发现 A 取走了最后一个硬币。即 A 必胜。
but，当 x 为 0 时，A 必败，类比刚刚的分析（B 在面对 (m+1) * k 时，必败）。

看完这个我们就可以知道，本题内的 m 为 3，硬币的数量就是银子的数量。
当没有金子的时候，可以知道对面 3 * k 个银子的人必输。
下边我们就来分析各个情况：

3 * k 个银子，0 个金子，先手败。
3 * k + 1 个银子，0 个金子，先手胜。先手拿走一个银子，后手面对 3 * k 个银子，必败。
3 * k + 2 个银子，0 个金子，先手胜。先手拿走两个银子，后手面对 3 * k 个银子，必败。
3 * k 个银子，1 个金子，先手胜。      先手拿走一个金子，后手面对 3 * k 个银子，必败。
3 * k + 1 个银子，1 个金子，先手败。无论先手拿走什么，后手都是必胜态。
3 * k + 2 个银子，1 个金子，先手胜。先手拿走一个银子，后手面对必败态。

最后，m 个 金子可以压缩成对应的 0 或 1。
这个题同样卡输入和输出
AC代码

#include <iostream>
#include <bits/stdc++.h>using namespace std;int main(int argc, char** argv) {int ncase;scanf("%d", &ncase);while(ncase--){long long a, b;scanf("%lld %lld", &a, &b);if(a % 3 == 2) printf("Alice\n");else if(a % 3 == 0){if(b & 1) printf("Alice\n");else printf("Bob\n");}else{if(b & 1) printf("Bob\n");else printf("Alice\n");}}return 0;
}

7-4 靶场射击2.0

思路：
字符串处理，统计每个字母出现的次数找最值即可。

AC代码

#include <iostream>
#include <bits/stdc++.h>using namespace std;int v[2][26] = {0};int main(int argc, char** argv) {int n, a, b;cin >> n >> a >> b;int res = 0; char c;for(int i = 1; i <= n; i++){cin >> c;if(c >= 'a' && c <= 'z'){	// 普通 int tmp = c - 'a';v[0][tmp]++;res = max(res, v[0][tmp] * b + v[1][tmp] * a);}else{		// 特殊 int tmp = c - 'A';v[1][tmp]++;res = max(res, v[0][tmp] * b + v[1][tmp] * a);}}for(int i = 0; i < 26; i++){if(v[0][i] * b + v[1][i] * a == res){cout << (char)(i + 'A') << endl;break;}}return 0;
}

7-5 这是一个数学题

思路
思维题~~~
如果一个数是 20 的倍数那么最后两位数要为偶数和一个零。
把一个数往这个状态转移，看需要换几次即可。
如果达不到这个状态，结果就为 -1。

AC代码

#include <iostream>
#include <bits/stdc++.h>using namespace std;int main(int argc, char** argv) {int ncase;cin >> ncase;while(ncase--){long long n;cin >> n;if(n < 20){cout << -1 << endl;continue;}vector<int> v;while(n){int tmp = n % 10;v.push_back(tmp);n /= 10;}int res = 0;if(v[0] != 0){int f = 0;for(int i = 2; i < v.size(); i++){if(v[i] == 0){swap(v[0], v[i]);f = 1;res++;break;}}if(f == 0 && v[1] == 0){swap(v[0], v[1]);res++;}else if(f == 0) res = -1;}if(v[1] % 2 != 0 && res != -1){int f = 0;for(int i = 2; i < v.size(); i++){if(v[i] % 2 == 0){swap(v[1], v[i]);f = 1;res++;break;}}if(f == 0) res = -1;}cout << res << endl;}return 0;
}

7-6 代码格式化

思路
字符串处理。

AC代码

#include <bits/stdc++.h>
using namespace std;string s, ss;int main(){getline(cin, ss);getline(cin, s);cout << ss << endl;int len = s.size();for(int i = 0; i < len; i++){if(s[i] == '{') cout << " " << s[i] << endl << "    ";else if(s[i] == ';' && i+2 != len) cout << s[i] << endl << "    ";else if(s[i] == ';') cout << s[i] << endl;else if(s[i] == '=') cout << " " << s[i] << " ";else if(s[i] == '+') cout << " " << s[i] << " ";else if(s[i] == '-') cout << " " << s[i] << " ";else if(s[i] == '*') cout << " " << s[i] << " ";else if(s[i] == '/') cout << " " << s[i] << " ";else if(s[i] == '%') cout << " " << s[i] << " ";else cout << s[i];}cout << endl;return 0;
}

7-7 贪心的小H

思路
假设当前背包有 x 个物品，价值为 y，对于未放入背包价位为 val 物品 A：
如果我们把它放入背包，背包的价值变为 (x+1) * (y + val), 展开得 x*y + y + (x+1) * val。
贪心得，如果 y + (x+1) * val 大于零，我们就把它放入背包。
对所有物品，按照 val 排序，从大到小去判断即可。

AC代码

#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#define ll long long
#define chushi(a, b) memset(a, b, sizeof(a))
#define endl "\n"
const double eps = 1e-8;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int maxn = 1e5 + 5;using namespace std;typedef struct Node{int id;int val;
} node;bool cmp(node A, node B){if(A.val == B.val) return A.id < B.id;return A.val > B.val;
}node a[205];int main(){int n;cin >> n;for(int i = 1; i <= n; i++) cin >> a[i].id;for(int i = 1; i <= n; i++) cin >> a[i].val;sort(a+1, a+1+n, cmp);int x = 0, y = 0;for(int i = 1; i <= n; i++){if(a[i].id == a[i-1].id) continue;if(y + (x+1) * a[i].val > 0){x += 1;y += a[i].val;}else break;}cout << x * y << endl;return 0;
}

7-8 #define int long long

签到题。

AC代码

#include <bits/stdc++.h>
using namespace std;int main(){for(int i = 1; i <= 10; i++) cout << "#define int long long" << endl;return 0;
}

7-9 小A的魔力

思路
按照题意取最大值对应的字符串即可。

AC代码

#include <bits/stdc++.h>
using namespace std;int main(){int n;cin >> n;int mx = -1, tmp; string res, s;for(int i = 1; i <= n; i++){cin >> s >> tmp;if(tmp > mx){mx = tmp;res = s;}}cout << res << endl;return 0;
}

7-10 魔法药水 (好题)

思路
二分答案，在贪心wa了一以后就感觉是二分答案，不过一直想不到check函数咋写。

答案要的是价值和大于等于 X 的最少药瓶数，优先取价值大的药水这样想肯定没问题。

本人第一想法：
依次取价值最大和次大的药水轮流放，然后被自己无情 hack
这里给出一组 hack 数据：
     4   67
     4   10
     3    5
     10   4
     10   1
答案是：10
其中一个满足的排列：10、4、5、10、4、5、10、4、5、10

下边来说说正解：
二分答案。每次取验证一个瓶子数是不是能满足题意，在所有满足题意里边取最优。
这里说一个点，对于第 i 种药水，它在一个需要 X 个药水的方案种能使用的最多药水数为：（X+1）/ 2
看图吧，应该看得懂对于 X 的奇偶性质，自己画个图数数就知道了

其他的细节看代码，详解，保懂。

AC代码

#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#define ll long long
#define chushi(a, b) memset(a, b, sizeof(a))
#define endl "\n"
const double eps = 1e-8;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int maxn = 1e5 + 5;using namespace std;typedef struct Node{ll num;ll val;
} node;bool cmp(node A, node B){	// 自定义排序，主要是按照价值排序，数量无所谓 if(A.val == B.val) return A.num > B.num;return A.val > B.val;
}ll n, x;
node a[maxn];int check(ll mid){	// check 函数 ll cnt = mid, sum = x;	// 有 mid 个 位置放药水，需要达到价值 sum for(int i = 1; i <= n; i++){				// 遍历，提前排过序的 ll num = a[i].num, w = a[i].val;		// 第 i 种药水的数量 和 单个的价值 ll tmp = min({num, (mid+1)/2, cnt});	// 对于当前情况，这个药水能用的最多个数是：//	当前药水的数量、一个方案里一种药水最多可以放多少个位置、还需要的药水数。三者取 min。 sum -= tmp * w;	// 减去这个药水贡献的价值 cnt -= tmp;		// 减去这个药水贡献的数量 if(cnt == 0) break;	// 数量满足就提前结束 }if(cnt > 0) return 1;	// 药水不够填满 mid 个位置 if(sum <= 0) return 2;	// 药水可以填满 mid 个位置，并且满足价值大于 x return 0;				// 不满足价值大于 x 
}int main(){cin >> n >> x;for(int i = 1; i <= n; i++) cin >> a[i].num >> a[i].val;sort(a+1, a+1+n, cmp);		// 按权值排序，贪心思想，优先取权值大的 ll l = 1, r = 1e18, res = -1;	// 二分答案 while(l <= r){ll mid = l + r >> 1;int op = check(mid);if(op == 1) r = mid -1;else if(op == 2) r = mid - 1, res = mid;else l = mid + 1;}cout << res << endl;return 0;
}

写在最后，这次最后这个题是我的锅，以后再也不提前写题解了，脸疼（；´д｀）ゞ
下 次 还 会