郑州 服装网站建设,吉林省城乡建设厅网站6,云南楚雄彝族自治州,wordpress 的论坛模板下载竞赛总览
CSDN 编程竞赛三十一期#xff1a;比赛详情 (csdn.net)
本次竞赛的最后一道题的描述部分有些问题#xff08;题目描述与样例不符#xff09;#xff0c;另外#xff0c;测试数据似乎也有点问题#xff0c;试了多种方式#xff0c;但最多只能通过10%的测试点。…竞赛总览
CSDN 编程竞赛三十一期比赛详情 (csdn.net)
本次竞赛的最后一道题的描述部分有些问题题目描述与样例不符另外测试数据似乎也有点问题试了多种方式但最多只能通过10%的测试点。竞赛体验较差希望之后的竞赛开始前能够对测试数据进行验证不要再发生这种情况了。
竞赛题解
题目1、最优利润值
你在读的经营课程上老师布置了一道作业。在一家公司的日常运营中会对一些商品的价格走势根据一些经验和数据进行预估并据此进行决策。例如假设某商品每天的价格都有可能变动我们要做的就是低买高卖获得最高利润。比如假设我们预估该商品接下来七天内的价格走势如下4 1 2 3 6 4 8那我们采取的最佳策略是在价格1块钱的时候买入在价格8块钱的时候卖出。为了简化整个过程我们限定在此周期内只能有一次买入、一次卖出且商品在没有购入前是无法卖出的即该商品不是期货而是现货。现要求你用程序来实现自动决策。输入一定天数的商品预估价格自动计算出最优利润值。例如上面的例子中最优利润值为8-17。为了简单起见只考虑0-100000之间的整数价格。
#include cstdioint data [100005];int main () {int result 0;int n 0;while (scanf (%d, data [n]) ! EOF) n;for (int i 0; i n; i) {for (int j i 1; j n; j) {int val data [j] - data [i];if (result val) result val;}}printf (%d, result);return 0;
}
题目2、开学趣闻之美食诱惑
小艺酱又开学了可是在上学的路上总会又各种意想不到的美食诱惑让小艺酱迟到。假设小艺酱家到学校是一个n*n的矩阵。每个格子包含一个诱惑值p诱惑着小艺让她迟到。小艺位于矩阵的左上角学校在矩阵的右下角。小艺想知道自己到达学校所要经历的最小诱惑值是多少。
#include cstdioint min (int a, int b) {if (a b) return a;return b;
}int main () {int n;scanf (%d, n);int data [n][n];for (int i 0; i n; i) {for (int j 0; j n; j) {scanf (%d, data [i][j]);}}int dp [n][n]; dp [0][0] data [0][0];for (int i 1; i n; i) dp [0][i] dp [0][i - 1] data [0][i];for (int i 1; i n; i) dp [i][0] dp [i - 1][0] data [i][0];for (int i 1; i n; i) {for (int j 1; j n; j) {dp [i][j] min (dp [i - 1][j], dp [i][j - 1]) data [i][j];}}printf (%d, dp [n - 1][n - 1]);return 0;
}
这个题型和动态规划初学者的例题一样非常经典不亚于打家劫舍系列学过动态规划的小伙伴应该都知道它的解法。
使用一个数组维护从原点到每个格子上的诱惑值第i行、第j列的那个格子可以从它的上面或者左面坐过来因此它的诱惑值为它上面和左面格子诱惑值的最小值加上它自己本身的诱惑值。
从原点开始不断扩大计算范围并将计算结果存储到数组中最后走到终点时即可得到答案。
题目3、小艺照镜子
回文串是一个正读和反读都一样的字符串。已知字符串str输出字符串str中最长回文串的长度。
#include cstdio
#include iostream
#include stringint match (std::string str) {int result 1;for (int i 0; i str.length (); i) {for (int j 0; j 2; j) {int left i - j, right i 1;while (left -1 right str.length () str [left] str [right]) {left--;right;}int len right - left - 1;if (result len) result len;}}return result;
}int main () {std::string str;std::cin str;printf (%d, match (str));
}
这道题之前也考过测试数据比较友好不需要使用马拉车算法。但也不能直接暴力否则复杂度为O(N^3)之前已经试过了会超时。可以使用中心扩展法完成此题。
题目4、爱吃鬼
小艺酱每天都在吃和睡中浑浑噩噩的度过。可是小艺酱的肚子是有空间上限v的。小艺酱有n种零食每包零食占据小艺酱肚子空间a [i]并会给小艺酱一个甜蜜值b [i]。小艺酱想知道在自己的肚子空间上限允许范围内最大能获得的甜蜜值是多少。
背包问题。测试数据有问题无法通过此题代码就不放了。
