来源：牛客网： 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld  题目描述  小西有一条很长的彩带，彩带上挂着各式各样的彩珠。已知彩珠有N个，分为K种。简单的说，可以将彩带考虑为x轴，每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠，但多个彩珠也可以出现在同一个位置上。 小布生日快到了，于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮，小西希望这一段彩带中能包含所有种类的彩珠。同时，为了方便，小西希望这段彩带尽可能短，你能帮助小西计算这个最短的长度么？彩带的长度即为彩带开始位置...

文章目录    题目描述： 题解： 代码：    题目描述：  链接：https://ac.nowcoder.com/acm/problem/112798 来源：牛客网 输入描述:  输出描述:  Print q lines — the answers for the queries.  示例1 输入 复制 3 8 4 1 2 2 3 1 2  输出 复制 5 12  示例2 输入 复制 6 1 2 4 8 16 32 4 1 6 2 5 3 4 1 2  输出 复制 60 30 12 3  备注:  In first sample in both queries the maximum va...

【每日一题】8月28日题目精讲 编号 链接：https://ac.nowcoder.com/acm/problem/19925 来源：牛客网 题目描述  你需要给一批商品编号，其中每个编号都是一个7位16进制数（由0~9, a-f组成）。为了防止在人工处理时不小心把编号弄错，要求任意两个编号至少有三个位置对应的数字不相同。第一个编号为0000000，第二个编号为不违反上述规定的前提下最小的编号，…，每次分配一个新编号时，总是选择不和前面编号冲突的最小编号（注意编号都是16进制数，可以比较大小）。 按此规律，前面若干编号分别是：0000000, 0000111, 0000222, …, 0000...

链接：https://ac.nowcoder.com/acm/problem/105905 来源：牛客网 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 10000K，其他语言20000K 64bit IO Format: %lld 题目描述 A tree is a well-known data structure that is either empty (null, void, nothing) or is a set of one or more nodes connected by directed edges between nodes satisfying the...

1153 Decode Registration Card of PAT (25分) 题意： 给出一组学生的准考证号和成绩 准考证号组成为：考试等级（TAB），考场号（从101到999），考试日期（yymmdd），考生号（000到999） 有三种查询方式： 第一种：给出考试等级，找到该等级的考生，然后按照成绩降序，准考证升序 排列 第二种：给出考场号，给出该考场的考生数量和总得分 第三种：给定考试日期，查询该日期下所有每个考场对应的考试人数，按照人数降序，考场号升序排列 题解： 前两个查询暴力找就行 第三个用按照日期查询每个考场人数，用unordered_map存储，最后排序 用map会超时，...

题意 给出一个L长的字符串，求出其中第一个k位长的素数 题解： 其实就是暴力求解，不过在这介绍一个函数 int num=stoi(s); s是string型的，stoi可以将string转换成int型 string f_str = std::to_string(f); 是将int型转化成string型 代码 #include<bits/stdc++.h> #include<string> using namespace std; bool judge(int num) {  if(num==1)return 0; if(num==0)return 0; for(int ...

题意： 给出一棵二叉搜索树的前序遍历，问结点u和v的共同最低祖先是谁，利用先序遍历特点。 二叉搜索树满足： 节点的左子树只包含键小于节点键的节点。 节点的键只包含节点的右键大于或等于子树的节点的键。 左子树和右子树也必须是二叉搜索树。 题解： 样例： 6 3 1 2 5 4 8 7 根据题目要求我们可以得到：  红字则是该数字在前序遍历中出现的顺序（从0开始） 我们可以从题目要求下手，在本题中，根的左子树总是小于根，右子树总是大于根 查询u和v的lca，如果一个x（x不与u和v重合）同时满足x>u,x<v,说明u在x的左边，v在x的右边，那说明x就是u和v的lca 同理。x<...

题意： 给定前序遍历和中序遍历，问u和v的lca （先是中序，后是中序） 题解： 方法一： 参考题解 将树映射到一颗BST上，在BST上找到答案然后再映射回原本的树 方法二： 参考题解 已知某个树的根结点，若a和b在根结点的左边，则a和b的最近公共祖先在当前子树根结点的左子树寻找，如果a和b在当前子树根结点的两边，在当前子树的根结点就是a和b的最近公共祖先，如果a和b在当前子树根结点的右边，则a和b的最近公共祖先就在当前子树的右子树寻找。中序加先序可以唯一确定一棵树，在不构建树的情况下，在每一层的递归中，可以得到树的根结点，在此时并入lca算法可以确定两个结点的公共祖先～ 代码： #inclu...

