博文
深搜之简单排序(2011-03-07 17:30:00)
摘要：哈哈。一同事说面试题。让我做做。10分钟以内。结果。写完程序+调试花了20分钟。
哎。看来自己老了。其实拿到题目想都没多想就编了。只是现在编码速度太低了。
//用1、2、2、3、4、5这六个数字，打印出所有不同的排列，如：512234、412345等，
//要求："4"不能在第三位，"3"与"5"不能相连,写一个个小程序
import java.util.Map;
import javolution.util.FastMap;
public class test1 {
public static Map<String , Integer> mymap = FastMap.newInstance();
public static int count = 0;
public static void main(String[] args) {
// 用1、2、2、3、4、5这六个数字，打印出所有不同的排列，如：512234、412345等，
//要求："4"不能在第三位，"3"与"5"不能相连,写一个个小程序
int []a = {0,0,0,0,0,0,0,0};
StringBuffer b = new StringBuffer();
dfs(1, a, b);
System.out.println("OK");
......
Kill the monster HDU2616(2009-07-19 05:38:00)
摘要：昨天的比赛题目，其实就是深搜，一个一个的枚举。。。。。
最多10个，就是9！次循环。不会超时！！
#include<stdio.h>#include<limits.h>int A[11],M[11];int mark[11];int n;int cout=INT_MAX;void dfs(int ,int ,int);int main(){ int xue; int i; while(scanf("%d %d",&n,&xue)!=EOF) { cout=INT_MAX; for(i=1;i<=n;i++) { scanf("%d %d",&A[i],&M[i]); mark[i]=0; } for(i=1;i<=n;i++) { mark[i]=1; dfs(1,xue,i); mark[i]=0; } if(cout==INT_MAX) printf("-1\n"); else printf("%d\n",cout); } return 0;}void dfs(int c,int xx,int i)//数量，血，第几块{ int j; int temp=xx; if(c>cout) return ; if(xx<=M[i]) { xx=xx-2*A[i]; } else xx=xx-A[i]; if(xx<=0) cout=c; else &nb......
HDU 1130 How Many Trees?(2009-07-16 21:26:00)
摘要：其实递推式是很简单的！不过数据太大牵扯到了大整数，以前自己用c写过大整数的加减乘除。
本来想调出来用用的，不过，想想，自己还是要学着写JAVA。决定用JAVA的大整数做。
第一次试着用jAVA做，一次AC，太开心了。。。。
递推式：f[n]=f[n-1]*2+f[i]*f[n-i-1] i:1.....n-1
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String args[])
{
List list = new ArrayList(101);
BigInteger f= BigInteger.valueOf(1);
list.add(f);
f= BigInteger.valueOf(2);
list.add(f);
for(int i=2;i<100;i++)
{
f=(BigInteger)list.get(i-1);
f=f.multiply(BigInteger.valueOf(2));
for(int j=0;j<i-1;j++)
{
f=f.add(((BigInteger)list.get(j)).multiply((BigInteger)list.get(i-j-2)));
}
list.add(f);
}
Scanner ......
Rescue HDU1242 广搜(2009-07-15 11:12:00)
摘要：超级无语，这样的题居然花了我这么久时间。头脑不清醒～～～
本来一拿到题目是要用广搜的。头脑不知道一下子怎么短路了，明知道深搜会超时还是用了深搜！
后来想想还是广搜。#include<stdio.h>
#include<limits.h>
#define MAX 205
int a[MAX][MAX];//路形
int mark[MAX][MAX];//是否已搜标志
int f[1011][2];//搜索队列
int MIN[MAX][MAX];
int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//4个方向
int main()
{
char c;
int M,N,i,j;
int p,rear,dd;
int si,sj,di,dj;
while(scanf("%d%d",&M,&N)!=EOF)
{
for(i=0;i<M;i++)
{
scanf("%c",&c);
for(j=0;j<N;j++)
{
mark[i][j]=0;
&n......
Asteroids! hdu1240(2009-07-15 08:47:00)
摘要：很简单的一道广度优先搜索题
#include<stdio.h>int a[11][11][11];int mark[11][11][11];int f[1011][4];int d[6][3]={{0,0,1},{0,1,0},{1,0,0,},{0,0,-1},{0,-1,0},{-1,0,0}};//六个方向int main(){ char str[10],c; int N,i,j,k; int p,rear,flag,dd; int si,sj,sk,di,dj,dk; while(scanf("%s",str)!=EOF) { scanf("%d",&N); // scanf("%c",&c); for(i=0;i<N;i++) { // scanf("%c",&c); for(j=0;j<N;j++) { scanf("%c",&c); ......
FatMouse and Cheese hdu1078 搜索(2009-07-14 10:48:00)
摘要：FatMouse and Cheese
想不通，其实是很简单的一道搜索题，怎么说是题目分类时分到动规那一组，害得我做死的想动规怎么做
还搞得我想了两天。用搜索不到一个小时搞定：不过，在我思路比较乱的情况下做的，所以这样搜也不是最优的。不管了，先贴出来再说：
a[][]记录每格的食物数量。max[][]记录从i,j搜时能吃到最多的食物数量。mark[][]记录当前结点是否在本次搜索过。flag[][]记录的是i,j,结点是否已经进行过一次深搜！！！！
#include<stdio.h>int a[103][103];int max[103][103],k,n;int mark[103][103];int flag[103][103];int d[4][2]={{-1,0},{1,0},{0,1},{0,-1}};int DFS(int i,int j);
int main(){ int i,j; while(scanf("%d%d",&n,&k)!=EOF) { if(n==-1&&k==-1) break; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%d",&a[i][j]); ......
Fast Food HDU1227 DP(2009-07-13 22:58:00)
摘要：int a[205],cost[205][205],f[35][205];//a保存的是rest的位置。cost保存的是i个rest与j个rest之间建一个dpot的各rest到该dpot的最短距离//f保存的是i个rest之间建j个dpot的最短距离。。。
状态方程：
f[i][j]=min{f[i-1][k]+cost[k+1][j]} k=i-1.......j-1;
#include<stdio.h>#include<string.h>int a[205],cost[205][205],f[35][205];//a保存的是rest的位置。cost保存的是i个rest与j个rest之间建一个dpot的各rest到该dpot的最短距离//f保存的是i个rest之间建j个dpot的最短距离。。。int abs(int a){ if(a<0) return -a; else return a;}int main(){ int i,j,kk,n,k,mid; int N=0; while(scanf("%d %d",&n,&k)!=EOF) { if(n==0&&k==0) break; N++; for(i=1;i<=n;i++) { scanf("%d",&a[i]); } &......
Fourier's Lines HDU Dp(2009-07-13 20:27:00)
摘要：比赛时想偏了！不过我觉得我比赛时想的那种方向是没错的。不过边界值应该很难考虑！
后来讨论时发现他们那种想法很好，写写：
题目意思是给你n条线，n条线有m个交点，要你求出这样的线能将平面分成多少区域！
首先
n条线最多有 (n-1)*n/2;个点 最多能划分成(n+1)*n/2区域
分别记为maxd。maxs
观察可得出规律：每减少一个点，就减少一个区域/
所以n条线m个交点能分平面的区域数为：maxs-maxd+m+1;
问题解决。接下来就是判断存不存在这样的n条线有m个交点
这就换成了一个DP问题
f[i][j]记录的是i条线能否有j个交线，若有存1，若无存0；
则有
如果f[i][j]=1;
则f[i+k][j+ki]=1 k=1,2,3.........(就相当于在i条线上加k条平行线能得的点数)
依次填表。代码如下：
#include<stdio.h>int f[101][20000];int main(){
int N=0; int maxd,maxs,m,n,k,i,res; int max,j; f[0][0]=1; f[1][0]=1; f[2][0]=1; f[2][1]=1; for(i=3;i<101;++i) { // f[i][1]=1; //for(j=i;j) for(k=i-1;k>=0;--k) { for(m=0;m<=(k)*(k-1)/2;++m) &......
hdu1480 钥匙计数之二(2009-07-12 13:43:00)
摘要：设lock[i]表示：有 i个槽的钥匙的个数设one[i]表示：有 i个槽且左边第一个槽深度为1的钥匙的个数设two[i]表示：有 i个槽且左边第一个槽深度为2的钥匙的个数....设six[i]表示：有 i个槽且左边第一个槽深度为6的钥匙的个数则显然：lock[i]=one[i]+two[i]+ three[i]+four[i]+five[i]+six[i] 由于易知：one[i]=six[i],two[i]=three[i]=four[i]=five[i]则可以得到：lock[i]=one[i]*2+two[i]*4 其中：one[i]=one[i-1]+two[i-1]+three[i-1]+four[i-1]+five[i-1]+a[i]; =one[i-1]+two[i-1]*4 +a[i] two[i]=one[i-1]*2+two[i-1]*4 +b[i]其中，a[i] 和b[i]的含义分别是：a[i]表示“有 i个槽且左边第一个槽深度为1，同时这种钥匙在除掉第一个槽后不再是钥匙”的钥匙的个数。例如 123,124,125,134,135,145,126,136,146,156 就属于这种情况。b[i]表示“有 i个槽且左边第一个槽深度为2，同时这种钥匙在除掉第一个槽后不再是钥匙” 的钥匙的个数。 分析到这里，可以知道，关键的是求a[i]和b[i]，我们可以得到如下表达式：a[i]=(2^(i-1)-2)*6+(2^(i-2)-1)*4b[i]=(2^(i-1)-2)*9其中，a[i] 的各部分的含义如下：(2^(i-1)-2)*6：当去掉第一位，后面i-1位只有 (2,3)或者 (2,4) 或者(2,5) 或者(3,4) 或者(3,5) 或者(4,5)两种数字的时候，显然是不合法的钥匙（不满足至少有3个不同的深度），加上第一位的1则显然是一个合格的钥匙。所以后面的数字可以为一个组合中两个数字的任意一个，根据乘法原理i-1位一共有2^(i-1)种组合，当然还需要去掉两种特殊情况，就是后面i-1位完全相同的情况。满足这种条件的一共有上面六种组合，所以得到(2^(i-1)-2)*6。(2^(i-2)-1)*4：当去掉第一位，后面i-1位只有 (2,6)或者 (3,6) 或者(4,......
钥匙计数之一 hdu1438(2009-07-12 12:49:00)
摘要：递推方程式如下1：如果X是钥匙 则X1/2/3/4也是 所以a[I]=a[I-1]*42: 如果X不是，X2/3是则X由1/4组成/但要除去全1和全4 所以a[I]+=(2^(I-1)-2)*23 如果X不是 X1/4是。则X=Y（1/4） M=X1/4=Y（4/1）（1/4）前I-2位可以是1234，但要除去全为1/4的情况 还有就是X是钥匙且X是以1/4结尾的情况。我们用b[I]数组表示i位时以1/4结尾的的数量
temp=4^(i-2)-2^(i-2)-b[i-1];
则 b[i]=a[i-1]*2+temp;
代码如下：
#include<stdio.h>#include<math.h>int main(){ int i; __int64 temp,a[32],b[32];//b[i]记录以1 4结尾的数 a[2]=0; a[3]=8; b[2]=0; b[3]=4; printf("N=2: 0\nN=3: 8\n"); for(i=4;i<=31;i++) { a[i]=a[i-1]*4; a[i]+=(__int64)pow(2,i)-4;//以2 3 结尾的 temp=((__int64)pow(4,i-2)-(__int64)pow(2,i-2))*2-b[i-1]; a[i]+=temp; b[i]=a[i-1]*2+temp;&n......