算法入门"/>
蓝桥杯算法入门
文章目录
- 2014
- 武功秘籍 （小学题...）
- 猜字母 （约瑟夫环）
- 大衍数列 （小学题...）
- 打印图形 （代码填空题）
- 神奇算式 (模拟 - 字符串转换 - 分解)
- 绳圈 (难 - dp) 但可以猜
- 分糖果 （模拟）
- 地宫寻宝 (dfs)
- 小朋友排身高 （树状数组 - 区间和数组 - 模板）
- 2014年总结
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 <iostream>
using namespace std;
#include<cstdio>
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<cstring>
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 = 0arr[len] = '\0'; //变成字符串 截断//结束标志'\0' ! ! 如char arr[10] = {a,b},其余自动补'\0'表示结束//cout << arr << endl; 测试}cout << arr[0] << endl;return 0;
}
大衍数列 （小学题…）
前几项 0 2 4 8 12 18 24 32 40 50
其规律是：对偶数项，是序列平方再除2，奇数项 ，是序号平方减1再除2
填空代码：
#include<cstdio>
int test_03() {int i;for(i = 1; i < 100; i++) {if(i % 2 == 0) {printf("%d ",i*i/2);} else {printf("%d ",(i*i-1)/2 );}}printf("\n");return 0;
}
打印图形 （代码填空题）
/*小明在X星球的城堡中发现了如下图形和文字：
rank=3** ** *
* * * *rank=5** ** ** * * ** ** * * ** * * ** * * * * * * ** ** * * ** * * ** * * * * * * ** * * ** * * * * * * ** * * * * * * *
* * * * * * * * * * * * * * * *ran=6** ** ** * * ** ** * * ** * * ** * * * * * * ** ** * * ** * * ** * * * * * * ** * * ** * * * * * * ** * * * * * * ** * * * * * * * * * * * * * * ** ** * * ** * * ** * * * * * * ** * * ** * * * * * * ** * * * * * * ** * * * * * * * * * * * * * * ** * * ** * * * * * * ** * * * * * * ** * * * * * * * * * * * * * * ** * * * * * * ** * * * * * * * * * * * * * * ** * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *小明开动脑筋，编写了如下的程序，实现该图形的打印。
*/#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+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;
}/*请仔细分析程序逻辑，填写缺失代码部分。答案：
*/
神奇算式 (模拟 - 字符串转换 - 分解)
由4个不同数字组成一个乘法算式，它们的乘积仍然由这4个数字组成
如：
210 * 6 = 1260
8 * 473 = 3784
27 * 81 = 2187
如果满足乘法交换律算作同一种情况，那么包含共有多少种 （坑点）
填写该数字
int ans = 0;
#include<algorithm>
#include<string>
#include<sstream>
bool check(int src,int r) { //bug == 18 ，答案 12种//先转字符串 排序 比较string src_str , r_str;stringstream ss;ss << src; //整型ss >> src_str; //转字符串stringstream ss1;ss1 << r; // 注意先 << 整型 !!ss1 >> r_str; // 再 >> 字符串 !!sort(r_str.begin(),r_str.end());sort(src_str.begin(),src_str.end());if(r_str == src_str){return true;}return false;
}
int test_04() { //一个小技巧 j = 2，k = 3 先打断点 j = 2时取消断点，再断k处for(int i = 1; i < 10; i++) { //第一位不能为0！！！for(int j = 0; j < 10; j++) {if(i != j) {for(int k = 0; k < 10; k++) {if(k != i && k != j) {for(int l = 0; l < 10; l++) {if(l != k && l != i && l != j) { // *可以插入在三个位置int src = i*1000 + j*100 + 10 * k + l;//验证 右式if(j != 0) { //注意拆数字，乘法除法运算，每个数字最高位不能为0 ！！！int r1 = i * (j *100 + k * 10 + l);if(check(src,r1)) {ans++;}}if(k != 0) {int r2 = (i*10+j) * (k * 10 + l);if((i*10+j) < (k * 10 + l) &&check(src,r2)) {ans++;}}//之前肯定已经出现过了 1位 * 3位 == 3位 * 1位if(l != 0) {int r3 = (i * 100 + j * 10 + k) * l;if(check(src,r3)) {ans++;}}//这段可略}}}}}}}cout << ans << endl;return 0;
}/*思路二：
可以使用枚举的方法进行三位数以内的相乘，将符合条件的两个数字单独拎出来，通过整型转换字符串的方式进行对比，最终得到想要的结果。#include<bits/stdc++.h>
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<j){sprintf(a,"%d",sum);sort(a,a+4);}for(l=1;l<4;l++){if(a[l-1]==a[l])break;}if(l==4){sprintf(b,"%d",i);sprintf(c,"%d",j);strcat(b,c);//将两者字符串连接sort(b,b+4);if(strcmp(a,b)==0){ans++;cout<<i<<" "<<j<<" "<<sum<<endl;}}}}cout<<ans;
}
绳圈 (难 - dp) 但可以猜
今天有 100 根绳子 ，当然会有 200 个绳头
如果任意取绳头两两配对 ，把所有的绳头打结连接起来，最后会形成若干个绳圈
我们的问题是：请计算最后将形成多少个绳圈的概率最高
结果为一个整数：
绳 头 圈 （分析）
1 2 1
2 4 圈2 1/3 圈1 2/3
i-1 2(i -1) ci-1
p(x圈) = 形成x圈的组合方式 /所有方式
分析：概率 – >dp
答案： 3
分糖果 （模拟）
n个小朋友做成一圈，随机发糖果，然后进行下面游戏：
每个小朋友都把自己的糖果分一半给左边的孩子
一轮分糖后，拥有奇数个糖果的孩子由老师补发1个糖果，从而变成偶数
反复进行这个游戏，直到每个小朋友的糖果数都相同为止
问老师要补发多少个糖果
输入：
3
2 2 4
输出：
4
/*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 ) == 1ans++;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 ) == 1ans++;//老师补一个a_05[n_05 - 1]++;}if(check()) { //检查所有元素是否相同printf("%d",ans);return 0;}//--------------------------------------------------}return 0;
}
*/// ~引用
#include<stdio.h>
int main()
{int a[101],n,i,count=0,flag=0;//定义数组，用来储存小朋友的糖数，count定义为老师需要补发的糖数，初始为0，flag为判断是否所有小朋友糖数都相等的标志。scanf("%d",&n);//输入N，小朋友的个数。a[0]=0;//把a[0]定义为一个类似于缓冲区的东西，用于暂时的存放数据。for(i=1;i<=n;i++)scanf("%d",&a[i]);//为方便起见，把a[i]直接就看成第i个小朋友 。while(!flag)//flag初始为0，即现在每人糖数不相等，需要进行以下操作进行重新分配。（即使现在糖数相同时 以下的操作也不影响目前的每个人的糖数，因为在每人都相等的情况下，无论进行多少次分配都不会改变数据。）{a[0]=a[1]/2;//缓冲区存放第一个小朋友的for(i=1;i<n;i++)a[i]=a[i]/2+a[i+1]/2;//用循环语句，依次将前n-1个小朋友的糖果传一半给前一个人a[n]=a[n]/2+a[0];//由于大家坐成一个圈，所以第n个小朋友把自己的一半去掉之后同时又得到第一个小朋友糖数的一半（即缓冲区的数目）for(i=1;i<=n;i++){if(a[i]%2!=0){a[i]=a[i]+1;count++;}} //用一个循环一次检查是否是奇数，并同时统计老师补发糖的数量。for(i=1;i<=n;i++){if(a[i]==a[1])flag=1;else{flag=0;break;}} //判断是否每个人糖数是否相等，如果糖数都相等，flag=1，此时while(!flag）跳出循环，游戏结束。如果糖数不相等，继续游戏。}printf("%d",count);return 0;
}地宫寻宝 (dfs)
【题目描述】
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：
2 3 2
1 2 3
2 1 5
输出2：
14
/* 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;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*///****************递归一定要想清楚上一步 到当前的所有情况
//此题还要改进 时间复杂度 -- 四维数组
int data[55][55];
int n_06,m_06,k_06;
const int mod_06 = 1000000007;
long long ans_06; //题目已经提示数值很大
void dfs_06(int x,int y,int max,int cnt) { //max记录当前最大值， cnt统计当前拿了多少件int cur = data[x][y];//cur取值比较if(x == n_06 || y == m_06 || cnt > k_06) { //越界 + 看看哪些变量可以剪枝 ，x，y，cnt可以剪枝return ;}if(x == n_06 - 1 && y == m_06 - 1) { //出口if(cnt == k_06 ||((cnt == k_06 - 1) && cur > max) ) { // 上一个格子已经k_06件 或者 加上这个格子k_06件 ！！！！ans_06++;if(ans_06 > mod_06) {ans_06 %= mod_06;}}}if(cur > max) { //可以取这个物品 ,更新max = curdfs_06(x , y + 1 , cur , cnt + 1 );//只能往右走或往下走dfs_06(x + 1 , y , cur , cnt + 1 );}//对于价值小的，或者价值大但不取dfs_06(x , y + 1 , max , cnt );dfs_06(x + 1 , y , max , cnt );
}
int test_06() {scanf("%d%d%d",&n_06,&m_06,&k_06);for(int i = 0; i < n_06; i++) {for(int j = 0; j < m_06; j++) {scanf("%d",&data[i][j]);}}dfs_06(0,0,-1,0); //第一个点的价值可能是0 ， 用-1保证可以选择拿cout << ans_06 << endl;return 0;
}
小朋友排身高 （树状数组 - 区间和数组 - 模板）
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。
数据规模和约定
对于10%的数据， 1<=n<=10；
对于30%的数据， 1<=n<=1000；
对于50%的数据， 1<=n<=10000；
对于100%的数据，1<=n<=100000，0<=Hi<=1000000。
预处理 模板
①前缀和数组，存放前缀和累加
如 a[3] = a1 + a2 + a3
但是一个改了，后面的全部都要改
②树状数组
某个区间的和 [k - lowbit(k), k] //lowbit(k)是k的二进制中最后一个1代表的整数
C6 – > 110 --> lowbit(6) = 2
C6 为Sum∑[4,6]
getSum()
①2n包含前面全部项的和
②奇数项只包括自己
③其余的按照 减去二进制的最后1代表的整数的规则 代表包括项
如查前10项 == C10 [8,10] + C8 (23包含前8项)
//树状数组模板
#include<cstring>
int lowbit(int n) { //（记代码）return n - (n&(n-1)); //n&(n-1)消去了最后的1的整数 ，再用n - n&(n-1)就得到最后一位1代表的整数值
}
//原始数组的i位置增加v后,更新c数组 （记代码）
void updata(int n,int i,int v,int c[]) { //c的下标代表第几个元素 ，1开始for( int k = i; k <= n; k += lowbit(k)) {c[k] += v;}
}
int getSum(int c[],int i) {int sum = 0;for(int k = i; k >= 1; k -= lowbit(k)) {sum += c[k];}return sum;
}
int test_07() {int arr[] = {1,2,3,4,5,6,7,8,9};int c[9];memset(c,0,sizeof(c));for(int i = 0; i < 8; i++) {updata(9,i+1,arr[i],c);}cout << getSum(c,5) << endl;cout << getSum(c,6) << endl;cout << getSum(c,7) - getSum(c,4) << endl; // Sum[4,7] 第4个元素到第7个元素return 0;
}//有规律的数列求和 -- 数学公式！！！ 等差 & 等比
//解题 ： 不高兴次数 = 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]只代表下标，而树状数组中不允许出现0cnt[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的个数，扣掉自己的个数，得到的就是当前数据右侧比数据小的个数*/ //合并为一步cnt[i] += getSum(c,h[i]); //求出小于h[i]+1的数据的个数}for(int i = 0; i < n; i++) {ans += cnt[i]*((cnt[i]-1) / 2); //先除2减小数值}printf("%lli\n",ans);return 0;
}2014年总结
01 武功秘籍 不用运算 ，考验思维（小学题）
02 等额本金 （小学题）
03 猜字母 数组的操作 （挪动数列） – （约瑟夫环）
04 大衍数列 奇偶数
05 打印图形 递归 上下文推测 - 参数的含义（图形规律）
06 神奇算式 枚举 -（字符串排序 比较）
07 神圈 数学归纳 dp推导 （难***）
08 分糖果 模拟
09 地宫取宝 深搜dfs （模板**） 子问题重复求解
10 小朋友排队 （最难****） 树状数组妙用
int main() {test_08();return 0;
}
更多推荐
蓝桥杯算法入门
发布评论