网站：csust 夜间练习6
A 猜数字 HDU 1172 就是猜数字那个游戏╮(╯▽╰)╭，当符合的为0或者大于等于两个，都是不能确定
代码： 15ms
1 #include <stdio.h> 2 #include <iostream> 3 #include <string.h> 4 using namespace std; 5 char map[102][6]; 6 int sum,n,ans,a[102],b[102],x[6],c[6]; 7 int panduan() 8 { 9 int j,k,i,w,v; 10 for(i=1;i<=n;i++) 11 { 12 memset(c,0,sizeof(c)); 13 w=0; 14 v=0; 15 for(j=1;j<=4;j++) 16 if(map[i][j]==x[j]+48) 17 v++; //数字和位置都对了的 18 if(b[i]!=v) 19 return 0; 20 for(j=1;j<=4;j++) 21 for(k=1;k<=4;k++) 22 if(map[i][j]==x[k]+48 && c[k]==0) 23 { 24 w++; 25 c[k]=1; //标记，记过的就不用再记了 26 break; 27 } 28 if(w!=a[i]) 29 return 0; 30 } 31 return 1; 32 } 33 int main() 34 { 35 int i; 36 while(~scanf("%d",&n)&&n) 37 { 38 sum=0; 39 for(i=1;i<=n;i++) 40 { 41 scanf("%s",map[i]+1); 42 scanf("%d%d",&a[i],&b[i]); 43 } 44 for(i=1000;i<=9999;i++) //枚举 45 { 46 x[4]=i%10; 47 x[3]=i/10%10; 48 x[2]=i/100%10; 49 x[1]=i/1000; 50 if(panduan()) 51 { 52 sum++; //符合的个数 53 if(sum>=2) //符合的有多个，跳出 54 break; 55 ans=i; //记录符合的 56 } 57 } 58 if(sum==0 || sum>=2) 59 printf("Not sure\n"); 60 if(sum==1) 61 printf("%d\n",ans); 62 } 63 return 0; 64 }
B HDU Today HDU 2112 这道题以前做最短路的时候看到过，不过当时没做，因为字符串太难处理了......╮(╯▽╰)╭，现在这道题成为我刷新我Dijkstra算法的题......QAQ.....
这道题真的是高了好久.......QAQ
1 #include <stdio.h> 2 #include <iostream> 3 #include <string.h> 4 #include <string> 5 using namespace std; 6 int inf=0x3f3f3f3f; 7 char a[160][40],x[40],y[40]; 8 int map[156][156],num,s[156],d[156]; 9 int dijkstra() 10 { 11 int i,j,min,pos; 12 memset(s,0,sizeof(s)); 13 for(i=1;i<=num;i++) 14 d[i]=inf; //直接赋为无穷大 15 //s[1]=1; 以后这一步还是不要再标记了..... 16 d[1]=0; 17 for(i=1;i<=num;i++) 18 { 19 min=inf; 20 for(j=1;j<=num;j++) 21 if(!s[j]&&min>d[j]) 22 { 23 pos=j; 24 min=d[j]; 25 } 26 s[pos]=1; 27 for(j=1;j<=num;j++) 28 if(d[j]>(d[pos]+map[pos][j])) //在这一步就不同考虑有没有被标记了 29 d[j]=d[pos]+map[pos][j]; 30 } 31 return d[2]; //终点伪2 32 } 33 int main() 34 { 35 int n,t,a1,b1,i,j; 36 while(~scanf("%d",&n)&&n!=-1) 37 { 38 memset(map,inf,sizeof(map)); 39 scanf("%s %s",a[1],a[2]); //起点设为1，终点设为2 40 num=2; 41 if(n==0 && strcmp(a[1],a[2])==0) 42 map[1][2]=0; 43 else if(n==0 && strcmp(a[1],a[2])!=0) 44 { 45 printf("-1\n"); 46 continue; 47 } 48 if(strcmp(a[1],a[2])==0) 49 map[1][2]=0; 50 for(i=1;i<=n;i++) 51 { 52 a1=0;b1=0; 53 scanf("%s %s %d",x,y,&t); 54 for(j=1;j<=num;j++) 55 if(strcmp(a[j],x)==0) //在前面是否出现过 56 a1=j; 57 if(a1==0) //若没有，则num++； 58 { 59 a1=++num; 60 strcpy(a[a1],x); 61 } 62 for(j=1;j<=num;j++) 63 if(strcmp(a[j],y)==0) 64 b1=j; 65 if(b1==0) 66 { 67 b1=++num; 68 strcpy(a[b1],y); 69 } 70 if(map[a1][b1]>t) 71 { 72 map[a1][b1]=t; 73 map[b1][a1]=t; 74 } 75 } 76 t=dijkstra(); 77 if(t==inf) 78 printf("-1\n"); 79 else 80 printf("%d\n",t); 81 } 82 return 0; 83 }
C 棋盘问题 POJ 1321 这是以前新生训练的题......DFS，不过之前没有去做，方法和N皇后类似，不过在输入地图那错了好久，最后好不容易检查出来了，居然交错题了，我还纠结了一下，怎么就WA了......╮(╯▽╰)╭
代码： 16ms
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 using namespace std; 5 char map[10][10]; 6 int n,sum,x[10]; 7 void dfs(int i,int j) 8 { 9 int l; 10 if(n-i<j-1) //剩下的地方不够放了 11 return ; 12 if(!j) //k个棋子够放完了，方法数++； 13 { 14 sum++; 15 return ; 16 } 17 for(l=1;l<=n;l++) 18 if(map[i][l]=='#' && !x[l]) //可以放 && l列没有棋子 19 { 20 x[l]=1; //标记，第l列已经放了 21 dfs(i+1,j-1); 22 x[l]=0; 23 } 24 dfs(i+1,j); //跳过第i行，放i+1行 25 } 26 int main() 27 { 28 int i,j,k; 29 while(~scanf("%d%d",&n,&k)&&n!=-1) 30 { 31 memset(x,0,sizeof(x)); 32 sum=0; 33 for(i=1;i<=n;i++) 34 scanf("%s",map[i]+1); //输入地图 35 dfs(1,k); //从第一行开始，还剩k个棋子 36 printf("%d\n",sum); 37 } 38 return 0; 39 }
解释：優YoU http://user.qzone.qq.com/289065406/blog/1299341345
代码： 16ms
1 #include <stdio.h> 2 #include <iostream> 3 #include <string.h> 4 using namespace std; 5 int dp[25][15002],a[22],b[22]; 6 int main() 7 { 8 int n,g,i,j,k; 9 while(~scanf("%d %d",&n,&g)) 10 { 11 for(i=1;i<=n;i++) 12 scanf("%d",&a[i]); //挂钩的距离 13 for(i=1;i<=g;i++) 14 scanf("%d",&b[i]); //钩码的重量 15 memset(dp,0,sizeof(dp)); 16 dp[0][7500]=1; //挂0个挂钩，为0有一个 17 for(i=1;i<=g;i++) //第i个钩码 18 for(j=0;j<=15000;j++) //状态 19 if(dp[i-1][j]) 20 for(k=1;k<=n;k++) //挂在那个挂钩上 21 dp[i][j+b[i]*a[k]]+=dp[i-1][j]; 22 printf("%d\n",dp[g][7500]); 23 } 24 return 0; 25 }
E Dirichlet's Theorem on Arithmetic Progressions POJ 3006 一个首项是a，公差为d的等差数列，求第n个素数~~~枚举就是~不过没超时很神奇~~~╮(╯▽╰)╭
代码： 250ms 不过要注意，这个虽然没有写C++的头文件，但是还是用C++提交，用C提交会Compile Error
1 #include <stdio.h> 2 int prim(int x) 3 { 4 int i; 5 if(x==1) 6 return 0; 7 for(i=2;i*i<=x;i++) 8 if(x%i==0) //只要有一个因子，就不是素数，返回0 9 return 0; 10 return 1; 11 } 12 int main() 13 { 14 int a,d,n; 15 while(~scanf("%d%d%d",&a,&d,&n)&&n&&a&&d) 16 { 17 a=a-d; //先减掉 18 int i=0; 19 while(i!=n) 20 { 21 a+=d; //加上 22 if(prim(a)) 23 i++; 24 } 25 printf("%d\n",a); 26 } 27 return 0; 28 }