编程题库

题面描述 老师有一棵有 $n$ 个结点的树，结点依次以 $1,2,\dots,n$ 编号。 老师想将这棵树作为奖品分给两位同学。具体而言，老师会选择一条边并从树上删去它，从而将这棵树分为两个连通块。两位同学分别可以得到其中一个连通块。 如果有同学拿到的连通块结点数明显小于另一位同学，那么这位同学会不太高兴。为了避免这种情况出现，老师想知道两个连通块结点数之差的绝对值最小是多少。 输入格式

题面描述 给定 $n$ 个整数构成的数组 $A = [a_1,a_2,\dots,a_n]$ 。 你需要将数组 $A$ 划分为若干非空连续子段。对于划分得到的某个子段，它的偏差值定义为子段内整数和的平方。划分方案的偏差值定义为所有子段偏差值之和。 你需要最小化划分方案的偏差值。 形式化地，你可以将 $A$ 划分为若干非空连续子段 $A_1,A_2,\dots,A_k$ ，使得 $A = A_1 +

题面描述 给定一棵包含 $n$ 个结点的有根二叉树，结点依次以 $1,2,\dots,n$ 编号，根结点编号为 1。 对于结点 $i$ ，其左儿子的编号记为 $l_i$ ，右儿子编号记为 $r_i$ 。特别地，如果左儿子不存在则 $l_i=0$ ，如果右儿子不存在则 $r_i=0$ 。 树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有 $n$ 棵子树中，有多少棵

题面描述 寒假到了，小杨同学打算找一份兼职，顺便体验一下打工人的生活。 小杨同学给一家蛋糕店发送了一份自己的简历，希望可以在寒假来这里帮忙。店长最近正好遇到了一个难题：店里每天会做一条长条蛋糕，但是不同长度的蛋糕块卖出的价格不同，应该怎么分才能卖得最多呢？ 有趣的是店长曾经学习过计算机专业。他最近对动态规划算法很感兴趣，于是打算用这个问题考一考小杨同学，问题如下： 给定一条长度为 $n$ 的长条蛋

题面描述 给定一棵包含 $n$ 个结点的有根二叉树，结点依次以 $1,2,\dots,n$ 编号，根结点编号为 $1$ 。 对于结点 $i$ ，其左儿子的编号记为 $l_i$ ，右儿子编号记为 $r_i$ 。特别地，如果左儿子不存在则 $l_i=0$ ，如果右儿子不存在则 $r_i=0$ 。 树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有 <span class

题面描述 给定两个包含 $n$ 个整数的数组 $a = [a_1, \dots, a_n]$ 与 $b = [b_1, \dots, b_n]$ 。你需要指定若干下标 $p_1 < \dots < p_k$ （ $1 \leq k \leq n$ ）使得以下条件成立： $1 \leq p_i \leq n \quad (1 \leq i \leq k)$ ； $p_{i+1} \g

题面描述 道具商店里有 $n$ 件道具可供挑选。第 $i$ 件道具可为玩家提升 $a_i$ 点攻击力，需要 $c_i$ 枚金币才能购买，每件道具只能购买一次。现在你有 $k$ 枚金币，请问你最多可以提升多少点攻击力？ 输入格式 第一行，两个正整数 $n,k$ ，表示道具数量以及你所拥有的金币数量。 接下来 $n$ 行，每行两个正整数 $a_i,c_i$ ，表示道具所提升的攻击力点数，以及购

题面描述 给定一棵有 $n$ 个结点的有根树 $T$ ，结点依次以 $1,2,\dots,n$ 编号，根结点编号为1。方便起见，编号为 $i$ 的结点称为结点 $i$ 。 初始时 $T$ 中的结点均为白色。你需要将 $T$ 中的若干个结点染为黑色，使得所有叶子到根的路径上至少有一个黑色结点。将结点 $i$ 染为黑色需要代价 $c_i$ ，你需要在满足以上条件的情况下，最小化染色代价之和。 叶子是

题面描述 A国有 $n$ 座城市，依次以 $1,2,\dots,n$ 编号，其中1号城市为首都。这 $n$ 座城市由 $n-1$ 条双向道路连接，第 $i$ 条道路（ $1 \leq i &lt; n$ ）连接编号为 $u_i,v_i$ 的两座城市，道路长度为 $l_i$ 。任意两座城市间均可通过双向道路到达。 现在 A 国需要从首都向各个城市运送货物。具体来说，满载货物的车队会从首都开出，经过一

题面描述 小A有一个由 $n$ 个小写字母组成的字符串 $s$ 。他希望将 $s$ 划分为若干个子串，使得子串中每个字母至多出现一次。 例如，对于字符串street来说，str + e + e + t是满足条件的划分；而s + tree + t不是，因为子串tree中e出现了两次。 额外地，小A还给出了价值 $a_1,a_2,\dots,a_n$ ，表示划分后长度为 $i$ 的子串价值为

