前言
每天打代码，快乐每一天！！！
一、啤酒和饮料
题目描述：
啤酒每罐2.3元，饮料每罐1.9元。小明买了若干啤酒和饮料，一共花了82.3元。我们还知道他买的啤酒比饮料的数量少，请你计算他买了几罐啤酒。
分析分析：
对于这种题目，我最喜欢的就是暴力了，直接模拟运算
题目代码：
#include <stdio.h> #include <math.h> int main() { for(int i=1;i<82.3/2.3;i++) { for(int j=i+1;j<82.3/1.9;j++) { if(fabs(i*2.3+j*1.9-82.3)<1e-6) { printf("%d %d",i,j); } } } }
运行结果：
11
二、切面条
题目描述：
一根高筋拉面，中间切一刀，可以得到2根面条。
如果先对折1次，中间切一刀，可以得到3根面条。
如果连续对折2次，中间切一刀，可以得到5根面条。
那么，连续对折10次，中间切一刀，会得到多少面条呢？
分析分析：
这个其实就是我们找规律的题目，小唐是用递归写的喔，但是后来想一想，其实就是我们
2的多少次方+1
大意了
题目代码：
#include <stdio.h> int fact(int n) { if(n==0) return 2; else return 2*fact(n-1)-1; } int main() { int n; scanf("%d",&n); printf("%d",fact(n)); return 0; }
运行结果：
1025
三、李白打酒
题目描述：
话说大诗人李白，一生好饮。幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：
无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。
这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。
请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。
分析分析：
老递归人了，我们把酒，店，花看作我们的递归体，他们的初始值是2，5，10
店=0 退出
花=1 退出
酒=1 退出
（满足最后一次遇到的是花，他正好把酒喝光了）
题目代码：
#include <stdio.h> int count=0; void fact(int jiu,int dian,int hua) { if(dian>0) { fact(jiu*2,dian-1,hua); } if(hua>0) { fact(jiu-1,dian,hua-1); } if(hua==1&&dian==0&&jiu==1) { count++; } } int main() { int a=2; fact(2,5,10); printf("%d",count); }
运行结果：
14
四、史丰收速算
题目描述：
史丰收速算法的革命性贡献是：从高位算起，预测进位。不需要九九表，彻底颠覆了传统手算!
速算的核心基础是：1位数乘以多位数的乘法。
其中，乘以7是最复杂的，就以它为例。
因为，1/7 是个循环小数：0.142857…，如果多位数超过 142857…，就要进1
同理，2/7, 3/7, … 6/7 也都是类似的循环小数，多位数超过 n/7，就要进n
下面的程序模拟了史丰收速算法中乘以7的运算过程。
乘以 7 的个位规律是：偶数乘以2，奇数乘以2再加5，都只取个位。
乘以 7 的进位规律是：
满 142857… 进1,
满 285714… 进2,
满 428571… 进3,
满 571428… 进4,
满 714285… 进5,
满 857142… 进6
请分析程序流程，填写划线部分缺少的代码。
//计算个位 int ge_wei(int a) { if(a % 2 == 0) return (a * 2) % 10; else return (a * 2 + 5) % 10; } //计算进位 int jin_wei(char* p) { char* level[] = { "142857", "285714", "428571", "571428", "714285", "857142" }; char buf[7]; buf[6] = '\0'; strncpy(buf,p,6); int i; for(i=5; i>=0; i--){ int r = strcmp(level[i], buf); if(r<0) return i+1; while(r==0){ p += 6; strncpy(buf,p,6); r = strcmp(level[i], buf); if(r<0) return i+1; ______________________________; //填空 } } return 0; } //多位数乘以7 void f(char* s) { int head = jin_wei(s); if(head > 0) printf("%d", head); char* p = s; while(*p){ int a = (*p-'0'); int x = (ge_wei(a) + jin_wei(p+1)) % 10; printf("%d",x); p++; } printf("\n"); } int main() { f("428571428571"); f("34553834937543"); return 0; }
分析分析：
其实这个题目他说的就是，看我们这一个数超过了多少，对于超过的数进行一个模拟运算
题目中的f（）就是我们的一个汇总过程 个位+进位然后遍历一个个输出
而我们要写的代码在进位那里，我们就是依次去比较我们的那些值
如果后面的数字比这个六位数大，就说明多位数大于这个循环数，需要进1；如果后面的数字比这个数字小呢，就说明还没达到这个进位要求，进0即可。
最后一个的while是为了防止相同，如果相同，我们就往后面挪6位再次去比较，直到不相同
题目中的上一句也给了提示，既然有进位，那么也肯定有不进位的情况。
题目代码：
if(r>0) return i;
五、打印图形
题目描述：
小明在X星球的城堡中发现了如下图形和文字：
#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（，，，，）
来吧，确定的是
f(a，rank-1，，）剩下的就是我们去试
题目代码：
f(a, rank-1, row, col+w/2);
六、奇怪的分式
题目描述：
上小学的时候，小明经常自己发明新算法。一次，老师出的题目是：1/4 乘以 8/5 小明居然把分子拼接在一起，分母拼接在一起，答案是：18/45 （参见图1.png）老师刚想批评他，转念一想，这个答案凑巧也对啊，真是见鬼！ 对于分子、分母都是 1~9 中的一位数的情况，还有哪些算式可以这样计算呢？ 请写出所有不同算式的个数（包括题中举例的）。显然，交换分子分母后，例如：4/1 乘以 5/8 是满足要求的，这算做不同的算式。但对于分子分母相同的情况，2/2 乘以 3/3 这样的类型太多了，不在计数之列!
注意：答案是个整数（考虑对称性，肯定是偶数）。请通过浏览器提交。不要书写多余的内容。
分析分析：
暴力，暴力，四个小小的for循环
题目代码：
#include <algorithm> #include <iostream> #include <cmath> using namespace std; int main() { int count=0; for(int a=1;a<10;a++) { for(int b=1;b<10;b++) { if(a!=b) for(int c=1;c<10;c++) { for(int d=1;d<10;d++) { if(c!=d) { if(fabs((a*c*1.0)/(b*d)-((a*10.0+c)/(b*10.0+d)))<1e-5) count++; } } } } } cout<<count; }
运行结果：
14
七、六角填数
题目描述：
如图【1.png】所示六角形中，填入1~12的数字。
使得每条直线上的数字之和都相同。
图中，已经替你填好了3个数字，请你计算星号位置所代表的数字是多少？
分析分析：
嘿嘿，我们的全排列来了
不过在全排列之前，我们可以知道每一条他们相加的和是26喔！
因为我们一共只有6条线，我们所有的和是78（1到12）
但是注意我们每一个和都算了两遍，78*2/6=26
题目代码：
#include <iostream> #include <algorithm> using namespace std; int a[9]={2,4,5,6,7,9,10,11,12}; int main() { while(next_permutation(a,a+9)) { if((8+a[0]+a[1]+a[2])==26) if((1+a[0]+a[3]+a[5])==26) if((1+a[1]+a[4]+a[8])==26) if((8+a[3]+a[6]+3)==26) if((3+a[2]+a[4]+a[7])==26) if((a[5]+a[6]+a[7]+a[8])==26) for(int i=0;i<9;i++) { cout<<" "<<a[i]; } } }
运行结果：
10
八、蚂蚁感冒
题目描述：
长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左，有的朝右。 每只蚂蚁都只能沿着杆子向前爬，速度是1厘米/秒。当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。这些蚂蚁中，有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。
【数据格式】
第一行输入一个整数n (1 < n < 50), 表示蚂蚁的总数。
接着的一行是n个用空格分开的整数 Xi (-100 < Xi < 100), Xi的绝对值，表示蚂蚁离开杆子左边端点的距离。正值表示头朝右，负值表示头朝左，数据中不会出现0值，也不会出现两只蚂蚁占用同一位置。其中，第一个数据代表的蚂蚁感冒了。
要求输出1个整数，表示最后感冒蚂蚁的数目。
分析分析：
这个话，我们主要就是去模拟
简单的来说，我们就是先按照绝对值来进行排列
看看，三只蚂蚁的情况
前面两个碰头
后面两个碰头
这个时候我们发现什么，最要我们的第一只蚂蚁在左边，那么只要是往右边走的蚂蚁都会被感染
蚂蚁B就相当于蚂蚁A的代言人，替他走在右边的路程。
题目代码：
#include<iostream> #include <cmath> using namespace std; int a[55]; int main() { int n,i; scanf("%d",&n); for(i=0; i<n; i++) { scanf("%d",&a[i]); } //判断是否同一方向 for(i=0; i<n-1; i++) { if(a[i] * a[i+1] < 0) break; } if(i == n-1)//如果最后的时候大家方向相同，就只有第一只蚂蚁感冒 { printf("1\n"); } int sum = 1; for(i=1; i<n; i++) { if(abs(a[i]) < abs(a[0]) && a[i] > 0)//第一个坐标左侧，并且方向是右边的会感染 { sum++; } if(abs(a[i]) > abs(a[0]) && a[i] < 0)//第一个坐标右侧，并且方向是左边的会感染 { sum++; } } printf("%d\n",sum); return 0; }
运行结果：
【输入样式】 3 5 -2 8 【输出样式】 1 【输入样式】 5 -10 8 -20 12 25 【输出样式】 3
九、地宫取宝
题目描述：
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 取模的结果。
分析分析：
害，老递归了，本人太水了，这个参考了别人的代码，大家来看看他的吧
题目代码：
#include <stdio.h> #include <string.h> #define N 1000000007 int n,m,k; int map[50][50]; int vis[50][50][15][15];//vis数组中记录的是状态：xy代表坐标 拥有宝物数量 拥有宝物的最大值(这4个可以详尽唯一的描述没一种可能) // 如 vis[3][4][5][6]=7 即当在map[3][4]且身上有5件宝物 宝物的最大值是6 到达终点有7种路径 int dfs(int x,int y,int num,int max)//当前位置 拥有宝物的数量 拥有的宝物的最大值 { if (vis[x][y][num][max+1]!=-1)//因为宝物的价值有可能为0，所以定义max时用最小值-1 。但这就导致无法作为下标使用，所以我们用max+1代表下标。实际上如果测试数据中宝物价值不可能为0，这时将所有的max+1中的1去掉也是可以的。 { return vis[x][y][num][max+1]; }//记忆化的记忆就指的是上面 if(x==n&&y==m) { if(num==k)return vis[x][y][num][max+1]=1;//满足条件 当前点到目标有1种方案 else if(num==k-1&&max<map[x][y])return vis[x][y][num][max+1]=1;//同样满足条件 当前点到目标有1种方案 else return vis[x][y][num][max+1]=0;//不满足条件 当前点到目标有0种方案 } long long s=0; if(x+1<=n)//可以向下走 { if (max<map[x][y]) //可以去走当前宝物 { s+=dfs(x+1,y,num+1,map[x][y]); s%=N; //每次都取余，这样可以避免是s值过大越界 } s+=dfs(x+1,y,num,max);//未取走当前宝物 s%=N; } if(y+1<=m)//可以向右走 { if (max<map[x][y]) { s+=dfs(x,y+1,num+1,map[x][y]); s%=N; } s+=dfs(x,y+1,num,max); s%=N; } return vis[x][y][num][max+1]=s%N;; } int main(int argc, char const *argv[]) { scanf("%d%d%d",&n,&m,&k); for (int i = 1; i<=n; i++) { for (int j = 1; j <=m; j++) { scanf("%d",&map[i][j]); } }//初始地宫 memset(vis,-1,sizeof(vis)); dfs(1,1,0,-1); printf("%d",vis[1][1][0][0]); return 0; }
运行结果：
【输入样式】 2 2 2 1 2 2 1 【输出样式】 2 【输入样式】 2 3 2 1 2 3 2 1 5 【输出样式】 14
十、小朋友排队
题目描述：
n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加k。请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。
分析分析：
嘿嘿，这个题目的话用的是树状数组，不好意思，我感觉我是一个fw呜呜呜呜呜，还有好多不会的地方
题目代码：
#include<stdio.h> #include<string.h> #define MAX 1000010 #define N 100010 int C1[MAX],C2[MAX],b[MAX]; int num[N]; long long total[N],ans; int lowbit(int x) { return x&(-x); } void add(int pos,int num,int *C) { while(pos<=MAX) { C[pos]+=num; pos+=lowbit(pos); } } int Sum(int pos,int *C) { int sum=0; while(pos>0) { sum+=C[pos]; pos-=lowbit(pos); } return sum; } void init() { total[0]=0; for(int i=1;i<=N;i++) { total[i]=total[i-1]+i; } } int main() { int i; init(); memset(C1,0,sizeof(C1)); memset(C2,0,sizeof(C2)); int n; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&num[i]); add(num[i]+1,1,C1); b[i]=i-Sum(num[i],C1); b[i]=b[i]-(Sum(num[i]+1,C1)-Sum(num[i],C1)-1); } for(i=n-1;i>=0;i--) { add(num[i]+1,1,C2); b[i]=b[i]+Sum(num[i],C2); } ans=0; for(i=0;i<n;i++) { ans+=total[b[i]]; } printf("%lld\n",ans); return 0; }
运行结果：
【输入样式】 3 3 2 1 【输出样式】 9
