夜间模式
字体
阴影
滤镜
主题色

标签:LOJ

31 篇文章

10188. 「一本通 5.6 练习 1」玩具装箱
Link 题意 你可以将一段连续的玩具扔到同一个容器中,如果要将 $i$ 号玩具到 $j$ 号玩具 $(i\le j)$ 放到同一个容器中,则容器长度不小于 $x=j-i+ \displaystyle\sum_{k=i}^{j}C_k$制作容器的费用与容器的长度有关,根据教授研究,如果容器长度为 $x$,其制作费用为 $(X-L)^2$,其中 $L…
10152. 「一本通 5.1 练习 3」矩阵取数游戏
题意 帅帅经常和同学玩一个矩阵取数游戏: 对于给定的 $n\times m$ 的矩阵,矩阵中每个元素 $a_{ij}$ 均为非负整数。游戏规则如下: 1. 每次取数时必须从每行各取走一个元素,共 $n$ 个,$m$ 次取完所有元素。 2. 每次取走的各个元素只能是该元素所在行行首或行尾。 3. 每次取数都有一个的分值,为每行取数得分之和,每行取数得…
10238. 「一本通 6.6 练习 9」网格
题意 某城市的街道呈网格状,左下角坐标为 $A(0, 0)$,右上角坐标为 $B(n, m)$,其中 $n \ge m$。现在从 $A(0, 0)$ 点出发,只能沿着街道向正右方或者正上方行走,且不能经过图示中直线左上方的点,即任何途径的点 $(x, y)$ 都要满足 $x\ge y$,请问在这些前提下,到达 $B(n, m)$ 有多少种走法。 思…
10166. 「一本通 5.3 练习 1」数字游戏
题意 给定多组数据,每组数据给定三个数:$a,b,n$表示求在区间$[a,b]$内各位数之和模$n=0$的数的个数。 思路 这是一道数位$DP$的模板题。 设$f[i][S]$表示处理到第$i$位,$S$为和。 $f[i][S]=f[i-1][(S+i)%N](0<=k<=Dim[i] or 9)$ 其中$k$的取值范围根据上一位的状态…
10181. 「一本通 5.5 练习 2」绿色通道
题意 高二数学《绿色通道》总共有 $n$ 道题目要抄,编号 $1\dots n$,抄第 $i$ 题要花 $a_i$ 分钟。小 Y 决定只用不超过 $t$ 分钟抄这个,因此必然有空着的题。每道题要么不写,要么抄完,不能写一半。下标连续的一些空题称为一个空题段,它的长度就是所包含的题目数。这样应付自然会引起马老师的愤怒,最长的空题段越长,马老师越生气。…
10182. 「一本通 5.5 练习 3」理想的正方形
题意 有一个 $a\times b$ 的整数组成的矩阵,现请你从中找出一个 $n\times n$ 的正方形区域,使得该区域所有数中的最大值和最小值的差最小。 思路 设$dp[i][j][k]$表示以$i,j$为左上角的正方形变成为$k$内的最大值,$dp2[i][j][k]$表示最小值。 可知,$dp[i][j][k]=max(dp[i+1][j…
2240. 「CQOI2014」数三角形
三倍经验 LOJ #2240. 「CQOI2014」数三角形 BZOJ 3505: [Cqoi2014]数三角形 Luogu P3166 [CQOI2014]数三角形 (Luogu要大一些。。。) 题意 给定一个$n \times m$的网格,请计算三点都在格点上的三角形共有多少个。下图为$4 \times 4$的网格上的一个三角形。注意三角形的三…
10137. 「一本通 4.4 练习 4」跳跳棋
题意 跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏:棋盘上有三颗棋子,分别在 $a,b,c$ 这三个位置。我们要通过最少的跳动把他们的位置移动成 $x,y,z$(注意:棋子是没有区别的)。跳动的规则很简单,任意选一颗棋子,对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过一颗棋子。…
10187. 「一本通 5.6 例 4」Cats Transport
题意 小S养了$M$只猫,雇了$P$位饲养员。农场旁边有$N$座山,从$1$到$N$编号,第$i$座山与第$i-1$座山的距离为$D_i$,饲养员都住在$1$号山上。 有一天,第$i$只猫到第$H_i$座山玩,一直玩到$T_i$停止。饲养员们必须接回所有的猫,饲养员们行走的速度为$1$个单位每单位时间。 问如何计划每个饲养员从$1$号山出发的时间,…
10162. 「一本通 5.2 练习 5」骑士
题意 有$n$个骑士,每个骑士有一个自己的战斗值,每个骑士也有且仅有唯一一个自己讨厌的骑士,每个骑士不可能与自己讨厌的骑士一起上场战斗,问最高的战斗值之和是多少? 思路 这道题与没有上司的舞会很像。但是注意,这道题可能会有环的存在,所以我们需要对于每个环,把它切割成两部分,再分别树形dp,然后取最大值,加入ans中。 树形dp的思路很简单: 设$f…