llllll_____的博客

转载 最小生成树--克里斯卡尔(Kruskal)+并查集

来源：JK老班克里斯卡尔：开始时，顶点集包含原图所有的点，边集E是空的。先把边从小到大排序。 从小到大依次选边加入边集E，加入的边要保证树不会形成圈，即(x, y)∈E，当T+(x, y)不会形成圈，就选这条边（把边加入最小生成树（子图）中）。如果会形成圈，不选。是否形成圈？x、y是否在同一个连通分支，是，会形成圈。原来的做法：跑1次DFS，看x能不能到y，能到，是一个连通分支...

转载 亲属关系--并查集训练T1

来源：JK老班问题描述：若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。输入格式：第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分...

转载 最高分是多少--线段树T1

来源：JK老班题目：老师想知道从某某同学到某某同学当中，分数最高的是多少。现在请你编程模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。输入：输入包含多组测试数据。每组输入第一行是两个正整数N和M（0<N<=30000,0<M<5000），分表代表学生的数目和操作的数目。学生ID编号从1编到N。第二行包含N个整数，代表这N个学生的初始成绩，其中第i...

原创 差值最大--动态规划T5

来源：JK老班题目：给一个长度为n的整数序列A0, A1,…, An-1, 找出两个整数Ai和Aj (i<j)，使得Ai-Aj尽量大。输入格式：输入的第一行包含组数K, 第二行开始每行一组数据用空格分隔输出格式：对于每组数据，输出Ai-Aj的最大值public class SubValue { public static void main(String[...

原创 二叉苹果树--树型动态规划T1

来源：JK老班题目:有一棵苹果树，如果树枝有分叉，一定是分 2 叉（就是说没有只有 1 个儿子的结点）。 这棵树共有 N 个结点（叶子点或者树枝分叉点），编号为 1-N,树根编号一定是 1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 4 个树枝 的树：2 5 \ / 3 4 \ / 1现在这颗树枝条太多...

原创 最长上升子序列--动态规划T8

来源：JK老班题目:给出一个由n个数组成的序列A[1..n]，求最长单调上升子序列（LIS)的长度。LIS即求最大的一个子序列长度m，使得a1<a2<……<am且A[a1]<A[a2]<……<A[am]。输入两行：第1行：整数n (1<=n<=1000)第2行：n个整数 （int范围内），空格隔开。输出一行：一...

原创 三角形--动态规划T3

来源：JK老班题目：73 88 1 02 7 4 44 5 2 6 5(图一)图一表示一个5行的数字三角形。假设给定一个n行数字三角形,计算出从三角形顶至底的一条路径，使该路径经过的数字总和最大。每一步只能由当前位置向下或右下。输入：你的程序要能接受标准输入。第一行包含一个整数T，表示总的测试次数。对于每一种情况：第一行包含一个整数N,其中1 ...

原创 和最大子序列--动态规划T6

来源：JK老班题目：对于一个给定的长度为N的整数序列A，它的“子序列”的定义是：A中非空的一段连续的元素（整数）。你要完成的任务是，在所有可能的子序列中，找到一个子序列，该子序列中所有元素的和是最大的（跟其他所有子序列相比）。程序要求你输出这个最大值。输入：输入文件的第一行包含一个整数N，第二行包含N个整数，表示A。其中1 <= N <= 100000-1000...

原创 Ones--动态规划T4

来源：JK老班题目：给一个整数n，要你找一个值为n的表达式，这个表达式只有1 + * ( ) 够成。并且1不能连续，比如11+1就不合法。输入：n,(1<=n<=10000)输出：最少需要多少个1才能构成表达式。样例：n=2=1+1 ans=2 n=10=(1+1)*(1+1+1+1+...

原创 跳楼梯--递归--动态规划--过渡

来源：JK老班题目：n阶楼梯，每次跳1 或 3 或 4阶，问有几种跳法？1.递归：#include<iostream>using namespace std;int count=0;//调用次数int F(int i){ count++; if(i==0) return 1; int sum=0; if(i>=1) sum+=F...

原创 拿石头--递归--动态规划--过渡

来源：JK老班题目：有n个石头，甲，乙2人轮流拿，每次只能拿1 或 3 或 4颗，拿到，拿到最后1颗的人输，甲先拿，问甲是赢是输？什么情况下甲能赢？如果有n-1颗石头的时候甲输（甲拿的石头中包含第n-1颗），或者有n-3颗石头的时候甲输（甲拿的石头中包含第n-3颗），或者有n-4颗石头的时候甲输（甲拿的石头中包含第n-4颗）。说明如果有n颗石头，那么拿到最后1颗石头的是乙，甲能赢。...

原创 找距离最小点对--分治

原创 求出给定2个自然数的最大公约数

来源：JK老班题目：求出给定2个自然数的最大公约数辗转相除法（欧几里德算法）377、319377÷319=1......58319÷58=5......2958÷29=2......0最大公约数为292、132÷13=0......213÷2=6......12÷1=2......0最大公约数为1当a%b != 0时，GCD(a , b)...

原创 查看调用次数

来源：JK老班import java.util.Scanner;public class test { static int count=0; static void F(int i) { count++; if(i<=2) return; F(i-1); F(i-2); } ...

原创 全排列--递归T1

来源：JK老班//全排列（有顺序）import java.util.Scanner;public class Permutation { int n; boolean[] Mark; int[] A; public Permutation() { Scanner sc=new Scanner(System.in);...

原创 组合--递归T2

来源：JK老班//组合（无顺序）import java.util.Scanner;public class Combination { int n,r; int[] A; public Combination() { Scanner sc=new Scanner(System.in); n=sc.nextIn...

原创 半数序列集--递归T4

来源：JK老班题目：给定数字n，n的半数序列集是（1）在 n 的右边加上一个自然数，但该自然数不能超过最近添加的数的一半，这样生了新的序列；（2）按此规则进行处理，直到不能再添加自然数为止。例如，4的半数序列集是｛4，4 2，4 2 1，4 1｝。输入：一个整数 n，(0<n<=50)。输出：按照数字降序，输出集合所有序列，每个序列一行，每个数字后面跟一个空格。样例输...

原创 组合--递归T6

来源：JK老班组合另一种方法降序输出import java.util.Scanner;//组合：降序输出public class Main { int n,m; int[] A; public Main() { Scanner sc=new Scanner(System.in); n=sc.ne...

原创 蛇形填数--递归T7

来源：JK老班题目：在n*n方阵里填入1,2,3,…,n*n，要求填成蛇形。例如n=4时方阵为：　 10 11 12 1　 9 16 13 2　 8 15 14 3　 7 6 5 4 上面的方阵中，多余的空格只是为了便于观察规律，不必严格输出，n<=8。输入：一个整数n，n≤8。输出：n行，每行n个整数...

原创 蛇形填数升级版--递归T8

来源：JK老班题目：蛇形填数，问第 i 排 j 列填的是什么数？模拟(全部填满，输出要求的)吗？先找出这个点在哪一圈的哪条边，再得出它的值。//升级版1469:蛇形填数，问第i排第j列放的是什么数字？//先找出这个点在哪一圈的哪条边上，算出它的值。import java.util.Scanner;public class P1470Query { int n;...

原创 组队选择--递归T3

来源：JK老班题目：逸才奉道玄掌门之命率领青云众弟子深入蛮荒之地寻找灵兽黄鸟，完成使命后率队需经过焚香谷镇守的幽暗小道。焚香谷门卫给一行人由1至n进行了编号，并有意为难让逸才选出k个人组成一队，他们的编号之和恰好等于m。逸才笑了笑说：“组队选择有许多种，你们要哪种？”焚香谷门卫顿时懵了，不知所措地说：“你们按号码降序输出所有方案吧。”输入：输入一行三个数字n，k和m。(n<=100,...

原创 java整型最大值

System.out.println(Integer.MAX_VALUE);