@[toc] 题意： 你在钓鱼，每次钓鱼固定时间为k（必定钓上一条鱼），池塘一共n条鱼，钓上鱼后要煮，每条鱼煮的时间不相同，可以在煮鱼的同时钓鱼，问钓上所有的鱼并煮完需要最短的时间是多少？ 题解： 每条鱼必被煮，所以煮鱼时间固定，我们要求的就是钓鱼时间。总时间=第一次钓鱼时间+煮鱼时间+额外的钓鱼时间为什么是额外的？因为我们可以在煮鱼的时候钓鱼，相当于两者抵消了一部分，煮鱼时间要%k，表示抵消后的煮鱼时间额外的钓鱼时间=捕鱼固定时间 - 处理过后的钓鱼时间要让额外时间越少，我们就要使得处理过后的钓鱼时间越长我们可以排序从大到小，先处理大的数据 代码： #include<bits/stdc...

题目 题意: 有一群牛，每个牛有两个属性值[S,E]，如果牛i和牛j属性值满足Si <= Sj 且 Ej <= Ei 且 Ei - Si > Ej - Sj，牛i比牛j强壮，输出每个牛比自己强壮的牛的数量。 题解： 我们可以把[S,E]看作坐标，条件Si <= Sj 且 Ej <= Ei 且 Ei - Si > Ej - Sj其实就是：求每个点左上角有多少点我们先将e按照降序，然后s按照升序这样的话，越往前的牛越弱我们可以用树状数组来求和计算 代码： #include <iostream> using namespace std; #includ...

试题链接 题意： 求出一个１到ｎ的排列，这个排列只告诉了你从第二个数字开始的比这个数字小的数的个数。 题解： 如果一个数p，p的前面有m个比他小的数，后面有n个比他小的数，那p的位置就是n+m+1我们可以二分这个p，如果m+n+1>mid,mid就取小了；否则就取大了p前面有多少比他小的数，在输入答案时就知道了p后面有多少比他小的数，可以用树状数组来搞定我们在处理时应该倒序处理，想想最后一个数的真实值就是a[n]+1,然后删除最后一个数，看倒数第二个，一次类推即可 代码： # include<cstdio> # include<iostream> # includ...

题意： m个星星，一个星星的等级取决于有多少其他星星的横纵坐标不大于它，如果有x个，该星星等级为x问各个等级的星星有多少个？（题目会按照y的升序给出星星坐标） 题解： 树状数组入门题（不要问我为什么又开始做入门题。。。好久没做树状数组都忘干净了）因为题目会按照y的升序给出星星坐标，所以星星A后面输入的x，y不可能都小于星星A，我们只需要在树状数组中找小于等于3的值即可，A[i]表示x坐标为i的个数，C[]为A[]的树状数组，那么GetSum(i)就是 序列中前i个元素的和，即x小于等于i的星星数。记得将x坐标统一加一，因为有可能x坐标为0。。 代码： #include<iostream&...

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

题意 给出一个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 i=2;...

题意： 给出一棵二叉搜索树的前序遍历，问结点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,x>v也是当...

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

题意： 有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;i&l...

题意： 给一个二叉树的层次遍历，问是什么类型的堆，是大顶堆还是小顶堆，然后输出这个树的后续遍历 题解： 大小堆根直接比较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); pos...

@[toc] 数位dp NC116652 uva11038 How many 0's 题目：输入a和b，求a到b的所有数之中有多少0出现题解：先算个位，个位是0的情况有x种再算十位，十位是0的情况有y种.........一共是x+y+..... 用数位dp做dp[i]中存的是从099...9(共i个9)中0的个数（不含前导0）dp0[i]中存放的是00...099...9(共i个0，i个9)中0的个数（含前导0）dp0[i]=dp0[i-1] * 10+power * (10,i-1)dp[i]=dp[i-1]+dp0[i-1]*9 NC15035 送分了QAQ 每次给出一个区间[n,m],求...

来源：牛客网： 题目描述 题目背景把一张纸对折100次就和珠穆朗玛峰一样高了哦 ——syh题目描述 注:本系列题不按难度排序哦 输入描述: 第一行一个n,m 接下来一行n个数表示a[i] 接下来m行，每行l,r,l1,r1,x，表示求get(l,r,x)get(l1,r1,x)输出描述:3×m行，先输出get(l,r,x),再输出get(l1,r1,x)，再输出get(l,r,x)get(l1,r1,x)示例1输入复制 5 1 2 2 2 2 2 1 5 1 3 2 输出复制 5 3 15 说明 题解： 莫队的裸题把l,r和l1,r1都读入，并放在一起排序，然后进行莫队最后按照原先顺序输出 代...

以前一直有接触，但是一直没单独进行分析处理单调栈：维护其中元素单调性的栈也就是从栈底到栈顶都是有序的维护：如果入栈的元素满足单调性，直接入栈；如果不满足，就让栈顶元素出栈，直到能让入栈元素满足单调性为止，再将元素入栈（已经出栈的元素就被抛弃） 例题： 求直方图中包含的最大矩阵面积 题解链接单调栈问题我们可以用一个单调栈来维护每个矩阵的高度和宽度，当前矩阵高于栈顶，进栈当前矩阵a小于栈顶时，直到栈为空或者栈顶矩形的高度比当前矩形小。在出栈过程中，我们累计被弹出的矩形的宽度和。每弹出一个矩形，就用他的高度（他指被弹出的矩阵）乘上累计的宽度取更新答案，因为每次弹出的高度要比上次弹出的小，相当于依次求...

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