例题： 十本不同的书放在书架上。现重新摆放，使每本书都不在原来放的位置。有几种摆法？  当n个编号元素放在n个编号位置，元素编号与位置编号各不对应的方法数用D(n)表示，那么D(n-1)就表示n-1个编号元素放在n-1个编号位置，各不对应的方法数，其它类推.  第一步，把第n个元素放在一个位置，比如位置k，一共有n-1种方法；  第二步，放编号为k的元素，这时有两种情况：⑴把它放到位置n，那么，对于剩下的n-1个元素，由于第k个元素放到了位置n，剩下n-2个元素就有D(n-2)种方法；⑵第k个元素不把它放到位置n，这时，对于这n-1个元素，有D(n-1)种方法；  综上得到  D(n) = (...

例题：  在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，问有多少种拆分方案。 啊啊啊啊  卡特兰数  卡特兰数又称卡塔兰数，卡特兰数是组合数学中一个常出现在各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名。 原理  令h(0)=1,h(1)=1，catalan数满足递推式：  h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)*h(0) (n>=2)  例如：h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2  h(3)=h(0)*h(2)+h(1)*h(1)+h...

描述 校门外有很多树，有苹果树，香蕉树，有会扔石头的，有可以吃掉补充体力的……  如今学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两个操作：  K=1，K=1，读入l、r表示在区间[l,r]中种上一种树，每次操作种的树的种类都不同  K=2，读入l,r表示询问l~r之间能见到多少种树  （l,r>0）  格式 输入格式 第一行n,m表示道路总长为n，共有m个操作  接下来m行为m个操作  输出格式 对于每个k=2输出一个答案  样例1 样例输入1 5 4  1 1 3  2 2 5  1 2 4  2 3 5  Copy  样例输出1 1  2  Co...

背景 你知道吗，SQ Class的人都很喜欢打CS。（不知道CS是什么的人不用参加这次比赛）。  描述 今天，他们在打一张叫DUSTII的地图，万恶的***要炸掉藏在A区的SQC论坛服务器！我们SQC的人誓死不屈，即将于***展开激战，准备让一个人守着A区，这样***就不能炸掉服务器了。（一个人就能守住??这人是机械战警还是霹雳游侠？）  但是问题随之出现了，由于DustII中风景秀丽，而且不收门票，所以n名反恐精英们很喜欢在这里散步，喝茶。他们不愿意去单独守在荒无人烟的A区，在指挥官的一再命令下，他们终于妥协了，但是他们每个人都要求能继续旅游，于是给出了自己的空闲时间，而且你强大的情报系统告...

网页链接http://218.62.22.209:8080/problem.php?cid=1599&pid=0  题目描述  平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。  比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。  输入  输入数据包含多个测试实例,每个测试实例占一行,每行包含一个正整数n（n<=20）,n表示直线的数量. 输出  Output  每个测试实例对应一行输出，从小到大列出所有相交方案，其中每个数为可能的交点数,每行的整数之间用一个空格隔开。  样例输入  2  3  样例输出  0 1  0 2 3 #include ...

#include <cstdio> #include <iostream> #include <queue> #include <cmath> using namespace std; int n; long long fai(int x){ long long re=x; for(int i=2;i<=sqrt(x);++i){ if(x%i==0){ re=re*(i-1)/i; } while(x%i==0) x/=i; } if(x!=1) re=re*(x-1)/x; return re; } int main(){ scanf(...

题目描述 麦克找了个新女朋友，玛丽卡对他非常恼火并伺机报复。 因为她和他们不住在同一个城市，因此她开始准备她的长途旅行。 在这个国家中每两个城市之间最多只有一条路相通，并且我们知道从一个城市到另一个城市路上所需花费的时间。 麦克在车中无意中听到有一条路正在维修，并且那儿正堵车，但没听清楚到底是哪一条路。无论哪一条路正在维修，从玛丽卡所在的城市都能到达麦克所在的城市。 玛丽卡将只从不堵车的路上通过，并且她将按最短路线行车。麦克希望知道在最糟糕的情况下玛丽卡到达他所在的城市需要多长时间，这样他就能保证他的女朋友离开该城市足够远。 编写程序，帮助麦克找出玛丽卡按最短路线通过不堵车道路到达他所在城市所...

