夜间模式
字体
阴影
滤镜
主题色
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$ 取…
洛谷 P3419 [POI2005]SAM-Toy Cars题解
题目描述 Jasio 是一个三岁的小男孩,他最喜欢玩玩具了,他有n 个不同的玩具,它们都被放在了很高的架子上所以Jasio 拿不到它们. 为了让他的房间有足够的空间,在任何时刻地板上都不会有超过k 个玩具. Jasio 在地板上玩玩具. Jasio'的妈妈则在房间里陪他的儿子. 当Jasio 想玩地板上的其他玩具时,他会自己去拿,如果他想玩的玩具在…
CF293B Distinct Paths 题解
题意 给定一个$n\times m$的矩形色板,有kk种不同的颜料,有些格子已经填上了某种颜色,现在需要将其他格子也填上颜色,使得从左上角到右下角的任意路径经过的格子都不会出现两种及以上相同的颜色。路径只能沿着相邻的格子,且只能向下或者向右。 计算所有可能的方案,结果对 $1000000007 (10^9 + 7)$ 输入及输出格式 输入格式 第一…
洛谷 P1992 不想兜圈的老爷爷 题解
题目描述 一位年过古稀的老爷爷在乡间行走 而他不想兜圈子 因为那会使他昏沉 偶然路过小A发扬助人为乐优良传统 带上地图 想知道路况是否一定使他清醒 usqwedf补充:为了让欢乐赛充满欢乐 小A还想问你一些数学作业…… 输入输出格式 输入格式: 一行 n m k 表示乡间共有 n 个村庄 m 条道路 接下来 m 行 每行两个整数 x y 表示 村 …
CF2B The least round way 题解
题目传送门 题意(直接复制了QWQ) 题目描述 给定由非负整数组成的$n \times n$的正方形矩阵,你需要寻找一条路径: 以左上角为起点, 每次只能向右或向下走, 以右下角为终点 并且,如果我们把沿路遇到的数进行相乘,积应当是最小“round”,换句话说,应当以最小数目的0的结尾. 输入格式 第一行包含一个整数 $(2 \leq n \leq…
P4009 汽车加油行驶问题 题解
当然食用spfa啦。 但本蒟蒻不会分层。所以就二维spfa啦。 基本思路就是:一开始先把(1,1)点的状态扔进队列。 然后分类讨论 详细见代码 丑陋无比的代码: [crayon-5e2fd689c5ced111609128/]