模拟赛总结
\mathcal{XuanFly's} 模拟赛总结
\mathcal{NOIP2014}
\mathcal{D1T1} 生活大爆炸版石头剪刀布
- 一看就知道是个模拟题，直接按照题意模拟，而且数据范围不大，模拟可行，
\color{green}{A} 了
\mathcal{D1T2} 联合权值
- 当时还没有背过图上的算法，就向先暴力，至少拿
30 分再说 - 使用
DFS 遍历，每遍历到一个点，来两个\mathcal{for} 循环遍历该点连接的点，时间复杂度大概\mathcal{O(n^3)} 。但是因为没有考虑到各种各样的情况，最后\color{red}{0} 了……
\mathcal{D1T3} 飞扬的小鸟
-
- 大概是枚举点击的次数，不行就回溯，这样写是期望50分的，
但是被自己手写的样例TLE了，最后\color{orange}{35} 分
\mathcal{D2T1} 无线网络发射器选址
- 这道题以前当做例题讲来着，这道题有四种解法，我凭借记忆应该是选了最快的一种
- 遍历每一个公共场所，处理以这个场所为中心，d为半径的坐标
- 然后又打了个暴力程序(
结果暴力打错了)，两个程序互相查错23333 -
\mathcal{D2T2} 寻找道路
- 正解不会，目标暴力
60 分 - 先
DFS 遍历整个图，把所有不是终点的没有出边的路径去掉 - 再
BFS 只要能找到终点，就是最短的 -
-
\color{orange}{30}
\mathcal{D2T3} 解方程
- 正解不会
- 暴力打了二次方以下的，
\color{red}{20}
\mathcal{NOIP2018}
\mathcal{D1T1} 铺设道路
- 去年真的被虐出阴影了，做题只记得是一个贪心但不知道怎么贪
- 尝试了：从大到小，从小到大，发现不可行
\mathfrak{cannot} \mathfrak{achieve} \mathfrak{it} ，最后选择了较为合理的方法 - 从左往右遍历，如果当前的比两边小，就不加，否则加上与两边差较小的，其实比较接近正确思路了，但还是
\color{red}{20} - 正确思路：遍历到一个点，如果比左边相邻的大，就加上差值
\mathcal{D1T2} 货币系统
- 爆
\color{red}{0} 了 - 不会打，想搜索来着，不知道怎么搜
- 看过题解的人都说
自己智障，竟然可以是个完全背包 - 不过看起来和线性筛素数好像，若
\mathcal{a} 可以被表示，则\mathcal{a+b_i (i\in Z)} 也可以被表示
\mathcal{D1T3} 赛道修建
- 看了看子任务，觉得可以做
\mathit{m = 1} 的情况 - 即找一条单源最长路
-
\mathcal{Dijkstra}
\mathcal{D2T1} 旅行
- 前
15 个点是树，可以一做 - 每次到一个新的城市，用 优先队列 存点，优先遍历字典序小的城市
\color{yellow}{60}
\mathcal{D2T2} 填数游戏
- 不会，也没有搜索的思路
- 观察子任务，发现可以输入样例骗分
\color{red}{15}
\mathcal{D2T3} 保卫王国
- 不会，没思路，没想法
\color{red}{0}
\mathcal{NOIP2017}
\mathcal{D1T1} 小凯的疑惑
-
观察程序文件发现是
\large\mathfrak{math} ，明显这是个数学问题 -
通过打表，观察规律，尝试各种排列组合，发现其符合这样一个式子
a + c = b \times (a - 1) 即
c = a \times b - a - b -
直接输出即可
\color{green}{\mathfrak{A}} 了
\mathcal{D1T2} 时间复杂度
- 很不错的一道模拟题
- 按行读入
- 用栈判断
\mathbb{F} 和\mathbb{E} 是否匹配 - 用极大数代替
\mathcal{n} 通过相减判断复杂度
\mathcal{D1T3} 逛公园
- 目标是前两个
\mathit{K = 0} 的点，但是不知道为什么对了最后一个点2333
\mathcal{D2T1} 奶酪
- 数据比较小，可以通过搜索剪枝实现
- 若搜到尽头没处搜了，就删掉这个空洞即可（
\mathit{vis[i] = -1} ）