蓝桥杯算法入门

• 2014
• • 武功秘籍 （小学题...）
  • 猜字母 （约瑟夫环）
  • 大衍数列 （小学题...）
  • 打印图形 （代码填空题）
  • 神奇算式 (模拟 - 字符串转换 - 分解)
  • 绳圈 (难 - dp) 但可以猜
  • 分糖果 （模拟）
  • 地宫寻宝 (dfs)
  • 小朋友排身高 （树状数组 - 区间和数组 - 模板）
• 2014年总结

2000多页的武功秘籍 （注意有1000页 ， 常识！！！：然后1001-1002页与1 - 2 是连在一起的）
书的10与11在同一张纸张上，第11和12页不在同一张纸张上
要想取走书的81到92页的武功，至少要撕下多少张纸带走
答案为7
*/
/*等额本金 （小学题…）
贷款3万块 ，约定24个月，以等额本金方式还款
每个月除了1/24的本金之外，还要还固定的利息
利息公式： 剩余还款本金 * 0.005
问小明在第十五个月需要还款多少（本金和利息的总和）：
答案为浮点数（保留两位小数 如32.5要写成32.50）
1312.50

#include 
using namespace std;
#include
int test_01() {
	int n = 30000;
	float ans = 0.00;
	for(int i = 1; i <= 15; i++) {
		ans = 1250+n*0.005;
		printf("%.2f\n",ans);
		n -= 1250;
	}

	return 0;
}

把abcd…s共19个字母组成的序列重复拼接106次，得到长度为2014的字符串
接下来删除第1个字母（即a），以及第3个字母，第5个字母等所有奇数位置的字母
得到的新串再进行删除奇数位置字母的动作，最后只剩下一个字母，请写出该字母
for()pop if(i%2)continue,else{q.push()}
“abcdefghijklmnopqrs” 赋值： for arr[i] = ‘a’ + i;
可以先用19个试验算法正确性

#include
int test_02() {

	char arr[2014];
	for(int j = 0; j < 106; j++) {
		for(int i = 0; i < 19; i++) { //赋值
			arr[i+j*19] = 'a' + i;
		}
	}
	int len = 2014;
	while(len!= 1) {
		int k = 0;
		for(int i = 1; i < len; i += 2) { //思路覆盖，同时k记录剩余元素个数
			arr[k++] = arr[i];
		}
		len = k;//等于删除后的剩余长度 即k（k记录元素个数） ，每轮循环后k刷新， k = 0
		arr[len] = ';'//变成字符串 截断//结束标志'//cout << arr << endl;  测试'  ! !   如char arr[10] = {a,b},其余自动补'}'表示结束 <<
		[
	0
	cout ] arr<<;return 0 endl;
	} #include
int

前几项 0 2 4 8 12 18 24 32 40 50
其规律是：对偶数项，是序列平方再除2，奇数项 ，是序号平方减1再除2
填空代码：

test_03(
) int;for {
	( i=
	1;i < 100; i ++ )if i(% {
		2==i 0 ) printf ("%d " {
			,*/2i)i;}elseprintf
		( "%d " {
			,(*-1i)i/2);} }printf
		(

	"\n"
	);return0;
	} #define
N

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


rank=5
               *
              * *
             *   *
            * * * *
           *       *
          * *     * *
         *   *   *   *
        * * * * * * * *
       *               *
      * *             * *
     *   *           *   *
    * * * *         * * * *
   *       *       *       *
  * *     * *     * *     * *
 *   *   *   *   *   *   *   *
* * * * * * * * * * * * * * * *


ran=6
                               *
                              * *
                             *   *
                            * * * *
                           *       *
                          * *     * *
                         *   *   *   *
                        * * * * * * * *
                       *               *
                      * *             * *
                     *   *           *   *
                    * * * *         * * * *
                   *       *       *       *
                  * *     * *     * *     * *
                 *   *   *   *   *   *   *   *
                * * * * * * * * * * * * * * * *
               *                               *
              * *                             * *
             *   *                           *   *
            * * * *                         * * * *
           *       *                       *       *
          * *     * *                     * *     * *
         *   *   *   *                   *   *   *   *
        * * * * * * * *                 * * * * * * * *
       *               *               *               *
      * *             * *             * *             * *
     *   *           *   *           *   *           *   *
    * * * *         * * * *         * * * *         * * * *
   *       *       *       *       *       *       *       *
  * *     * *     * *     * *     * *     * *     * *     * *
 *   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

