备战蓝桥杯决赛----坚持第五天！！！

        坚持第五天，感觉马上快坚持不住了呀--从我接触算法开始，就是这个样子，对于算法来说，我都是阶段性的学习，因为当我一整天没有什么太大成果的时候，我就感觉没有什么太多意义（也许这就是初级程序猿的感觉）甚至觉得还不如看一天的美剧（真切的感受~~）。或者做点其他事情，比如做些开发，运用我那世界上最好的语言---PHP。

      先不说这么多了，自己走的路，只能自己体会到那感觉，如果你感同身受，希望你能积极地度过每一天。

蓝桥杯题目：剪格子

问题描述

如下图所示，3 x 3 的格子中填写了一些整数。

+--*--+--+
|10* 1|52|
+--****--+
|20|30* 1|
*******--+
| 1| 2| 3|
+--+--+--+

我们沿着图中的星号线剪开，得到两个部分，每个部分的数字和都是60。

本题的要求就是请你编程判定：对给定的m x n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。

如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。

如果无法分割，则输出 0。

输入格式

程序先读入两个整数 m n 用空格分割 (m,n<10)。

表示表格的宽度和高度。

接下来是n行，每行m个正整数，用空格分开。每个整数不大于10000。

输出格式

输出一个整数，表示在所有解中，包含左上角的分割区可能包含的最小的格子数目。

样例输入1

3 3
10 1 52
20 30 1
1 2 3

样例输出1

3

样例输入2

4 3
1 1 1 1
1 30 80 2
1 1 1 100

样例输出2

10

代码：

#include <iostream>  
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX=10;  
int m,n,min_len,sum;
int temp[MAX][MAX];
int vis[MAX][MAX];
int dict[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; //再一次用到关于移动方向的问题，可以看我昨天的博客
void dfs(int x,int y,int l,int p)
{  
       if(x<0||x>=n||y<0||y>=m||vis[x][y]){
       	return;
	   }	   
	   if(sum/2==l&&vis[0][0]){//满足的条件：当l为总和的一半，且遍历了0,0点 
	   	min_len=min(min_len,p);//寻找最短步数 
	   	return;
	   }
	   for(int i=0;i<4;i++){
	   	 int j=x+dict[i][0];
	   	 int k=y+dict[i][1];
	   	 vis[x][y]=1;
	   	 dfs(j,k,l+temp[j][k],p+1);
	   	 vis[x][y]=0;//这一步比较关键，当我们深搜递归不满足条件时，向上返回一层，将访问点再次置为未访问 
	   }
}  
int main()  
{  
    cin>>m>>n;
    sum=0;
	for(int i =0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>temp[i][j];
			sum+=temp[i][j];
		}
	}
	memset(vis,0,sizeof(vis));
	min_len=200;
	if(sum%2==0){
			for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
           	dfs(i,j,temp[i][j],1);			
		}
	}
		if(min_len==200){
		cout<<0;
	}else{
		cout<<min_len;
	}	
	}else{
		cout<<0;
	}

 
    return 0;  
}   

这也是一道dfs的应用题，至少可以总结出一点，就是对于这样

蓝桥杯题目：带分数

问题描述

100 可以表示为带分数的形式：100 = 3 + 69258 / 714。

还可以表示为：100 = 82 + 3546 / 197。

注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。

类似这样的带分数，100 有 11 种表示法。

输入格式

从标准输入读入一个正整数N (N<1000*1000)

输出格式

程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。

注意：不要求输出每个表示，只统计有多少表示法！

样例输入1

100

样例输出1

11

样例输入2

105

样例输出2

6

代码：

#include<stdio.h>  
#define limit 9  
int N;  
int mark[10];  
int num[10];  
int count;  
int addend, dividened, divider;  
  
void round_number(int i, int j){  
    int k;  
  
    for(k = 1; k <= 9 ; k++){  

        if(k <= i)  //不管是if还是else if只要是满足一个，就再进行下一次循环 
            addend = addend * 10 + num[k];  //加号之前的整数 
        else if(k <= j)  
            dividened = dividened * 10 + num[k];  //分子 
        else  
            divider = divider * 10 + num[k];      //分母 
    }  
}  
  
void full_array(int level)  
{  
    int i, j;  
    if(level == limit + 1)  {   
        for(i = 1; i <=  limit - 2; i++)//表示’+‘在第几个数之后  
            for(j = i + 1; j <= limit - 1; j++)  {//表示’/ ‘在第几个数之后  
  
                round_number(i, j);  
                if(divider != 0){  
                    if(dividened % divider == 0)  
                        if(addend + dividened / divider == N)  
                            count++;  
                }  
                addend = 0;  
                dividened = 0;  
                divider = 0;   
            }  
    }  
    else{  
        for(i = 1; i <= limit; i++){  
  
            if( mark[i] == 0){  
  
                mark[i] = 1;  
                num[level]= i;  
                full_array(level + 1);  
                mark[i] = 0;      
                }  
        }  
    }  
}  
  
int main()  
{  
  
    scanf("%d", &N);  
    full_array(1);  
    printf("%d\n", count);  
    return 0;  
}