传送门 题解 树的直径不止一条，而题目要求我们把所有直径上的点给输出来。 数组名 数组作用 d1 i点到叶子节点的最长距离 d2 i点到叶子节点的次长距离 d3 i点向除子树外的最远距离 就拿样例来说，下面这个图应该很清楚了（红色的是树的直径） 显然，如果一个点满足d1+d2=树的直径或者d1+d3=树的直径，那么这个点肯定是树的直径上的点 代码 …

题目 题目描述 Tyvj 两周年庆典要到了，Sam 想为 Tyvj 做一个大蛋糕。蛋糕俯视图是一个 N×M的矩形，它被划分成 N×M个边长为 1×1的小正方形区域（可以把蛋糕当成 N 行 M 列的矩阵）。蛋糕很快做好了，但光秃秃的蛋糕肯定不好看！所以，Sam 要在蛋糕的上表面涂抹果酱。果酱有三种，分别是红果酱、绿果酱、蓝果酱，三种果酱的编号分别为 …

题目 题目描述 在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。 注：数据有加强（2018/4/25） 输入输出格式 输入格式 只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N） 输出格式…

题目 题目描述 Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a…

前言：最近做了很多动态规划题，但是每次遇到新的题目的时候还是做不出来，于是就像做一个小结，梳理下近些天做的题目，从中获取经验。 第零节：DP的基础概念 动态规划和其他某些算法具有一定的相似度，都是利用问题的可划分性以及子问题的相似性来进行归纳，降低时间复杂度。 来说说动态规划的几个基本条件： 条件 解释 无后效性 已求解的子问题不受后续阶段的影响[…

题目 题目描述 杨先生希望为他的班级拍照。学生将排成一行，每行不超过后面的行，并且行的左端对齐。例如，可以安排12名学生排列（从后到前）5,3,3和1名学生。 [crayon-67eceebdbb87c484295148/] 此外，杨先生希望每排学生安排高度从左到右减少。此外，学生身高应从后向前减少。想想看，杨先生看到，对于这个12人的例子，至少有…

题目 题目描述 设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下： subtree的左子树的加分× subtree的右子树的加分＋s…

题目 题目描述 在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。 试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分. 输入格式 数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数. 输出格式 …

题目 题目描述 有一个箱子容量为 V （正整数，$ 0 <= V <=20000 $），同时有 n 个物品（ $ 0<n<=30 $ ，每个物品有一个体积（正整数）。 要求 nn 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 注：此问题区分大小写 输入格式 1 个整数，表示箱子容量 1 个整数，表示有 n 个物品 …

题目 题目描述 回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字符，都可以变成回文词。此题的任务是，求出将给定字符串变成回文词所需要插入的最少字符数。 比如 “Ab3bd”插入2个字符后可以变成回文词“dAb3bAd”或“Adb3bdA”，但是插入少于2个的字符无法变成回文词。 注：此问题区分大小写 输入格式 一个字符串(0<st…