小明开动脑筋，编写了如下的程序，实现该图形的打印。


*/

70void f (


char [][ a],intN,int , rankint ) rowif ( col==
{
1)rank[][{
a]row='*'col; return ;}
int=
1

; w int ;for
( i=
0;i<-1 i;rank++)*= i2; w ; f(

____________________________________________,
-1a, rank+/2 row,w);f col(,
-1a, rank+/2 row,w+); col}wintmain
(


) char[]
{
[ a]N;intN,;
for i(j=
0;i<;++i)Nfori(=
0;j<;++j)N[j][ a]i=' 'j; f (,

6,a0,0);for(=

0;i<;++ i)Nfor i(={
0;j<;++ j)Nprintf j("%c" ,[][a]i);jprintf("\n"
);}return0
;

} int=
0

/*
    请仔细分析程序逻辑，填写缺失代码部分。



答案：
*/

由4个不同数字组成一个乘法算式，它们的乘积仍然由这4个数字组成
如：
210 * 6 = 1260
8 * 473 = 3784
27 * 81 = 2187
如果满足乘法交换律算作同一种情况，那么包含共有多少种 （坑点）
填写该数字

; ans # include
#include#
includebool
check(
int ,int) src//bug == 18  ，答案 12种//先转字符串 排序 比较 r, { ;
	;
	string src_str << r_str;
	stringstream ss//整型
	ss ; src//转字符串 ;
	ss >> src_str<< ;
	stringstream ss1// 注意先 << 整型  !!
	ss1 ; rsort  (
	ss1 >> r_str.  // 再 >> 字符串  !!
	begin(r_str),.end(r_str));sort(.
	begin(src_str),.end(src_str));if(==
	)returnr_str true src_str;{
		} returnfalse
	;
	} inttest_04
(
) //一个小技巧  j = 2，k = 3 先打断点 j = 2时取消断点，再断k处for( { int
	=1; i < 10; i ++ )//第一位不能为0！！！ ifor( { int
		=0; j < 10; j ++ )if j(!= {
			)fori ( jint {
				=0; k < 10; k ++ )if k(!= {
					&&!=k ) i for k ( jint {
						=0; l < 10; l ++ )if l(!= {
							&&!=l && k != l ) i // *可以插入在三个位置 l int j= { *
								1000 src + i*100 + j10* + ; //验证 右式 k if l(
								!=
								0)j //注意拆数字，乘法除法运算，每个数字最高位不能为0 ！！！ int= { *
									( r1  * i 100 +j *10 + k ) ; if l(check
									(,))src++r1;} {
										ans}if
									(
								!=
								0)k int =( {
									* r2 10 +i)*(j* 10 +k ) ; if l((
									*10+i)<(j* 10 +k ) && check l( ,))src++r2;} {
										ans}//之前肯定已经出现过了 1位 * 3位 == 3位 * 1位
									if
								(
								!=
								0)l int =( {
									* r3 100 +i * 10 + j ) * ; kif ( lcheck
									(,))src++r3;} {
										ans}//这段可略
									}
								}
								}
							}
						}
					}
				}
			<<
		<<
	;
	cout return ans 0 endl;
	} /*bug
int a_05[100];
int n_05;
bool check() {
	int t = a_05[0];
	for(int i = 1; i < n_05; i++) {
		if(a_05[i] != t ) {
			return false;
		}
	}
	return true;
}

int test_05() {
	scanf("%d",&n_05);
	for(int i = 0; i < n_05; i++) {
		scanf("%d",&a_05[i]);
	}
	int ans = 0;
	while(1) {  //多轮
		//一轮
		int t = a_05[0];
		for(int i = 1; i <= n_05 - 2; i++) {
			a_05[i] -= a_05[i]/2; //分自己一半给左边的小朋友
			a_05[i] += a_05[i+1]/2;  //加右边的一个小朋友给的
			if(a_05[i] % 2) {   //或用 (a_05[i] & 1 ) == 1
				ans++;
				a_05[i]++;
			}
		}
		a_05[n_05 - 1] -= a_05[n_05 - 1] / 2; //单独处理最后一个
		a_05[n_05 - 1] += t / 2;//得到a_05[0]的一半
		if(a_05[n_05 - 1] % 2) {   //或用( a_05[n_05 - 1] & 1 ) == 1
			ans++;//老师补一个
			a_05[n_05 - 1]++;
		}
		if(check()) { //检查所有元素是否相同
			printf("%d",ans);
			return 0;
		}
		//--------------------------------------------------
	}
	return 0;
}
*/// ~引用
#




