CSDN 编程竞赛三十三期题解

竞赛总览

CSDN 编程竞赛三十三期题解：比赛详情 (csdn.net)

竞赛题解

题目1、奇偶排序

给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数（奇数和偶数的顺序根据输入的数字顺序排列）。

第七期竞赛原题。

#include <cstdio>
#include <vector>int main () {int n; scanf ("%d", &n);std::vector<int> even;while (n --> 0) {int data; scanf ("%d", &data);if (data % 2 == 1) printf ("%d ", data); else even.push_back (data);}for (int i = 0; i < even.size (); i++) printf ("%d ", even [i]);return 0;
}

解法很多。

解法1：遇到奇数直接输出；遇到偶数存起来，最后统一输出。

解法2：将奇数和偶数分别存到两个列表中，最后统一输出。

解法3：使用稳定的排序算法（稳定不是指算法结果固定，而是排序时不改变元素的相对顺序，例如两个同为1级的角色，但id不同，id大的在前面，如果使用稳定的排序算法，则按等级排序时，这两个相同级别的角色排序之后id依然保持原顺序，而不是变成id小的在前面）。可以魔改一下冒泡排序，完成此题。

解法4：自己挖掘一下吧，真的还有很多方法，思维活跃点可以想出来一大堆。

虽然这道题的解法很多，但博主选择了比较简单的写法，以便能够在更短的时间内通过此题。

题目2、小艺改编字符串

已知字符串str，添加至少多少字符可以使得str变成回文串。

第八期竞赛原题。

#include <cstdio>
#include <iostream>
#include <string>int inv [10005];
int dp [10005][10005];int max (int a, int b) {if (a > b) return a;return b;
}int main () {std::string str;std::cin >> str;int len = str.length ();for (int i = 0; i < len; i++) inv [i] = str [len - i - 1];for (int i = 1; i <= len; i++) {for (int j = 1; j <= len; j++) {if (str [i - 1] == inv [j - 1]) dp [i][j] = dp [i - 1][j - 1] + 1;else dp [i][j] = max (dp [i - 1][j], dp [i][j - 1]);}}printf ("%d", len - dp [len][len]);return 0;
}

有没有觉得这道题的代码和一道经典字符串动态规划问题的模板很像？

没错，在经典的LCS（最长公共子序列）问题中，状态转移方程也是这样的。

这道题把原字符串视为字符串1，将其逆序之后的结果视为字符串2，计算LCS结果。

最终答案为字符串长度减去LCS结果。

至于为什么可以这样做，留给读者自行思考。原因并不复杂，当突然想明白的时候，会有一种豁然开朗的感觉。

题目3、公司新表

公司里为了凸显公司的特性。安装了一个n进制表。已知新的表的时间是H:M。时间合法的定义为H<=23 && M<=59。时间有多少种进制定义的方式，依次打印出来。如果有无数种解输出-1，不存在输出0。

第十三期竞赛原题。

bool match (std::string str, int base) {int time [2] = {0, 0}, t = 0;for (int i = 0; i < str.length (); i++) {if (str [i] == ':') {t = 1;continue;}int x = (str [i] >= '0' && str [i] <= '9') ? (str [i] - '0') : (str [i] - 'A' + 10);if (x < base) time [t] = time [t] * base + x; else return false;}return time [0] < 24 && time [1] < 60;
}

最小的进制为2进制。对于时间来说，最大为60进制。依次校验2到60进制，将符合条件的值记录下来。全部判断完成之后，如果列表为空，输出0；如果60进制可用，输出-1（表示有无数种解）；否则，按顺序输出测试结果即可。

题目4、选择客栈

丽江河边有n家很有特色的客栈，客栈按照其位置顺序从1到n编号。每家客栈都按照某一种色调进行装饰（总共k种，用整数0到k-1表示）。且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一 家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过p元。他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过p元的咖啡店小聚。

第十五期竞赛原题。

NOIP上古原题，代码懒得贴了，自己搜索一下就可以找到很多代码。