Atoposyz
avatar🌸
AtoposyzAtoposyz

生活本就是奇迹与日常的结合体

Atoposyz 的个人博客

模拟赛总结

笔记

XuanFly′s\mathcal{XuanFly's} 模拟赛总结 ​

written\color{navy}{written} with\color{navy}{with} $\LaTeX $ &\& $ \mathcal{Markdown}$

NOIP2014\mathcal{NOIP2014}

quot;">​

D1T1\mathcal{D1T1} 生活大爆炸版石头剪刀布 ​

  1. 一看就知道是个模拟题，直接按照题意模拟，而且数据范围不大，模拟可行，A\color{green}{A}了

D1T2\mathcal{D1T2} 联合权值 ​

  1. 当时还没有背过图上的算法，就向先暴力，至少拿 3030 分再说
  2. 使用 DFSDFS 遍历，每遍历到一个点，来两个 for\mathcal{for} 循环遍历该点连接的点，时间复杂度大概 O(n3)\mathcal{O(n^3)}。但是因为没有考虑到各种各样的情况，最后 0\color{red}{0} 了……

D1T3\mathcal{D1T3} 飞扬的小鸟 ​

  1. DFSDFS 骗分
  2. 大概是枚举点击的次数，不行就回溯，这样写是期望50分的，但是被自己手写的样例TLE了，最后35\color{orange}{35} 分

D2T1\mathcal{D2T1} 无线网络发射器选址 ​

  1. 这道题以前当做例题讲来着，这道题有四种解法，我凭借记忆应该是选了最快的一种
  2. 遍历每一个公共场所，处理以这个场所为中心，d为半径的坐标
  3. 然后又打了个暴力程序(结果暴力打错了)，两个程序互相查错23333
  4. A\color{green}{\mathcal{A}} 了

D2T2\mathcal{D2T2} 寻找道路 ​

  1. 正解不会，目标暴力 6060 分
  2. 先 DFSDFS 遍历整个图，把所有不是终点的没有出边的路径去掉
  3. 再 BFSBFS 只要能找到终点，就是最短的
  4. But\large\mathcal{But} DFSDFS 是有极限的不应该把路径全删了，应该只删一条边，其他的还可能会用到(读错题)
  5. 30\color{orange}{30}

D2T3\mathcal{D2T3} 解方程 ​

  1. 正解不会
  2. 暴力打了二次方以下的，20\color{red}{20}

NOIP2018\mathcal{NOIP2018}

quot;">​

D1T1\mathcal{D1T1} 铺设道路 ​

  1. 去年真的被虐出阴影了，做题只记得是一个贪心但不知道怎么贪
  2. 尝试了：从大到小，从小到大，发现不可行 cannot\mathfrak{cannot} achieve\mathfrak{achieve} it\mathfrak{it} ，最后选择了较为合理的方法
  3. 从左往右遍历，如果当前的比两边小，就不加，否则加上与两边差较小的，其实比较接近正确思路了，但还是 20\color{red}{20}
  4. 正确思路：遍历到一个点，如果比左边相邻的大，就加上差值

D1T2\mathcal{D1T2} 货币系统 ​

  1. 爆 0\color{red}{0} 了
  2. 不会打，想搜索来着，不知道怎么搜
  3. 看过题解的人都说自己智障，竟然可以是个完全背包
  4. 不过看起来和线性筛素数好像，若 a\mathcal{a} 可以被表示，则 a+bi(i∈Z)\mathcal{a+b_i (i\in Z)} 也可以被表示

D1T3\mathcal{D1T3} 赛道修建 ​

  1. 看了看子任务，觉得可以做 m=1\mathit{m = 1} 的情况
  2. 即找一条单源最长路
  3. Dijkstra\mathcal{Dijkstra}

D2T1\mathcal{D2T1} 旅行 ​

  1. 前 1515 个点是树，可以一做
  2. 每次到一个新的城市，用 **优先队列 ** 存点，优先遍历字典序小的城市 60\color{yellow}{60}

D2T2\mathcal{D2T2} 填数游戏 ​

  1. 不会，也没有搜索的思路
  2. 观察子任务，发现可以输入样例骗分 15\color{red}{15}

D2T3\mathcal{D2T3} 保卫王国 ​

  1. 不会，没思路，没想法 0\color{red}{0}

NOIP2017\mathcal{NOIP2017}

quot;">​

D1T1\mathcal{D1T1} 小凯的疑惑 ​

  1. 观察程序文件发现是 math\large\mathfrak{math} ，明显这是个数学问题

  2. 通过打表，观察规律，尝试各种排列组合，发现其符合这样一个式子

    a+c=b×(a−1)a + c = b \times (a - 1)

    即

    c=a×b−a−bc = a \times b - a - b

  3. 直接输出即可 A\color{green}{\mathfrak{A}} 了

D1T2\mathcal{D1T2} 时间复杂度 ​

  1. 很不错的一道模拟题
  2. 按行读入
  3. 用栈判断 F\mathbb{F} 和 E\mathbb{E} 是否匹配
  4. 用极大数代替 n\mathcal{n} 通过相减判断复杂度

D1T3\mathcal{D1T3} 逛公园 ​

  1. 目标是前两个 K=0\mathit{K = 0} 的点，但是不知道为什么对了最后一个点2333

D2T1\mathcal{D2T1} 奶酪 ​

  1. 数据比较小，可以通过搜索剪枝实现
  2. 若搜到尽头没处搜了，就删掉这个空洞即可（vis[i]=−1\mathit{vis[i] = -1}）
模板练习
Apple Tree 2