/*思路二：
可以使用枚举的方法进行三位数以内的相乘，将符合条件的两个数字单独拎出来，通过整型转换字符串的方式进行对比，最终得到想要的结果。



#include
using namespace std;
char a[10],b[10],c[10];
int l,sum,ans;
int main(){
	for(int i=1;i<=999;i++){
		for(int j=1;j<=999;j++){
			sum=i*j;
			if(sum>1000&&sum<9999&&i

include

int
main(
) int[101
{
    ] a,,,=n0i,count=0;flagscanf("%d"//定义数组，用来储存小朋友的糖数，count定义为老师需要补发的糖数，初始为0，flag为判断是否所有小朋友糖数都相等的标志。


    ,&);[n0]//输入N，小朋友的个数。


    a=0;for(=//把a[0]定义为一个类似于缓冲区的东西，用于暂时的存放数据。


    1;i<=;++i)nscanfi("%d"
    ,&[])a;iwhile(!//为方便起见，把a[i]直接就看成第i个小朋友 。


    )[0flag]//flag初始为0，即现在每人糖数不相等，需要进行以下操作进行重新分配。

（即使现在糖数相同时 以下的操作也不影响目前的每个人的糖数，因为在每人都相等的情况下，无论进行多少次分配都不会改变数据。

）
    {
        a=[1]a/2;//缓冲区存放第一个小朋友的for(=
        1;i<;++i)n[i]=
        a[i]/a2i+[+1a]i/2;//用循环语句，依次将前n-1个小朋友的糖果传一半给前一个人[]=
        a[n]/a2n+[0]a;//由于大家坐成一个圈，所以第n个小朋友把自己的一半去掉之后同时又得到第一个小朋友糖数的一半（即缓冲区的数目）for(=
        1;i<=;++i)nifi([
        {
            ]%a2i!=0)[]={a[i]+a1i;++;}count}for
            (
        =                   //用一个循环一次检查是否是奇数，并同时统计老师补发糖的数量。


        1;i<=;++i)nifi([
        {
            ]==a[i1]a)=1;
            flagelse=0
            ;{flagbreak;}}}
            printf
        (                   //判断是否每个人糖数是否相等，如果糖数都相等，flag=1，此时while(!flag）跳出循环，游戏结束。

如果糖数不相等，继续游戏。


    "%d"
    ,);returncount0;
    } //****************递归一定要想清楚上一步 到当前的所有情况//此题还要改进 时间复杂度 -- 四维数组
int

/* my~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
int d[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}
int map[55][55];
int n,m,k;
int ans = 0;
int mod = 1000000007;
int value[55 * 55];   // ---------优化，每次记录最大的值就好了，与最大的比较就好了，不需要数组
bool check(int v){ //当前宝物值
	for(int i = 0;i < k;i++){
		if(value[i] < v){
			return false;
		}
	}
	return true;
}
void dfs(int x,int y){
	if(x >= 0 && x < n &&y >=0 && y < m){
		if(check(map[x][y])){ //选或者不选 ...

		}
		else{ //不能拿
			for(int i = 0;i < 4;i++){
			dfs(x + d[i][0],y + d[i][1]);
			}
		}
	}
}

int test_06(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++){
			scanf("%d",&map[i][j]);
		}
	}
	value[0] = map[0][0];
	dfs(0,0);

	return 0;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*/

[
55
] data[55];int,,
; n_06constm_06intk_06=
1000000007 ; mod_06 long long;
//题目已经提示数值很大 void ans_06dfs_06  (
int ,int, xint, yint) max//max记录当前最大值，  cnt统计当前拿了多少件int cnt= {  [
	] cur [ data]x;//cur取值比较yif(==
	||==x || n_06 ) y //越界  + 看看哪些变量可以剪枝   ，x，y，cnt可以剪枝 m_06 return cnt > k_06; { }
		if (
	==
	-1x && n_06 == - 1 y ) m_06 //出口 if( { ==
		||(cnt ( k_06 ==-1cnt ) k_06 && )) // 上一个格子已经k_06件 或者 加上这个格子k_06件     ！！！！ cur > max++  ; {  if
			ans_06()
			%=;ans_06 > mod_06} {
				ans_06 } mod_06}
			if
		(

	)
	//可以取这个物品  ,更新max = curdfs_06cur > max( { ,
		+1x , y , + 1 cur ) cnt ; //只能往右走或往下走 dfs_06(+
		1,x , , + y 1 cur ) cnt ; } //对于价值小的，或者价值大但不取dfs_06
	(
	,
	+1x , y , ) ; max dfs_06 cnt (+
	1,x , , ) y ; max } cnt inttest_06
