竞赛总览

竞赛题解

题目1、打家劫舍

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

#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]);
    for (int i = 2; i < n; i++) {
        int value = dp [i - 2] + data [i];
        dp [i] = value > dp [i - 1] ? value : dp [i - 1];
    }
    printf ("%d", dp [n - 1]);
    return 0;
}

动态规划练手题目。

首先，初始化结果数组的前两项。对于第一个房屋，最好的选择是直接偷，当前收益为第一个房屋的物品价值。对于第二个房屋，由于前面只有一个房屋，因此要比较一下第一个房屋和第二个房屋的相对价值，选择价值更高者。

之后，就可以套用递推公式了：f (n) = max (f (n - 2) + value (n), f (n - 1))。

题目2、小Q的鲜榨柠檬汁

团建活动是大家所想要的，小Q给大家准备了鲜橙汁。现在有n个朋友，买回了k瓶饮料（每瓶有l毫升），同时，还买回了c个柠檬（每个柠檬可以切成d片），以及p克盐。已知每个朋友需要nl毫升的饮料，一片柠檬，以及np克盐。小Q想知道每个朋友最少可以喝多少杯饮料。

#include <cstdio>

int main () {
    int n, k, l, c, d, p, nl, np;
    scanf ("%d %d %d %d %d %d %d %d", &n, &k, &l, &c, &d, &p, &nl, &np);
    result = k * l / nl / n;
    result = min (result, c * d / n);
    result = min (result, p / np / n);
    return 0;
}

入门级的题目，给出的变量很多，但难度不大。仔细读题就可以解决啦。

题目3、收件邮箱

已知字符串str，表示邮箱的不标准格式。其中点号会被记录成dot，艾特符号会被记录成at。写一个程序，将str转化成可用的邮箱格式（字符串中除了开头结尾所有dot都会被转换，at只会被转化一次，开头结尾的不转化）。

第28期竞赛原题。

使用正则表达式只需一行代码。

也可以用C++标准库std::string字符串类提供的find和substr方法对文本进行查找和拼接操作。

题目4、莫名其妙的键盘

有一个神奇的键盘，你可以用它输入a到z的字符。然而，每当你输入一个元音字母（a、i、e、o、u）的时候，已输入的字符串会发生一次反转！比方说，当前输入了tw，此时再输入一个o，屏幕上的字符串two会反转成owt。现给出一个字符串，若用该键盘输入，有多少种方法可以得到？

第56期竞赛原题。刚写过一次题解，这里不重复写了，感兴趣的小伙伴可以参考往期文章。