CSDN竞赛第17期题解

CSDN竞赛第17期题解

• 第一题
• • 题目描述
  • 题解
  • 复杂度分析
• 第二题
• • 题目描述
  • 题解
  • 复杂度分析
• 第三题
• • 题目描述
  • 题解
  • 复杂度分析
• 第四题
• • 题目描述
  • 题解
  • 复杂度分析
• 总结

第一题

题目描述

题目名称：判断胜负
已知两个字符串A,B。 连续进行读入n次。 每次读入的字符串都为A|B。 输出读入次数最多的字符串。

题解

直接用map存储后比较即可。

#include
#include
using namespace std;
int main() {int n;cin >> n;string s;map<string,int> m;for (int i = 0; i < n; i++) {cin >> s;m[s]++;}int ma = 0;for (auto it = m.begin(); it != m.end(); it++) {if (it->second > ma) {ma = it->second;s = it->first;} else if (ma != 0 && it->second == ma) {s = "dogfall";}}cout << s << endl;return 0;
}

复杂度分析

时间复杂度为$O(n)$，n为读入次数。

第二题

题目描述

题目名称：买铅笔
P老师需要去商店买n支铅笔作为小朋友们参加编程比赛的礼物。她发现商店一共有 3 种包装的铅笔，不同包装内的铅笔数量有可能不同，价格也有可能不同。为了公平起 见，P老师决定只买同一种包装的铅笔。 商店不允许将铅笔的包装拆开，因此P老师可能需要购买超过 n 支铅笔才够给小朋 友们发礼物。 现在P老师想知道，在商店每种包装的数量都足够的情况下，要买够至少 n 支铅笔最少需要花费多少钱。

题解

只要注意到题目中提到的“只买同一种包装的铅笔”，计算买够充足铅笔所需的花费即可。

#include 
#include 
#include 
#include 
using namespace std;
int main() {int n;cin >> n;vector<int> num(3);vector<int> cost(3);vector<double> eve(3);for (int i = 0; i < 3; i++) {cin >> num[i] >> cost[i];eve[i] = ceil(n*1.0/num[i])*cost[i];}int ans = min({eve[0],eve[1],eve[2]});cout << ans << endl;return 0;
}

复杂度分析

时间复杂度为$O(1)$，因为只有三种包装的铅笔，注意精度使用浮点数即可。

第三题

题目描述

题目名称：拯救爱情
小艺酱走到一个花之占卜店中。 店员小Q看到小艺酱可怜的样子，允许小艺酱免费占卜一次。 花瓣占卜： 1. 一瓣“在一起”，一瓣“不在一起”；开始的花瓣表示“在一起”。 2. 直到最后一个花瓣落地游戏结束。 3. 可以选择多朵花，选择撕一朵花就必须撕完。

题解

这道题只能说很玄学了，按理说，如果所有花的花瓣之和是奇数，那么题目所求就是所求的花瓣之和；否则减去最小的奇数才是满足题目所求；若是没有奇数则输出0。但是。。只能过70%，我不理解。

#include 
#include 
#include 
using namespace std;
int main() {int n;cin >> n;vector<int> a(n);int ans = 0;for (int i = 0; i < n; i++) {cin >> a[i];ans += a[i];}if (ans%2==1){cout << ans << endl;return 0;}sort(a.begin(), a.end());for (int i = 0; i < n; i++) {if (a[i] % 2 == 1) {ans -= a[i];cout << ans << endl;return 0;}}cout << 0 << endl;return 0;
}

复杂度分析

时间复杂度为$O(n)$，其中n为输入的花数。

第四题

题目描述

题目名称：拯救公主
在Flower Kingdom里，住着一位美丽的公主Ana，有一天Ana得了一种怪病，神医告知国王，在遥远的幽谷中有一种药能治愈Ana， 但是神医只有一份不完整的地图，地图的描述如下：
该地图的共有3行，第一行有m列，m为奇数，第二行有m+1列，第三行有m+2列；每一行用一个字符串表示，只有【两种字符】；‘.'表示草地，可以从它上面通过，‘*’表示岩石，每一行最多一个‘*’； 入口在左上角，由于在对角线方向上，因此即使对角线两边都有岩石，但是缝隙较大，人可以通过，故人可以向八个方向行走；
真实地图是由该地图的【每一行无限循环】得到的，这种神奇的药草就生长在第x行第y列的草地上,药草可能会在岩石上；国王决定派遣勇敢的骑士David前去寻找拯救公主的解药； 现在聪明的你是否知道David能否找到该药？

题解

额，这道题想表述的意思其实就是是否存在比第y列更靠左的一列全为岩石，若存在，我们可知无论如何都无法到达药草所在位置；若不存在，则可到达。题目中仍有表达不明确的地方，题面并没有明确说明长在石头上的药草无法采摘，但我记得自测数据中有一组体现出了这一点。
通过上面的分析，很简单的暴力方法就得出了，从1遍历到第y列即可，但y的最大值值好像是1e9吧，因此我们要找到复杂度更低的方法。如果仔细观察，很轻易就能发现，三行的组合是以m，m+1，m+2三个数字的最小公倍数为周期循环的，因而我们并不需要遍历到第y列就可以得到结果。

#include
using namespace std;
int main() {int t;cin >> t;while (t--) {int m, x, y;cin >> m >> x >> y;int a, b, d;for (int i = 0; i < m; i++) {char c;cin >> c;if (c == '*') a = i;}for (int i = 0; i < m + 1; i++) {char c;cin >> c;if (c == '*') b = i;}for (int i = 0; i < m + 2; i++) {char c;cin >> c;if (c == '*') d = i;}int p = y % (m+x-1);if (x == 1 && p == a+1) {cout << "NO" << endl;continue;}if (x == 2 && p == b+1) {cout << "NO" << endl;continue;}if (x == 3 && p == d+1) {cout << "NO" << endl;continue;}int flag = 1;for (int i = 1; i < y; i++) {if (i % m == a && i % (m+1) == b && i % (m+2) == d) {flag = 0;break;}if (i % m == 0 && i % (m+1) == 0 && i % (m+2) == 0) break;}if (flag) cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}

复杂度分析

时间复杂度为$O(t $\times$ LCM(m $\times$ (m+1) $\times$ (m+2))，其中t为查询次数，m为第一行的列数。

总结

题目总体不难，但是第三题30%数据干扰了绝大部分人的做题思路与提交时间。若后续出现这种问题，希望官方能给出更合理的解决办法。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！