模拟赛总结

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

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

$\mathcal{NOIP2014}$ ​

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

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

$\mathcal{D1T2}$ 联合权值 ​

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

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

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

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

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

$\mathcal{D2T2}$ 寻找道路 ​

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

$\mathcal{D2T3}$ 解方程 ​

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

$\mathcal{NOIP2018}$ ​

$\mathcal{D1T1}$ 铺设道路 ​

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

$\mathcal{D1T2}$ 货币系统 ​

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

$\mathcal{D1T3}$ 赛道修建 ​

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

$\mathcal{D2T1}$ 旅行 ​

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

$\mathcal{D2T2}$ 填数游戏 ​

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

$\mathcal{D2T3}$ 保卫王国 ​

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

$\mathcal{NOIP2017}$ ​

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

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

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

   $$a + c = b \times (a - 1)$$

   即

   $$c = a \times b - a - b$$

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

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

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

$\mathcal{D1T3}$ 逛公园 ​

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

$\mathcal{D2T1}$ 奶酪 ​

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