题意： 有n个玩家，有两个狼人，有两人说慌（其中一个为狼人一个为非狼人），找出狼人是谁？ 题解： 暴力枚举 先枚举i和j为狼人，然后从1号开始假设其说谎，然后判断是否符合题目要求 代码： #include<stdio.h> #define maxn 110 int wolf[maxn],st[maxn]; int N; int main(){  int i,j,k; int w,lair; scanf("%d",&N); for(i=1;i<=N;i++){  scanf("%d",&st[i]); } for(i=1;...

题意： 给一个二叉树的层次遍历，问是什么类型的堆，是大顶堆还是小顶堆，然后输出这个树的后续遍历 题解： 大小堆根直接比较a[i]与a[i/2]即可 因为给的树的层次遍历，i就是i/2儿子 后序遍历，对于节点index分别遍历孩子index2和右孩子index2+1，遍历完左右子树输出根节点 代码建议背诵 代码：  #include <iostream> using namespace std; int a[1005], m, n; void postOrder(int index) {  if (index > n) return; postOrder(index * 2);...

文章目录  数位dp   NC116652 uva11038 How many 0's NC15035 送分了QAQ NC20669 诡异数字 NC20665 7的意志 NC17385 Beautiful Numbers CF55D NC108918 Beautiful numbers    数位dp NC116652 uva11038 How many 0’s 题目：输入a和b，求a到b的所有数之中有多少0出现 题解： 先算个位，个位是0的情况有x种 再算十位，十位是0的情况有y种 … 一共是x+y+… 用数位dp做 dp[i]中存的是从0~99…9(共i个9)中0的个数（不含前导0） dp...

Neat Tree 题意： n个数，每个区间的贡献为区间内最大值减最小值，问这个n个数的总贡献是多少？也就是n所能组成的所有区间的贡献值之和 题解： 我们可以用单调栈来做 第i个数对答案的贡献值为=h[i] * 作为最大值出现的次数-h[i] * 作为最小值出现的次数 求每个点贡献值的过程可以用单调栈来维护 例如求最大值的次数： 对于第i点，找到左端第一个比h[i]大的数，记其位置为L，找到右端第一个比h[i]大的数，记其位置为R，(默认第0个位置最小，第n+1个位置最大)则区间(L,R)区间内包含点i的子区间个数就是(i-L) * (R-i) 答案的贡献就是h[i] * (i-L) * (R...

文章目录    [ZJOI2007]棋盘制作 题意： 题解：   单调栈   代码：  悬线法     [ZJOI2007]棋盘制作 题意： 选取最大的01相邻的正方形和矩形，输出面积 题解： 单调栈  如图： 左图为题目给的样例，我们要找01相邻最大的正方形  就是图中绿色部分 矩形就是如图 01相邻不好找，我们可以转换下思路，仔细看看正方形和矩形的两个图，0和1相邻说明0和1同行但列差1，同列但行差1，所以我们可以通过坐标奇偶性取反 奇数行偶数列取反，偶数行奇数列取反 这样就会得到： 第一个图的右图：  这样我们就将01问题转换成求最大的全1正方形和矩阵问题 最大正方形的边长其实就是最大矩...

【悬线法】学习总结 主要用于求满足某条件的最大矩阵 定义： 一条竖线，竖线的上端点位于矩阵的上边界或是一个障碍点，然后对这条悬线进行左右移动，直到移至障碍点或者是矩阵边界，进行确定这条悬线所在的极大矩阵。 底线为(i,j)的悬线 Left[]存每个点能达到的最右位置 Right[]存放每个点能到达的最左边的位置 height[]为高度 递推公式： height[i,j]=height[i-1,j]+1 left[i,j]=max( left[i-1,j] , (i-1,j)左边第一个障碍点位置,边界0也是障碍点 ) right[i,j]=max( right[i-1,j] , (i-1,j)右...