“Wishare杯”南邮第九届大学生程序设计竞赛之现场赛 部分题解

2024-03-20 12:58
文章标签 竞赛 部分 大学生 程序设计 题解 南邮 现场 第九届 wishare

本文主要是介绍“Wishare杯”南邮第九届大学生程序设计竞赛之现场赛 部分题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A. 年轮

时间限制: 2000ms  内存限制: 65536KB

题目描述：

荒草丛生的青春

倒也过的安稳

代替你陪着我的

是年轮

数着一圈圈的年轮

我认真

将心事都封存

 

            现在就让我们数一数一圈圈的年轮吧，由于年轮不一定是标准的圆形，为了方便，我们规定一圈年轮一定是一个凸多边形，且任意两圈年轮必然不会有交点，现在把年轮上的所有可见的点全部投影到一个平面直角坐标系上，请问最多能数出多少圈年轮？注: 有些顶点可能不在任何一圈年轮上(凸多边形的定义：把一个多边形的所有边中，任意一条边向两方无限延长成为一直线时，其他各边都在此直线的同旁，这样的多边形就是凸多边形)。

 

输入：

            第一行为一个整数T(1<=T<=5)代表数据组数，每组数据第一行为一个整数n(3<=n<=1000)，接下来n行，每行两个实数，代表一个点的坐标，坐标的绝对值不超过10^6。

 

输出：

            对于每组数据输出一个数字代表最多能数出的年轮圈数，如果一圈都数不出来输出”unlucky!” (引号不用输出)。

 

样例输入：

2

9

1.00 1.00

6.001.00

2.003.00

3.002.00

5.003.00

4.003.00

3.004.00

1.005.00

6.005.00

3

1.002.00

2.002.00

3.002.00

 

样例输出：

2

unlucky!

 

提示：

第一个样例中的两圈年轮为

{(1.00,1.00), (1.00, 5.00), (6.00, 1.00), (6.00, 5.00)}

{(2.00,3.00), (3.00, 2.00), (5.00, 3.00), (3.00, 4.00)}

 

题目分析：一层层求凸包

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const MAX = 1e5;struct POINT {double x, y;int id;
}base, p[MAX], stk[MAX];
bool vis[MAX];
int n, top;double getDist(POINT p1, POINT p2) {return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}double getCross(POINT p0, POINT p1, POINT p2) {return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}bool cmp(POINT p1, POINT p2) {if (getCross(base, p1, p2) == 0) {return getDist(base, p1) < getDist(base, p2);}return getCross(base, p1, p2) > 0;
}void getBase() {base.x = p[0].x;base.y = p[0].y;int pos = 0;for (int i = 1; i < n; i ++) {if (p[i].y < base.y || (p[i].y == base.y && p[i].x < base.x)) {base.x = p[i].x;base.y = p[i].y;pos = i;}}swap(p[0], p[pos]);
}bool getConvexHull() {if (n < 3) {return false;}sort(p + 1, p + n, cmp);  stk[0] = p[0];  stk[1] = p[1];  top = 1;  bool flag = false;for (int i = 2; i < n; i ++) {  while (top > 0 && getCross(stk[top - 1], stk[top], p[i]) < 0) {  top --;  }  if (top > 0 && getCross(stk[top - 1], stk[top], p[i]) > 0) {flag = true;}stk[++ top] = p[i];  }  if (top > 1 && flag) {for (int i = 0; i <= top; i ++) {vis[stk[i].id] = true;}return true;}return flag;
}void Delete() {int cnt = 0;for (int i = 0; i < n; i ++) {if (!vis[p[i].id]) {p[cnt ++] = p[i];}}n = cnt;memset(stk, 0, sizeof(stk));memset(vis, false, sizeof(vis));
}int main() {int T;scanf("%d", &T);while (T --) {scanf("%d", &n);memset(vis, false, sizeof(vis));for (int i = 0; i < n; i ++) {scanf("%lf %lf", &p[i].x, &p[i].y);p[i].id = i;}getBase();int ans = 0;while (getConvexHull()) {ans ++;Delete();getBase();} if (ans == 0) {printf("unlucky!\n");} else {printf("%d\n", ans);}}
}


E. 冷翻大师

时间限制：1000ms   内存限制：65536KB

