- 博客(16)
- 资源 (5)
- 收藏
- 关注
RSS订阅原创 分组背包[魔板]
每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；每组物品有若干个，同一组内的物品最多只能选一个。有 N 组物品和一个容量是 V 的背包。...
2022-08-26 17:10:42
175
原创 Post Office--邮局问题（动态规划）
Post OfficeDescriptionThere is a straight highway with villages alongside the highway. The highway is represented as an integer axis, and the position of each village is identified with a single integer coordinate. There are no two villages in the same
2022-02-15 23:04:55
1096
3
原创 划分大理石（多重背包+二进制优化）
划分大理石（多重背包+二进制优化）Description有价值分别为1…6的大理石各a[1…6]块，现要将它们分成两部分，使得两部分价值之和相等，问是否可以实现。其中大理石的总数不超过20000。Input有多组数据！所以可能有多行如果有0 0 0 0 0 0表示输入文件结束其余的行为6个整数Output有多少行可行数据就有几行输出如果划分成功，输出Can，否则Can’tSamplesInput 复制4 7 4 5 9 19 8 1 7 2 46 6 8 5 9
2022-02-14 22:22:18
486
1
原创 排列计数(数论）
排列计数Description求有多少种长度为n的序列A，满足以下条件：1 n这n个数在序列中各出现了一次若第i个数A[i]的值为i，则称i是稳定的。序列恰好有m个数是稳定的满足条件的序列可能很多，序列数对109+7取模。Input第一行一个数 T，表示有 T 组数据。接下来 T 行，每行两个整数 n,m。T=500000，n≤1000000，m≤1000000output输出T行，每行一个数，表示求出的序列数SamplesInput 复制51 01 15 2
2022-02-08 23:14:56
699
原创 反素数讲解
反素数Description对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i) 0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。现在给定一个数N，你能求出不超过N的最大的反质数么？Input一个数N（1≤N≤2,000,000,000）。Output不超过N的最大的反素数。SamplesInput1000Output840本题就是反素数经常考的一种类型–给定n，求n以内因
2022-01-21 23:54:26
824
原创 Gopher II
Gopher II(二分图匹配-匈牙利算法）DescriptionThe gopher family, having averted the canine threat, must face a new predator.The are n gophers and m gopher holes, each at distinct (x,y) coordinates. A hawk arrives and if a gopher does not reach a hole in s seconds i
2022-01-19 23:27:27
378
原创 最短路径(shopth)
最短路径(shopth)（floyd）Description给出一个有向图G=(V,E)，和一个源点v0∈V，请写一个程序输出v0和图G中其它顶点的 最短路径。只要所有的有向环权值和都是正的，我们就允许图的边有负值。顶点的标号从 1 到n（n为图G的顶点数）Input第 1 行：一个正数 n（2≤n≤80)表示图 G 的顶点总shu第 2 行：一个整数，表示源点v0（v0∈V，v0可以是图G中任意一个顶点）。第 3 至第 n+2 行，用一个邻接矩阵 W 给出了这个图。Output共包含 n−
2021-11-04 20:59:48
565
原创 最优乘车（最短路）
最优乘车(dijkstra)DescriptionH城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。一名旅客最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士, 这样换乘几次后到达S公园。现在用整数1,2,…,N 给H城的所有的巴士站编号
2021-11-04 20:11:51
267
原创 D2. Half of Same（CF）
Exampleinput4648 13 22 -15 16 358-1 0 1 -1 0 1 -1 04100 -1000 -1000 -100041 1 1 1output132-1-1题意：给n个数，可以每个数进行a[i]-k的操作。在操作后，使至少一半的数相同，求k最大是多少思路：和d1的k一样，都是所有差值的最大公约数，所以k有可能是任何差值的因子，我们把所有的因子存贮遍历，求最大//学长yydsint a[maxn];int main(){..
2021-10-14 20:23:55
410
原创 Blockdoku
BlockdokuDescriptionBlockdoku is a game that is similar to Sudoku and Tetris. It is played on a 9×9 grid that is empty initially. To start the game, the player is offered 3 random tetrominoes, which can be used in any order. The player may place them an
2021-10-06 11:11:21
227
原创 Card Hands（字典树）
**Card HandsDescriptionJim is writing a program for statistically analyzing card games. He needs to store many different card hands in memory efficiently. Each card has one of four suits and one of thirteen values. In his implementation, each hand is s
2021-10-04 20:14:30
181
原创 Sorting Device
Sorting Device题目After being stuck at home for months because of covid, you decided to explore the contents of your parent’s basement. Among numerous useless items, you found one peculiar object - a sorting device from the sixties that was used to teach s
2021-09-08 23:53:24
202
原创 2021-07-23
Ordering Tasks题意：一共n个人物，m组关系，i，j必须保证i任务在j之前完成，让你找到一个满足这个要求的序列样例Sample Input5 41 22 31 31 50 0Sample Output1 4 2 5 3解题思路把关系看成箭头，i,j就可以看成i->j,这样就变成了一个有向图（在这里建议先去学学拓扑排序，这个题是个标准的拓扑排序）代码int n,m,book[1010][1010];struct w{ int x,y;}s[1010.
2021-07-23 11:40:31
119
原创 2021-03-18
D. Word AmalgamationDescriptionIn millions of newspapers across the United States there is a word game called Jumble. The object of this game is to solve a riddle, but in order to find the letters that appear in the answer it is necessary to unscramble f
2021-03-18 21:33:09
156
1
原创 2021-01-28
区间DP题目描述开始你有一个空白字符串，每次可以选择一段区间[l,r]进行涂色，问最少涂色几次会形成字符串s。注意：涂色会覆盖。样例输入：AABCBA样例输出3这是区间dp比较经典的一个写法。memset(dp,inf,sizeof(dp))//初始dp数组for(int len=2;len<=n;len++){//枚举区间长度 for(int i=1;i<n;++i){//枚举区间的起点 int j=i+len-1;//根据起点和长度得出终点
2021-01-28 00:22:20
128
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人