题目描述  LIS问题是最经典的动态规划基础问题之一。如果要求一个满足一定条件的最长上升子序列，你还能解决吗？  给出一个长度为N整数序列，请求出它的包含第K个元素的最长上升子序列。  例如：对于长度为6的序列<2,7,3,4,8,5>，它的最长上升子序列为<2,3,4,5>，但如果限制一定要包含第2个元素，那么满足此要求的最长上升子序列就只能是<2,7,8>了。  输入  第一行为两个整数N,K，如上所述。  接下来是N个整数，描述一个序列。  80%的数据，满足0 < n <=1000，0 < k<=n  100%的数据，满足0 ...

题目描述  树的直径：树上两点之间的最大距离。 给出一个树，让你求树的直径。 输入 一个数n表示节点数，以下（n-1）行每行两个数x，y表示x与y间有边。 输出  一个整数，树的直径。 样例输入  10  2 8  7 2  2 1  1 10  2 3  3 4  4 9  3 5  3 6 样例输出  5 提示 40% n<=2000 100% n<=200000 #include <cstdio> #include <iostream> #include <queue> #include <cstring> #define N ...

1．计数  (count.cpp/c/pas)  时间限制：1s  内存限制：256MB  【问题描述】  给出m个数a[1],a[2],…,a[m]  求1~n中有多少数不是a[1],a[2],…,a[m]的倍数。  【输入】  输入文件名为count.in。  第一行，包含两个整数：n,m  第二行，包含m个数，表示a[1],a[2],…,a[m]  【输出】  输出文件名为count.out。  输出一行，包含1个整数，表示答案  【输入输出样例】  count.in count.out  10 2  2 3 3  【数据说明】  对于60%的数据，1<=n<=106  对于...

2．第k大区间  (kth.cpp/c/pas)  时间限制：1s  内存限制：256MB  【问题描述】  定义一个长度为奇数的区间的值为其所包含的的元素的中位数。  现给出n个数，求将所有长度为奇数的区间的值排序后，第K大的值为多少。  【输入】  输入文件名为kth.in。  第一行两个数n和k  第二行，n个数。（0<=每个数<231）  【输出】  输出文件名为kth.out。  一个数表示答案。  【输入输出样例】  kth.in kth.out  4 3  3 1 2 4 2 【样例解释】  [l,r]表示区间l~r的值  [1,1]：3  [2,2]：1  [3,3...

题目描述  题目描述  小澳最喜欢的歌曲就是《葫芦娃》。  一日表演唱歌，他尽了洪荒之力，唱响心中圣歌。  随之，小澳进入了葫芦世界。  葫芦世界有n个葫芦，标号为1~ n。n个葫芦由m条藤连接，每条藤连接了两个葫芦，这些藤构成了一张有向无环图。小澳爬过每条藤都会消耗一定的能量。  小澳站在1号葫芦上（你可以认为葫芦非常大，可以承受小澳的体重），他想沿着藤爬到n号葫芦上，其中每个葫芦只经过一次。  小澳找到一条路径，使得消耗的能量与经过的葫芦数的比值最小。  输入  输入文件第一行两个正整数n,m，分别表示葫芦的个数和藤数。  接下来m行，每行三个正整数u,v,w，描述一条藤，表示这条藤由u连...

2370 小机房的树  时间限制: 1 s  空间限制: 256000 KB  题目等级 : 钻石 Diamond  题解  题目描述 Description  小机房有棵焕狗种的树，树上有N个节点，节点标号为0到N-1，有两只虫子名叫飘狗和大吉狗，分居在两个不同的节点上。有一天，他们想爬到一个节点上去搞基，但是作为两只虫子，他们不想花费太多精力。已知从某个节点爬到其父亲节点要花费 c 的能量（从父亲节点爬到此节点也相同），他们想找出一条花费精力最短的路，以使得搞基的时候精力旺盛，他们找到你要你设计一个程序来找到这条路，要求你告诉他们最少需要花费多少精力 输入描述 Input Descript...

T1  低价购买  问题描述：  “低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(216范围内的正整数)，你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买；再低价购买”的原则。写一个程序计算最大购买次数。  这里是某支股票的价格清单：  日期 1 2 3 4 5 6 7 8 9 10 11 12  价格 68 69 54 ...