苍南具城乡建设局网站,教育类网站建设方案,国外优秀网页设计赏析,2008 iis 添加 网站 权限设置竞赛总览
CSDN 编程竞赛三十三期题解#xff1a;比赛详情 (csdn.net)
竞赛题解
题目1、奇偶排序
给定一个存放整数的数组#xff0c;重新排列数组使得数组左边为奇数#xff0c;右边为偶数#xff08;奇数和偶数的顺序根据输入的数字顺序排列#xff09;。
第七期竞赛…竞赛总览
CSDN 编程竞赛三十三期题解比赛详情 (csdn.net)
竞赛题解
题目1、奇偶排序
给定一个存放整数的数组重新排列数组使得数组左边为奇数右边为偶数奇数和偶数的顺序根据输入的数字顺序排列。
第七期竞赛原题。
#include cstdio
#include vectorint main () {int n; scanf (%d, n);std::vectorint 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 stringint 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。时间合法的定义为H23 M59。时间有多少种进制定义的方式依次打印出来。如果有无数种解输出-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上古原题代码懒得贴了自己搜索一下就可以找到很多代码。
