标签:LOJ

11 篇文章

【模板】二维树状数组 & LOJ #133 二维树状数组 1
题面 题目链接 这是一道模板题。 给出一个  的零矩阵 ,你需要完成如下操作: 1 x y k:表示元素  自增 ; 2 a b c d:表示询问左上角为 ,右下角为  的子矩阵内所有数的和。 思路 一维树状数组的扩展 我们知道,一维树状数组可以求一段区间的和,将其扩展到二维,对于一个矩阵,每一层可以看做一个数,实际上是树状数组,每次求到每一层时求…
洛谷 P2756 飞行员配对方案问题 & LOJ #6000「网络流 24 题」搭配飞行员
题面 洛谷 P2756 飞行员配对方案问题 LOJ #6000.「网络流 24 题」搭配飞行员 因为 LOJ 上的版本比较简洁,所以就放这个版本的题面了。 飞行大队有若干个来自各地的驾驶员,专门驾驶一种型号的飞机,这种飞机每架有两个驾驶员,需一个正驾驶员(英国)和一个副驾驶员(外籍)。由于种种原因,例如相互配合的问题,有些驾驶员不能在同一架飞机上飞…
LOJ 10176 -「一本通 5.5 例 2」最大连续和
题面 题目传送 给你一个长度为 $n$ 的整数序列 ${a_1,a_2,\dots,a_n}$ ,要求从中找出一段连续的长度不超过 $m$ 的子序列,使得这个序列的和最大。 思路 单调队列优化 DP 模板题。 设 $t[i]$ 为 $s[1]+s[2]+\dots+s[i]$,则有状态转移方程 $f[i]=t[i]-min(t[i-1],t[i-2…
LOJ 10170 -「一本通 5.4 例 1」骑士
题面 题目传送门 在 $N*N$ 的棋盘上放 $K$ 个国王,国王可攻击相邻的 $8$ 个格子,求使它们无法互相攻击的方案总数。 思路 状压 DP 的模板,以前 DP 技能一直没怎么点,现在数据结构什么的都差不多了,开始补 DP。 预处理 对于每一行来说,我们可以用二进制来表示当前这一行的放置状态。然后再压成十进制。 然后预处理出对于一行来说的所有…
洛谷 P1486 & LOJ 10145 -「一本通 4.6 练习 2」郁闷的出纳员
题面 题目传送门 [collapse title="展开题面"] 题目描述 OIER公司是一家大型专业化软件公司,有着数以万计的员工。作为一名出纳员,我的任务之一便是统计每位员工的工资。这本来是一份不错的工作,但是令人郁闷的是,我们的老板反复无常,经常调整员工的工资。如果他心情好,就可能把每位员工的工资加上一个相同的量。反之,如果心情不好,就可能把…
洛谷 P2286 & LOJ 10144 -「一本通 4.6 练习 1」宠物收养所
题面 题目传送门 [collapse title="展开题面"] 题目描述 凡凡开了一间宠物收养场。收养场提供两种服务:收养被主人遗弃的宠物和让新的主人领养这些宠物。 每个领养者都希望领养到自己满意的宠物,凡凡根据领养者的要求通过他自己发明的一个特殊的公式,得出该领养者希望领养的宠物的特点值a(a是一个正整数,a<2^31),而他也给每个处在…
洛谷 CF776B & LOJ 10201 -「一本通 6.2 练习 4」Sherlock and His Girlfriend
题面 题目传送门 Sherlock 有了一个新女友(这太不像他了!)。情人节到了,他想送给女友一些珠宝当做礼物。 他买了 $n$ 件珠宝。第 $i$ 件的价值是 $i+1$ 。那就是说,珠宝的价值分别为 $2,3,4,.. ,n+1$ 。 Watson 挑战 Sherlock,让他给这些珠宝染色,使得一件珠宝的价格是另一件的质因子时,两件珠宝的颜色…
LOJ 10127 -「一本通 4.3 练习 1」最大数
题面 题目描述 给定一个正整数数列 $a_1, a_2, a_3, \dots , a_n$,每一个数都在 0~p-1之间。可以对这列数进行两种操作: 添加操作:向序列后添加一个数,序列长度变成 n+1; 询问操作:询问这个序列中最后 L 个数中最大的数是多少。 程序运行的最开始,整数序列为空。写一个程序,读入操作的序列,并输出询问操作的答案。 输…
LOJ 10160 – 「一本通 5.2 练习 3」周年纪念晚会 / 没有上司的晚会
题面 传送门 Ural 州立大学的校长正在筹备学校的 8080 周年纪念聚会。由于学校的职员有不同的职务级别,可以构成一棵以校长为根的人事关系树。每个资源都有一个唯一的整数编号,从 $1$ 到 $N$ 编号,且对应一个参加聚会所获得的欢乐度。为使每个职员都感到快乐,校长设法使每个职员和其直接上司不会同时参加聚会。 你的任务是设计一份参加聚会者的名单…