梦溪笔淡

· · 生活·游记

如果...

你们看到了这篇游记

那么说明...

我对于上周发的那一篇已经忍无可忍了

于是我进行了一些修改

原因如下：

1.一些信息需要补全

2.上篇的“梦的解析”板块是中文的，为了避免大家看的太懂，所以我将它改成了英文，以让大家误以为我没有精神类问题

正文

呵~

考完CSP-S已经好几天了，我终于 在老师的督促下 开始写游记liao

DAY -1

梦的解析

In a daze, I heard the gentle sound of footsteps very close by

Opening my eyes, I saw her in the distance

I want to hold her hand because she's right beside me

I watched her figure in the distance, and felt a gentle coolness in my outstretched hand, as if it had been brushed by a soft breeze

I couldn't touch her

I felt lost and looked around. It was as if she had never been there at all, as if she had simply hidden herself in the hazy mist

Where is she exactly?

I quickened my pace, almost running towards her distant figure

I must be faster than her because she is also moving forward

I suddenly stopped

Because I saw the figure slowly turn around

Without being able to see clearly, I was certain it was a beautiful face.

I can only describe it as “beautiful” because I can't find a more vivid phrase than this

Oh no! I tripped over something and was about to fall

But I still kept my eyes on her, refusing to look away

I seemed to catch a glimpse with my peripheral vision, and an inexplicable smile appeared at the corner of her mouth

But before falling to the ground, I only saw her eyes, a pair of beautiful eyes

上学

7:20 坚持到校 差点迟到 然后发现同班的XinJing大佬们都没来

8:20 准时下课去机房 没人、黑灯、锁门

调完一道陈年老题

10~11点 终于来人啦！人走了

做黄题增加信心！！！

。。。。怎么。。做不出来呀。。。。

12:40 成功从校门出逃

6:30 到达RZ

7:40 吃面（适合中国宝宝体质）

    什么？ 你说你想吃78的蟹酱面？
    可是它并没有32的海鲜面好吃

8:00 出发试机 并将爸爸弄丢

8:20 屏 幕 好 别 扭 啊

11:00 听音乐惬意入睡。。睡不着。。bie听了。。Z~~

DAY 1

7:00 响铃

8:00 起！！！！

9:30 吃饱了

看蓝书 。。。看不下去了。。。

看《 G M Z Z 》小说 。。。看不下去了。。。

看。。。（tarjan好好看啊）

12:00 好孩子都应该 睡午觉

1:40 与同学愉快交谈

yhc：你看《 S Y W Z 》了么？你看《 T S X K 》了么？

yxy：我猜 T1推理 T2图论 。。。我 not only 不会关同步流，but also 不会写快读快写

2:30 考试

T1

这不一眼贪心！ 。。。怎么贪啊

直接选最大？后期不好处理，而且一听就假

经过对样例的手模，发现选择与性价比有关 废话

性价比： 选当前部门贡献 - 另外两个部门贡献的最大值

手模样例发现正确

那么可以用 优先队列 维护 n个人类 的 3个性价比

将 pair<性价比，pair<部门，人类>> 扔进队列，然后枚举判断

时间复杂度 O(k n logn)

测样例，全部正确

问题： 写的时候，为了美观，将1个while 2个判断条件，拆成2个while各1个判断条件，但并没有意识到有何不妥。虽然，因某些性质，最后各平台的民间数据都过了，但仅限此题特殊，并不能因此忽视这一错误。

T2

说真的，考后看完正解，我现在越发觉得T2比T1简单，真的

看完题目名称那一刹那，我瞬间想起一道叫灾后重建的题，但看完题目发现并未存在太大关联。

养成马上看数据范围的好习惯，这样可以有效帮助你想出——

就没什么思路 就很有胃口

因为这个 k个村庄可建可不建 就hin烦

去掉这个不就是 最小生成树板子 了ma

但这个k怎么处理呢？？？

——————>> 枚举。。。

是的，因为k很小

然后 O(2^k m logm)

噫！我中了！。。。。32分

咳，其实还可以 （还是没什么品味）

去做 T3 T4 吧

问题： 显而易见的两个优化没有想

  1. 我使用的是优先队列维护边 实在是太爱了 ，导致每次都要把m多条边扔进去，完全可以预处理m+kn条边，然后再判能不能用（即若是 未选择的村庄 的边就不用），（当然，要将队列改为数组）

  2. 原树m条边，只有最小生成树的那n-1条有用，所以可以先预处理原树的最小生成树

    把这两个显而易见的优化结合，可以得到O(m logm + 2^k kn logkn)，卡卡就差不多了（起码民间超水数据是过了）

    T3

    打了个10分暴力，并努力加了很多优化

    包括但不限于 二分 剪枝 ，以致复杂度为 1e8 ，但远远跑不到

    T4

    打了8分暴力

    惊喜发现特性A好像很友善

    然后细心的我察觉到了一丝蹊跷，仔细看了数据范围——

    c可以为0

    时间分配

    T1：1h

    T2：1~1.5h

    T4：0.5h

    T3：1h

    记不太清了，起码T1是准的，T2记得大体范围，这就是我的做题顺序，先4再3

    分数

    赛后估计 100+32+10+8=150

    云斗 100+52+25+8=185

    洛谷 100+56+25+12=193

    海西省某中学OJ 100+40+30+8=178

    CCF 100+40+25+8=173

    那么，还是有个一等拿的

    最后

  3. 回复yhc，《 T S X K 》确实变好看了 终于不水了

  4. 送大家一朵 塞维亚菊，象征着快乐

  5. 其实还是很满意的，没出什么大的纰漏

  6. 祝大家都有好成绩，另外，NOIP RP++！！！