2014第五届蓝桥杯C/C++本科A组题解

猜年龄

结果：10

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int a,b;
 7     for(a=1 ; ; a++)
 8     {
 9         for(b=a+1 ; b<=a+8 ; b++)
10         {
11             if(a*b == (a+b)*6)
12             {
13                 cout<<a<<endl;
14             //    cout<<b<<endl;
15                 return 0;
16             } 
17         }
18     }
19 }

View Code

切面条

结果：1025

推导，f[n+1] = f[n]*2 - 1

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int ans = 2;
 7     for(int i=1 ; i<=10 ; i++)
 8     {
 9         ans = (ans<<1) - 1;
10         cout<<ans<<endl;
11     }
12     return 0;
13 }

View Code

神奇算式

结果：12

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int a[4];
 5 bool f[10];
 6 int ret;
 7 
 8 //判断乘积中的数是不是刚好是排列中四个 
 9 bool judge(int n)
10 { 
11     int c[10]={0};
12     while(n)
13     {
14         c[n%10]++;
15         n/=10;
16     }
17     for(int i=0 ; i<4 ; i++)
18     {
19         if(c[a[i]] != 1) return false;
20     }
21     return true;
22 }
23 
24 
25 void count()
26 {
27     for(int i=1 ; i<=2 ; i++)
28     {
29         if(a[0]==0 || a[i]==0) continue;
30         int x=0,y=0;
31         //把排列分成两段 
32         for(int j=0 ; j<i ; j++)
33         {
34             x = x*10 + a[j];
35         }
36         for(int j=i ; j<4 ; j++)
37         {
38             y = y*10 + a[j];
39         } 
40         if(x < y && judge(x*y))//保证x比y小可以去重复 
41         {
42             cout<<x<<" * "<<y<<" = "<<x*y<<endl;
43             ret++;
44         }
45     }
46 }
47 
48 //dfs 从0-9中选4个数的全排列 
49 void dfs(int k)
50 {
51     if(k == 4)
52     {
53         count();
54         return ;
55     }
56     for(int i=0 ; i<10 ; i++)
57     {
58         if(!f[i])
59         {
60             f[i] = true;
61             a[k] = i;
62             dfs(k+1);
63             f[i] =false;
64         }
65     }
66 }
67 
68 
69 int main()
70 {
71     dfs(0);
72     cout<<"total number : "<<ret<<endl;
73     return 0;
74 }

View Code

史丰收速算

答案：if(r > 0) return i

锦标赛

答案：a[b[k1]]>a[b[k2]]

扑克序列

结果： 2342A3A4

搜索，顺便把所有种类都求出来了....。

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int a[8];//存放牌序列 
 5 int f[6] = {0,0,2,2,2,2};//牌的剩余数量，f[5]代表'A' 
 6 int pre[6];//存每种牌第一次放的位置，pre[5]代表'A' 
 7 int dif[6] = {0,0,2,3,4,1};//每种牌两牌间差的最小值，dif[5]代表'A' 
 8 int ret;
 9 
10 void Output()
11 {
12     ret++;
13     for(int i=0 ; i<8 ; i++)
14     {
15         if(a[i] == 5) cout<<'A';
16         else cout<<a[i];
17     }
18     cout<<endl;
19 }
20 
21 void dfs(int k)
22 {
23     if(k == 8)
24     {
25         Output();
26         return ;
27     }
28     for(int i=2 ; i<6 ; i++)
29     {
30         if(f[i] == 1)
31         {
32             if(k - pre[i] > dif[i])
33             {
34                 a[k] = i;
35                 f[i]--;
36                 dfs(k+1);
37                 f[i]++;
38             }
39         }
40         if(f[i] == 2)
41         {
42             pre[i] = k;
43             a[k] = i;
44             f[i]--;
45             dfs(k+1);
46             f[i]++;
47         }
48     }
49 }
50 
51 int main()
52 {
53     dfs(0);
54     cout<<"total number : "<<ret<<endl;
55     return 0;
56 }

