子希

算法设计与分析题库

ACM动态规划(4) ACM花里胡哨(1) c++(4) Dijkstra(5) javafx开发(1) java学习(1) oj几何(1) oj贪心(7) oj递归(5) stl练习题(6) 动态规划(2) 单调栈(4) 图论最小生成树(6) 图论-网络流(1) 图论最短路(8) 图论（杂）(5) 字典树(2) 字符串(8) 并查集(14) 思维题(23) 数据结构实现(2) 数据结构实验(2) 数论(1) 暴力(1) 暴力搜索(26) 有趣的数学题(1) 未归档(2) 树状数组(6) 模拟(3) 每日一题(1) 离散数学实验(5) 线段树(10) 网络比赛(6) 题解(43)

/ 注册

全部文章 / 算法设计与分析题库（共15篇）

循环赛日问题

循环赛日问题：设有n=2^k个选手参加循环赛，要求设计一个满足以下要求比赛日程表： 1）每个选手必须与其它n-1个选手各赛一次； 2）每个选手一天只能赛一次。分析，按照上面的要求，可以将比赛表设计成一个n行n-1列的二维表，其中第i行第j列的元素表示和第i个选手在第j天比赛的选手号。思...

2020-05-21

0 585

整数划分问题

Problem Description “Well, it seems the first problem is too easy. I will let you know how foolish you are later.” feng5166 says. “The second problem...

2020-05-21

0 629

选择问题

第k小的数 Description 现有一个包含n个整数（1<=n<=900000）的无序序列(保证序列内元素各不相同)，输入一个整数k（1<=k<=n）,请用较快的方式找出该序列的第k小数并输出。 Input 多组输入。首先输入一个数据组数T（1<=T<=...

2020-05-21

0 470

最大间隙问题

最大间隙问题 Description 最大间隙问题：给定n个实数x1,x2,……,xn，求这n 个数在实轴上相邻2 个数之间的最大差值。假设对任何实数的下取整方法耗时O(1)，设计解最大间隙问题的线性时间算法。对于给定的n 个实数x1,x2,……,xn，计算它们的最大间隙。 Input 输...

2020-05-21

0 1071

棋盘划分问题

思路：为了完整的用完（4^k - 1）/3 个L型骨牌，不妨采用四等分划分，对于没有特殊方格的区域构造一个L型骨牌，这样使得所有区域再放一下L型骨牌刚刚好把整个棋盘放满，然后再进行四等分递归划分，直到只有一个方格时才结束划分，应该算是一个经典的分治法吧。代码： #include<bits/...

2020-05-21

0 609

半数集问题

问题描述：给定1个自然数n，求由n产生的半集数set(n)中的数：n∈set(n)，在n左边加一个不超过最近添加的数一半的数，不断这样处理，直至不能添加自然数为止。如：输入n=6 得到set(6)={6,16,26,126,36,136,236}，共6个元素。思路：这题比较简单，因为左边不能...

2020-05-21

0 760

整数因子分解问题

整数因子分解问题 Description 大于1的正整数n可以分解为：n=x1x2…xm。例如，当n=12 时，共有8 种不同的分解式： 12=12； 12=62； 12=43； 12=34； 12=322； 12=26； 12=232； 12=22*3。对于给定的正整数n，计算n共有多少种...

2020-05-21

0 1335

最长公共子序列

最长公共子序列问题 Description 给定两个序列 X={x1,x2,…,xm} 和 Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。 Input 输入数据有多组，每组有两行，每行为一个长度不超过500的字符串（输入全是大写英文字母（A,Z）），表示序列X和Y。 Output ...

2020-05-21

0 746

矩阵连乘问题

问题描述：矩阵连乘问题是通过给矩阵连乘时加括号，使得总的计算量最小。考虑3个矩阵相乘的例子， A1,A2,A3,假设这3个矩阵的维数分别为 10x100,100x50,5x50 若按照（（A1A2）A3）方式计算，需要的数乘次数为10x100x5+10x5x50 = 7500 若按照（A1...

2020-05-21

0 1228

FatMouse and Cheese(DP+记忆化搜索)

题意：给你一个N*N的的矩阵，要你找到一条最大的路径，并且每次只能水平或者垂直的走不超过k步，并且下一步的值要大于上一步的值，要你输出路径的最大值。思路：这个题不太难想到dp[ i ][ j ]可以由四个方向转移过来，但是这样做不了。因为无论你怎么搞都会存在有些转移本身就不是最优解，无法转移过来...

2020-05-21

0 557