2014年省赛c组

年省赛c组"/>

2014年省赛c组

A 武功秘籍

刷题链接: link.

小明到X山洞探险，捡到一本有破损的武功秘籍（2000多页！当然是伪造的）。他注意到：书的第10页和第11页在同一张纸上，但第11页和第12页不在同一张纸上。

小明只想练习该书的第81页到第92页的武功，又不想带着整本书。请问他至少要撕下多少张纸带走？

这是个整数，请通过浏览器提交该数字，不要填写任何多余的内容。

参考代码(简单题)

#include<bits/stdc++.h>
int main()
{printf("7");return 0;
}

B 等额本金

刷题链接: link.

小明从银行贷款3万元。约定分24个月，以等额本金方式还款。

这种还款方式就是把贷款额度等分到24个月。每个月除了要还固定的本金外，还要还贷款余额在一个月中产生的利息。

假设月利率是：0.005，即：千分之五。那么，

第一个月，小明要还本金 1250, 还要还利息：30000 * 0.005，总计 1400.00

第二个月，本金仍然要还 1250, 但利息为：(30000-1250) * 0.005 总计 1393.75

请问：小明在第15个月，应该还款多少（本金和利息的总和）？

请把答案金额四舍五入后，保留两位小数。注意：32.5，一定要写为：32.50

通过浏览器提交答案，这是一个含有小数点和两位小数的浮点数字。不要写多余内容（例如：多写了“元”或添加说明文字）

注意：每个月要还的利息及保留两位小数。

参考代码

#include<bits/stdc++.h>
int main()
{double sum;for(int i=1;i<=15;i++){sum=1250+(30000-1250*(i-1))*0.005;}printf("%.02f",sum);return 0;
}

C 猜字母

刷题链接: link.

把abcd…s共19个字母组成的序列重复拼接106次，得到长度为2014的串。

接下来删除第1个字母（即开头的字母a），以及第3个，第5个等所有奇数位置的字母。

得到的新串再进行删除奇数位置字母的动作。如此下去，最后只剩下一个字母，请写出该字母。

答案是一个小写字母，请通过浏览器提交答案。不要填写任何多余的内容。

注意：一定要初始化数组以及数组尽量开的大一些。

参考代码(HASH数组)