题面描述 给定一棵有 $10^9$ 个结点的有根树，这些结点依次以 $1,2,\dots,10^9$ 编号，根结点的编号为 $1$ 。对于编号为 $k$ （ $2 \leq k \leq 10^9$ ）的结点，其父结点的编号为 $k$ 的因数中除 $k$ 以外最大的因数。 现在有 $q$ 组询问，第 $i$ （<span class="ql-formula" data-v

题面描述 班主任计划将班级里的 $n$ 名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。观察发现，如果一个学习小组中恰好包含 $k$ 名同学，则该学习小组的讨论积极度为 $a_k$ 。 给定讨论积极度 $a_1,a_2,\dots,a_n$ ，请你计算将这 $n$ 名同学划分为学习小组的所有可能方案中，讨论积极度之和的最大值。 输入格式 第一行，一个正整数 $n$

题面描述 小A喜欢坐地铁。地铁环线有 $n$ 个车站，依次以 $1,2,\dots,n$ 标号。车站 $i$ （ $1\le i <n$ ）的下一个车站是车站 $i+1$ 。特殊地，车站 $n$ 的下一个车站是车站 $1$ 。 小A会从某个车站出发，乘坐地铁环线到某个车站结束行程，这意味着小A至少会经过一个车站。小A不会经过一个车站多次。当小A乘坐地铁环线经过车站 $i$ 时，小A会获得</sp

题面描述 小A有一棵 $n$ 个结点的树，这些结点依次以 $1,2,\dots,n$ 标号。 小A想在这棵树上漫步。具体来说，小A会从树上的某个结点出发，每一步可以移动到与当前结点相邻的结点，并且小A只会在偶数步（可以是零步）后结束漫步。 现在小A想知道，对于树上的每个结点，从这个结点出发开始漫步，经过偶数步能结束漫步的结点有多少个（可以经过重复的节点）。 输入格式 第一行，一个正整数 $n$ 。

题面描述 小杨管理着 $m$ 辆货车，每辆货车每天需要向A市和B市运送若干次物资。小杨同时拥有 $n$ 个运输站点，这些站点位于A市和B市之间。 每次运送物资时，货车从初始运输站点出发，前往A市或B市，之后返回初始运输站点。A市、B市和运输站点的位置可以视作数轴上的三个点，其中A市的坐标为0，B市的坐标为 $x$ ，运输站点的坐标为 $p$ 且有 $0&lt;p&lt;x$ ，货车每次去A市运送

题面描述 小杨有一棵包含无穷节点的二叉树（即每个节点都有左儿子节点和右儿子节点；除根节点外，每个节点都有父节点），其中根节点的编号为 1，对于节点 $i$ ，其左儿子的编号为 $2 \times i$ ，右儿子的编号为 $2 \times i + 1$ 。 小杨会从节点 $s$ 开始在二叉树上移动，每次移动为以下三种移动方式的任意一种： 第1种移动方式：如果当前节点存在父亲节点，向上移动

题面描述 小杨计划学习 $m$ 种算法，为此他找了 $n$ 道题目来帮助自己学习，每道题目至多学习一次。 小杨对于 $m$ 种算法的初始掌握程度均为 0。第 $i$ 道题目有对应的知识点 $a_i$ ，即学习第 $i$ 道题目可以令小杨对第 $a_i$ 种算法的掌握程度提高 $b_i$ 。小杨的学习目标是对 $m$ 种算法的掌握程度均至少为 <span class=

题面描述 小杨有一个正整数 $n$ ，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。 小杨请你编写程序计算出总和为 $n$ 的完全平方数的最少数量。 输入格式 第一行包含一个正整数 $n$ ，含义如题面所示。 输出格式 输出一个整数，代表总和为 $n$ 的完全平方数的最少数量。 样例1 输入： 18 输出： 2 样例解释 $18=9+9=16+1+1$ ，其

题面描述 小杨有一棵包含 $n$ 个节点的二叉树，且根节点的编号为1。这棵二叉树任意一个节点要么是白色，要么是黑色。之后小杨会对这棵二叉树进行 $q$ 次操作，每次小杨会选择一个节点，将以这个节点为根的子树内所有节点的颜色反转，即黑色变成白色，白色变成黑色。 小杨想知道 $q$ 次操作全部完成之后每个节点的颜色。 输入格式 第一行一个正整数 $n$ ，表示二叉树的节点数量。 第二行

题面描述 小杨想要计算由 $m$ 个小写字母组成的字符串的得分。 小杨设置了一个包含 $n$ 个正整数的计分序列 $A = [a_1,a_2,\cdots,a_n]$ ，如果字符串的一个子串由 $k\ (1 \leq k \leq n)$ 个 abc 首尾相接组成，那么能够得到分数 $a_k$ ，并且字符串包含的字符不能够重复计算得分，整个字符串的得分是计分子串的总和。 例如，假设