好题好题，太棒了这题！直接想是十分困难的，你连\(dp\)状态都想不出合理的，因此考虑二分答案，转化成一个判定问题。下文\(d\)表示二分出的答案。设\(sum_i\)表示\(i\)子树内的合法路径数，那他就一共分为两部分：来自于\(sum_{son}\)，直接累加即可。经过\(i\)的路径。我们

算法对于一棵树的情况,dfs+贪心选取显然是正确的对于基环树的情况我们观察到城市不能重复行走所以长为\(L\)的环最多只会被访问\(L-1\)条边枚举断边,再跑dfs+贪心即可代码#include<bits/stdc++.h>constintMAXN=5e3+20;intn,m;std::vector<int>e

题目描述给定一棵有\(n\)个节点的树，根节点为\(1\)，节点\(i\)有权值\(w[i]\)。这棵树非常奇怪，它的每个叶子结点都有一条连向根节点的权值为\(0\)的边。给定\(q\)次询问，每次给定\(u,v\)，请计算出一条\(u\)到\(v\)的路径（每条边最多经过\(1\)次），最小化该路径上的点权之和，并在其基础上最

[NOIP2018提高组]铺设道路题目背景NOIP2018提高组D1T1题目描述春春是一名道路工程师，负责铺设一条长度为$n$的道路。铺设道路的主要工作是填平下陷的地表。整段道路可以看作是$n$块首尾相连的区域，一开始，第$i$块区域下陷的深度为$d_i$。春春每天可以选择一段连续

原题链接：https://www.luogu.com.cn/problem/P5018题意解读：找到是对称二叉树的最大子树节点数。解题思路：1、先统计每一个节点为子树的节点数intdfs1(introot){if(root==-1)return0;returncnt[root]=dfs1(tree[root].l)+dfs1(tree[root].r)+1;}2、再

原题链接：https://www.luogu.com.cn/problem/P5017题意解读：先将问题进行抽象、建模。设一条数轴，从左到右，每个点对应一个时刻，每个时刻可能有多个人到达，然后有若干个发车时刻，每两个发车时刻间隔必须>=m，每个人的等待时长就是到最近一个发车时刻的时间累加，计算所有人等待时间最小值。

题1：标题统计题目描述凯凯刚写了一篇美妙的作文，请问这篇作文的标题中有多少个字符？注意：标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字符数时，空格和换行符不计算在内。【输入格式】输入文件只有一行，一个字符串