#include<bits/stdc++.h>
int main()
{int a[3000]={0}; int t,count=0;while(count!=1){int i;count=0;for(i=1;i<2015;i++){if(a[i]==0){count++;if(count%2){a[i]=1;t=i;//printf("%d\n",i);}}	}	}int x=t%19;if(x==0)x=19;printf("%c",'a'+x-1);return 0;
}

D 大衍数列

刷题链接: link.

中国古代文献中，曾记载过“大衍数列”, 主要用于解释中国传统文化中的太极衍生原理。

它的前几项是：0、2、4、8、12、18、24、32、40、50 …

其规律是：对偶数项，是序号平方再除2，奇数项，是序号平方减1再除2。

以下的代码打印出了大衍数列的前 100 项。

int main()
{int i;for(i=1; i<100; i++){if(__________________) //填空printf("%d ", i*i/2);elseprintf("%d ", (i*i-1)/2);}printf("\n");
}

请填写划线部分缺失的代码。通过浏览器提交答案。

注意：不要填写题面已有的内容，也不要填写任何说明、解释文字。

完整代码实现：

#include<bits/stdc++.h>
int main()
{int i;/*for(i=1; i<100; i++){if(i%2==0) //填空printf("%d ", i*i/2);elseprintf("%d ", (i*i-1)/2);}*///printf("\n");printf("i%2==0");
}

E 打印图形

刷题链接: link.

小明在X星球的城堡中发现了如下图形和文字：

rank=3

   * * * *   *  
* * * *

rank=5

		               *                                                      * *                                                     *   *                                                    * * * *                                                   *       *                                                  * *     * *                                                 *   *   *   *                                                * * * * * * * *                                               *               *                                              * *             * *                                             *   *           *   *                                            * * * *         * * * *                                           *       *       *       *  * *     * *     * *     * *  *  *   *   *   *   *   *    *   * * * * * * * * * * * * * * * *  

#define N 70
void f(char a[][N], int rank, int row, int col)
{if(rank==1){a[row][col] = '*';return;}int w = 1;int i;for(i=0; i<rank-1; i++) w *= 2;____________________________________________;f(a, rank-1, row+w/2, col);f(a, rank-1, row+w/2, col+w);
}int main()
{char a[N][N];int i,j;for(i=0;i<N;i++)for(j=0;j<N;j++) a[i][j] = ' ';f(a,6,0,0);for(i=0; i<N; i++){for(j=0; j<N; j++) printf("%c",a[i][j]);printf("\n");}return 0;
}

答案:f(a,rank-1,row,col+w/2);

完整代码实现:

#include <bits/stdc++.h>
#define N 70void f(char a[][N], int rank, int row, int col)
{if(rank==1){a[row][col] = '*';return;}int w = 1;int i;for(i=0; i<rank-1; i++) w *= 2;f(a, rank-1, row, col+w/2);	//填空部分f(a, rank-1, row+w/2, col);f(a, rank-1, row+w/2, col+w);
}int main()
{char a[N][N];int i,j;for(i=0;i<N;i++)for(j=0;j<N;j++) a[i][j] = ' ';f(a,6,0,0);for(i=0; i<N; i++){for(j=0; j<N; j++) printf("%c",a[i][j]);printf("\n");}return 0;
}

F 神奇算式

刷题链接: link.

由4个不同的数字，组成的一个乘法算式，它们的乘积仍然由这4个数字组成。

比如： 210 x 6 = 1260 
8 x 473 = 3784
27 x 81 = 2187 都符合要求。

如果满足乘法交换律的算式算作同一种情况，那么，包含上边已列出的3种情况，一共有多少种满足要求的算式。

请填写该数字，通过浏览器提交答案，不要填写多余内容（例如：列出所有算式）

注意：

1.该题的解题方式

2.不可用暴力枚举

3.巧用字符串函数解题

4.注意四位数互不相等的条件

5.注意满足乘法交换律的算式算作同一种情况

6.数组开大一点

参考代码（字符串函数解题）

#include<bits/stdc++.h>
using namespace std;
int main()
{int count=0;char s1[10],s2[10],s3[10];for(int a=1;a<987;a++){for(int b=1;b<987;b++){int m=a*b;if(m>=1023&&m<=9876&&b<a){sprintf(s1,"%d",m);sort(s1,s1+4);if(s1[0]!=s1[1]&&s1[1]!=s1[2]&&s1[2]!=s1[3]){sprintf(s2,"%d",a);sprintf(s3,"%d",b);strcat(s2,s3);sort(s2,s2+4);if(strcmp(s1,s2)==0){count++;//printf("%d*%d=%d\n",a,b,m);}}		}}}printf("%d",count);return 0;
}

G 绳圈（该题不会，代码转自网络）

刷题链接: link.

今有 100 根绳子，当然会有 200 个绳头。

如果任意取绳头两两配对，把所有绳头都打结连接起来。最后会形成若干个绳圈（不考虑是否套在一起）。

我们的问题是：请计算最后将形成多少个绳圈的概率最大？

注意：结果是一个整数，请通过浏览器提交该数字。不要填写多余的内容。

思路:dp

参考代码:

#include<iostream>  
#define N 100  
using namespace std;  double dp[N+1][N+1] = {0};   int main(){  dp[1][1] = 1;  for(int i=2;i<=N;i++){  dp[i][1] = dp[i-1][1] * (2*i-2)/(2*i-1);  dp[i][i] = dp[i-1][i-1] / (2*i-1);  }  for(int i=3;i<=N;i++){  for(int j=2;j<i;j++){  dp[i][j] = dp[i-1][j-1]/(2*i-1) + dp[i-1][j] * (2*i-2) / (2*i-1);  }  }  int index = 0;  double maxR = 0;  for(int i=1;i<=N;i++){  if(dp[N][i]>maxR){  index = i;  maxR = dp[N][i];  }     }  cout<<index<<endl;  return 0;  
}

思路:递推

参考代码:

#include<iostream>
using namespace std;
double f[102][102];
int main()
{int i,j;double max;f[1][1]=1;for(i=2;i<=100;i++){for(j=1;j<=i;j++)f[i][j]=1.0/(2.0*i-1)*(f[i-1][j]*(2*i-2)+f[i-1][j-1]);}max=0;for(i=1;i<=100;i++){if(max<f[100][i])max=f[100][i];}for(i=1;i<=100;i++){if(max==f[100][i])cout<<i<<endl;}return 0;
}

H 分糖果

刷题链接: link.

有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果，然后进行下面的游戏：

每个小朋友都把自己的糖果分一半给左手边的孩子。

一轮分糖后，拥有奇数颗糖的孩子由老师补给1个糖果，从而变成偶数。

反复进行这个游戏，直到所有小朋友的糖果数都相同为止。

你的任务是预测在已知的初始糖果情形下，老师一共需要补发多少个糖果。

【格式要求】

程序首先读入一个整数N(2<N<100)，表示小朋友的人数。

接着是一行用空格分开的N个偶数（每个偶数不大于1000，不小于2）

要求程序输出一个整数，表示老师需要补发的糖果数。

例如：输入
3
2 2 4
程序应该输出：
4

思路:利用数组解题。

参考代码:

#include<bits/stdc++.h>
int main()
{int a[105];int n,count=0;scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&a[i]);bool is=true;while(is){int temp=a[0];for(int i=0;i<n;i++){if(i==n-1)a[i]=a[i]/2+temp/2;elsea[i]=a[i]/2+a[i+1]/2;if(a[i]%2){count++;a[i]++;}	}int j;for(j=0;j<n-1;j++)if(a[j]!=a[j+1])break;if(j==n-1)is=false;			}printf("%d",count);return 0;
}

I 地宫取宝（该题暂时还不会）

刷题链接: link.

X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。

【数据格式】

输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12)

接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值

要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。

例如，输入：
2 2 2
1 2
2 1
程序应该输出：
2再例如，输入：
2 3 2
1 2 3
2 1 5
程序应该输出：
14

思路:用dfs求解

参考代码:

#include <bits/stdc++.h>
using namespace std;
int main()
{return 0;
}

j 小朋友排队（该题暂时还不会）

刷题链接: link.

n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。

每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。

如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加k。

请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。

如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。

【数据格式】

输入的第一行包含一个整数n，表示小朋友的个数。

第二行包含 n 个整数 H1 H2 … Hn，分别表示每个小朋友的身高。

输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。

例如，输入：
3
3 2 1
程序应该输出：
9

【样例说明】

首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和1的小朋友，每个小朋友的不高兴程度都是3，总和为9。

思路:树状数组

参考代码:

#include <bits/stdc++.h>
using namespace std;
int main()
{return 0;
}