南山建网站,wordpress什么意思,自建网站避免侵权,杭州 城西 做网站题目大意
原题面链接
在一个 1 0 9 W 10^9\times W 109W 的平面里有 N N N 个方块。我们用 ( x , y ) (x,y) (x,y) 表示第 x x x 列从下往上数的 y y y 个位置。第 i i i 个方块的位置是 ( x i , y i ) (x_i,y_i) (xi,yi)。现在执行无数次操作#xff0c;每一次…题目大意
原题面链接
在一个 1 0 9 × W 10^9\times W 109×W 的平面里有 N N N 个方块。我们用 ( x , y ) (x,y) (x,y) 表示第 x x x 列从下往上数的 y y y 个位置。第 i i i 个方块的位置是 ( x i , y i ) (x_i,y_i) (xi,yi)。现在执行无数次操作每一次操作如下
如果整个平面的最下面一行的 W W W 个位置上都有方块那么把这一行的方块都消除掉。从下往上遍历每一个未被消除的方块如果它不在最下面一行且它下面是空格子将它向下移动一格。注意只移动一格
思路
观察数据范围需要预处理。我们不妨令 t i i ti_i tii 表示第 i i i 个方块什么时候被消除。对于无法被消除的方块其 t i i ti_i tii 为极大值。我们可以拿样例来寻找突破口样例解释里面的那个图片如下 观察一下第二次操作执行完和第三次操作执行完的结果是一样的所以继续执行下去结果不会改变。也就是说第三次操作及以后的操作都是“无效操作”而其中可以消除的操作只有第二次我们将其称为“有意义”。稍加观察可以发现有意义的操作数量是每一列方块数量的最小值很容易证明出来。
每一次有意义的操作之前我们可能需要一些有的时候不需要操作来让所有方块掉到地上这种操作我们称之为“预备操作”。不难发现预备操作的结束时间是每一列最下面的方块的纵坐标的最大值减一。所以有意义的操作的结束时间就是每一列最下面的方块的纵坐标的最大值有点绕可以用来更新 t i i ti_i tii。
一个很重要的问题怎么预处理每一列的那堆格子开个 vector 数组具体实现看代码。
那么在每一次询问的时候只要看 t i A j ti_{A_j} tiAj 与 T j T_j Tj 的大小关系即可。
预处理部分代码
其实有点小细节能 hack见文末彩蛋。
for (int i 1; i n; i)
{cin x[i] y[i]; // 读入v[x[i]].push_back(i); // 这一列的方块ti[i] 1e9 7; // 极大值
}
int mn 1e9 7; // 极大值
for (int i 1; i w; i)
{int cnt v[i].size(); // 强转一下// int 类型不能直接和 unsigned int 类型取 minmn min(mn, cnt);
}
for (int i 0; i mn; i)
{int mx 0; // 计算最大值for (int j 1; j w; j)mx max(mx, y[v[j][i]]);for (int j 1; j w; j)ti[v[j][i]] mx; // 更新
}完整代码
我的提交记录
时间复杂度分析
预处理里面有个双重循环为什么没有超时呢 m n mn mn 最大为 N N N复杂度理论上来说是 O ( N ⋅ W ) O(N\cdot W) O(N⋅W) 的但是考虑到实际构造原因其均摊时间复杂度是不会超时的所以可以通过本题。
彩蛋
大框架没问题有个小细节出锅了。请问题目保证输入按 y i y_i yi 升序排序了吗没有得自己排个序。注意一下得用结构体排序既可以让变量对应上也可以存储初始下标。正确版本我还没写应该没啥太大区别遇到问题欢迎在评论里问我或私信沟通哦要是有其他问题或者 hack 数据也可以联系我哦
