九宫重排

发表于 搜索 分类,标签:
 问题描述  如下面第一个图的九宫格中,放着1~8的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面。  我们把第一个图的局面记为:12345678.  把第二个图的局面记为:123.46758  显然是按从上到下,从左到右的顺序记录数字,空格记为句点。  本题目的任务是已知九宫的初态和终态,求最少经过多少步的移动可以到达。如果无论多少步都无法到达,则输出-1。输入格式  输入第一行包含九宫的初态,第二行包含九宫的终态。输出格式  输出最少的步数,如果不存在方案,则输出-1。样例输入12345678.123.46758样例输出3样例输入13524678.46758123.样例输出22思路:这是一个八数码问题,用bfs+状态压缩水过了。代码:#include<bits/stdc++.h>usi...

51nod-1133 不重叠的线段

发表于 动态规划 分类,标签:
 X轴上有N条线段,每条线段有1个起点S和终点E。最多能够选出多少条互不重叠的线段。(注:起点或终点重叠,不算重叠)。例如:[15][23][36],可以选[23][36],这2条线段互不重叠。Input第1行:1个数N,线段的数量(2 <= N <= 10000)第2 - N + 1行:每行2个数,线段的起点和终点(-10^9 <= S,E <= 10^9)Output输出最多可以选择的线段数量。Input示例31 52 33 6Output示例2思路:按线段结束点从小到大排序,然后贪心。。代码:#include<bits/stdc++.h>using ...

51nod-1091 线段的重叠

发表于 动态规划 分类,标签:
 X轴上有N条线段,每条线段包括1个起点和终点。线段的重叠是这样来算的,[1020]和[1225]的重叠部分为[1220]。给出N条线段的起点和终点,从中选出2条线段,这两条线段的重叠部分是最长的。输出这个最长的距离。如果没有重叠,输出0。Input第1行:线段的数量N(2 <= N <= 50000)。第2 - N + 1行:每行2个数,线段的起点和终点。(0 <= s , e <= 10^9)Output输出最长重复区间的长度。Input示例51 52 42 83 77 9Output示例4思路:按线段起点从小到大排序,然后贪心。代码:...

字符混编