明显要以\(1\)为起点。原图是树这种情况下，走路不能回头，只能用\(dfs\)的思路走。当然肯定每次都走较小的那棵子树，\(vector\)存图后排序即可达到这种效果。时间复杂度\(O(n\logm)\)。原图是基环树明显可以分别考虑将所有边断掉后的情况，取字典序最小的。时间复杂度\(O(

P5021[NOIP2018提高组]赛道修建在树上选\(m\)条不重合的路径（可以有交点），使得这些路径长度的最小值最大。看到最小值最大，很自然想到二分模型：枚举最小值\(L\)，看大于等于\(L\)的路径能不能有\(m\)条。如何在树上选出\(m\)条路径最优成为我们要思考的问题，考虑树上贪心。

原题链接题解等价于线性代数中求最大无关组的大小code#include<bits/stdc++.h>usingnamespacestd;intmain(){intt;cin>>t;while(t--){intn;cin>>n;inta[105]={0};for(inti=1;i<=n;i++)cin>>a[i]

原题链接：https://www.luogu.com.cn/problem/P5019题意解读：最短时间内填满道路，连在一起的不为0的坑可以一起填解题思路：方法1：分治法对于一段连续不同深度的坑，可以最多连续填的天数是最小深度在填满最小深度之后，分别针对其左边和右边的区域再进行填充，这就是此题分治法的理论基

1.题目介绍[NOIP2018普及组]标题统计题目背景NOIP2018普及组T1题目描述凯凯刚写了一篇美妙的作文，请问这篇作文的标题中有多少个字符？注意：标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字符数时，空格和换行符不计算在内。输入格式输入文件只有一行，

观察题目不难想到二分答案。考虑二分所有赛道的最小长度值，那么我们可以去判断最后修建出来的赛道数是不是大于等于\(m\)条即可。用\(f_{i}\)表示当前以\(i\)为根，最长的未被赛道占用的链的长度。但是有很多链，匹配的过程不好进行，所以改为用multiset来维护当前点的链有多

先递归判断当前子树是不是对称二叉树，如果是就取\(\max\)然后退出，否则继续递归左儿子的左子树和右儿子的右子树、左儿子的右子树和右儿子的左子树判断。最坏情况是每次都递归到叶子，也就是每层都是\(O(n)\)。但一共只有\(O(\logn)\)层，所以时间复杂度是\(O(n\logn)\)。

前言一日知基环树弱，固补题。关于基环树基环树定义一个环，环上每个点都有一颗以该点为根的树，如下图为一棵基环树关于基环树常规思路通常来说基环树常规思路是先处理环上树的结果，后通过树的结果来处理换上结果。具体处理方式依照题目来定。然而只是通常来说因为基环树的问

题目描述传送门凯凯刚写了一篇美妙的作文，请问这篇作文的标题中有多少个字符？注意：标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字符数时，空格和换行符不计算在内。输入格式输入文件只有一行，一个字符串\(s\)。输出格式输出文件只有一行，包含一个整数，即作

#include<cstdio>#include<algorithm>usingnamespacestd;constintN=105;constintA=25005;inta[N];booldp[A];intmain(){ intt;scanf("%d",&t); while(t--){ intn;scanf("%d",&n); for(inti=

题目链接挺综合的一道题目。询问最小值最大，考虑二分最小值，二分上下界是\([最小边权,树的直径]\)，但是为了方便我们直接设为\([1,5\times10^8]\)即可。考虑如何\(check\)，可以采用类似树形\(dp\)的方式进行贪心。对于节点\(u\)的子树，\(u\)内部的点显然可以构成几条链，同

2.下列属于解释执行的程序设计语言是（）A.C B.C++ C.Pascal D.Python错误原因：忘记了正解：C、C++和Pascal都是编译性语言，而Python是解释性语言 5.设某算法的时间复杂度函数的递推方程是 T(n)=T(n-1)+n（n 为正整数）及 T(0)=1，则该算法的时间复杂度为（）A.O(logn) 

Link因为是道NOIP，那么我们不妨按照考场上的策略一点一点想。先看部分分，有一档有很明显的特征\(n=m-1\)这显然构成一棵树，对于一棵树，我们想把他按照题目的要求遍历完，一定是像dfs的遍历顺序一样，对于一个点，必然遍历完以它为根的子树，才能回到它的父亲节点，于是就有了一个很明显的贪

1.标题统计原题：https://www.luogu.com.cn/problem/P5015#include<bits/stdc++.h>#definelllonglongusingnamespacestd;strings;intans=0;intmain(){ getline(cin,s);intlen=s.length(); for(inti=0;i<len;i++){ if(s[i]>='0'&&

[NOIP2018普及组]标题统计题目描述凯凯刚写了一篇美妙的作文，请问这篇作文的标题中有多少个字符？注意：标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字符数时，空格和换行符不计算在内。输入格式输入文件只有一行，一个字符串\(s\)。输出格式输出文件只有

这里没有代码，去相应的文章找。。。一、基础1、排序冒泡、选择、插入、快排、归并、堆、桶找k大数、排序+链表找最近值、2、高精度四则运算和高精四则运算和低精开根号3、模拟递推最大子段和矩阵找数4、二分5、贪心6、倍增二、动态规划最大字段和LIS字符串三、数学数论同余四、数据

截至目前见过的最妙背包问题。藏的真的很深。有必要为此写一篇笔记。题意给你一个货币系统\(A\)，其中包含\(n\)种不同面值的货币，第\(i\)种货币面值为\(a_i\)。

注意：此题题解写的较为简略。P5020[NOIP2018提高组]货币系统转化为完全背包即可。#include<iostream>#include<cstring>#include<algorithm>usingnamespaces