View Code

程序把所有可能按照字典序从小到大输出....。

蚂蚁感冒

想一想两球相撞无消耗反弹就好了

只要记下感冒蚂蚁前方相反方向的蚂蚁数量和后方相同方向的数量就好了

 1 #include<iostream>
 2 #include<cmath>
 3 using namespace std;
 4 int n,a[100],preR,sufL,ans;//pre:左方;suf:右方;L:向左;R:向右 
 5 
 6 int main()
 7 {
 8     cin>>n;
 9     cin>>a[0];
10     for(int i=1 ; i<n ; i++)
11     {
12         cin>>a[i];
13         if(abs(a[i]) > abs(a[0]))
14         {
15             if(a[i]<0) sufL++;
16         }
17         else
18         {
19             if(a[i]>0) preR++;
20         }
21     }
22     if((a[0]>0 && sufL>0) || (a[0]<0 && preR>0))
23     {
24         ans = sufL + preR;
25     }
26     cout<<ans + 1<<endl;
27     return 0;
28 }

View Code

地宫取宝

四维DP

先对所有宝物价值排序去重

然后维护第i大宝物在(x,y)位置是第j次取的宝物的方法数就好了

转移方程为

dp[x][y][i][j]=dp[x-1][y][i][j]+dp[x][y-1][i][j]+dp[x-1][y][h][j-1]+dp[x][y-1][h][j-1] ; (0<=h<i)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 #define MAXN 55
 8 #define MAXM 55
 9 #define MAXK 15
10 #define Mod 1000000007
11 
12 int n,m,k,v[MAXN][MAXM];
13 int dp[MAXN][MAXM][255][MAXK];
14 int a[255],ak=1;
15 int d=1;
16 
17 //递推动归
18 void work_dp(int x,int y)
19 {
20     int cv = v[x][y],id;
21     for(id=1 ; id<d ; id++)
22     {
23         if(cv == a[id]) break;
24     }
25 
26     for(int i=0 ; i<d ; i++)
27     {
28         for(int j=0 ; j<=k ; j++)
29         {
30             dp[x][y][i][j] = (dp[x-1][y][i][j] + dp[x][y-1][i][j]) % Mod;
31         }
32     }
33 
34     for(int i=0 ; i<id ; i++)
35     {
36         for(int j=1 ; j<=k ; j++)
37         {
38             dp[x][y][id][j] += dp[x-1][y][i][j-1];
39             dp[x][y][id][j] %= Mod;
40             dp[x][y][id][j] += dp[x][y-1][i][j-1];
41             dp[x][y][id][j] %= Mod;
42         }
43     }
44 }
45 
46 
47 void work()
48 {
49     sort(a,a+ak);//排序
50     for(int i=1 ; i<ak ; i++)
51     {
52         if(a[i] != a[i-1])//去重
53         {
54             a[d++] = a[i];
55         }
56     }
57 
58     dp[1][0][0][0] = 1;//初始化...
59 
60     for(int i=1 ; i<=n ; i++)
61     {
62         for(int j=1 ; j<=m ; j++)
63         {
64             work_dp(i,j);
65         }
66     }
67 
68     int ans = 0;
69     for(int i=k ; i<d ; i++)
70     {
71         ans = (ans + dp[n][m][i][k]) % Mod;
72     }
73     printf("%d
",ans);
74 }
75 
76 
77 void init()
78 {
79     scanf("%d%d%d",&n,&m,&k);
80     a[0] = -1;
81     for(int i=1 ; i<=n ; i++)
82     {
83         for(int j=1 ; j<=m ; j++)
84         {
85             scanf("%d",&v[i][j]);
86             a[ak++] = v[i][j];
87         }
88     }
89 }
90 
91 
92 int main()
93 {
94     init();
95     work();
96 //    system("pause");
97     return 0;
98 }

View Code

斐波那契

找到完美解答

http://blog.csdn.net/acdreamers/article/details/21822165