HZOJ
写在前面
终于有一场没有一大堆数学的摩尼塞了，但这个难度是认真的？码量甚至T2>T1>T3>T4？CSP-S还有十多天，貌似现在还没确定自己大概的水平。。。好像能做的只有听天由命了。再坚持一个多月就能离开这个破地方了，最后再加把劲吧。
《Dlwlrma》(窝的同名曲哦)
이건 비밀이야
这是个秘密
아무에게도 고백하지 않았던
当我把对谁都不曾坦白过的
이야기를 들려주면
故事讲给你听
큰 눈으로 너는 묻지
你瞪大眼睛问我
How wow wow whatever
怎么会 wow wow 不管怎样
나 실은 말이야
其实我啊
저기 아득한 미래로부터 날아왔어
是从那遥远的未来飞过来的
쏟아질 듯이
如散落一般
빼곡한 별들 사이를 지나 fly fly fly
穿过了漫天的繁星之间 飞着 飞着 飞着
있지
说真的
그곳도 사실 바보들투성이야
其实那里也都是白痴和傻瓜
아니 매우 반짝이는 건
不 格外闪亮的事物
오히려 now now now
反而是此刻 此刻 此刻
이 하루 이 지금 우리
这一天 这一刻 我们
눈부셔 아름다워
多耀眼 多美丽
이 불꽃놀이는 끝나지 않을 거야
这场烟火永远不会结束
Ooh whatever
喔 不管怎样
흐린 날이면
当阴天到来
거짓말처럼 무섭게 깜깜했지
就会如谎言般恐怖地变得漆黑一片
새침데기 태양은 뜨겁기는 커녕 peacoke
斯文的太阳不但不滚烫 反而炫耀起自己
Blue blue blue whatever
忧伤 忧伤 忧伤 不管怎样
매일 매일
每日每夜
제멋대로인 바람결을 땋아서 만든
在编织着任性胡闹的风儿而做成的
이 나침반이 가리킨 그곳에서 발견
这个指南针指向的那个地方发现
Oh that's you you yes you
噢 那就是你 你 是的 你
있지 저런 건
说真的 那种东西
그저 자그만 돌멩이야
不过是小小的石子
빛이 나는 건 여기 있잖아
发光的事物就在这里啊
Life is cool cool cool
人生多么惬意 惬意 惬意
시간은 많아 이대로면 아마
时间还有很多 这样下去
영원히 살 수 있지 않을까
或许会一直活到永远呢
안녕 나의 주인공
你好 我的主人公
그래 너를 만나러 나
是的 为了遇见你 我
짜잔 우아하게 등장
“当当” 优雅地登场
바로 이 하루 이 지금 우리
就在这一天 这一刻 我们
눈부셔 아름다워
多耀眼 多美丽
나는 확실히 알아
我很清楚地知道
오늘의 불꽃놀이는 끝나지 않을 거야
今天的烟火永远不会结束
우우우 우우우
呜呜呜 呜呜呜
우우우 우우우
呜呜呜 呜呜呜
더 놀라운 건 지금부터야
更惊奇的将从现在开始
A. 远征
观察到\(a_i, x\) 的范围比较小，考虑预处理每个值出现次数前缀和，查询时二分搜索下一个位置即可。实现难度为0。
B. 传送
哈哈哈大概就是接近正解了但是没写出来，而且没抢赢时间然后特殊性质都没来得及交吧。
题意是给出无向图\(G\)，存在一张图\(G'\) 满足前者是后者的子集，且每条长度为3的链首尾间都有一条边。给出起点和终点，求问两者之间的距离。
首先起点终点相同或没在同一连通块内可以容易地判掉。剩下的情况就需要具体实现了。对图进行分析，当起点和终点拥有一条长度为奇数的路径时答案为1，否则答案为0。
首先树上很容易实现，直接判断两个点距离奇偶性即可。
这里给出普通图的两种做法：
1.对树上的情况进行推广。先建一棵生成树。考虑树外的边如何影响答案。当一条边连接的两个点奇偶性不同则该边不产生任何贡献，因为通过该边改变的奇偶性与通过树边改变的奇偶性相同。当一条边连接的两个点奇偶性相同时，该两点间路径长度既可以是奇数也可以是偶数，改变了树上的奇偶性，所以一旦一张子图拥有这样的边，则该子图内任意两点都存在长为奇数的路径，直接输出1即可。否则说明树上的非树边不能造成任何贡献，则和树上的做法相同。由于距离只与奇偶性有关，所以深度直接对2取模即可。
2.考虑两个点经过一个中转点的路径。由于中转点到两点的路径可能存在重合的部分（没有重合则为0），则该部分的长度和一定为偶数。若中转点到两点的距离奇偶性相同那么偶数减偶数一定是偶数。反之中转点到两点的奇偶性不同，奇数减偶数还是奇数。所以我们可以每个连通块内选取一个点作为中转点，bfs预处理每个点到中转点是否有长为奇/偶数的路径。由于每个点至多入队两次，所以可以保证复杂度正确。询问时查询两点到中转点是否存在奇偶性不同的路径即可。
（正解好像是二分图之类的东西来着。就是如果同一连通块内两点距离不全是1,那么这张子图一定是张二分图）
C. 先辈
哼哼哼啊啊啊啊啊啊啊
赛时\(O(26^3n)\) 狂砍60pts。
正解其实和我赛时做法差不多，只是优化掉了一个26。然后大概就是由于取模的问题死活过不去，优化常数快了很多倍、、、
D. 矩阵
算是一道类数学（？）
题意是给出一个01矩阵的大小\(n\) 和要求的次幂\(k\)，求问在该矩阵内至多有多少个1，使得该矩阵求乘方后得到一个全0矩阵。
赛时暴搜砍了60pts。竟然没忘记矩阵即重载运算符的写法。
实际上这个01矩阵可以转化为一张图的邻接矩阵。全0的限制就转化为了图上的链长度小于\(k+1\) 且图中不存在环。考虑将所有的点均分为\(k\) 份（\(k>n\) 与\(k=n\) 等价）。问题就转为了同一份的点间不连边，不同份的点从前往后连边，不在平均的\(k\) 份的点单独考虑连边即可。代码极短。