2014年第五届蓝桥杯省赛B组训练活动

我们还知道他买的啤酒比饮料的数量少&＃xff0c;请你计算他买了几罐啤酒。

#include
#include
#include
#include
using namespace std;
int main(){double price1&＃61;2.3,price2&＃61;1.9;for(int i&＃61;0;i<50;i&＃43;&＃43;){for(int j&＃61;i&＃43;1;j<50;j&＃43;&＃43;){if(fabs(price1*i&＃43;price2*j-82.3)<&＃61;1e-6){cout<}
//112.切面条

一根高筋拉面&＃xff0c;中间切一刀&＃xff0c;可以得到2根面条。

如果先对折1次&＃xff0c;中间切一刀&＃xff0c;可以得到3根面条。

如果连续对折2次&＃xff0c;中间切一刀&＃xff0c;可以得到5根面条。

那么&＃xff0c;连续对折10次&＃xff0c;中间切一刀&＃xff0c;会得到多少面条呢&＃xff1f;

//推一下可知
//2,3,5,9......
//即&＃xff1a;2^0&＃43;1,2^1&＃43;1,2^2&＃43;1,2^3&＃43;1......
//直接算出答案&＃xff1a;1025
3.李白打酒

话说大诗人李白&＃xff0c;一生好饮。幸好他从不开车。

一天&＃xff0c;他提着酒壶&＃xff0c;从家里出来&＃xff0c;酒壶中有酒2斗。他边走边唱&＃xff1a;

无事街上走&＃xff0c;提壶去打酒。

逢店加一倍&＃xff0c;遇花喝一斗。

这一路上&＃xff0c;他一共遇到店5次&＃xff0c;遇到花10次&＃xff0c;已知最后一次遇到的是花&＃xff0c;他正好把酒喝光了。 

请你计算李白遇到店和花的次序&＃xff0c;可以把遇店记为a&＃xff0c;遇花记为b。则&＃xff1a;babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢&＃xff1f;请你计算出所有可能方案的个数&＃xff08;包含题目给出的&＃xff09;。

#include
#include
#include
using namespace std;
int count0,cnt;
void dfs(int step,int sum,int pre){//步数 酒量 前一步状态(1:店 0:花)if(step&＃61;&＃61;16){if(count0&＃61;&＃61;10&&sum&＃61;&＃61;0&&pre&＃61;&＃61;0){cnt&＃43;&＃43;;}return;}count0&＃43;&＃43;;dfs(step&＃43;1,sum-1,0);count0--;dfs(step&＃43;1,sum*2,1);
}
int main(){dfs(1,2,0);cout<}
//144.史丰收速算

史丰收速算法的革命性贡献是&＃xff1a;从高位算起&＃xff0c;预测进位。不需要九九表&＃xff0c;彻底颠覆了传统手算!

速算的核心基础是&＃xff1a;1位数乘以多位数的乘法。

其中&＃xff0c;乘以7是最复杂的&＃xff0c;就以它为例。

因为&＃xff0c;1/7 是个循环小数&＃xff1a;0.142857...&＃xff0c;如果多位数超过 142857...&＃xff0c;就要进1

同理&＃xff0c;2/7, 3/7, ... 6/7 也都是类似的循环小数&＃xff0c;多位数超过 n/7&＃xff0c;就要进n

下面的程序模拟了史丰收速算法中乘以7的运算过程。

乘以 7 的个位规律是&＃xff1a;偶数乘以2&＃xff0c;奇数乘以2再加5&＃xff0c;都只取个位。

 乘以 7 的进位规律是&＃xff1a;

满 142857... 进1,
满 285714... 进2,
满 428571... 进3,
满 571428... 进4,
满 714285... 进5,
满 857142... 进6
请分析程序流程&＃xff0c;填写划线部分缺少的代码。
//计算个位 
int ge_wei(int a){
if(a % 2 &＃61;&＃61; 0)
return (a * 2) % 10;
else
return (a * 2 &＃43; 5) % 10;
}
//计算进位 
int jin_wei(char* p){
char* level[] &＃61; {
"142857",
"285714",
"428571",
"571428",
"714285",
"857142"
};

char buf[7];
buf[6] &＃61; &＃39;\0&＃39;;
strncpy(buf,p,6);

int i;
for(i&＃61;5; i>&＃61;0; i--){
int r &＃61; strcmp(level[i], buf);
if(r<0) return i&＃43;1;
while(r&＃61;&＃61;0){
p &＃43;&＃61; 6;
strncpy(buf,p,6);
r &＃61; strcmp(level[i], buf);
if(r<0) return i&＃43;1;
______________________________;  //填空
}
}

return 0;
}
//多位数乘以7
void f(char* s) {
int head &＃61; jin_wei(s);
if(head > 0) printf("%d", head);

char* p &＃61; s;
while(*p){
int a &＃61; (*p-&＃39;0&＃39;);
int x &＃61; (ge_wei(a) &＃43; jin_wei(p&＃43;1)) % 10;
printf("%d",x);
p&＃43;&＃43;;
}

printf("\n");
}
int main(){
f("428571428571");
f("34553834937543");
return 0;
}

答案&＃xff1a;if(r>0) return i;

注意题目中的...指的是循环小数

5.打印图形

使得每条直线上的数字之和都相同。

 图中&＃xff0c;已经替你填好了3个数字&＃xff0c;请你计算星号位置所代表的数字是多少&＃xff1f;

#include
#include
#include
using namespace std;
int main(){int count&＃61;0;int a[9]&＃61;{2,4,5,6,7,9,10,11,12};do{int sum1&＃61;8&＃43;a[0]&＃43;a[1]&＃43;a[2];int sum2&＃61;a[0]&＃43;1&＃43;a[3]&＃43;a[5];int sum3&＃61;1&＃43;a[1]&＃43;a[4]&＃43;a[8];int sum4&＃61;a[5]&＃43;a[6]&＃43;a[7]&＃43;a[8];int sum5&＃61;3&＃43;a[6]&＃43;a[3]&＃43;8;int sum6&＃61;3&＃43;a[7]&＃43;a[4]&＃43;a[2];if(sum1&＃61;&＃61;sum2&&sum2&＃61;&＃61;sum3&&sum3&＃61;&＃61;sum4&&sum4&＃61;&＃61;sum5&&sum5&＃61;&＃61;sum6){cout<}
//108.蚂蚁感冒

长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左&＃xff0c;有的朝右。 

每只蚂蚁都只能沿着杆子向前爬&＃xff0c;速度是1厘米/秒。

当两只蚂蚁碰面时&＃xff0c;它们会同时掉头往相反的方向爬行。

这些蚂蚁中&＃xff0c;有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时&＃xff0c;会把感冒传染给碰到的蚂蚁。

请你计算&＃xff0c;当所有蚂蚁都爬离杆子时&＃xff0c;有多少只蚂蚁患上了感冒。

【数据格式】
第一行输入一个整数n (1 接着的一行是n个用空格分开的整数 Xi (-100 要求输出1个整数&＃xff0c;表示最后感冒蚂蚁的数目。
例如&＃xff0c;输入&＃xff1a;
3
5 -2 8
程序应输出&＃xff1a;
1
再例如&＃xff0c;输入&＃xff1a;
5
-10 8 -20 12 25
程序应输出&＃xff1a;
3

/*
两只蚂蚁碰面后反向&＃xff0c;其实可以看做两只蚂蚁仍按照原来的方向运动感冒的蚂蚁(传染源)向右运动:
对于该蚂蚁左面的的蚂蚁&＃xff0c;向左运动的&＃xff0c;传染不了感冒&＃xff0c;向右运动的&＃xff0c;要看原蚂蚁的右面有没有向左运动的蚂蚁
对于该蚂蚁右面的蚂蚁&＃xff0c;向右运动的&＃xff0c;传染不了感冒&＃xff0c;向左运动的&＃xff0c;必定被传染感冒的蚂蚁(传染源)向左运动&＃xff1a;
对于该蚂蚁左面的的蚂蚁&＃xff0c;向左运动的&＃xff0c;传染不了感冒&＃xff0c;向右运动的&＃xff0c;必定被传染
对于该蚂蚁右面的蚂蚁&＃xff0c;向右运动的&＃xff0c;传染不了感冒&＃xff0c;向左运动的&＃xff0c;要看原蚂蚁的左面有没有向右运动的蚂蚁
*/
#include
#include
#include
using namespace std;
int main(){int flag&＃61;0,cnt&＃61;1,n,a[60];cin>>n;for(int i&＃61;0;i>a[i];}if(a[0]>0){//感冒的蚂蚁向右运动for(int i&＃61;1;ia[0]){flag&＃61;1;break;}}for(int i&＃61;1;i0){if(a[i]a[0])cnt&＃43;&＃43;;}}}else{//感冒的蚂蚁向左运动for(int i&＃61;1;i0&&a[i]<-a[0]){flag&＃61;1;break;}}for(int i&＃61;1;i0){if(a[i]<-a[0])cnt&＃43;&＃43;;}else{if(-a[i]>-a[0]&&flag)cnt&＃43;&＃43;;}}}cout<}9.地宫取宝

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

地宫的入口在左上角&＃xff0c;出口在右下角。

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

走过某个格子时&＃xff0c;如果那个格子中的宝贝价值比小明手中任意宝贝价值都大&＃xff0c;小明就可以拿起它&＃xff08;当然&＃xff0c;也可以不拿&＃xff09;。

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

请你帮小明算一算&＃xff0c;在给定的局面下&＃xff0c;他有多少种不同的行动方案能获得这k件宝贝。
【数据格式】
输入一行3个整数&＃xff0c;用空格分开&＃xff1a;n m k (1<&＃61;n,m<&＃61;50, 1<&＃61;k<&＃61;12)
接下来有 n 行数据&＃xff0c;每行有 m 个整数 Ci (0<&＃61;Ci<&＃61;12)代表这个格子上的宝物的价值
要求输出一个整数&＃xff0c;表示正好取k个宝贝的行动方案数。该数字可能很大&＃xff0c;输出它对 1000000007 取模的结果。
例如&＃xff0c;输入&＃xff1a;
2 2 2
1 2
2 1
程序应该输出&＃xff1a;
2
再例如&＃xff0c;输入&＃xff1a;
2 3 2
1 2 3
2 1 5
程序应该输出&＃xff1a;
14

有几点需要注意

1.宝贝的价值可能为零&＃xff0c;如果不处理&＃xff0c;当开始遇到的为价值为零的宝贝&＃xff0c;那么就不能取了&＃xff0c;所以读取数据时让所有宝贝的价值均加1

2.小明只能向下和向右走&＃xff0c;因此小明是无法在当前搜索路径中回到已经走过的位置的&＃xff0c;所以不用标记也可以(如法二&＃xff0c;法三)

法一&＃xff1a;普通搜索,(i.j)表示要去处理的位置

#include
#include
#include
using namespace std;
#define MOD 1000000007
int n,m,k;
long long int dp[60][60][15][15];
int map[60][60];
int Next[2][2]&＃61;{{0,1},{1,0}};
void dfs(int x,int y,int cnt,int Max){if(dp[x][y][cnt][Max]!&＃61;-1){return;}dp[x][y][cnt][Max]&＃61;0;if(x&＃61;&＃61;n&&y&＃61;&＃61;m){if(cnt&＃61;&＃61;k||(cnt&＃61;&＃61;k-1&&map[n][m]>Max)){dp[x][y][cnt][Max]&＃61;1;}}int xnext,ynext;for(int i&＃61;0;i<2;i&＃43;&＃43;){xnext&＃61;x&＃43;Next[i][0];ynext&＃61;y&＃43;Next[i][1];if(xnext>&＃61;1&&xnext<&＃61;n&&ynext>&＃61;1&&ynext<&＃61;m){if(map[x][y]>Max){dfs(xnext,ynext,cnt&＃43;1,map[x][y]);dp[x][y][cnt][Max]&＃43;&＃61;dp[xnext][ynext][cnt&＃43;1][map[x][y]];dp[x][y][cnt][Max]%&＃61;MOD;}dfs(xnext,ynext,cnt,Max);dp[x][y][cnt][Max]&＃43;&＃61;dp[xnext][ynext][cnt][Max];dp[x][y][cnt][Max]%&＃61;MOD;}}
}
int main(){cin>>n>>m>>k;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;){cin>>map[i][j];map[i][j]&＃43;&＃43;;}}memset(dp,-1,sizeof(dp));dfs(1,1,0,0);printf("%lld\n",dp[1][1][0][0]%MOD);return 0;
}法二&＃xff1a;可以想到&＃xff0c;在搜索过程中有些状态是重复的&＃xff0c;因此可采用记忆化搜索&＃xff0c;存储已经搜索过的状态

dp[i][j][w][t]:表示当前在(i,j)位置上要去处理&＃xff0c;已经取到w个宝贝&＃xff0c;取到宝贝的最大价值为t 时到达终点的最终方案数

具体搜索方式仍为法一中的&＃xff0c;(i,j)为要处理的点

#include
#include
#include
using namespace std;
#define MOD 1000000007
int n,m,k;
long long int dp[60][60][15][15];
int map[60][60];
int Next[2][2]&＃61;{{0,1},{1,0}};
void dfs(int x,int y,int cnt,int Max){if(dp[x][y][cnt][Max]!&＃61;-1){return;}dp[x][y][cnt][Max]&＃61;0;if(x&＃61;&＃61;n&&y&＃61;&＃61;m){if(cnt&＃61;&＃61;k||(cnt&＃61;&＃61;k-1&&map[n][m]>Max)){dp[x][y][cnt][Max]&＃61;1;}}int xnext,ynext;for(int i&＃61;0;i<2;i&＃43;&＃43;){xnext&＃61;x&＃43;Next[i][0];ynext&＃61;y&＃43;Next[i][1];if(xnext>&＃61;1&&xnext<&＃61;n&&ynext>&＃61;1&&ynext<&＃61;m){if(map[x][y]>Max){dfs(xnext,ynext,cnt&＃43;1,map[x][y]);dp[x][y][cnt][Max]&＃43;&＃61;dp[xnext][ynext][cnt&＃43;1][map[x][y]];dp[x][y][cnt][Max]%&＃61;MOD;}dfs(xnext,ynext,cnt,Max);dp[x][y][cnt][Max]&＃43;&＃61;dp[xnext][ynext][cnt][Max];dp[x][y][cnt][Max]%&＃61;MOD;}}
}
int main(){cin>>n>>m>>k;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;){cin>>map[i][j];map[i][j]&＃43;&＃43;;}}memset(dp,-1,sizeof(dp));dfs(1,1,0,0);printf("%lld\n",dp[1][1][0][0]%MOD);return 0;
}

法三&＃xff1a;也为记忆化搜索&＃xff0c;但具体思路有差异。法二更偏向于搜索&＃xff0c;因为考虑时更多考虑(i,j)为当前要处理的点&＃xff0c;另两个量是当前位置的附属状态。而法三更偏向于动态规划&＃xff0c;四维数组的四个分量共同组成了当前的搜索状态->在&＃xff08;i,j&＃xff09;位置上&＃xff0c;已经取到w个宝贝&＃xff0c;取到宝贝的最大价值为t &＃xff0c;不管当前搜索路径此位置处没处理过&＃xff0c;不管有没有从当前位置取过宝贝

#include
#include
#include
using namespace std;
#define MOD 1000000007
int n,m,k;
long long int dp[60][60][15][15];
int map[60][60];
int Next[2][2]&＃61;{{0,1},{1,0}};
void dfs(int x,int y,int cnt,int Max){if(dp[x][y][cnt][Max]!&＃61;-1){return;}dp[x][y][cnt][Max]&＃61;0;if(x&＃61;&＃61;n&&y&＃61;&＃61;m&&cnt&＃61;&＃61;k){dp[x][y][cnt][Max]&＃61;1;}if(map[x][y]>Max&&cnt}
int main(){cin>>n>>m>>k;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;){cin>>map[i][j];map[i][j]&＃43;&＃43;;}}memset(dp,-1,sizeof(dp));dfs(1,1,0,0);printf("%lld\n",dp[1][1][0][0]%MOD);return 0;
}10.小朋友排队

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

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

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

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

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

【数据格式】

输入的第一行包含一个整数n&＃xff0c;表示小朋友的个数。

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

输出一行&＃xff0c;包含一个整数&＃xff0c;表示小朋友的不高兴程度和的最小值。
例如&＃xff0c;输入&＃xff1a;
3
3 2 1
程序应该输出&＃xff1a;
9
【样例说明】
 首先交换身高为3和2的小朋友&＃xff0c;再交换身高为3和1的小朋友&＃xff0c;再交换身高为2和1的小朋友&＃xff0c;每个小朋友的不高兴程度都是3&＃xff0c;总和为9。
【数据规模与约定】
对于10%的数据&＃xff0c; 1<&＃61;n<&＃61;10&＃xff1b;
对于30%的数据&＃xff0c; 1<&＃61;n<&＃61;1000&＃xff1b;
对于50%的数据&＃xff0c; 1<&＃61;n<&＃61;10000&＃xff1b;

对于100%的数据&＃xff0c;1<&＃61;n<&＃61;100000&＃xff0c;0<&＃61;Hi<&＃61;1000000。

//考察树状数组的一个应用&＃xff1a;求逆序数  有一个结论&＃xff1a;对于一个序列&＃xff0c;想得到按大小排好的序列&＃xff0c;每个位置的数交换的次数等于该数产生的逆序数

//每个小盆友交换的次数&＃xff0c;就是每个数左边更大右边更小的数的个数
//因为小朋友身高可出现重复&＃xff0c;而且而且用到的是左边更大右边更小&＃xff0c;所以树状数组表示 管辖范围内 早出现的小于当前数的数 的数量
//注意小朋友身高可为负
#include
#include
#include
using namespace std;
int a[1000010],b[1000010],re[100010],num[100010];
long long unhappy[1000010];
int lowBit(int x){return x&(-x);
}
int get(int a[],int p){int re&＃61;0;for(;p>&＃61;1;p-&＃61;lowBit(p)){re&＃43;&＃61;a[p];}return re;
}
void update(int a[],int p){for(;p<1000010;p&＃43;&＃61;lowBit(p)){a[p]&＃43;&＃43;;}
}
int main(){int n;long long ans&＃61;0;for(int i&＃61;1;i<1000010;i&＃43;&＃43;){unhappy[i]&＃61;unhappy[i-1]&＃43;i;}scanf("%d",&n);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){scanf("%d",&num[i]);//从比当前数大的第一个数开始更新update(a,num[i]&＃43;1);if(i!&＃61;1){//第一个位置不用记录左边的数比该位置的数小的数量re[i]&＃61;i-get(a,num[i]&＃43;1);//此处用num[i]&＃43;1是因为 想要得到左边比自己大的&＃xff0c;所以要去掉左边小于等于当前位置数的数(包括自己)}}for(int i&＃61;n;i>&＃61;1;i--){update(b,num[i]&＃43;1);ans&＃43;&＃61;unhappy[re[i]&＃43;get(b,num[i])];}printf("%lld\n",ans);return 0;
}