看上去很复杂的一个题. 然而数据范围 ( n \leq 50 ) 基础知识0: python 里面 list 可以做 dict 的 key. 基础知识1: python 里面 list 可以直接比较大小, 比较方式就是元素的字典序. 做法是先按照 username 对记录进行归类 (dict of list). 然后把每个 username 对应的所有记录按 timestamp 进行排序. (sorted(…, key=lambda …)) 然后枚举每个用户的所有访问页面三元组并扔进 list 里面. 因为要求一个用户只算一次, 所以要去除 list 里面重复的元素. 所以把 list 转换成 set (集合) 就好了. 也可以直接用 set. 然后把 set 里面的元素都用一个 dict 做一下记数. 最后从记数的 dict 里面挑出次数最多且字典序最小的就可以了. 代码链接
首先弄清楚中序遍历是什么意思. 中序遍历是一个序列 (list). 不存在的节点的中序遍历是空序 ([]). 以 u 为根的二叉树的中序遍历 = u 的左儿子的中序遍历 + u + u 的右儿子的中序遍历 其中加号就是连接两个序列的意思. 题目里说只考虑叶子节点的中序遍历, 就是把所有非叶子从中序里扔掉就好了. 然后考虑从随便一个序列构造一个满足条件的二叉树. 其实这个二叉树上的任意一个点会对应原序列中的连续一段, 而这个点的值就是这一段的所有数的最大值. 我们考虑自底向上的建树. 也就是说最开始是 n 个单独的点, 然后每次建一个新点, 它的两个儿子分别是原来的两个点. 然后用这个新点代替原来的两个点. 重复 “挑选, 替代” 的过程直到只剩一个点, 就建成了一棵完整的树. 每次挑选的两个点一定代表原数组上相邻的两个区间. 合并后建成这棵树的 最小 代价为 左儿子的最小代价 + 右儿子的最小代价 + 左边最大值 * 右边最大值. 而我们的最小化目标是根的 最小 代价. 自然想到用 f[l][i] 代表以 i 为第一个数的长度为 l 的区间所代表的点为根的树 的 最小 代价. 首先 f[1][i] == a[i], 而我们的目标是 f[n][0]. 进一步想, 最小化 f[l][i] 就是在所有该点的左右儿子分配方式 (就是各有多长, 总之加起来是 l) 中挑一个最小的....
很基础的 BFS 题目. BFS 和 DFS 是相对应的两种算法. 其区别在于对于新发现的可能性, BFS 将其放入队列末尾, 稍后进行探索, 而 DFS 立即探索这种新情况, 等探索完之后再回到之前的状态继续枚举. 对于这道题目来说, 具体来讲, 状况可以用 (位置, 距离, 颜色) 这么一个 tuple 来表示. 最开始的时候, 有 (0, 0, blue) 和 (0, 0, red) 这两种情况. 假设 0到1 有一条蓝边, 0到2 有一条红边, 那么新的情况是 (1, 1, red) 和 (2, 1, blue). 如果我们使用 DFS, 那么当新发现 (1, 1, red) 这个状态的时候, 我会立即以 (1, 1, red) 为起点, 继续探索 1 号点的邻居, 比如找到了 (3, 2, blue) … 直到找完所有通过 (1, 1, red) 可以达到的状态之后, 再继续以 (2, 1, blue) 为基础进行枚举....
先预处理一下, 把 >8h 的变成 +1, <=8h 的变成 -1 现在问题就变成了: 找最长的连续一段使其和 >0 使用前缀和数组, 要求 i~j 的和, 公式是 sum[j] - sum[i - 1]. 枚举左端点 i. 对于某个确定的 i, 要找以 i 为左端点的最长一段符合要求的区间, 即找满足条件 sum[j] > sum[i - 1] 的最大的 j 注意到 sum 数组的取值为 [-n, n], 故使用值域数组 values. value[k] 表示 sum[j] == k 的最大的 j. 该数组可以在求 sum 数组时一并求出. 满足条件 sum[j] > sum[i - 1] 的最大 j 即求 values[sum[i - 1] + 1], values[sum[i - 1] + 2], values[sum[i - 1] + 3], …, values[正无穷] 中的最大值....
状压动态规划. dp[x] 表示 x 状态下的最少人数. 其中 x 是二进制数, 第 i 位表示第 i 项技能是否有人已经拥有. 例如 ( x = (10010)_2 ) 从右往左第 1, 4 位是 1, 表示技能 1, 4 已有人掌握, 而 0, 2, 3 无人掌握. 假设一个人的技巧是 p, 现在的状态是 x, 则加入后的状态是 x|p. 其中 | 即 python/cpp 中的 | 运算符, 意义是取二进制或. 运算过程为最初时只有 dp[0] = 0. 对于每个人的技能集合 p, 可以更新 dp 数组 dp[x | p] = min(dp[x | p], dp[x] + 1) 最后的答案是 dp[((111\dots 1)_2)] 即 dp[(1 « len(skills)) - 1]...
PA3-3 题意 一堆字符串判循环相等 做法 最小表示法模板题 也可以直接 hash 不过最小表示了也得 hash. PA <= 常数优化实习. 可能会在这里贴代码.
1 使用数论快速傅立叶变换进行多项式乘法. 要压三位才能过. 2 先把两维坐标分别快速排序 然后每个问题二分 然后建立两个向量, 看它们的夹角是劣的还是优的, 从而判断这个点在线段和坐标轴围成的三角形的内外 3 维护一个栈 如果右边所有数里的最大值都没有栈顶大, 就弹栈, 否则一直压栈到右边最大的数, 输出最大的数, 然后重复执行此操作. 4 在普通的队列里再维护一个单调队列, 对价格单调. 每次从单调队列里选择当前持有的股票, 用普通队列维护添加 / 删除. 5 替罪羊树维护序列. 至今 90 的数据有一个点 wa 掉不知为何. 可能满跑速度有点悬. 6 利用双向链表进行操作. 链表并不记录前后, 而是只记录两个端. 每个光标记录左右. 然而还是被卡常了.
组合数 求n和m都各在一个范围里的组合数里能被k整除的数的个数. 用熟悉的组合数的公式. \( C_n^m = C_{n-1}^{m-1} + C_{n-1}^m \) 把组合数先处理出来. 对于多组询问, 求出上面那个数组的二维前缀和即可. 蚯蚓 你有n只蚯蚓. 每秒把最长的蚯蚓砍成同比例的两段, 且其它蚯蚓变长. 求m秒中每一秒被砍的蚯蚓和最后所有的蚯蚓. \( n \leq 10^5, m \leq 7*10^6 \) 目测那个t只是为了输入输出不超时. 正常的暴力是用堆来维护蚯蚓长度. 发现一个性质, 下一次被砍的蚯蚓被砍之后两段肯定会分别短于本次被砍的蚯蚓的两段. 仔细想想没有低于\( O(m) \) 的做法. 所以我们把堆换成若干个队列, 每次只取队首的蚯蚓来比较, 砍, 然后塞回队尾. 保证队列中的元素单调. 这样时间复杂度就变成线性了. 小鸟 平面上有若干只猪. 你可以从原点发射一个抛物线并消灭抛物线上的所有猪. 求最小发射多少次. \( n \leq 18 \) 我们知道两点确定一条过原点的抛物线. 所以枚举两只猪就能得到所有能消灭至少两只猪的消灭方式. 剩余的猪只能直接消灭. 可以使用状态压缩型动态规划来解决这个问题. 只需要记录下当前已经消灭了哪些猪, 就可以进行转移了. ps 题目难度还是比去年高. 祝各位好运. laekov版权所有, 未经允许不得转载. 侵权必究.
简单看了看NOIP2016的题. 口糊一下自己的想法吧. 玩具 描述好乱. 反正就是一群人围成圈, 若干次左走右走问最后到哪. 加加减减取模就好了. 水水水水过. 跑步 一棵n个点的树, m条路径, 问对于每个点, 经过本点且起点距离本点为本点点权的路径条数. \( n, m \leq 3*10^5 \) 我感觉这个题有点难呀. 很有可能是我想复杂了. 把每条路径从lca处拆成两段. 考虑对于每个点的询问. 对于起点到lca这段, 询问就是询问子树里lca深度小于等于当前深度的深度刚好为某个值的路径起点个数. 对于lca到终点这段, 询问就是询问子树里lca深度小于等于当前深度的 (长度-深度) 刚好为某个值的路径终点个数. 然后就成了一个比较简明的数据结构问题. 一种思路是平衡树启发式合并, 但是时间可能会炸. 另一种思路是用dfs序式树链剖分, 每条路径会被拆分为不超过lg个dfs序上的子段. 在路径的每个子段的起点和终点处分别打上标记. 然后对dfs序进行一次扫描即可得出答案. 复杂度比较优. 换教室 n节课, v间教室. 每节课有两种教室位置选择, 其中一种是已定的. 你有m次机会申请换掉其中一节课的教室位置, 每个请求有独立的p的概率成功. 教室在一张图上, 求最小总奔波路期望. \( n, m \leq 10^3, v \leq 3*10^2 \) 个人认为这题比上一题水. 先用floyd处理出任意两间教室间的最短路. 然后用dp. \( f_{i,j,k} \) 表示前i间教室, 用了j次交换机会, k表示上一次有没有换. 存答案. 转移就是一个概率的算式, 较为简单. 略. ps 八年来第一次没有在赛场上考noip. 今年题目描述好长好长好长....
题意: 给你n个数和一个k. 求这n个数的一个最小子集, 使得元素乘积为k的倍数, 且元素之和最小. 要输出方案. \( n \leq 10^3, k \leq 10^{12} \) 结局: 死在输出方案上了. 思路: 首先发现k的质因数不会很多, 最多有14个. 然后k的因数也不会很多. 所以就dp一下. \(f_i\)表示当前积与k的gcd为i的时候的元素个数. 然后就像个背包一样嘛. 输出方案? 记录从哪里转移来的不就好了. 然后. 考虑这个例子. 3 9 3 24 21 你会先拿24从3更新到9. 然后21就会把3和9的转移都更新. 然后就炸了. 因为3应该是从原来的状态更新的. 但是现在被覆盖了. 然后发现状态是棵树. 可以把状态可持久化记下来. 更新一个状态的时候, 不是直接覆盖, 而是新建一个状态来保证从原来的状态转移出去的情况不会出错. 这样空间复杂度应该和转移次数有关? 然后怎么就糊过去了. 另一个细节是k=1是答案不能是0. woc. 依然感觉很鬼蓄. 代码