题目描述：

            德州扑克AI冷扑大师完胜中国龙之队的事让南邮ACM协会的成员们热血沸腾，他们也想做一个AI程序，但由于德州扑克的规则太复杂，于是他们自己发明了一个翻牌游戏，一共有n张gain牌和m张loss牌，所有牌的反面均相同，现将这n+m张牌反面朝上随机打乱后放在桌上，每位玩家的初始得分都是0且均知道gain牌和loss牌的数量，一次可随意抽取若干张牌，也可以选择一张不抽，抽到gain牌得1分，抽到loss牌扣1分，选完一轮后记下分数作为该玩家本次游戏的最终得分，然后继续将这n+m张牌打乱换下一个玩家抽，所有玩家都抽完，谁得分最高谁获胜。该AI程序将被命名为冷翻大师，完成冷翻大师的编写前，请你帮成员们计算出在玩家每次都使用最优策略的情况下，一轮抽牌的得分期望。(设X1, X2, …, Xn为离散型随机变量，P(X1), P(X2), …, P(Xn)为变量对应事件发生的概率，则期望E(X)=X1*P(X1)+X2*P(X2)+…+Xn*P(Xn) )

 

输入：

            第一行为一个整数T代表数据组数，每组数据包含两个整数n和m

(1<=T<=5,0 <= n, m <= 1000)

 

输出：

            对于每组数据输出一个数字代表得分期望，要求保留4位小数(四舍五入)

 

样例输入：

3

1 0

1 1

0 1

 

样例输出：

1.0000

0.5000

0.0000

 

提示：

第二组数据中若先抽到gain牌，得1分，因知道还剩一张loss，必不会继续抽，相反如果先抽到loss，必会去抽第二次，总得分为0，所以E=0.5*1+0.5*0=0.5


题目分析：简单期望dp，dp[i][j]，还剩i张gain和j张loss的得分期望，转移方程不难推，见程序

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const MAX = 1e3 + 5;
double dp[MAX][MAX];int main() {int T, n, m;scanf("%d", &T);for (int ca = 1; ca <= T; ca ++) {memset(dp, 0, sizeof(dp));scanf("%d %d", &n, &m);for (int i = 0; i <= n; i ++) {for (int j = 0; j <= m; j ++) {if (i == 0) {continue;} else if (j == 0) {dp[i][j] = dp[i - 1][j] + 1;} else {double gain = (dp[i - 1][j] + 1) * ((1.0 * i) / (1.0 * (i + j)));double loss = (dp[i][j - 1] - 1) * ((1.0 * j) / (1.0 * (i + j)));dp[i][j] = max(dp[i][j], gain + loss);}}}printf("%.4f\n", dp[n][m]);}
}


F．人民的名义

时间限制: 3000ms   内存限制:65536KB

题目描述：

提前给大家剧透一下”人民的名义的大结局”，检察官候亮平收到一封匿名信，信中暗含了所有贪官的名字，但是为了保密，名字没有直接写出来，信中给的是一个语料库和若干行字符串，每行字符串中分别暗含了一个贪官的名字，你需要根据语料库通过分词来解析字符串中暗含的信息，比如语料库{“gao”,”yu”,”liang”,”li”,”ang”}，字符串为gaoyuliang，所有被解析出来的内容为”gaoyu liang”和”gao yu li ang”，现在请你帮助检察官侯亮平解析这封匿名信。

 

输入：

每个测试文件仅包含一组数据，输入第一行为一个整数n(1 <= n <= 1000)，代表语料库字符串个数，第二行输入n个互不相同的字符串代表语料库(最长的字符串的长度不会超过30)，第三行为一个要被解析的字符串(长度不超过100)，语料库和待解析的字符串均只含小写字母。

 

输出：

对每个要被解析的字符串，解析结果的每两个单词或拼音间用一个空格隔开，将解析的结果作为一个整体(含空格)按照字典序从小到大输出(字典序排序：两个字符串依次按照对应位的Ascii码值比较，如果首字符相同则比较第二个，第二个相同则比较第三个，依次类推，比如b>a，ab>aa，aab>aaa)，若无法解析出任何信息，输出”nothing!”(引号不用输出)

 

样例输入：

5

gao yuliang li ang

gaoyuliang

 

样例输出：

gao yuli ang

gao yuliang

 