(
) scanf("%d%d%d" {
	,&,&,n_06&)m_06;fork_06(int
	=0; i < ;++ i ) n_06for i(int {
		=0; j < ;++ j ) m_06scanf j("%d" {
			,&[][data]i);j}}dfs_06
		(
	0
	,0,-1,0);//第一个点的价值可能是0 ， 用-1保证可以选择拿<<<<  ;
	cout return ans_06 0 endl;
	} n3
//树状数组模板

int
lowbit(
int )//（记代码）return n- { (
	& n ( -n1)n);//n&(n-1)消去了最后的1的整数  ，再用n - n&(n-1)就得到最后一位1代表的整数值  }//原始数组的i位置增加v后,更新c数组    （记代码）  void
updata
(
int ,int, nint, iint[ v]) c//c的下标代表第几个元素 ，1开始for( { int

	=; <= k ; i+= k lowbit n( k ) )[k]+= {
		c;k} } vint
	getSum
(
int [], cint)int= i0 {
	; sum for (int
	=;1 k ; i-= k >= lowbit( k ) )+=k[] {
		sum ; c}kreturn;
	}
	int sumtest_07
(

) int[] {
	= arr1, 2 {,3,4,5,6,7,8,9};int[9
	] c;memset(,
	0,csizeof());cfor(int
	=0; i < 8; i ++ )updata i(9 {
		,+1,i[],arr)i;}c<<getSum
	(
	cout , 5)c<<;<< getSum endl(
	cout , 6)c<<;<< getSum endl(
	cout , 7)c-getSum( , 4)c<<;// Sum[4,7] 第4个元素到第7个元素 return endl0  ;
	} //有规律的数列求和 -- 数学公式！！！ 等差  & 等比//只能相邻位， -- 暴力会超时  -- 树状数组的思维转换 （此处代码略）
//每一个数要交换的次数 == 这个数前面比它大的数+后面比它小的数，即逆序对数  ！！

//合并为一步
//解题 ： 不高兴次数 =  1 + 2 + ... + i = i(1+i)/2  (交换次数i)   -->转换为记录所有的交换次数，再累加求和
[
]

/*
int test_08() { // ............logic bug ·················
	int n;
	long long ans = 0;
	scanf("%d",&n);
	int h[n];
	int cnt[n];//记录每个孩子交换的次数
	memset(cnt,0,sizeof(cnt));
	int maxH = -1;
	for(int i = 0; i < n; i++) {
		scanf("%d",&h[i]);
		if(h[i] > maxH)maxH = h[i];
	}
	int c[maxH+1];
	
	for(int i = 0; i < n; i++) {
		updata(maxH+1,h[i] + 1,1,c);  //真正的身高对应成下标  ，在相应位置计数变为1，其实就是用树状数组维护数据出现的个数
		//
		int sum = getSum(c,h[i] + 1); //小于等于 h[i]+1的数据的个数  h[i]只代表下标，而树状数组中不允许出现0
		cnt[i] += (i + 1) - sum; //得到的就是当前数据左侧比数据大的数的个数
	}
	memset(c,0,sizeof(c));
	for(int i = n-1; i >= 0; i--) {
		updata(maxH+1,h[i]+1,1,c); //在响应位置的计数变为1，其实就是用树状数组维护数据出现的个数
		/*
		int sum = getSum(c,h[i]+1); //小于等于 h[i]+1的数据的个数
		int self = getSum(c,h[i]+1) - getSum(c,h[i]);
		cnt[i] += sum ; //上一步求出的等于h的个数，扣掉自己的个数，得到的就是当前数据右侧比数据小的个数
		*/ +=
		cntgetSumi( , []c)h;i//求出小于h[i]+1的数据的个数}for (
	int
	=0; i < ;++ i ) n+= i[] {
		ans * cnt(i([]-cnt1i)/2) ; //先除2减小数值}printf  (
	"%lli\n"
	,);returnans0;
	} intmain
(

) test_08() {

	;return0;

	}