发表于 DP 分类,标签:
 A、B和C。如果C包含且仅包含来自A和B的所有字符,而且在C中属于A的字符之间保持原来在A中的顺序,属于B的字符之间保持原来在B中的顺序,那么称C是A和B的混编。实现一个函数,判断C是否是A和B的混编。给定三个字符串A,B和C,及他们的长度。请返回一个bool值,代表C是否是A和B的混编。保证三个串的长度均小于等于100。测试样例:"ABC",3,"12C",3,"A12BCC",6返回:true代码:class Mixture {public:    bool chkMixture(string A, int n, string B, int m, string...

51nod-1279 扔盘子

发表于 动态规划 分类,标签:
 有一口井,井的高度为N,每隔1个单位它的宽度有变化。现在从井口往下面扔圆盘,如果圆盘的宽度大于井在某个高度的宽度,则圆盘被卡住(恰好等于的话会下去)。盘子有几种命运:1、掉到井底。2、被卡住。3、落到别的盘子上方。盘子的高度也是单位高度。给定井的宽度和每个盘子的宽度,求最终落到井内的盘子数量。如图井和盘子信息如下:井:5643623盘子:23524最终有4个盘子落在井内。本题由 @javaman 翻译。Input第1行:2个数N, M中间用空格分隔,N为井的深度,M为盘子的数量(1 <= N, M <= 50000)。第2 - N + 1行,每行1个数,对应井的宽度Wi(1 <= Wi &...

51nod-1315 合法整数集

发表于 数论 分类,标签:
 一个整数集合S是合法的,指S的任意子集subS有Fun(SubS)!=X,其中X是一个固定整数,Fun(A)的定义如下:A为一个整数集合,设A中有n个元素,分别为a0,a1,a2,...,an-1,那么定义:Fun(A)=a0ora1or...oran-1;Fun({})=0,即空集的函数值为0.其中,or为或操作。现在给你一个集合Y与整数X的值,问在集合Y至少删除多少个元素能使集合Y合法?例如:Y={1,2,4},X=7;显然现在的Y不合法,因为1or2or4=7,但是删除掉任何一个元素后Y将合法。所以,答案是1.Input第一行两个整数N,X,其中N为Y集合元素个数,X如题所述,且1<=N<=50,1<=X<=1,000,000,000.之后N行,每行一个整数yi,即集合Y中的第i个元素,且1<=yi<...

51nod-1417 天堂里的游戏

发表于 数论 分类,标签:
 多年后,每当Noder看到吉普赛人,就会想起那个遥远的下午。Noder躺在草地上漫无目的的张望,二楼的咖啡馆在日光下闪着亮,像是要进化成一颗巨大的咖啡豆。天气稍有些冷,但草还算暖和。不远的地方坐着一个吉普赛姑娘,手里拿着塔罗牌,带着耳机,边上是她的狗。狗看起来有点凶,姑娘却漂亮。Noder开始计算各种搭讪方式的成功概率,然而狗的存在......。奇怪的事情发生了,姑娘自己走了过来,把耳机戴在Noder的耳朵上,里面播放着:“......Knock-knock-knockin'onheaven'sdoor......”。姑娘冲他诡异的一笑,Noder只觉得自己眼前一阵眩晕,然后就站在了天堂的门口。正当Noder惊魂未定的时候,走来一个美女,要求和他一起玩个数学游戏。美女提议:“让我们各自亮出硬币的一面,或正或反。如果我们都是正面,那么我给你A元,如果我们都...

51nod-1428 活动安排问题

发表于 枚举 分类,标签:
 有若干个活动,第i个开始时间和结束时间是[Si,fi),同一个教室安排的活动之间不能交叠,求要安排所有活动,最少需要几个教室? Input第一行一个正整数n (n <= 10000)代表活动的个数。第二行到第(n + 1)行包含n个开始时间和结束时间。开始时间严格小于结束时间,并且时间都是非负整数,小于1000000000Output一行包含一个整数表示最少教室的个数。Input示例31 23 42 9Output示例2思路:将所有活动按起始时间排序,然后对于每个活动的起点,找出所有将这个时间点包括在内的时间段的数量t,比较所有t,输出最大的t;代码:#include<bits/stdc++.h>//#include<stdio.h>...

51nod-1432 独木舟

发表于 动态规划 分类,标签:
 n个人,已知每个人体重。独木舟承重固定,每只独木舟最多坐两个人,可以坐一个人或者两个人。显然要求总重量不超过独木舟承重,假设每个人体重也不超过独木舟承重,问最少需要几只独木舟?Input第一行包含两个正整数n (0<n<=10000)和m (0<m<=2000000000),表示人数和独木舟的承重。接下来n行,每行一个正整数,表示每个人的体重。体重不超过1000000000,并且每个人的体重不超过m。Output一行一个整数表示最少需要的独木舟数。Input示例3 6123Output示例2思路:因为最多只能坐两个人所以只需要看最小的和最大的能否坐在一起,不能就让最大的坐,将最大的去掉后再重复上述步骤。代码:#include<bits/stdc++.h>//#include<stdio....

51nod-1413 权势二进制

发表于 动态规划 分类,标签:
 一个十进制整数被叫做权势二进制,当他的十进制表示的时候只由0或1组成。例如0,1,101,110011都是权势二进制而2,12,900不是。当给定一个n的时候,计算一下最少要多少个权势二进制相加才能得到n。Input单组测试数据。第一行给出一个整数n (1<=n<=1,000,000)Output输出答案占一行。Input示例9Output示例9思路:其实只要比较数各个位数,找出其中最大的输出就行,因为如:321=111+110+100。代码#include<bits/stdc++.h>using namespace std;#define LL long long#define INF 0x3f3f3f3f#define MAX ...