题目分析：就是让分词，DFS搞，预处理记录一下以某个位置结尾的单词，然后搜一搜就可以了，也可以用trie维护

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <string>
#include <iostream>
using namespace std;vector<string> dp[200];void DFS(int pos, vector<string>& ans, vector<string>& tmp) {if (pos == 0) {int tmpSize = tmp.size();string cur = tmp[tmpSize - 1];for (int i = tmpSize - 2; i >= 0; i --) {cur += " ";cur += tmp[i];}ans.push_back(cur);return;}int sz = dp[pos].size();if (sz) {for (int i = 0; i < sz; i ++) {tmp.push_back(dp[pos][i]);DFS(pos - dp[pos][i].size(), ans, tmp);tmp.pop_back();}}
}vector<string> wordBreak(string s, vector<string> wordDict) {vector<string> ans;int len = s.size();dp[0].push_back("");for (int st = 0; st < len; st ++) {if (dp[st].size() > 0) {for (int i = 0; i < wordDict.size(); i ++) {string cur = wordDict[i];int ed = st + cur.size();if (ed <= len) {if (s.substr(st, ed - st) == cur) {dp[ed].push_back(cur);}}}}}if (dp[len].size() == 0) {return ans;}vector<string> tmp;DFS(len, ans, tmp);return ans;
}vector<string> vt;
string str;
int m;int main() {scanf("%d", &m);string tmp;for (int i = 0; i < m; i ++) {cin >> tmp;vt.push_back(tmp);}cin >> str;int len =str.length();vector<string> ans = wordBreak(str, vt);if (ans.size() == 0) {printf("nothing!\n");} else {sort(ans.begin(), ans.end());for (int i = 0; i < ans.size(); i ++) {cout << ans[i] << endl;}}
}


G. 中韩大战之人浪

时间限制：2000ms        内存限制65536KB

题目描述：

            世界杯预选赛亚洲区12强赛，中国队1:0领先韩国队的时候全场的中国球迷都沸腾了，他们玩起了人浪，所谓人浪就是观众以排为单位依照顺序起立举手再坐下，呈现类似波浪的效果，为简单起见，我们称某个位置比两边都高的为浪尖。已知体育场有n排座位，每排可以坐m个人，现给出某一时刻各排人浪的状态，请计算出最多的浪尖个数及浪尖最多的排号。假设足球场的观众席是圆形的且比赛时座无虚席。

 

输入：

            每个测试文件仅包含一组数据，输入第一行为两个整数n (1 <= n <= 1000)和m (3 <= m <=1000)，接下来输入共n行，每行m个实数，第i行的第j个数字h[i][j]表示第i排的第j个观众当前的高度，(1.00<=h[i][j] <= 6.00)

 

输出：

            输出两个数字，分别代表最多的浪尖个数及其所对应的排号，最多浪尖个数不止一排的时候，输出总高度最高那排的排号，若总高度也相同，则输出最大的排号，若这n排一个浪尖都没有，则输出”unbelievable!” (引号不用输出)。

 

样例输入：

2 4

1.002.00 3.00 4.00

2.004.00 1.00 3.00

 

样例输出：

2 2

 

提示：

本题数据量较大，输入请使用scanf


题目分析：C语言课后作业难度，输出讨论情况较多

#include <cstdio>
int const MAX = 1005;
double a[MAX][MAX];int main() {int n, m, ans = 0, id = 0;double maSum = 0;scanf("%d %d", &n, &m);for (int i = 1; i <= n; i ++) {int cnt = 0;double sum = 0;for (int j = 1; j <= m; j ++) {scanf("%lf", &a[i][j]);sum += a[i][j];}if (a[i][1] > a[i][m] && a[i][1] > a[i][2]) {cnt ++;}for (int j = 2; j < m; j ++) {if (a[i][j] > a[i][j - 1] && a[i][j] > a[i][j + 1]) {cnt ++;}}if (a[i][m] > a[i][1] && a[i][m] > a[i][m - 1]) {cnt ++;}if (cnt > ans) {ans = cnt;id = i;if (sum > maSum) {maSum = sum;}} else if (cnt == ans && sum >= maSum) {maSum = sum;id = i;}}if (ans == 0) {printf("unbelievable!\n");} else {printf("%d %d\n", ans, id);}
}


这篇关于“Wishare杯”南邮第九届大学生程序设计竞赛之现场赛 部分题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/829522。

相关文章

Javascript高级程序设计(第四版)--学习记录之变量、内存

Javascript高级程序设计(第四版)--学习记录之变量、内存

原始值与引用值 原始值：简单的数据即基础数据类型，按值访问。 引用值：由多个值构成的对象即复杂数据类型，按引用访问。 动态属性 对于引用值而言，可以随时添加、修改和删除其属性和方法。 let person = new Object();person.name = 'Jason';person.age = 42;console.log(person.name,person.age);//'J
阅读更多...
LeetCode11. 盛最多水的容器题解

