[USACO2018]Out of Sorts

[USACO2018]Out of Sorts
神仙数论题,重点是分析一下他排序的分割点。膜了题解还是觉得这题很神仙。

题解考虑的是对于每一个数他会被算多少次,也就是他递归的层数
这个我也想过,但是我完全没有思路啊TAT
然后一个数,他的递归层数是多少呢?
显然地,就是剩下他一个的时候
也就是他左边的出现了分隔符,右边也出现了分隔符
于是,问题就转化为,某一个分隔符出现的时间
然后一个点的答案就是两个分隔符取max
考虑一个数i前面的分隔符怎么得到
其实就是所有比i−1i−1小的数,位置的最大值减去i−1i−1
至于为什么,你结合一下我上文说的  ......  查看更多

[Usaco2012 Dec]First!

[Usaco2012 Dec]First!
这题老旧之前做过,但是好像没调出来T了,然后弃了,现在看到有人在做,然后就顺便丢了出来调了一下调过了。憎恨把true写成false的我。
还找来师兄代码改呀改才改对的。
这题其实真的不难,终点在于你怎么去处理他们之间的关系呢,我们可以先用他们建一棵字典树,然后对所有儿子节点进行拓扑排序,如果有入度为零的点就代表有解。 ......  查看更多