Day -1

本来以为自己不会紧张的，结果今天早上就开始了。后来直到晚上心态渐渐好点了。想去看山水。

今天做了点题，大概也是有心无力了，紧张起来就很想笑。不过明天一定会万事顺利哒。元宵节快乐！

Day 0

我现在……非常地开心！因为我已经没有什么牵挂啦哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈。

精神状态堪忧……。意思就是今天的题目很难的啦。今天早上天气还挺好的。考完之后很轻松，其实我在开考后看完所有题目就已经很轻松了……

简单说一下题意和我的思路吧。具体能拿多少分不知道，反正几十不超过 50。看人品。

A

就是给你个小写字母字符串，和个小写字母字符串，然后，然后表示在中出现了多少次。求

我最开始直接暴力，真的就直接暴力。后来觉得可能连第一个点都过不去，就给加了个哈希乱搞。

最开始我尝试想正解的时候曾经想出了一个 SA + HASH 的方法，但是我望而生退了……而且感觉有问题。反正这什么题啊，普通人，做不起。

B

来了，典中典，计算几何。就是首先给你一个矩形边框，，然后呢平面上有个互不相同的点。现在要你对于每个求，表示在平面上选择一个点使得有恰好个点到的距离小于点到的距离的所有合法构成的区域的面积。点坐标的范围我记得是的，反正不会爆精度就对了。只要和答案不超过的差就行。

首先有大概的半平面交做法，我打过一次，结果一不小心打成的方法了呜呜呜。然后其实我最开始想到的做法是下面的：

就是会发现这条中垂线肯定最多就把这个正方形分成个区间（显然达不到，原因有下面的），然后又会发现，这种偏序关系是可以传递的！因为你可以看到任意三个点的那个中垂线是交于一点的，也就是只要满足了那么不用再去验证的那条中垂线了。然后呢我就写了一个 dfs。里面传入当前的点的大小关系（一个链表），然后当前的多边形吗，还有当前要加入的点。然后我就去枚举这个点插在哪里。然后再写一个函数，就是传进去一条有向线段，返回两个多边形，就是切割后的，一左一右。然后只需要插入这个位置前后的两个关系切割就行了。然后一直往下就行了。现在想了想发现考场上代码还可以减小一半常数，因为后面大于这个点的那个向量的限制的切下来的多边形的右半部分就是循环到下一个位置的起始状态，就能少算一半的切割。优化的化就是多边形为空就直接返回了。

但是问题来了，我只能跑过三个点的东西！继续往上就会 WA 了！现在回忆起来感觉自己有点傻叉，第一个大点是 12 个点我就不能手搓一个四个点的样例嘛……算了，也没有必要哩。反正这道题就看人品了，然后我跑了一下后面一个所有点一条线的情况，发现是对的，但是时间有一点超……说不定加上前面那个常数优化就能过了嘿嘿。

总之我这个复杂度吧，我也说不清楚。

C

刚刚去吃饭咯，今天元宵节，天气也很好，正月十五。

讲一下第三题的题意吧，就是有个怪兽，每个怪兽有血量，然后有一个爆炸伤害的区间，这个怪物去世（血量不大于 0）的时候对剩余所有怪物造成的爆炸伤害。未知，在那个区间里面。现在你可以选择秒杀一些怪物，然后让所有怪物去世。求对于所有可能的序列对应的最少秒杀次数的和。似乎是要模一个数，但是忘了模多少了。然后数据范围后面提醒我们请让我们相信常数。

简单想了一下，大概就是状态压缩，然后弄个背包，然后每次背包转移只用转移当前状态还不能结束局面的情况。然后数量一样的再容斥一下，但是后来想了想不知道怎么容斥。然后打了个简单暴力跑了。我也想过用二分图之类的网络流来搞，发现不是很会建模。

刚才又想了想，想出了一种新的模型，大概就是把怪兽给排个序，就是如果前面所有的和小于这个的，那么就会加。好像也不太对。

总之今天是很有趣的一天！我感觉我现在的状态比早上好，第一天就这么难，第二天也就没有什么压力啦哈哈哈哈。

总结：不要踟蹰，向前望，有美丽的风景。

Day 1

都隔了一周才来写……先说结果吧，噶了。如果我第一天把 T2 切了就好了。现在在上文化课，也很有趣欸。我们学校的 OJ 上面已经有题目了，可以去做。

A

给定 n 个数字串 s，你可以进行 k 次操作，每次操作可以选择所有串中的任意两个不同位置，并将这两个位置上的字符交换。定义 k 次操作过后的权值为将这nn 个数字串变成数字后的乘积，求对于所有的操作方式的权值之和，模。

注意操作之间独立，两次操作可以选择相同的位置。

对于所有测试点，。

看起来像是矩阵快速幂，但是没想到方法，打了一个 40 pts。

B

给定一个行列的网格图，相邻格子之间有带权边相连。有一个机器人从出发，要到达，初始机器人有一个权值，经过一条权为的边时，就会将变为，特殊的，。机器人不会重复经过一个格子。为了使得机器人到达时，你需要删去一些边，求最小删去的边。

有次询问，每次询问会将一条边权为的边改为。你需要对于每一组询问都求出最小删去的边。当时强制在线。

对于所有测试点，。

容易发现答案不超过 2，我乱搞了一下，15分。

C

给定你一个的网格。你有两种形状的图形。

1
2
3

*   *
**  *
    **

可以通过旋转翻折这两个图形，最后有 11 种基本图形，并且有标号。先在让你用最少的这种形状覆盖整个网格所有的边，不能重叠（是填的边，围成的网格）。给出方案，多组询问。

不知道怎么做，本来想打舞蹈链，后来发现太麻烦了，而且最恶心的是这道题的列数是，行数是，简直恶心人。似乎是有轮廓线的暴力做法的，反正打了个 10 分的暴力。

总结

两天加起来才 100 分。我们省自己出题可真是厉害。不过过去的都过去啦，今年可能还能参加个 D 类什么的。一切安好。