题目链接：最长递增子序列 【线性规划与网络流24题 6】最长递增子序列 Description 给定正整数序列x1, .., xn。 （1）计算其最长递增子序列的长度s。 （2）计算从给定的序列中最多可取出多少个长度为s的递增子序列。 （3）如果允许在取出的序列中多次使用x1和 xn，则从给定序列中最多可取出多少个长度为s的递增子序列。 编程任务： 设计有效算法完成（1）（2）（3）提出的计算任务。 Input 第1 行有 1个正整数n(n<500)，表示给定序列的长度。 接下来的1 行有 n个正整数x1, ..., xn. Output 程序运行结束时...

这场比赛充分说明了一个问题：读题大法好+模拟大法好！有个题好像数据还是标程有问题，最后给删掉了 所有只有ABCE四个题 A题：cf719A 这个题结果成了最“好”得分的题！ 如果手速快，并且敢去hack，相当于赚了1000分的C，而且稳得分 注意0和15的坑点就好了呀~~~ B题：cf719B 这个题比赛场上一直wa4：最后竟然不去重新读题也是自己蠢 In one turn he can either swap any two cockroaches, or take any single cockroach and change it's color. 这句话是关键...

数位DP的一道所谓的水题！ 但是呢，必须得胆子大！ 题意：求区间【L，R】中有多少个满足条件的十进制数 条件是：任意连续K个数值都不相同，K=2，3，4，5 dp最难的是设计状态和状态转移啊！ K很小，所以可以每一个有意义的数位都来一维来表示呗 dp[pos][p1][p2][p3][p4] pos表示当前位，p4表示前一位。这里要考虑前导0的情况，p4=10的时候表示前一位为0 然后呢，最特殊的情况是：全是0的情况 转移呢，枚举即可 判断条件要根据K来说咯，如果K=2，那么当前枚举的这一位不等于p4 K=3，4，5是同理的 代码如下： #includ...

看到这个式子，心里就很不爽啊！ 这要怎么搞啊！ 先贴个证明的方法：猜想的公式的证明 首先呢，题目中其实给的是三组样例哦 n=1，m=3，ans=4 n=1，m=2，ans=3 n=2，m=3，ans=13 有没有发现，当n变大一位的时候，ans变大得很多很多 尤其是n和m都是这么大的值的时候，这个题必定是个公式题 那么，我们来猜测一发公式吧！ 看到ans=13，会想到13是怎么来的？            27-1 13 = ---------  对吧               2 因为13是个素数，所以这是它唯一可以分解的形式了 那么看分子，27是个什么？...

