题目传送门：D - Prefix K-th Max (atcoder.jp) 题目大意 给定一个大小为N的排列，从第K个数字开始，每次求从开始到该数字为止的序列中的第K大的数字。 思路 如果是一个月前，我将会不知所措。但是最近atcoder出了好几个multiset和set的题目，于是不难想到用set这个神奇的数据结构。 因为set的插入和查询复杂度均为O(logN)，所以可以很轻松地完成这道题。 […]

题目链接：P2678 [NOIP2015 提高组] 跳石头 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目大意就不说了，请看原题。 这道题我在很久之前就A了，昨天朋友问起发现自己还写错了几次，实在惭愧，今天记录一下这个思路。 思路 首先，如果已知撤走的石头，想要求最短距离，是不容易的，但是如果已知最短距离，求“一定要至少撤走多少个石头”可以通过遍历一遍，O(N)的复杂度算出 […]

题目链接：E - Wrapping Chocolate (atcoder.jp) 题目大意 有N个矩形巧克力，M个矩形盒子，一个盒子只能放最多一块巧克力，且巧克力的长和宽不能旋转，问能否装下。 思路 输入巧克力和盒子的数据，将巧克力的type设为1，盒子为0，将他们存在同一个数组里，数组大小为N + M。 将所有矩形（包括巧克力和盒子）按照宽度排降序，规则是宽更大的在左边，如果宽相同，则盒子在前， […]

在学习竞赛的过程中，环境搭建是一个比较头疼的事情，但是其实我们不需要那么复杂的操作，devcpp对于算法竞赛的学习已经足够了。 这里分享的devcpp5.4.0是离线且稳定的版本，无需安装，无需搭建环境，解压就可以直接使用。 下载地址：http://eriktse.kuaiyunds.com/eriktse/devcpp5.4.0.7z

题目传送门：C - Choose Elements (atcoder.jp) 题目大意 给定长度为N的整数序列 A 和 B ，能否构造出一个序列X，使得Xi = Ai or Bi，且| Xi - X(i-1) | <= K。 思路 这里用dp的思路，dp[i][0]表示能够从起点构造到第i位，并使Xi = Ai，dp[i][1]则表示Xi = Bi。 状态转移方程就是转移一下“到起点的连通性 […]

题目传送门：P2088 果汁店的难题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 这是今天的一道练习题，我一看普及+/提高感觉蛮难的，其实想一下也还好。主要是数据非常小，复杂度是O(N ^ 2)。 题目大意请看原题。 思路 我们用used来表示某种水果被用在一个榨汁机里，具体在哪个榨汁机不重要。 cnt表示当前有多少个榨汁机里面是有东西的。 先将整个序列离线，然后遍历。如果水 […]

题目链接：Problem - 729C - Codeforces 题目大意 现在俺在坐标为0的租车场要去一个电影院看电影，电影院在S点（一维数轴），电影T时刻开场。 我这里有很多车，每辆车有一个价格Ci和油箱容量Vi。 路上有K个加油站，每个加油站可以免费把油加满，车辆在起点时油箱是满的。 在路上有两种驾驶模式： 模式1：每1单位油走1公里，耗时2时间（正常模式） 模式2：每2单位油走1公里，耗时 […]

题目传送门：P2136 拉近距离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 在之前有写过spfa做的题《[NOIP2009]最优贸易（分层图论 + SPFA最长路） – ErikTse Runtime》，不过那道题比较复杂，本题是一道纯模板题。 思路 直接spfa，有几个点需要注意。 这里是单向图，根据题意，需要对d[1][N]和d[N][1]取小。 注意判环，方法是如果一 […]

题目传送门：F - Shortest Good Path (atcoder.jp) 啊shit，这题没做出来啊。这个dp状态属实想不到，之前写了好几次dfs都T了，看了题解才明白，用bfs好多了。 dfs无法保证第一个拓展到的点是长度最短的，但是bfs可以，然后下一次就不会拓展已经拓展了的点。于是bfs的复杂度比dfs低了很多。 题目大意 有一个N个点，M条无向边，现在有2^N条线路，分别是0 ~ […]

题目传送门：E - King Bombee (atcoder.jp) 没错，就是一个纯纯的DP，难在状态表示。 一开始我也以为是图论，但是观察到特点：取模、数据范围、奇偶性、求方案数。这些可都是DP的显著特征啊，于是考虑使用dp。 题目描述请看原题，自己翻译一下。 思路 这题难就难在表示状态，我们用dp[i][j][k]表示第i个点，在时间j（时间就是在序列中的位置），走过x的次数为奇数或偶数（1 […]