20240925 模拟赛
A pow
显然如果出现了 \(1\),那么 \(1\) 和后面的数都没用了。于是剩下的数不小于 \(2\)。
考虑 \(3\) 个数的情况,只有 \(a^{(b^c)}\) 和 \((a^b)^c\) 两种情况。第二中等价于 \(a^{bc}\),注意到当 \(b,c\geq2\) 时 \(b^c\geq bc\),于是第一种情况一定不优,所以直接从前往后做就是答案。
B good
感觉构成最小生成树的边一定不变,于是容易联想到做一遍 kruskal。
kruskal 过程中,每次会加边合并集合,但是如果 \([1,M]\) 的所有边都存在,此时也许会有更小的合法边出现。这时只能将这些边的两个端点规定在同一集合内。那么不难想到判断合法的条件:每次加边之前,有足够的位置去放原先不存在的边。只需维护同一集合内的边数和减去已被占用的边数。有个细节是当前没有遍历到的输入进来的边也会占用边数,启发式合并搞一搞就好了。时间还是很宽裕的,考场多一个 \(\log\) 都能过。
C stamp
肯定是以某种方式跑最短路,那么将问题转化:一个白点可以 \(0\) 代价走到四连通的白点,可以 \(1\) 代价走到以这个点为中心的边长为 \(2n-1\) 的正方形中除四个角外的所有点。第二种方式也可拆分为 \(1\) 次四连通的移动和 \(n-1\) 次八连通的移动。接下来最难想到的点在于向状态中添加一个类似于高度的维度。那么可以这样求出最短路:
若当前高度为 \(0\) 且位于白格,则可以花费 \(0\) 代价向四连通格移动,高度仍为 \(0\)。
若当前高度为 \(0\) 且位于黑格,则可以花费 \(1\) 代价向四连通格移动,高度变为 \(n−1\)。
若当前高度不为 \(0\),则可以花费 \(0\) 代价向八连通格移动,高度减少 \(1\)。
正确性不懂,引用题解:
标签:连通,短路,高度,20240925,边数,01bfs,代价,模拟 From: https://www.cnblogs.com/luyuyang/p/18535164先想一想正常 01bfs 的正确性。
其实就是把 dijkstra 换了。对于最短路最小的点的出边松弛时,若边权为0,那肯定也是最短路最小的点,若为1,那其实可以想,因为上面那种操作,他会把最小的最短路长度全部便利完(后面也不会出现),然后再去弄次小的最短路长度,那说明什么?队列里顶多就两种最短路权值。
回到原问题,如何满足代价(从小到大)为第一关键字,高度(从高到低)为第二关键字?
因为当要增加代价的时候是高度为 0(操作二),那说明高度更大的已经没有了。推出当队列有高度大于 0 的点时,那肯定当前队列全是代价一样的点,且高度只能两种(和 01bfs 差不多)。
那说明调用操作一时,只有当前代价且高度为 0 和代价加一且高度最大,那放前面是绝对没有问题的。操作二同理。操作三就和正常 01bfs 一样了。