CSDN 编程竞赛二十九期题解

竞赛总览

CSDN 编程竞赛二十九期：比赛详情 (csdn.net)

竞赛题解

题目1、订班服

小A班级订班服了！可是小A是个小糊涂鬼，整错了好多人的衣服的大小。小A只能自己掏钱包来补钱了。小A想知道自己至少需要买多少件衣服。

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>int search (std::vector<std::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::vector<std::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，逐个计算每种型号出现的次数，M1=M2，S1=S2，L1=1但L2=0，所以检测出L这里出错1次。然而，检测到XL时，XL1=0、XL2=1，这里也出错一次。

这样扫描一遍之后，实际上L被改为了XL，但一次更改被统计了两次，所以还要除以2才能得到最终答案。

题目2、争抢糖豆

抓糖豆，小Q与小K都喜欢吃糖豆。但是糖豆分两种，超甜糖豆和普通糖豆。现在有w个超甜糖豆和b个普通糖豆。小Q和小K开始吃糖豆，他们决定谁先吃到超甜糖豆谁就获胜。小K每次吃的时时候会捏碎一颗糖豆。小Q先吃，小Q想知道自己获胜的概率。如果两个人都吃不到超甜糖豆小K获胜。

#include <cstdio>double 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/(w+b)。

这里就要用到博弈论的知识了，首先从1个超甜糖豆和1个普通糖豆这种情况考虑，可以计算出这种条件下的获胜概率。超甜糖豆和普通糖豆之一的数量超过1时，可以通过游戏过程转移到这种情况。

游戏开始时，小Q先吃糖豆。如果小Q没胜利，小K（机器人）会执行最优策略，且执行操作之后，要么就是小K胜利，要么就是游戏未结束，又轮到小Q操作。整个过程中，小K操作时是全自动的，并且小K的操作取决于小Q之前一步的操作。只有轮到小Q操作时，才有一次主动选择权（虽然吃到的糖豆类型仍是未知的，但可以按照下棋的这种思想来分析）。

小Q吃到超甜糖豆游戏就会结束，概率为w/(w+b)。

没吃到超甜糖豆的概率为b/(w+b)。这时小K会开始吃，他也没吃到超甜糖豆游戏才会继续下去，否则就结束了。小K吃的时候会捏碎一颗糖豆，这时说明他已经将要吃的糖豆拿到了，而不是捏完再吃。因此，当两个人都没吃到超甜糖豆时，游戏继续，概率为b/(w+b) * (b-1)/(w+b-1)。

游戏继续时，分两种情况：捏碎超甜糖豆和捏碎普通糖豆。

捏碎超甜糖豆，概率为w/(w+b-2)；捏碎普通糖豆，概率为(b-2)/(w+b-2)。

游戏继续，相对上一回合，糖豆数已经变少。这时，可以使用动态规划算法，套用之前算出来的概率，提升计算效率。

整个分析过程到此结束，其实这道题目并不是很难，但比较考验博弈论分析的基本功。

题目3、走楼梯

现在有一截楼梯，根据你的腿长，你一次能走1级或2级楼梯，已知你要走n级楼梯才能走到你的目的楼层，请实现一个方法，计算你走到目的楼层的方案数。

#include <cstdio>long 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级楼梯，可以0+1+1，也可以直接0+2。

要上到更高级别的楼梯，可以在前一级楼梯的基础上，再上1级；或者，在前两级楼梯的基础上，再上2级。

题目4、打家劫舍

一个小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

#include <cstdio>int 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;
}

经典的动态规划题目，和上楼梯这道题的难度差不多。