zcmimi's blog

代码见文末

2010

题目 算法 题解
机器翻译 模拟 直接模拟即可
乌龟棋 动态规划 直接四维dp即可
关押罪犯 并查集 二分图 贪心 并查集做法更为方便,记录敌人并查集,从大到小添加边直到出现矛盾(详见代码)
引水入城 记忆化搜索 bfs 贪心 记忆化搜索或bfs出第1行每个城市建设蓄水站后能覆盖第n行的区间,然后贪心线段覆盖即可

2011

题目 算法 题解
铺地毯 模拟 直接模拟即可
计算系数 动态规划 组合数 动态规划(更简单,详见代码)或直接推式子
选择客栈 rmq 枚举颜色,直接统计即可
聪明的质监员 前缀和 二分 发现W对答案有单调性,直接二分即可
Mayan游戏 模拟 搜索 剪枝 一道比较麻烦的搜索题, 不用想太多,直接模拟即可,唯一的剪枝就是与右边颜色相同时不必交换
观光公交 贪心 模拟 首先规划出不使用加速的行程(人等车,车不等人),然后以贪心的策略使用加速器

2012

题目 算法 题解
Vigenère 密码 模拟
同余方程 exgcd ax\equiv 1 \pmod b
国王游戏 贪心 按照a_ib_i从小到大排序,接着高精度比较麻烦
借教室 前缀和 二分 二分订单即可
开车旅行 倍增 可以发现对于每个x,路径是固定的. 先预处理出离每个点最近点和次近点,然后倍增处理出走2^i天到达的点,然后就可以对每个x求出路径了
疫情控制 倍增 二分 贪心 可以发现答案具有单调性,所以可以二分时间;判断: 让所有军队尽可能向上走(可以控制更多路径),能到首都的先停在首都,然后再判断首都的未被覆盖的孩子能否被停留的军队覆盖

2013

题目 算法 题解
积木大赛 模拟
转圈游戏 模拟 快速幂
花匠 贪心/动态规划
货车运输 kruscal 倍增 lca 构造生成树后对x,y查询路径上最小的边即可
火柴排队 排序不等式 逆序对 \sum (a_i-b_i)^2中变化的只有a_i\times b_i,根据排序不等式,a中第i大的与b中第i大的相乘\sum a_i\times b_i最大,于是变为邻位交换问题,求逆序对数
华容道 搜索 图论 最短路 询问有五百次,不可能对每次询问都作一次搜索。我们只需要保留有用的状态并建图,对每个询问都跑一次最短路即可

2014

题目 算法 题解
生活大爆炸版石头剪刀布 模拟
无线网络发射器选址 模拟
联合权值 树论 一个点连接的所有点两两之间距离为2,对每个点分别统计即可
寻找道路 图论 最短路 建立反向边,遍历处理出出边都可到达终点的点,然后再跑最短路
飞扬的小鸟 动态规划 f(i,j)表示到达坐标(i,j)最少需要点击几次屏幕
解方程 数论 枚举x,判断是否成立即可

2015

题目 算法 题解
神奇的幻方
跳石头
信息传递
斗地主 搜索
子串 动态规划 前缀和优化 f(i,j,k)=\begin{cases}f(i-1,j,k) &A_i\neq B_j\\ f(i-1,j,k)+\sum f(i-t,j-t,k-1) &A_i=B_j\end{cases}
运输计划 lca 二分 树上差分 二分最大值,将大于最大值的路径标记,使用树上差分找出能覆盖所有标记路径的边,判断删除该边是否可行

2016

题目 算法 题解

2017

题目 算法 题解

2018

题目 算法 题解
noip提高历年题目题表
comment评论
Search
search