7.14的比赛要注意:
0. 摆好蒟蒻心态,不要自以为是。
1. 先打暴力再打正解,有助于思考与查错。
2. 首次思考时间控制在1h, 每一题都要保证至少思考20分钟。 不能在最后没事干了才想没想过的题目
2.1. 先把所有题都看一遍再思考,把握一下时间。
3. 记得多根据数据范围与问题想一下学过的算法。
第一题十分简单,有两种做法。
如果一个区间[l,r]他已经存满了,那么r再增大也对答案没有贡献。 直接增大l。
如果一个区间没有存满,那么继续增大r. 这样做是O(n)的。
然而一开始没有想到,打了O(n log n)的二分。 如果数据出到10^6就要被卡了。 出题人十分良心n<=500000
第二题画风突变。 先总结了一下题意,发现是给定串x,求从0到达x的最小步数。 因为异或取的次数肯定是0/1,所以先把所有方案叠出来10^6。 然后我就想建trie….
之后思路一直在先把所有方案预处理出来上,就没有想到比较一种比较暴力的方法。 因为原数只有10^6,所以不妨从0开始bfs,用这20+20=40个数转移。这样复杂度只有
第三题不可做,想了并查集与离线,都没什么收获 (然而正解是离线+分治)
7.14的比赛要注意:
0. 摆好蒟蒻心态,不要有心理落差.
1. 先打暴力再打正解,有助于思考与查错。
2. 首次思考时间控制在1h, 每一题都要保证至少思考20分钟。
3. 记得多根据数据范围与问题想一下学过的算法。
4. 不要被自己的思路带跑(看到类原题十分激动?),当想了十几分钟没什么想法的时候,考虑回溯。
5. ~早上不要喝茶,吃成白白一定要在七点前起床! 最好预定!