LeetCode11. 盛最多水的容器题解

LeetCode11. 盛最多水的容器题解 题目链接： https://leetcode.cn/problems/container-with-most-water 示例 思路 暴力解法 定住一个柱子不动，然后用其他柱子与其围住面积，取最大值。 代码如下： public int maxArea1(int[] height) {int n = height.length;int
阅读更多...
android一键分享功能部分实现

android一键分享功能部分实现

为什么叫做部分实现呢，其实是我只实现一部分的分享。如新浪微博，那还有没去实现的是微信分享。还有一部分奇怪的问题：我QQ分享跟QQ空间的分享功能，我都没配置key那些都是原本集成就有的key也可以实现分享，谁清楚的麻烦详解下。 实现分享功能我们可以去www.mob.com这个网站集成。免费的，而且还有短信验证功能。等这分享研究完后就研究下短信验证功能。 开始实现步骤（新浪分享，以下是本人自己实现
阅读更多...
【计算机组成原理】部分题目汇总

【计算机组成原理】部分题目汇总

计算机组成原理 部分题目汇总 一. 简答题 RISC和CICS 简要说明，比较异同 RISC（精简指令集）注重简单快速的指令执行，使用少量通用寄存器，固定长度指令，优化硬件性能，依赖软件（如编译器）来提升效率。 CISC（复杂指令集）包含多样复杂的指令，能一条指令完成多步操作，采用变长指令，减少指令数但可能增加执行时间，倾向于硬件直接支持复杂功能减轻软件负担。 两者均追求高性能，但RISC
阅读更多...
LeetCode：经典题之141、142 题解及延伸

LeetCode：经典题之141、142 题解及延伸

系列目录 88.合并两个有序数组 52.螺旋数组 567.字符串的排列 643.子数组最大平均数 150.逆波兰表达式 61.旋转链表 160.相交链表 83.删除排序链表中的重复元素 389.找不同 1491.去掉最低工资和最高工资后的工资平均值 896.单调序列 206.反转链表 92.反转链表II 141.环形链表 142.环型链表 目录 系列目录141. 环形链表常量因子 1
阅读更多...
C语言 | Leetcode C语言题解之第188题买卖股票的最佳时机IV

C语言 | Leetcode C语言题解之第188题买卖股票的最佳时机IV

题目： 题解： int maxProfit(int k, int* prices, int pricesSize) {int n = pricesSize;if (n == 0) {return 0;}k = fmin(k, n / 2);int buy[k + 1], sell[k + 1];memset(buy, 0, sizeof(buy));memset(sell, 0, size
阅读更多...
6月21日训练 (东北林业大学)（个人题解）

6月21日训练 (东北林业大学)（个人题解）

前言：   这次训练是大一大二一起参加的训练，总体来说难度是有的，我和队友在比赛时间内就写出了四道题，之后陆陆续续又补了了三道题，还有一道题看了学长题解后感觉有点超出我的能力范围了，就留给以后的自己吧。话不多说，上正文。 正文：   Problem:A 幸运数字： #include <bits/stdc++.h>using namespace std;int sum,ans;in
阅读更多...
LeetCode：经典题之389 题解与延伸

LeetCode：经典题之389 题解与延伸

系列目录 88.合并两个有序数组 52.螺旋数组 567.字符串的排列 643.子数组最大平均数 150.逆波兰表达式 61.旋转链表 160.相交链表 83.删除排序链表中的重复元素 389.找不同 1491.去掉最低工资和最高工资后的工资平均值 896.单调序列 206.反转链表 92.反转链表II 141.环形链表 142.环型链表 目录 系列目录389.找不同哈希表
阅读更多...
大学生自救数据结构与算法（py实现）——01递归

大学生自救数据结构与算法（py实现）——01递归

目录 目录 递归 基本概念 工作原理 基本要素 优点 缺点 实现技巧 实例解析：计算阶乘 斐波那契数列 高效的斐波那契数列 python中的最大递归深度 二分查找 基本原理 性能分析 优化与变体 线性递归  元素序列的递归求和 二路递归 二路递归的基本概念 典型应用 工作原理 多重递归  示例：计算卡特兰数（Catalan Number） 尾递
阅读更多...
Google Code Jam 2014（附官方题解）

Google Code Jam 2014（附官方题解）

2014年Google编程挑战赛 Problem A. Magic Trick Confused? Read the quick-start guide. Small input 6 points You have solved this input set. Note: To advance to the next rounds, you will need to s
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2