有点迷茫，刷题到底值不值得

从contest 48的结果看，国人刷题的水平远超三哥呀  

找工作需要，你说值不值

pinpindatou 发表于 2017-9-4 12:42
非常感谢逐条的回复，受益良多！

楼主，不好意思歪楼了，我想对上周那个关灯的题目再讨论一下。这道题我也没做出来当时（我的想法是用位运算xor开关灯 然后搜索 最后去重。现在AC了，但是位运算基础不好，想了很久当时没有来得及做完。）
后来看discussion 几乎全部都在说是数学题 brain teaser 有些人甚至给出了简单地直接解： 当XXX时 return XXX 这种。

你觉得 如果面试的时候面试官出了这个题目，面试的意图是什么呢？ 真的是希望我们观察规律证明这个规律正确并给出数学解吗？ 如果我们一开始用XOR的方法做出来了，面试官会不会说 你这个太繁琐了你看看还有没有数学解法？

有的时候做搜索或者dp 我挺能理解面试官要什么的，比如dp 一来看你观察能力强不强 二来看能不能短时间转化为正确的code  但是对于这种题我真的不知道搞懂数学解 怎么能举一反三到其他问题上，反而觉得像是贪心的题目，一题一解，想到了就是想到了，想不到就是死。

stargazer 发表于 2017-9-5 00:13
从contest 48的结果看，国人刷题的水平远超三哥呀

三哥不看这个 他们看Geeksforgeeks的。。。。我们学校都是。。。

2011051305 发表于 2017-9-4 11:45
这个我其实也挺惊讶的 最后一道题其实不算是传统的算法题 是个数学题，这么多人能在这么短时间找到数学规 ...

不是把，我就是直接按一个典型的memorization的dp题做的，没找啥数学规律也ac了。
唯一trick是m=min(m,4)，要不然会TLE...

Tsien 发表于 2017-9-5 01:42
不是把，我就是直接按一个典型的memorization的dp题做的，没找啥数学规律也ac了。
唯一trick是m=min(m,4 ...

我是把那四个按键方法 用xor的方式表达出来，每次按钮 四个方法都试一遍，结果放到set里去重 m次按完之后直接把set的size返回。。。 也过了。

但是那个数学解法。。。。我看了好几个帖子 没有看懂！！ 有一个人说什么六个灯之后的结果完全重复 根本就没懂他啥意思。。。。 可能是英语不好？  醉了！

第四道题我一开始是用 brute force做出来的，六个灯以后完全重复的意思是：你把每个开关控制的灯的index画出来，就可以发现1-6 , 7-12, 13-18都是重复一样的，以此类推，所以只要解前6个就可以了。后来看答案又发现其实解前三个就好了，因为如果你把奇偶开关互换，1-3 和4-6也是重复的，并没有增加自由度。想明白了这个以后，就可以穷举所有可能的结果了。

这类题我觉得在限定时间内一开始就能想出完美数学解是不容易的，先用brute force测测，慢慢找规律不妨是个好办法，面试中也是这样。

第四道题我解出来时用的还真不是数学方法。我当时觉得那四个条件可以将灯划为六个一组。因为这四种操作会使得每个组的灯的情况都是一致的。所以可以将灯的数目简化到六个之内。之后我就是用bit manipulation（就几个灯很适合这么做）和一个hashset做出这道题并AC的。

实际上在竞赛那种紧张的环境里想出数学解法不是一件容易事，我看到那些排名靠前的人他们也有用到我说出来的解法来解决这道题的。

2011051305 发表于 2017-9-5 01:44
我是把那四个按键方法 用xor的方式表达出来，每次按钮 四个方法都试一遍，结果放到set里去重 m次按完之后 ...

我好像歪楼lol....

messfish 发表于 2017-9-5 02:34
第四道题我解出来时用的还真不是数学方法。我当时觉得那四个条件可以将灯划为六个一组。因为这四种操作会使 ...

是的 我看到discussion也说可以划分为六个一组 后面无论多少个灯 都是和这六个灯的亮灯status一直 但是我就是没懂怎么就能六个一组。。。。求解。。。。。。。。。。。