首页 > 其他分享 >20240925 模拟赛

20240925 模拟赛

时间:2024-11-08 15:20:19浏览次数:1  
标签:连通 短路 高度 20240925 边数 01bfs 代价 模拟

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\)。

正确性不懂,引用题解:

先想一想正常 01bfs 的正确性。

其实就是把 dijkstra 换了。对于最短路最小的点的出边松弛时,若边权为0,那肯定也是最短路最小的点,若为1,那其实可以想,因为上面那种操作,他会把最小的最短路长度全部便利完(后面也不会出现),然后再去弄次小的最短路长度,那说明什么?队列里顶多就两种最短路权值。

回到原问题,如何满足代价(从小到大)为第一关键字,高度(从高到低)为第二关键字?

因为当要增加代价的时候是高度为 0(操作二),那说明高度更大的已经没有了。推出当队列有高度大于 0 的点时,那肯定当前队列全是代价一样的点,且高度只能两种(和 01bfs 差不多)。

那说明调用操作一时,只有当前代价且高度为 0 和代价加一且高度最大,那放前面是绝对没有问题的。操作二同理。操作三就和正常 01bfs 一样了。

标签:连通,短路,高度,20240925,边数,01bfs,代价,模拟
From: https://www.cnblogs.com/luyuyang/p/18535164

相关文章

  • 20240918 模拟赛
    20240918模拟赛AStringBPack看这个数据范围很容易想到dp,设\(f_{i,,j,k}\)(pair<int,int>)表示前\(i\)个物品,拿走\(j\)个\(1\),\(k\)个\(2\)所用的最少车数,以及最后一辆车所用的最少空间。转移分当前这个拿不拿掉讨论,非常显然。最后枚举总共拿了几个\(1\)和几个......
  • 20240914 模拟赛
    20240914模拟赛A开挂(openhook)可以发现结果序列是能确定的,而且我们并不关心具体对哪个数进行操作,有用的信息只有操作次数,从而可以得到一个数组\(c\)表示对某个数操作了某个次数。设对\(tot\)个数进行了操作,将\(c\)从小到大排序,将\(b\)中的前\(tot\)小从大到小排序,于......
  • Chromium 进程降权和提权模拟示例c++
     一、背景知识概念参考微软链接:强制完整性控制-Win32应用程序|Microsoft学习授权)(模拟级别-Win32apps|MicrosoftLearnDuplicateTokenEx函数(securitybaseapi.h)-Win32apps|MicrosoftLearn本文主要演示 low,medium,high,andsystem四种权限创建......
  • C++:模拟实现STL的list
    目录一.list类1.list的创建节点2.list迭代器的运算符操作3.list的构造函数及析构4.list的迭代器5.list的插入及删除二.整体代码1.list.h2.list.cpp在上一节已经了解list在库中的用法,在这里实现list的底层逻辑一.list类1.list的创建节点template<classT>struc......
  • [赛记] NOIP2024加赛1 && 多校A层冲刺NOIP2024模拟赛18
    暴力错解大赛玩游戏82pts乱糊的错解,正确性和时间复杂度都不对,但是拿了82pts;对于正解,考虑从$k$将原序列分成两个部分,左边和右边,然后分别求一次前缀和(注意这里,可以省去很多分讨和常数),设前一个前缀和数组为$a$,后一个为$b$,那么问题就转化成有两个指针$i,j$,可以任......
  • NOIP 模拟 7
    T1图书管理(book)考虑每个数做中位数的贡献,经典trick就是小于的为\(-1\),大于的为\(1\),前缀和相减为\(0\)的就合法,不会链表。T2两棵树(tree)又是经典trick,森林的连通块数为点数减边数,证明就是算树的数量,好像之前见过这个trick。然后把贡献拆开,\(e\)代表点,\(v\)代......
  • 多校A层冲刺NOIP2024模拟赛19
    多校A层冲刺NOIP2024模拟赛19其实不太想写博客,但还是从今天开始坚持写吧。T1图书管理对于这种一边大一边小的问题,一般套路是大的设为$1$,小的设为$-1$,这道题也是,这样之后去扫一遍,两端的前缀和值一样即可。T2两棵树新学到的一个重要$trick$是:$$连通块的个数......
  • C# 队列的一些并发模拟
    usingSystem;usingSystem.Collections.Generic;usingSystem.ComponentModel;usingSystem.Data;usingSystem.Drawing;usingSystem.Linq;usingSystem.Text;usingSystem.Windows.Forms;usingSystem.Threading;usingSystem.Collections.Concurrent;namespace......
  • 【记录分享】多任务黑客攻击仿真模拟器
     在电影和电视剧中,黑客攻击的场景往往充满了紧张、快速的打字声和不断滚动的命令行界面。为了让这种体验更具沉浸感,我们可以通过编程模拟出一个真实的黑客攻击过程。本篇文章将介绍如何使用Python和Tkinter库设计一个多任务黑客攻击仿真模拟程序,包含攻击模拟、网络带宽......
  • [63] (多校联训) A层冲刺NOIP2024模拟赛19
    lhx对\((\lnn)^{\lnn}\)求导求出一个形如\(\frac{1}{n\lnn\ln\lnn}\)的东西A.图书管理说一种很好玩的\(n^2\logn\)做法(因为动态中位数我只会这个)对顶堆:就是你开一个大根堆和一个小根堆,然后把它们怼在一起,钦定比中位数大的放小根堆,小的放大根堆,这样中间就是中位......