题目链接：魔术球问题 【线性规划与网络流24题 4】魔术球 Description 假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为 1，2，3，...的球。 （1）每次只能在某根柱子的最上面放球。 （2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。 试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4 根柱子上最多可放11个球。 编程任务： 对于给定的n，计算在 n根柱子上最多能放多少个球。 Input 第1 行有 1个正整数n，表示柱子数。(0<n<60) Output /* 程序运行结束时，将 n 根柱子上最多能放...

题目链接：最小路径覆盖 【线性规划与网络流24题 3】最小路径覆盖 Description 给定有向图G=(V,E)。设P 是G 的一个简单路（顶点不相交）的集合。如果V 中每个顶点恰好在P 的一条路上，则称P是G 的一个路径覆盖。P 中路径可以从V 的任何一个顶点开始，长度也是任意的，特别地，可以为0。G 的最小路径覆盖是G 的所含路径条数最少的路径覆盖。设计一个有效算法求一个有向无环图G 的最小路径覆盖。 提示：设V={1，2，... ，n}，构造网络 G1=(V1,E1)如下： V1 = { x0, x1, ..., xn} U { y0, y1, ..., yn} , ...

这个题是卡特兰数的公式题 不需要讲太多的东西，关键是贴个大数的模板 bin神的模板改造过来 bin神的思路是一个int值保存一个整数的4个数位 其实在模拟题中，如果内存够的话，保存1个数位是更好处理的，因为可以更好的判断首位和末位的情况 改动如下： 把private的a数组和len值改为public的（不然在BigNum的定义外面没有访问的权限） 把DLEN改为1 把MAXN改为9 然后注意，istream和ostream其实可以不需要（因为可以先读取字符串，然后在转化成BigNum） 在print（）函数中 要把%04d改为%0d，因为现在一位中只有一个数字...

题目链接：圆桌问题 【线性规划与网络流24题 5】圆桌问题 Description 假设有来自 n 个不同单位的代表参加一次国际会议。每个单位的代表数分别为ri, i=1,2,...,n。会议餐厅共有 m张餐桌，每张餐桌可容纳 ci(i=1,2,...,m) 个代表就餐。为了使代表们充分交流， 希望从同一个单位来的代表不在同一个餐桌就餐。 试设计一个算法，给出满足要求的代表就餐方案。 编程任务： 对于给定的代表数和餐桌数以及餐桌容量，编程计算满足要求的代表就餐方案 Input 第1行有 2 个正整数m和 n，m表示单位数，n表示餐桌数，1<=m<=150, 1...

题目链接：试题库问题 【线性规划与网络流24题 7】试题库问题 Description 假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。 编程任务： 对于给定的组卷要求，计算满足要求的组卷方案 Input 文件第1行有2个正整数k和n (2 <=k<= 20, k<=n<= 1000)k 表示题库中试题类型总数，n 表示题库中试题总数。 第2 行有k 个正整数，第i 个正整数表示要选出的类型i 的题数。这k个数相加就是要选出的...

求四边形的费马点 费马点的定义：在平面上的到四边形四个顶点A，B，C，D的点 当ABCD为凸四边形的时候 可以证明M点是费马点，M是对角线的交点 当ABCD为凹四边形的时候 在ABCD四点中有某一个点为费马点 所以，这个点就是个计算几何的模板题啦~~~~~~ 我们也不需要判断四边形的凹凸性 把六条线段算出来，判断是不是有交点就好，然后暴力枚举每一个可能性 #include<bits/stdc++.h> using namespace std; const double eps=1e-6; const double inf=1e20; const d...

这种模拟题是很类似于南阳ccpc国赛的铜牌题难度的 所以，想要保证拿奖，这种恶心的题还是得写出来 题目大意是：现在有个棋盘，里面有黑色和白色的棋子，五子棋的游戏规则。问你，三步之内，是不是可能出现某一方的必胜情况 分析： A：如何判断哪方棋子先落子？ 如果黑色棋子数目=白色，那么黑先落子 如果黑色棋子数目=白色棋子数目+1，那么白色先落子 其他情况，不合法 B：如何判断第一步的情况？ 第一步，先落子方想要赢：只需要在棋盘上找到某一个点，使得成至少五子相连即可 C：如何判断第二步的情况？ 第二步，也就是说后落子方想要赢 条件1：先落子方赢不了 条件2：后落子...

【线性规划与网络流24题 12】软件补丁 Description T 公司发现其研制的一个软件中有n 个错误，随即为该软件发放了一批共m 个补丁程序。每一个补丁程序都有其特定的适用环境，某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时，往往会加入另一些错误。 换句话说，对于每一个补丁i，都有2 个与之相应的错误集合B1[i]和B2[i]，使得仅当软件包含B1[i]中的所有错误，而不包含B2[i]中的任何错误时，才可以使用补丁i。补丁i 将修复软件中的某些错误F1[i]，而同时加入另一些错误F2[i]。另外，每个补丁都耗费一定的时间。试设计一...

题意： n个青蛙，m个点，编号为0到m-1 每个青蛙的跳跃的距离为xi，起点都是0，问：m个点中，所有可以到达的编号的和是多少 分析样例： 先选个简单的： 2 12 9 10 （9）：产生的所有数是：3，6，9 （10）：产生的所有数是：2，4，6，8，10 发现了GCD：（9，12）=3，（10，12）=2 而且和是与GCD，m有关的一个式子 那么6多了，如何处理呢？容斥原理减掉 选个最麻烦的吧： 9 96 81 40 48 32 64 16 96 42 72 （81，96）=3，（40，96）=8，（48，96）=48，（32，96）=32，（64，9...

codeforces722C 题意：求按照序列删除之后的当前还剩下的数列中的最长的连续的子序列和 分析样例来说明白好了 5 1 2 3 4 5 4 2 3 5 1 删除的顺序是4，2，3，5，1 第一轮：数列变成了1 2 3 & 5（最大的连续子段和：1+2+3=6） 第二轮：数列变成了1 & 3 & 5（最大的连续子段和：5） 第三轮：数列变成了1 & & & 5（最大的连续子段和：5） 第四轮：数列变成了1 & & & &（最大的连续子段和：1） 第五轮：数列变成了& &...