身败名裂

在BZOJ上RE, 在本OJ AC. 两个OJ的数据应该不一样吧??

VIP a.find(z.top())==string::npos 这个好厉害..学到了...
string::find
Searches the string for the first occurrence of the sequence specified by its arguments.
When pos is specified, the search only includes characters at or after position pos, ignoring any possible occurrences that include characters before pos.
Notice that unlike member find_first_of, whenever more than one character is being searched for, it is not enough that just one of these characters match, but the entire sequence must match.

无聊时自己想了个打印解方法 速度当然没楼上的大神们快- -
深夜又无聊于是乎决定在这里水一贴
用动归的时候已经把每个节点的最大路径值算出来了，
在打印解得时候每次只需要选择比较大的路径值就行（忘了咋推的了 占坑以后补）
从(1,1)开始选择下一行的左边(i+1)(j)或者右边(j+1)(j+1)
比如样例每个状态为
86
57 73
39 46 65
18 27 39 32
12 07 13 24 11
选择的顺序应该是86 73 65 39 24
记录选择的点（用个数组），打印数塔中原来的数据
会发现i是逐层递增的，不需要记录
对于j
d[i+1][j+1]>d[i+1][j]或d[i+1][j+1]<d[i+1][j]
第一种情况时需要把j+1来记录 说明选择的是右边的点 记入数组
第二个则j不需要变 选择的是左边的点 记入数组
打印相应的解就行了

int j=1; now[1]=1; //从点（1,1）开始记录

 for(int i=1;i<=n-1;i++){

 if(d[i+1][j+1]>d[i+1][j]) j++;

 now[m++]=j;

}

for(int i=1;i<=n;i++)

 printf("%d ",a[i][now[i]]);

当初一时兴起想到了一个神奇的压缩trie数占用内存空间的方法。假设trie转移的范围是0~255，这种情况下以直接寻址表的形式跳转的话，也就是每个节点开256个儿子。占用空间极大。
神奇的优化方法:每4位看作一个字符，这样每个节点只需要2^4 = 16个儿子，但是相当于字符串长度 *= 2
这样做可以认为: 时间 *= 2;空间 = 2*sqrt(空间)

场主垃圾线段树板子，常数大如狗。

回复 @mikumikumi :
( 排序之后从小的跑一遍优先解决自己子树的就是最优的了
吐槽: 半个下午.... 把5e4看成了5e5...... M了两次

此题制杖

回复 @Go灬Fire :
装的一手好B（滑稽）

回复 @liu_runda :
+1

真心赞一下评测插件，我按字典序倒序输出的。。

论仔细审题的重要性！！！！！！

回复 @Asm.Def :
Orz萌帝，能学CDQ分治

回复 @Fmuckss :
我推出的公式需要除s来求解的上界，于是就挂了三个点

评测机是不是有问题啊。我的程序本地测试无误，交上去是一个W九个E，NOI2003的标程交上去也是WEEEEEEEEE

写了一个效率最坏O(n^2)的单调队列，居然过了，而且速度接近O(n)……

这个高精实在恶心到我了- -。。