建设mylove卡网站,wordpress获取菜单链接,网站设计公司哪家比较好,wordpress视频不全屏播放竞赛总览
CSDN 编程竞赛二十九期#xff1a;比赛详情 (csdn.net)
竞赛题解
题目1、订班服
小A班级订班服了#xff01;可是小A是个小糊涂鬼#xff0c;整错了好多人的衣服的大小。小A只能自己掏钱包来补钱了。小A想知道自己至少需要买多少件衣服。
#include cstdio…竞赛总览
CSDN 编程竞赛二十九期比赛详情 (csdn.net)
竞赛题解
题目1、订班服
小A班级订班服了可是小A是个小糊涂鬼整错了好多人的衣服的大小。小A只能自己掏钱包来补钱了。小A想知道自己至少需要买多少件衣服。
#include cstdio
#include iostream
#include string
#include vectorint search (std::vectorstd::string data, std::string str) {int result 0;for (int i 0; i data.size (); i) {if (data [i] str) result 1;}return result;
}int main () {int result 0;int n;scanf (%d, n);std::vectorstd::string data [2];for (int i 0; i 2; i) {for (int j 0; j n; j) {std::string str;std::cin str;data [i].push_back (str);}}std::string str [] {M, S, L, XL, XLL, XLLL, XLLLL, XLLLLL};for (int i 0; i 8; i) {int num search (data [0], str [i]) - search (data [1], str [i]);result num 0 ? num : - num;}printf (%d, result / 2);return 0;
}
此题通过比较两个列表的差异即可计算出答案。
例如M、S、L被改为了M、S、XL逐个计算每种型号出现的次数M1M2S1S2L11但L20所以检测出L这里出错1次。然而检测到XL时XL10、XL21这里也出错一次。
这样扫描一遍之后实际上L被改为了XL但一次更改被统计了两次所以还要除以2才能得到最终答案。
题目2、争抢糖豆
抓糖豆小Q与小K都喜欢吃糖豆。但是糖豆分两种超甜糖豆和普通糖豆。现在有w个超甜糖豆和b个普通糖豆。小Q和小K开始吃糖豆他们决定谁先吃到超甜糖豆谁就获胜。小K每次吃的时时候会捏碎一颗糖豆。小Q先吃小Q想知道自己获胜的概率。如果两个人都吃不到超甜糖豆小K获胜。
#include cstdiodouble dp [1005][1005];int main () {int w, b;scanf (%d %d, w, b);for (int i 1; i w; i) dp [i][0] 1;for (int i 1; i b; i) dp [0][i] 0;for (int i 1; i w; i) {for (int j 1; j b; j) {dp [i][j] (double) i / (i j);dp [i][j] j 1 ? (double) j / (i j) * (j - 1) / (i j - 1) * i / (i j - 2) * dp [i - 1][j - 2] : 0;dp [i][j] j 2 ? (double) j / (i j) * (j - 1) / (i j - 1) * (j - 2) / (i j - 2) * dp [i][j - 3] : 0;}}printf (%.9lf, dp [w][b]);return 0;
}
这道题目结合了动态规划和博弈论的知识但分析过程不是很难属于中等难度的题目。
用一个二维数组进行存储第一个维度表示超甜糖豆数量第二个维度表示普通糖豆数量元素值表示当前情况下吃到超甜糖豆的概率。
初始化时只有超甜糖豆情况下获胜概率为1只有普通糖豆情况下获胜概率为0。
对于w个超甜糖豆和b个普通糖豆吃到超甜糖豆的概率可以表示为w/(wb)。
这里就要用到博弈论的知识了首先从1个超甜糖豆和1个普通糖豆这种情况考虑可以计算出这种条件下的获胜概率。超甜糖豆和普通糖豆之一的数量超过1时可以通过游戏过程转移到这种情况。
游戏开始时小Q先吃糖豆。如果小Q没胜利小K机器人会执行最优策略且执行操作之后要么就是小K胜利要么就是游戏未结束又轮到小Q操作。整个过程中小K操作时是全自动的并且小K的操作取决于小Q之前一步的操作。只有轮到小Q操作时才有一次主动选择权虽然吃到的糖豆类型仍是未知的但可以按照下棋的这种思想来分析。
小Q吃到超甜糖豆游戏就会结束概率为w/(wb)。
没吃到超甜糖豆的概率为b/(wb)。这时小K会开始吃他也没吃到超甜糖豆游戏才会继续下去否则就结束了。小K吃的时候会捏碎一颗糖豆这时说明他已经将要吃的糖豆拿到了而不是捏完再吃。因此当两个人都没吃到超甜糖豆时游戏继续概率为b/(wb) * (b-1)/(wb-1)。
游戏继续时分两种情况捏碎超甜糖豆和捏碎普通糖豆。
捏碎超甜糖豆概率为w/(wb-2)捏碎普通糖豆概率为(b-2)/(wb-2)。
游戏继续相对上一回合糖豆数已经变少。这时可以使用动态规划算法套用之前算出来的概率提升计算效率。
整个分析过程到此结束其实这道题目并不是很难但比较考验博弈论分析的基本功。
题目3、走楼梯
现在有一截楼梯根据你的腿长你一次能走1级或2级楼梯已知你要走n级楼梯才能走到你的目的楼层请实现一个方法计算你走到目的楼层的方案数。
#include cstdiolong long int dp [1005] {1, 1, 2};int main () {for (int i 3; i 1005; i) dp [i] dp [i - 1] dp [i - 2];int n;scanf (%d, n);printf (%lld, dp [n]);return 0;
}
初始情况下位于0级楼梯到1级楼梯只能上1级。到2级楼梯可以011也可以直接02。
要上到更高级别的楼梯可以在前一级楼梯的基础上再上1级或者在前两级楼梯的基础上再上2级。
题目4、打家劫舍
一个小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算不触动警报装置的情况下一夜之内能够偷窃到的最高金额。
#include cstdioint dp [1005];int main () {int n;scanf (%d, n);int data [n];for (int i 0; i n; i) scanf (%d, data [i]);if (n 1) {printf (0);return 0;}if (n 1) {printf (%d, data [0]);return 0;}dp [0] data [0];dp [1] data [data [1] data [0] ? 1 : 0];for (int i 2; i n; i) {int val dp [i - 2] data [i];dp [i] val dp [i - 1] ? val : dp [i - 1];}printf (%d, dp [n - 1]);return 0;
}
经典的动态规划题目和上楼梯这道题的难度差不多。
