文章目录    题目描述 题解： 代码：     传送  时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld  题目描述  给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。  输入描述:  第一行一个数n表示点的个数； 接下来n-1行，每行两个整数x，y表示边； 保证输入数据形成一棵树； 1<=n<=100000  输出描述:  一行一个整数表示答案。  示例1 输入 3 1 2 1 3  输出 1  ...

牛客网题目 题目描述  给出一个长度为n的序列，你需要计算出所有长度为k的子序列中，除最大最小数之外所有数的乘积相乘的结果  输入描述:  第一行一个整数T，表示数据组数。 对于每组数据，第一行两个整数N，k，含义如题所示 接下来一行N个整数，表示给出的序列 保证序列内的数互不相同  输出描述:  对于每组数据，输出一个整数表示答案，对109 + 7 取模 每组数据之间以换行分割  示例1 输入 3 4 3 5 3 1 4 5 4 3 7 5 2 1 10 3 100 1020 2050 102 12 235 4 57 32135 54354  输出 144 81000 521918013  ...

文章目录    题目描述 题解： 代码     传送  时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 131072K，其他语言262144K 64bit IO Format:%lld  题目描述  求所有长度为n的01串中满足如下条件的二元组个数： 设第i位和第j位分别位ai和aj（i<j），则ai=1,aj=0。 答案对1e9+7取模。  输入描述: 输入一个n。 输出描述: 输出答案对1e9+7取模 示例1 输入 3  输出 6  说明  备注: n <= 1018 题解： 就是一个求逆序对 我们看如果1后面有5个0，就能构成5个逆序对 也就是我们考虑任意两个...

文章目录    关于时间复杂度： Kruskal讲解 Kruskal模板 Prim讲解 Prim模板     昨天做蓝桥杯的题，最后一题最小生成树，但好久没用一下子生疏了。。。  又过了几天离散学到了最小生成树。。。趁此复习一波 最小生成树两种方法： Prim和Kruskal 关于时间复杂度： prim:该算法的时间复杂度为O(n2)。与图中边数无关，该算法适合于稠密图。 kruskal:需要对图的边进行访问，所以克鲁斯卡尔算法的时间复杂度只和边又关系，可以证明其时间复杂度为O（eloge）。适合稀疏图。 Kruskal讲解 利用并查集来求 连通块：无向图中相互连通 的一些点 具体步骤：将一个...

ST表主要用于解决RMQ问题（区间最值问题） 当然你可以用线段树等，但今天用一种ST表（倍增算法） ST表是倍增算法的一个典型应用 暴力做RMQ问题，往往会超时，ST表利用对其进行优化 给定一段序列A，ST算法能在O(NlogN)的时间预处理后，以O(1) 的复杂度查询，在线回答在一段区间l,r 中最大（小）值是多少。 f[i][j]用于表示在序列a中， 从第i位数字往后数2j个数，这个区间内的最大值，即区间[ i , i + 2 j ]内取得的最大值。 而这段区域的最大值等于左右子区间的最大值,2j = 2 * 2 j-1 = 2j-1 + 2j-1,把区间[i,i+2j]分成[i , i ...

文章目录    LCA介绍 解决方法概括： 倍增法： Tarjan 欧拉序 树剖解法：     看了很多关于LCA的文章，这里是一个总结 我们通过这个题洛谷P3379 【模板】最近公共祖先来讲LCA LCA介绍 lca是啥？最近公共祖先 就是：两个点在这棵树上距离最近的公共祖先节点 LCA（x，y）=z，z是x与y的最近公共祖先，（换句话说z的深度要尽可能大） 来看一个经典图  LCA（4,5）=2 LCA（4,3）=1 LCA

文章目录    题目描述 题解： 代码： 推荐例题：     试题链接  时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld  题目描述 二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也就是说，对于一根长度为N的木棍，华华可以精准的将它们裁剪为若干段木棍，使它们的长度之和为N。 华华不知道裁剪成多长比较好，所以...

链接：  时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 131072K，其他语言262144K 64bit IO Format:%lld  题目描述  Nancy喜欢吃果冻！ Nancy钻进了一个n \times n \times nn×n×n的果冻里，她想从(1,1,1)一路上、下、左、右、前、后六个方向吃到(n,n,n)。 但果冻毕竟是有许多口味的，标记为*的口味是Nancy不愿意吃的，其余的果冻均标记为.。 Nancy不想吃坏肚子，于是她想尽可能少的吃果冻。 下面给出果冻的情况，请你帮忙计算一下她能吃多少块果冻叭！  输入描述:  第一行：一个整数n。 接下来n层，每组...

链接：  时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 131072K，其他语言262144K 64bit IO Format:%lld  题目描述  赛时提示：保证出发点和终点都是空地 帕秋莉掌握了一种木属性魔法 这种魔法可以生成一片森林（类似于迷阵），但一次实验时，帕秋莉不小心将自己困入了森林 帕秋莉处于地图的左下角，出口在地图右上角，她只能够向上或者向右行走  现在给你森林的地图，保证可以到达出口，请问有多少种不同的方案 答案对2333取模 输入描述:  第一行两个整数m , n表示森林是m行n列 接下来m行，每行n个数，描述了地图 0 - 空地 1 - 树（无法通过）...

链接 表达式求值  时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 131072K，其他语言262144K 64bit IO Format: %lld  题目描述  给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。  输入描述:  输入仅有一行，为需要你计算的表达式，表达式中只包含数字、加法运算符“+”和乘法运算符“*”，且没有括号。 所有参与运算的数字均为 0 到 231-1 之间的整数。 输入数据保证这一行只有0~9、+、*这12种字符。 输出描述: 输出只有一行，包含一个整数，表示这个表达式的值。注意：当答案长度多于4位时，请只输出最后4位，前导0不输出。 ...

来源：牛客网 Sunscreen  时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld  题目描述  To avoid unsightly burns while tanning, each of the C (1 ≤ C ≤ 2500) cows must cover her hide with sunscreen when they’re at the beach. Cow i has a minimum and maximum SPF rating (1 ≤ minSPFi ≤ 1,000; mi...

试题 糖糖别胡说，我真的不是签到题目  时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 131072K， 其他语言262144K 64bit IO Format:%lld  题目描述  从前，有n只萌萌的糖糖，他们分成了两组一起玩游戏。他们会排成一排，第i只糖糖会随机得到一个能力值bi。从第i秒的时候，第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。 为了使游戏更加有趣，糖糖的爸爸，娇姐，会发功m次，第i次发功的时间为ci，则在第ci秒结束后，b1,b2,…,bci都会增加1. 现在，娇姐想知道在第n秒后，会有多少只糖糖存活下来。  输入描述:  第...

链接：  时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 524288K，其他语言1048576K 64bit IO Format:%lld  题目描述  小雨所在的城市一共有 m 条地铁线，分别标号为 1 号线，2 号线，……，m 号线。整个城市一共有 n 个车站，编号为 1∼n 。其中坐 i 号线需要花费 ai的价格，每坐一站就需要多花费 bi的价格。i 号线有 ci个车站，而且这 ci个车站都已知，如果某一站有多条地铁线经过，则可以在这一站换乘到另一条地铁线，并且能多次换乘。现在小雨想从第 ss 个车站坐地铁到第 t 个车站，地铁等待时间忽略不计，求最少花费的价格，若不能...

链接：  时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 65536K，其他语言131072K 64bit IO Format:%lld  题目描述  Alice are given an array A[1…N] with N numbers. Now Alice want to build an array B by a parameter K as following rules: Initially, the array B is empty. Consider each interval in array A. If the length of this interv...