前言
四道题, 分别锻炼
哈希, 贪心, 贪心 + 排序, 二分
四个能力.
第一题较为简单, 后续的题目都需要一定的基础.
贪心是最基础的能力, codeforce 有专门的
Tag 用以描述, 叫做 greedy;
二分是常用的一种降低时间复杂度方法, 前提的要求是单调性;
哈希和排序是工程中常见的处理, 前者用于映射, 后者用于数据有序化.
这四个能力也多用于面试的算法题, 因为其属于基础能力.
正文
1.Santa Claus and Keyboard Check
题目链接 http://codeforces.com/contest/752/problem/B
题目大意:
小明把键盘的键都卸下来清洗, 在装回去后, 发现有些键装错了.
他看着键盘, 打出一个字符串 str, 在屏幕显示出来一个字符串 str';
现在他可以选择任意两个键, 交换它们的位置, 但是每个键只能交换一次;
问, 小明是否能复原正确的键盘?
如果可以, 先输出交换次数, 接下来每行输出每次交换的字母;(顺序无关)
如果不可以, 直接输出 - 1.
输入数据:
str 长度不超过 1000;
- Examples
- input
- helloworld
- ehoolwlroz
- output
- 3
- h e
- l o
- d z
- input
- merrychristmas
- christmasmerry
- output
- -1
题目解析:
题目有个很重要的条件, 每个键只能使用一次.
那么每次当遇到字符不同的时候, 这两个字符就必须交换; 如果这个字符已经交换过, 那么无解.
实现逻辑, 可以用一个简单字符 hash 来实现, 对 str 的字符, 每次先判断是有 hash 字符, 如果有则转成 hash 后的符;
如果没有, 添加 hash[c]=c; 保证下次再遇到不会出错;
然后进行判断, 如果 hash 后的字符和 str'上的不对应, 则无解;
2.Santa Claus and Robot
题目链接 http://codeforces.com/contest/752/problem/C
题目大意:
有一个机器人, 在一个网格的网格线上行走, 每次有 L/R/U/D 四个方向;
当机器人从点 p1 走到点 p2 时, 它会走最短的路径.
如果有 3 个点 p1,p2,p3, 机器人会按照最短的路径走向 p1 点, 到达后再走向 p2 点, 再到 p3 点;
现在假设机器人在原点, 已知机器人走的序列(长度为 n), 求最少有几个点, 可以满足机器人走的序列.
输入数据:
- n (1n2.105)
- Examples
- input
- 6
- RRULDD
- output
- 2
- input
- 26
- RRRULURURUULULLLDLDDRDRDLD
- output
- 7
题目解析:
看似很难, 仔细分析一下, 只要找到两点之间路径的规律即可.
当出现过 R 之后, 本次路径, 就不允许再出现 L, 同理 L,U,D;
这样, R,L 之间算一条路径, U,D 之间算一条路径, 加起来就是需要的最小点数.
3.Santa Claus and a Palindrome
题目链接 http://codeforces.com/contest/752/problem/D
题目大意:
k 个字符串, 长度均为 n;
每个字符串有一个权值 a[i];
现在可以从 k 个字符串中, 选择若干个字符串拼成一个新的回文串 str, 要求每个字符串只能用一次, 并且不能改变原有字符串的字符排列顺序;
str 的权值为所有拼成的串的权值和, 求 str 的最大权值.
(注意, 空串也是回文串, 所有 str 的最大权值不小于 0)
输入数据:
- 1k,n100000; n.k 100000
- -10000a[i]10000
- Examples
- input
- 7 3
- abb 2
- aaa -3
- bba -1
- zyz -4
- abb 5
- aaa 7
- xyx 4
- output
- 12
样例解释: 最后的结果是 abbaaaxyxaaabba, 组合第 5, 2, 7, 6 和 3 字符串.
题目解析:
每个字符串分两种, 第一种是自身为回文, 第二种是自身不为回文.
自身为回文串有两种选择, 放在中心点 (单独一个) 和不放在中心点(两两配对分在左右);
自身不为回文串的字符串 str, 可以和 str 的 reverse 组合回文串;(比如 abc 和 cba)
我们把字符串相同的放到同一个桶, 把桶按照字符串是否为回文分成两类.
对于非回文串 str, 每次从 str 的桶里找一个最大的 key 值 x, 再从 reverse(str)的桶里找一个最大的 key 值 y, 只要 x+y>0, 那么就组成一个匹配;
对于回文串 paliStr, 每次从 paliStr 的桶里找 key 值最大的两个 x 和 y, 如果 x+y>0, 那么就组成一个匹配;
这里有个 trick: 因为 paliStr 还可以单独放在中间, 如果 paliStr 的两个权值是 - 3 和 5, 那么选中 - 3 其实是不划算的.
但是如果只选择 x>0&&y>0 的话, 假设有多个 - 3 和 5 的组合, 就会失去 - 3+5=2 的额外收益.
抉择是根源是在于 paliStr 可以选择放在中间! 但是中间其实只能有一个字符串.
于是可以采取额外补偿的方式, 我们还是采用 x+y>0 的选择, 但是保留一个 addition 的收益, 类似 - 3 和 5 的组合, addition 的收益是 3;
同理, 如果只剩下一个回文串, 那么 addition 的收益是该回文串.
最后计算所有的收益和 + addition 收益得到答案.
思考:
更好理解 addition 的方式, 是把组合看成单体的, 比如说 pair(-3, 5), pair(2, 3); 把剩下的单个, 也视为单体;
然后从所有的单体中选择一个, 放入中间的收益.
4.Santa Claus and Tangerines
题目链接 http://codeforces.com/contest/752/problem/E
题目大意:
给出 n 个数字 a[i], 要分给 k 个人;
数字 a[i]可以平分, 如果是奇数, 那么会分成 a[i]/2 和 a[i]/2 + 1;
每个人只能分得一个数字, 问所有人中最小的数字的最大值是多少?
如果不够分, 那么输出 - 1;
输入数据:
- n and k (1n1e6, 1k2.1e9)
- 1a[i] 1e7
- Examples
- input
- 3 2
- 5 9 3
- output
- 5
- input
- 2 3
- 1 1
- output
- -1
题目解析:
分出 k 个数, 保证最小值尽可能大;
第一想法是二分答案, 假设最后的结果是 ans, 对于数字 x,while(x/2>=ans), 对数字 x 进行平分;
假设 num[x]表示数字 x 的数量, 如果 x/2>=ans, 那么有 num[x/2] += num[x], num[x - x/2] += num[x];
最后再统计所有数字比 ans 大的数字数量, 判断是否大于 k;
复杂度为二分复杂度 log(1e7) * 枚举平分复杂度(1e7) =24*1e7=2.4e8 的复杂度;
因为题目给的时限为 2s, 勉强可以完成;
思考:
另一种更优雅的方案.
以数字 21 为例, 如果 ans[11, 21]这一区间,>ans 的数字只有一个;
如果 ans=10 时, 就能算两个数字;(因为 21 可以拆分为 10+11)
数字 x, 可以切分为数字较小的部分 x/2 和数字较大的部分 (x-x/2), 我们用 a[x] 来表示数字 x 的个数, b[x]表示当 x 拆分时 (x-x/2) 的数量;
当 ans>(x-x/2)时, x 的拆分没有额外收益;
当 ans<=x/2 时, x 的拆分相当于多出来一个数字 a[x/2];
于是有:
- a[x/2] += a[x]+b[x];
- b[x-x/2] += a[x]+b[x];
核心代码很短, 如下:
- for (lld i = maxAns; i> 0; --i) {
- total += a[i];
- if (total>= k) {
- cout << i << endl;
- return 0;
- }
- else {
- a[i / 2] += a[i] + b[i];
- b[i - i / 2] += a[i] + b[i];
- }
- }
总结
基础能力在做一线开发的时候极为重要, 往往决定了综合能力的天花板.
实际开发中的各种性能优化, 功能系统的时间空间复杂度分析, 都是基于基本的算法能力.
算法是编程能力提升的必要条件, 做题只是学算法的一种实践手段.
而在业余时间越来越少的现在, 做题占用的是我的娱乐时间和学习时间. 如果一直停留在重复做类似题的境界, 对我的能力提升微乎其微.
所以我现在在做的事情是尝试用规范的方式去解决, 思考问题, 然后把这个过程用文字描述出来. 在保持思考习惯的同时, 提升描述能力和锻炼耐力.
来源: http://www.jianshu.com/p/e6f42030a69f