T1 KAMEN
只能说一言难尽。 60pt暴力模拟每一个石头往下掉的情况。 在这里，我并没有打暴力，而是用set存储了每一列的X和O的石子分布情况。当前节点的位置在(x, y)，寻找x列中比y大的第一个位置在ny(这里可以用upper_bound)，那么石子在这一列能往下掉到的位置就是（x, ny - 1） 然后再判断能不能往左下往右下滚动，不断这样操作。 当石头停下时，再在它所在的列的set数组中加上它的行数字。 考场上的我天真的认为这玩意的时间复杂度一定能过。殊不知从一个位置上扔石子，石子往左下移动，再往右下移动，并且一直往这个位置上面扔石头，这个复杂度就乘上了一个n 好好的logn就成nlogn了...... 100pt 于是，对于这种左右摇摆的情况（适用于所有情况，这里只是打比方），我们考虑记录这个石头的路径。 在这里，石头路径的定义是：这个石头的起点，这个在路径中改变x坐标之前的到达的转折点，这个石头的终点。 一个从i列滚下来的石头到达了(x, y)，这个点不存在于其它任何石头的路径之中，那么不影响其他的未来会从其他列扔下的石头。 这个点如果存在于一些石头的路径之中，那么我们就将原来那些石头的路径王辉删，直到这个一样的路径被删除，前面的路径保留下来（仍然可以继续走） 这样就不用重复遍历一些路径了。 关键点就是c的范围非常的小，以及同一个位置石头被扔下去的路径是有重复的，我们需要思考如何跳过重复的路径。T2 Travelling Merchant
考场上面打了一堆奇奇怪怪的东西，得了30pt（强连通分量看一个点能不能到达一个环的奇观玩意以及n非常小时的超级暴力）
接下来就让我们谈谈正解。
我们先想象一件事情，如果，所有的，点，都拥有出边，这说明了什么。
这说明你一定能去下一个点，也就是所谓的无限制的走下去。
那么这道题无解的情况就是
1.自己所有的一步能到达的点无解。
2.自己根本就没有能到的点。
那么我们首先就应该去计算那些出点都被计算过，或者根本没有出点的点。
于是我们就可以把这种操作想象成从一个已知答案的点向外不断扩展，每扩展到一个点，这两个点之间的联系就会断开，因为信息已经传递完成了。
这个操作就像点与点之间的边断开了一样。
那么，如果没有任何一个点的出度是0怎么办呢？
相当于这个连通图中的所有点都是有解的。
于是我们思考如何才能做到最有效，最正确地传递信息。
如果我们随便将一个点选出来进行计算，这个点的答案是不确定的，而且可能是错误的。
例如u的前面有一个节点v，v的限制比u更大，但是我们先更新了u，于是u的值就会偏小，后面与u有关的所有在它基础之上进行计算的节点都会偏小。
只有选择没有断掉的边中最大的，才能保证自己的正确，并且不干扰其它节点的正确。
这条边断掉之后，会出现新的出度为0的点，说明断边是这些点为能任意到达其它节点的一条可以经过的边，所以出度为0的节点v和一个能到它的起点u，ans[u] = min(ans[u], max(ans[v] - e[id].c, e[id].r))
而对于这条断边本身的起点u和终点v来讲，断边还在，说明图是联通的，点还是可以任意到达，而且已经删去了前面若干条边，这条边的r是剩下的图中最大的,ans[u] = min(ans[u], r)
ans为极大值说明这个节点不能做到自由走。
标签：这个,一个点,NOIP,路径,石头,35T1T2,ans,节点,模拟 From： https://www.cnblogs.com/ybC202444/p/17830203.html