2019-team11/summary-191012
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
== 流水账 ==
ln开门看A不太会，然后看B，虽然很讨厌suffice这种词题目也读了好久，但是感觉好像可以做？根据最后一个元素的位置就可以划归问题或者直接得出原串了，然后就是验证合不合法了……ln想了好一会不知道怎么验证，只有突然想到既然第一位确定了，只要验证后面合不合法就好了，而这可以根据给定的信息O(n)的做。虽然并不确定这样真的是对的但还是莽了一发然后就A了……'''B1y48'''
xtx发现全世界都过了I就一直想然后想到考察每条边对点的贡献就可了。一堆map套套套套出来了。'''I1y104min'''
ln在xtx想I的时候想H想数学方法然后越想越自闭，然后在xtx说可以dfs+打表后猛地发现自己是傻逼……算了一下上界发现爆long long了于是用python跑dfs，发现这个东西跑得巨慢怀疑栈炸了但看了看代码确信栈没炸再根据所用时间的增长规模推算出来了跑完整个程序所用时间差不多为30min（比较粗的估计），尚可接受。这还是没剪枝的情况，中间ln发现可以随便搞个小剪枝然后在服务器上又开了个进程开始并行计算hhh。事实证明这个剪枝虽然很粗但还是有一点加速效果的。'''H1y126min'''
然后大家陷入啥也不会想要回去吃饭的局面了。xtx推了推发现G是个最短路然后就做出来了。'''G1y169min'''。ln看了看trac发现F大家都会做是因为大家暴力后发现合法串数目很少就跑暴力就过了，然后xtx就过F了。'''F2y195min'''
事实证明ln不会搜索hhh 主要是敏感度太低了，码力也不够，不然F应该尝试小数据打打表的。
== 题解 ==
A：
B：考虑给你的信息中n的位置，如果在中间，那么第n位填一，信息中n以后的位置全填1，信息中n以前的位置全填0；如果n打头，那么n填0，问题化归到n-1的规模。如此可以得到唯一的原串，接着判定它合不合法：为方便讨论，假设n在中间，那么把信息分成左右两端，以样例1 2 4 6 3 5为例，就是分成1 2 4和3 5两端，然后把他们都右移一位变成2 3 5和4 6，再看他们分别在原串的位置里是不是递增（符合字典序）的，是则合法否则不合法。证明不会。（听说其他队都是后缀数组做的但是ln不会后缀数组只能用智商解法解题了hhh
C：
D：
E：
F：
G：
H：上界border为\sqrt \prod p[i]，爆long long了所以要python做。考虑dfs，参数设当前是第几个素数还有a的当前值就好了。不知道怎么剪枝，不过可以并行计算（可是这样因为木桶原理耗时最少也是T(30)，差不多10min诶
I：
J：流水账
ln开门看A不太会，然后看B，虽然很讨厌suffice这种词题目也读了好久，但是感觉好像可以做？根据最后一个元素的位置就可以划归问题或者直接得出原串了，然后就是验证合不合法了……ln想了好一会不知道怎么验证，只有突然想到既然第一位确定了，只要验证后面合不合法就好了，而这可以根据给定的信息O(n)的做。虽然并不确定这样真的是对的但还是莽了一发然后就A了……B1y48
xtx发现全世界都过了I就一直想然后想到考察每条边对点的贡献就可了。一堆map套套套套出来了。I1y104min
ln在xtx想I的时候想H想数学方法然后越想越自闭，然后在xtx说可以dfs+打表后猛地发现自己是傻逼……算了一下上界发现爆long long了于是用python跑dfs，发现这个东西跑得巨慢怀疑栈炸了但看了看代码确信栈没炸再根据所用时间的增长规模推算出来了跑完整个程序所用时间差不多为30min（比较粗的估计），尚可接受。这还是没剪枝的情况，中间ln发现可以随便搞个小剪枝然后在服务器上又开了个进程开始并行计算hhh。事实证明这个剪枝虽然很粗但还是有一点加速效果的。H1y126min
然后大家陷入啥也不会想要回去吃饭的局面了。xtx推了推发现G是个最短路然后就做出来了。G1y169min。ln看了看trac发现F大家都会做是因为大家暴力后发现合法串数目很少就跑暴力就过了，然后xtx就过F了。F2y195min
事实证明ln不会搜索hhh 主要是敏感度太低了，码力也不够，不然F应该尝试小数据打打表的。
题解
A：
B：考虑给你的信息中n的位置，如果在中间，那么第n位填一，信息中n以后的位置全填1，信息中n以前的位置全填0；如果n打头，那么n填0，问题化归到n-1的规模。如此可以得到唯一的原串，接着判定它合不合法：为方便讨论，假设n在中间，那么把信息分成左右两端，以样例1 2 4 6 3 5为例，就是分成1 2 4和3 5两端，然后把他们都右移一位变成2 3 5和4 6，再看他们分别在原串的位置里是不是递增（符合字典序）的，是则合法否则不合法。证明不会。（听说其他队都是后缀数组做的但是ln不会后缀数组只能用智商解法解题了hhh
C：
D：
E：
F：
G：
H：上界border为\sqrt \prod p[i]，爆long long了所以要python做。考虑dfs，参数设当前是第几个素数还有a的当前值就好了。不知道怎么剪枝，不过可以并行计算（可是这样因为木桶原理耗时最少也是T(30)，差不多10min诶
I：
J：