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

---