HZOJ
写在前面
大概就是切不了任何一道题，大概就是T4改了一辈子。大概就是个人感觉T2严格简单于T1，T3严格简单于T4。感觉好久没有模拟赛改完4道题了。时间貌似不多了，那还是速战速决吧。
《Shopper》
아직도 난
我现在还是
더 가지고 싶어
渴望拥有更多
Yeah I want more
I'll get it more more
설레는 게
让我心动的事
이렇게나 많은 걸
其实有很多
Oh I want all
I must have all all
저녁 일곱시
晚上七点钟
노을의 팔레트
彩霞的调色板
I need it course
I'll take it course course
가슴 터질 듯
心情好到爆炸
내 이름을 외치는 목소리
呼喊着我姓名的声音
Oh it's so worth
It's more than what what
빼곡히 적은 wish list
在愿望清单上密密麻麻地记录着
빠짐없이 가질 때까지
直到我拥有一切为止
Take what you want
No matter who calls you a freak
설명할 필요 없어
不需要解释什么
나 그때와는 다른 걸 원해 원해
我想要和之前不一样的东西
Let's go haul
더 미어터질 만큼 다 채워
全部填满 直到溢出来
Look around
시간은 짧아 더 빨리 가져
时间很短 要快点把握住
Shop all day ay
Greed is free ay
Go Make your own
가지러 태어난 것처럼
就像是生来就能主宰一切
이 샵은 문 닫지 않아 늘 영원히
这家店永远都不会关门
마지막 소절 숨의 첫 모금
最后一段呼吸的第一口气
It's time to show
Go make it sure sure
승리를 앞둔
即将获胜时
마음이 달릴 때 내는 소리
发出狂跳不止的心跳声
It's time to go
I'll make my goal goal
내게는 없어 plan B
我不会有其他计划
모조리 내 것이 될 때까지
直到我拥有一切
Take what you want
No matter who puts down you're greed
적당히로는 안돼
我才不会适可而止
난 훨씬 더 대담한 걸 원해 원해
我想要的是更大胆的东西
Let's go haul
더 미어터질 만큼 다 채워
全部填满 直到溢出来
Look around
시간은 짧아 더 빨리 가져
时间很短 要快点把握住
이 샵은 문 닫지 않아 봐
这家店不会关门的 看吧
필요 없는 건 없어
全都是必需品
For my Victory even your jealousy
나 이제껏 모르던 세상을
对于这个我至今都不曾看清的世界
욕심 내볼래
我有太多的欲望
Let's go haul
더 미어터질 만큼 다 채워
全部填满 直到溢出来
Look around
시간은 짧아 더 빨리 가져
时间很短 要快点把握住
Shop all day ay
Greed is free ay
Go Make your own
가지러 태어난 것처럼
就像是生来就能主宰一切
이 샵은 문 닫지 않아 늘 영원히
这家店永远都不会关门
A. 岛屿
麻了。完全没思路，甚至暴力也不想打。题意大概是给出\(x,y\)，然后共有\(2n, n=2*x+y\) 个点，第\(1-x\) 个和第\(n+1-2*n-x\) 个点是红色，其余点是蓝色。第\(i\) 个点和第\(i+n\) 个点间存在一条边。求问如果只能等概率地在所有红蓝点对上连边，且每个点必须且仅可连一条边，求问最终能形成的连通块个数。
没有任何思路噜噜噜。除了打表找规律，讲讲一种非常巧妙而又更全年龄向的做法。可知一共存在两种点：同色相连和异色相连的点。那么我们将同色相连的点类比为成人（adult），把异色点相连类比成儿童（child）。首先考虑儿童，儿童能贡献一整个连通块，当且仅当其连重边。否则无论连成人或儿童它都只能和其他块共同贡献，直接把其归到其他块里即可。所以每个儿童对答案的贡献是\(1/n\)，\(n\) 是当前剩余的节点数。考虑成人。我们知道成人肯定会和其他成人相连，所以我们先钦定某对点被连过了，那么我们只用考虑它的伴侣的连法即可。然后发现如果只看端点，这两个成人正好生出了一个儿童，参考上面的，这个儿童能贡献当且仅当其首尾相连。以此类推，每次钦定某条边已经连了，然后把成人转为儿童再考虑连法即可。
代码就不放了，但是亮点是变量名就分别是adult和child。
B. 小朋友
为啥挂了为啥挂了为啥挂了。题意是有两个字符串，选择留下一些位置的字符，然后将两个串拼接，求字典序最大的串。
本来想贪心写个单调队列的，然后显然结论是假的。然后苦瞪数据范围：这不一眼折半搜索吗。然后就折半搜索过了样例。然后没管了。然后大概就是挂如分了。大点全T，甚至特殊性质的分数也丢了呜呜呜。然后本题比较特殊，折两半过不了就折三半，反正复杂度还是\(2^{n/k}\) 的，只不过带个字符串长度的常数。就算折三半过不了还能再继续折下去。还好折三半就能过了。正解是\(O(n^3)\) 的dp，但是我不会。
C. 列表
还是不会。题意是给定一个长为\(2n+1\) 的序列，每次取序列正中间的数加入集合\(S\)，然后再删去这个数的同时还能再选一个数删，求问\(S\) 中最长值域连续段的长度。
赛时打了一大堆，最后只无奈拿了特性的5pts。首先有两个性质：1.对于最后在\(S\) 中的\(n+1\) 个元素，\(i\) 无论取何值，都至少有\(i+1\) 数在\([n-i+1,n+i+1]\) 中；2.对于\(S\) 的一个子集\(A\)，不在该范围内的数至多有\(n-i\) 个。
显然可以枚举值域连续段，但是加上check合法性复杂度是\(O(n^3)\) 的。观察到区间左端点递增时，区间右端点一定单调不降。因为如果一个区间合法，那么它的任意一个子区间都合法。那么考虑用数据结构动态维护合法性。我们选用线段树。观察到整个序列的区间具有对称性，所以我们可以考虑将整个序列对折。每次向右扩展右端点时，其代表点的点权增加1。如果整个序列某一区间最大值超过了0，说明该区间已经扩展到极限了，就向右移动左端点。然后答案就是当前枚举的区间长度。然后就\(O(nlogn)\) 解决了本题。
T4 种植
疑似严格简单于T3（？）题意是给出一张网格图，存在一些点可以走且可以种植植物。只能向右或向下走。求问从左上角到右下角的所有路径，使每条路径仅经过1个植物的种植方案数。
首先看特殊性质：所有格子都能走。注意到要想没有经过多个植物的路径，我们只能反其道而行之：从某个点向其左下右上扩展，显然方案数是\(n+m-1\) 的。
考虑一个点如何才能被经过。如果一个点左边&上边都到不了起点||右边&下边都到不了终点，那么这样的点一定不会被经过。那么这些点可种可不种。令这样的点有\(ssum\) 个，那么这样的点对答案的贡献是\(2^{cnt}\)。
考虑不能走的地方如何对答案产生了影响。比如我们原本只能向右上延展，但是如果我们中间经过了一块不能走的地方，那么我们可以通过这块地方保证合法性的同时改变延伸方向。我们考虑将所有的不可达的点八连通缩点，容易知道如果右边界和上边界附近的路径上种植了植物，那么这也阻断了道路，我们便可以把右边界外的点和上边界外的点与其相邻的不能走的点缩到一起。然后方案数就是从左边或者下边把路封上的方案数，等价于从左边和下边到达右上边界外点的路径数。
考虑如何求。首先最基本的一个点能够向其右上方的点跳。然后显然如果一个路径上的点在一个不可走的块旁边，如果其更靠近终点，那么可通过块将路径转移到上面。反之，这个点就可以跳到这个块上改变路径。但是需要特判的是，如果一个2x2的格子出现了X形，那么此时这个点不能直接向其右上方，因为这样会有先跳到旁边再跳过去的方案算重。与之相似的注意点是，如果左下角是一个不能走的块，那么我们的方案数需要减去左边和下边据其最近的能走的点的贡献，因为从不能走的块开始跳和从能走的点开始跳的方案实际上是一样的。
然后就根据上面的描述连边跑方案数即可。答案就是\(2^{cnt} \times 方案数\)。