HZOI
写在前面
挂如分挂如分天天挂如分。T1秒切，T2看似有思路实则推半天推不出来，T4跑去
upd: 既然《拜夏》音源出了那就再回味回味吧。去年初听的感觉是对夏日一场盛大演出落幕的感激与不舍，但心怀夏日热情迎接秋天的到来。但今年再品动画版歌词，带来的更多是一种感伤和忧郁，落寞和无奈。这是个痛苦的夏天，精神世界极度空虚，身心俱疲，所以告别是一种解脱。但这同样是一个不可或缺的夏天，即使痛苦，也是我青春的组成部分。又逝去一个夏日，又逝去一年青春。所以告别必定会流露着不舍。现在正处于人生之路上的一座孤岛上，进退两难。迷茫，想退缩，却没有选择的权力，只能硬着头皮往前干。秋天已然来临，但这注定也会是一个充满挑战和痛苦的秋天。只能盼望能在这个秋天能有可观的收获。然后，也许就能肆无忌惮地享受冬日暖阳了吧。
《Bye, Summer》
Hey Summer 到了离别的时候呀 一阵凉风吹起
不知不觉已经快到尽头
与今天相似的每个夜晚向我传达的话语 我无法忘记
我们曾热烈相爱的每一个无名的日子
再见，我长长的夏天啊 不要回头
没什么晦涩难懂的话 就这样送别吧
远走的是曾跟着我们的夜晚
也正像是毫无预告开始的夏日一样呢
My Summer 我会想念你的 就连那刺痛的灼烧也一同
Sweet Sorrow 不知为何眼泪汇聚
这季节里爱过都会留下痕迹 长长久久地不变色
再见，我长长的夏天啊 不要回头
没什么晦涩难懂的话 就这样送别吧
远走的是曾跟着我们的夜晚下的那份炎热
走好 我长长的夏天啊 不要犹豫
代替最后的问候 我只想就这样拥抱你
停滞的那些繁星流转夜晚
与我而言成为永恒 也将我们承载
以布满痕迹的脸庞，以热烈的声音
将我们承载
以爽朗的笑声，以沙哑的声音
Bye Summer 到了告别的时候啦 这微凉的风
T1 雷暴（storm）
签到题，定义maxn和maxm应该用maxm的但是用了更小的maxn狂挂10pts
T2 神力 (god)
题意就是从坐标轴0点开始，每个时间点有\(p%\) 的概率停在该点或者\(1-p%\) 的概率向指定方向移动一步。求问\(n\) 秒内经过坐标轴上\(-n~n\) 号节点分别的概率是多少。
又到了烦人的概率dp的环节。。。观察到数据范围肯定期望要一个\(O(n^2)\) 的dp。设计状态\(dp_{i,j}\) 为第\(i\) 秒停在第\(j\) 个位置的概率。显然有转移式子：
如何得出最终答案呢？其实如果数轴范围以0为起点这题其实就已经解完了。但是这题好讨厌，难得我推出了一个式子，却不让我结束。显然不能将每个时刻的概率简单相加，因为存在经过某个点多次的情况，但我们只能取第一次的概率贡献答案。苦思冥想显然想不出来正解了，那打打特殊性质分。反正期望得分40挂成24我也是无话可说。
正解其实思路类似，只不过正解是通过倒着便历来规避重复贡献。定义状态\(dp{i,j}\) 为后\(i\) 秒离起点的有向距离为\(j\) 的概率。观察到每次转移只对当前点的贡献会造成错误影响，因为经过当前点的概率一定为1，所以每转移完1秒都要将距离为0的点对应的dp值赋为1。转移方程类似于上面那个。最后后\(n\) 秒时的dp数组的值就为以-2/-1/0/1/2/......为起点经过距离为\(j\) 的点的概率。我们便钦定起点为0，直接输出dp数组的值即可，避免了重复计算和错误计算。
代码
#include<bits/stdc++.h>
#define d(u) (u+5000)
using namespace std;
const int maxn=5010,mod=1e9+7,mil=570000004;
int n,p,a[maxn];
int f[maxn][maxn<<1];
int main(){freopen("god.in","r",stdin);freopen("god.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>p;for(int i=1;i<=n;i++) cin>>a[i];f[0][n]=1;for(int i=1;i<=n;i++){memset(f[i&1],0,sizeof(f[i&1]));for(int j=n-i+1;j<=n+i-1;j++){f[i&1][j]=(1ll*f[(i&1)^1][j]*p%mod*mil%mod+f[i&1][j])%mod;f[i&1][j+a[n-i+1]]=(f[i&1][j+a[n-i+1]]+1ll*(100-p)*f[(i&1)^1][j]%mod*mil%mod)%mod;} f[i&1][n]=1;}for(int i=0;i<=n*2;i++) cout<<f[n&1][i]<<' ';return 0;
}
T3 之缘千里（fate）
纯纯恶心人。指的是题面SPJ和数据。
题意是给定一个长为\(2*n\) 的数列，含有\(n\) 对数。每对数所对应的位置要求括号朝向相同。要求构造一个符合要求且字典序最小的括号串。如果没有满足的方案则输出:( （对对对中间没有空格。我服了OJ题面明明中间有空格。而且pdf题面格式本来就很迷，我不敢断定pdf里面中间是否有空格。关键还不给个无解的样例，我咋知道输出啥？无论输出啥按OJ题面输出才该是合理性最高的吧？实则不然。狂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂不止）。累死累活打个特殊性质还没暴力分高，数据水到直接输出最小字典序答案得80+，\(O(2^n2n)\) 能得60+。哈哈。然后喜提WA+TLE=36pts。气到晕厥。
题解里又有那个晦涩难懂的“偏序”。不能保证理解正确，只能说尽力理解了。显然括号前缀和大于等于0，等价于所有左括号的位置能被1, 3, 5, 7, · · · , 2n − 1 偏序，肯定是正确的但是我不知道为什么正确。大概就是1以内至少有1个左括号，3以内至少有2个左括号......？反正照这个思路写。开一个set，首先插入2n以内的所有奇数。然后贪心地将\(nxt_i\) 能被偏序的位置设为(，记得判无解，本题就结束了。判无解具体就是提前偏序完（前缀和数组小于0）或最后还有元素未偏序。
代码巨短无比（恼）
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const string nope=":(";
int n,p[maxn<<1],pre[maxn<<1],nxt[maxn<<1],last[maxn];
bool ans[maxn<<1];
set<int> st;
int main(){freopen("fate.in","r",stdin);freopen("fate.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=2*n;++i){cin>>p[i];pre[i]=last[p[i]];nxt[last[p[i]]]=i;last[p[i]]=i;} for(int i=1;i<=n;i++) st.insert(i*2-1);for(int i=1;i<=2*n;i++)if(nxt[i])if(st.size()&&*st.rbegin()>=nxt[i]){//rbegin 返回最后一个元素的迭代器 st.erase(st.lower_bound(nxt[i]));auto p=st.lower_bound(i);if(p==st.end()) return cout<<nope,0;st.erase(p),ans[i]=ans[nxt[i]]=1;}if(st.size()) cout<<nope;else for(int i=1;i<=n*2;i++) cout<<(ans[i]?'(':')');return 0;
}
T4 怒气冲天（ rectangle）
不会扫描线，题解看不懂，无能为力。
