标签: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…
10161. 「一本通 5.2 练习 4」叶子的染色
题意 给一棵有 $m$ 个节点的无根树,你可以选择一个度数大于 $1$ 的节点作为根,然后给一些节点(根、内部节点、叶子均可)着以黑色或白色。你的着色方案应保证根节点到各叶子节点的简单路径上都包含一个有色节点,哪怕是叶子本身。对于每个叶子节点 $u$,定义 $c_u$ 为从根节点到 $u$ 的简单路径上最后一个有色节点的颜色。给出每个 $c_u$ …
10206. 「一本通 6.3 练习 1」X-factor Chain
题意 输入正整数 $x$,求 $x$ 的大于 $1$ 的因子组成的满足任意前一项都能整除后一项的序列的最大长度,以及满足最大长度的序列的个数。 思路 题目读起来很困难?告诉你题目的实际意思。 给你一个数,要求你输出将这个数分解成因式相乘,并且后面一个因子至少是前面一个因子的2倍,问最长的因式相乘链有多长,有几条最长的因式相乘链。 为什么可以这样转化…
10204. 「一本通 6.3 例 2」Hankson 的趣味题
题意 已知正整数 $a_0,a_1,b_0,b_1$,设某未知正整数 $x$ 满足:1. $x$ 和 $a_0$ 的最大公约数是 $a_1$;2. $x$ 和 $b_0$ 的最小公倍数是 $b_1$。Hankson 的「逆问题」就是求出满足条件的正整数 $x$ 的个数。 思路 先从第二个条件入手。 $$lcm(x,b_0)=b_1$$ 因为$lcm…
10156. 「一本通 5.2 例 4」战略游戏
题意 有一座古城堡,里面的路形成一棵树, 某个士兵在一个节点上时,与该节点相连的所有边都将能被瞭望到。问最少需要多少士兵才可以使所有的路都被瞭望到。 输入数据表示一棵树,描述如下。 第一行一个数 $N$ ,表示树中节点的数目。 第二到第 $N+1$ 行,每行描述每个节点信息,依次为该节点编号 $i$,数值 $k$,$k$ 表示后面有 $k$ 条边与…
10230. 「一本通 6.6 练习 1」牡牛和牝牛
题意 牡 mǔ,畜父也。牝 pìn,畜母也。 ——《说文解字》 约翰要带 $N$ 只牛去参加集会里的展示活动,这些牛可以是牡牛,也可以是牝牛。牛们要站成一排,但是牡牛是好斗的,为了避免牡牛闹出乱子,约翰决定任意两只牡牛之间至少要有 $K$ 只牝牛。请计算一共有多少种排队的方法,所有牡牛可以看成是相同的,所有牝牛也一样,答案对 $5000011$ 取…
10082. 「一本通 3.3 例 1」Word Rings
题意 每组数据读入一个n和n个字符串。定义前2个与末尾2个字母相同可以连接。问使这个环串的平均长度最大。求这个最大值。不存在输出No solution。 思路 平均值公式: $$Average=(E_1+E_2+…..+E_n)/n$$ $$Average*n=(E_1+E_2+…+E_n)$$ $$(E_1-Average)+(E_2-Avera…
10086. 「一本通 3.3 练习 3」Easy SSSP
题意 给你一个图,问从源点到每个节点的最短路径分别是多少。 如果存在负权回路,只输出一行 -1;如果不存在负权回路,再求出一个点 S 到每个点的最短路的长度。如果 S 与这个点不连通,则输出 NoPath。 思路 当然食用spfa啦。 先跑一下非源点的。万一数据卡你其他有环呢? 然后再跑一次源点。得出Ans [crayon-5db0827e899e…
10087. 「一本通 3.4 例 1」Intervals
题意 从$0\sim 5\times 10^4$中选出尽量少的整数,使每个区间$ [a_i,b_i]$内都有至少 $c_i$个数被选出。 思路 当然食用spfa啦。 设s[k]表示0~k中至少选多少个整数。根据题意可得: $$s[b_i]-s[a_i-1]\geq c_i$$ $$s[k]-s[k-1]\geq0$$ $$s[k]-s[k-1]\l…
10088. 「一本通 3.4 例 2」出纳员问题
题意 R(0)、R(1)、R(2)…R(23)表示第x个时刻需要R(x)个出纳员,有n个出纳员申请工作,第i个出纳员从t_i时刻开始工作8小时,问至少需要多少出纳员? 思路 设$x[i]$表示第$i$时刻实际上需要雇佣$x[i]$人,$r[i]$为第$i$时刻至少需要$r[i]$个人。 $$x[i-7]+x[i-6]+x[i-5]+x[i-4]+x…
10089. 「一本通 3.4 练习 1」糖果
题意 满足条件: 如果 X=1.表示第 A 个小朋友分到的糖果必须和第 B 个小朋友分到的精果一样多。 如果 X=2,表示第 A 个小朋友分到的糖果必须少于第 B 个小朋友分到的糖果。 如果 X=3,表示第 A 个小朋友分到的糖果必须不少于第 B 个小朋友分到的糖果。 如果 X=4,表示第 A 个小朋友分到的糖果必须多于第 B 个小朋友分到的糖果。…
10090. 「一本通 3.4 练习 2」布局 Layout
题意 有些奶牛是好基友,它们希望彼此之间的距离小于等于某个数。有些奶牛是情敌,它们希望彼此之间的距离大于等于某个数。 思路 如果两只奶牛是好基友,那么: $$A-B\leq D$$ 如果两只奶牛是情敌,那么: $$A-B\ge D$$ 即: $$D\leq A-B$$ 也就是: $$B-A\leq -D$$ 直接上代码: [crayon-5db08…
10117. 「一本通 4.1 练习 2」简单题
题意 有一个 $n$ 个元素的数组,每个元素初始均为 $0$。有 $m$ 条指令,要么让其中一段连续序列数字反转——$0$ 变 $1$,$1$ 变 $0$(操作 $1$),要么询问某个元素的值(操作 $2$)。 思路 当然是树状数组啦。。。 这里介绍C++的一大利器——位运算。 &在C++里叫做与运算。应该差不多吧。。大概就是这样的:(按一…
10121. 「一本通 4.2 例 3」与众不同
题意 定义完美序列:一段连续的序列满足序列中的数互不相同。 想知道区间 $[L,R]$ 之间最长的完美序列长度。 思路 设$las[x]$表示盈利$x$最近出现位置。 设$st[i]$表示以第$i$个数结尾的最长完美序列的起始位置。 $$st[i]=max(st[i-1],las[a[i]]+1)$$ 设$f[i]$表示以第$i$个数结尾的最长完美…
2597. 「NOIP2011」选择客栈
题意 有$n$个客栈,每个客栈都配有咖啡馆。有两名旅客想住在同色调的客栈中,又想在两客栈之间的咖啡馆中小聚,咖啡馆的价钱不能高于$p$。 对于 $100\%$ 的数据,有 $2\leq n\leq2\times 10^6$,$0<k\leq10^4$ ,$0\leq p\leq100$,$0\leq$ 最低消费 $\leq100$ 。 思路 …
10128. 「一本通 4.3 练习 2」花神游历各国
题意 每一次旅行中,花神会选择一条旅游路线,它在那一串国家中是连续的一段,这次旅行带来的开心值是这些国家的喜欢度的总和,当然花神对这些国家的喜欢程序并不是恒定的,有时会突然对某些国家产生反感,使他对这些国家的喜欢度 $\delta$ 变为 $\sqrt \delta$(可能是花神虐爆了那些国家的 OI,从而感到乏味)。 现在给出花神每次的旅行路线,…
10202. 「一本通 6.2 练习 5」樱花
题意 求不定方程: $$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$$ 的正整数解 $(x,y)$ 的数目。 思路 $$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$$ $$\frac{y}{xy}+\frac{x}{xy}=\frac{1}{n!}$$ $$\frac{x+y}{xy}=\…
10147. 「一本通 5.1 例 1」石子合并
题意 将 $n$ 堆石子绕圆形操场排放,现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数记做该次合并的得分。 请编写一个程序,读入堆数 $n$ 及每堆的石子数,并进行如下计算: 选择一种合并石子的方案,使得做 $n-1$ 次合并得分总和最大。选择一种合并石子的方案,使得做 $n-1$ 次合并得分总和最小。 思…
10153. 「一本通 5.2 例 1」二叉苹果树
题意 有一棵二叉苹果树,如果数字有分叉,一定是分两叉,即没有只有一个儿子的节点。这棵树共 $N$ 个节点,标号 $1$ 至 $N$,树根编号一定为 $1$。 我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果树,因为树枝太多了,需要剪枝。但是一些树枝上长有苹果,给定需要保留的树枝数量,求最多能留住多少苹果。 思路 设$f[i]…
10149. 「一本通 5.1 例 3」凸多边形的划分
题意 给定一个具有 $N$ 个顶点的凸多边形,将顶点从 $1$ 至 $N$ 标号,每个顶点的权值都是一个正整数。将这个凸多边形划分成 $N-2$ 个互不相交的三角形,试求这些三角形顶点的权值乘积和至少为多少。 思路 首先随便搞一个多边形: 然后给它顺时针每个顶点表上序号: 然后枚举$i,j$,要求:$i+1<j$,然后给$i,j$连一条线,分…
10106. 「一本通 3.7 例 2」单词游戏
题意 有 $N$ 个盘子,每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子安排一个合适的顺序,使得相邻两个盘子中,前一个盘子上单词的末字母等于后一个盘子上单词的首字母。请你编写一个程序,判断是否能达到这一要求。如果能,请给出一个合适的顺序。多组数据。第一行给出数据组数 $T$,每组数据第一行给出盘子数量 $N$,接下去 $N$ 行给出…
10178. 「一本通 5.5 例 4」旅行问题
题意 John 打算驾驶一辆汽车周游一个环形公路。公路上总共有 $n$ 车站,每站都有若干升汽油(有的站可能油量为零),每升油可以让汽车行驶一千米。John 必须从某个车站出发,一直按顺时针(或逆时针)方向走遍所有的车站,并回到起点。在一开始的时候,汽车内油量为零,John 每到一个车站就把该站所有的油都带上(起点站亦是如此),…