蓝桥杯练习题库 4算法提高 VIP题DOC.docx
《蓝桥杯练习题库 4算法提高 VIP题DOC.docx》由会员分享，可在线阅读，更多相关《蓝桥杯练习题库 4算法提高 VIP题DOC.docx（229页珍藏版）》请在冰点文库上搜索。
蓝桥杯练习题库4算法提高VIP题DOC
1、算法提高日期计算
问题描述
已知2011年11月11日是星期五，问YYYY年MM月DD日是星期几？
注意考虑闰年的情况。
尤其是逢百年不闰，逢400年闰的情况。
输入格式
输入只有一行
YYYYMMDD
输出格式
输出只有一行
W
数据规模和约定
1599<=YYYY<=2999
1<=MM<=12
1<=DD<=31，且确保测试样例中YYYY年MM月DD日是一个合理日期
1<=W<=7，分别代表周一到周日
样例输入
20111111
样例输出
5
#include
intmonth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
intmain（void）{
inty,m,d,i,temp=0,sum=0,j,u;
scanf（"%d%d%d",&y,&m,&d）;
for（i=0;i<2011;i++）{
if（（i%4==0）&&（i%100!
=0）||（i%400==0））
{
sum++;
}
sum+=365;
}sum=sum+365-50;
for（i=0;iif（（i%4==0）&&（i%100!
=0）||（i%400==0））
{
temp++;
}
temp+=365;
}
for（j=1;jtemp+=month[j];
if（（（y%4==0）&&（y%100!
=0）||（y%400==0））&&（j==2））temp++;
}temp+=d;
if（temp>=sum）{
if（（temp-sum+5）%7==0）
printf（"%d",7）;
else
printf（"%d",（temp-sum+5）%7）;
}else{
u=sum-temp;
if（u<=5）{
printf（"%d",!
（5-u）%7?
7:
（5-u）%7）;
}else{
printf（"%d",7-（u-5）%7?
7-（u-5）%7:
7）;
}
}
return0;
}
2、 算法提高概率计算
问题描述
生成n个∈[a,b]的随机整数，输出它们的和为x的概率。
输入格式
一行输入四个整数依次为n，a，b，x，用空格分隔。
输出格式
输出一行包含一个小数位和为x的概率，小数点后保留四位小数
样例输入
2134
样例输出
0.3333
数据规模和约定
对于50%的数据，n≤5.
对于100%的数据，n≤100,b≤100.
#include
#include
doubled[101][10001];
intn,a,b,x;
intmain（）
{inti,j,k;
scanf（"%d%d%d%d",&n,&a,&b,&x）;
for（i=a;i<=b;i++）
d[1][i]=1.0/（b-a+1）;
for（i=2;i<=n;i++）
for（j=i*a;j<=i*b;j++）
for（k=a;k<=b;k++）
d[i][j]+=d[1][k]*d[i-1][j-k];
printf（"%.4f",d[n][x]）;
return0;
}
3、算法提高6-17复数四则运算
设计复数库，实现基本的复数加减乘除运算。
输入时只需分别键入实部和虚部，以空格分割，两个复数之间用运算符分隔；输出时按a+bi的格式在屏幕上打印结果。
参加样例输入和样例输出。
注意考虑特殊情况，无法计算时输出字符串"error"。
样例输入
24*-32
样例输出
-14-8i
样例输入
3-2+-13
样例输出
2+1i
#include
intmain（）
{
doublea,b,c,d;
doublebb=0.0;
charop;
scanf（"%lf%lf%c%lf%lf",&a,&b,&op,&c,&d）;
bb=c*c+d*d;
switch（op）
{
case43:
printf（"%.0lf%+.0lfi\n",a+c,b+d）;break;
case45:
printf（"%.0lf%+.0lfi\n",a-c,b-d）;break;
case42:
printf（"%.0lf%+.0lfi\n",a*c-b*d,a*d+b*c）;break;
case47:
{
if（bb!
=0.0）
if（（a*c+b*d）/bb<0&&（a*c+b*d）/bb>-1）
printf（"%.1lf%+.1lfi\n",（a*c+b*d）/bb,（b*c-a*d）/bb）;
elseprintf（"%.0lf%+.0lfi\n",（a*c+b*d）/bb,（b*c-a*d）/bb）;
elseprintf（"error"）;
}
break;
}
return0;
}
4、算法提高c++_ch02_01
编写一个程序，利用强制类型转换打印元音字母大小写10种形式的ASCII码。
输出的顺序为：
大写的字母A，E，I，O，U的ASCII码，小写的字母a，e，i，o，u的ASCII码。
所有的ASCII码都用十进制表示.输出10行,每行一个ASCII码，最后输出一个空行。
//河职院Stanley
#include
intmain（）
{
chara,e,i,o,u;
a='a';
e='e';
i='i';
o='o';
u='u';
printf（"%d\n",a-32）;
printf（"%d\n",e-32）;
printf（"%d\n",i-32）;
printf（"%d\n",o-32）;
printf（"%d\n",u-32）;
printf（"%d\n",a）;
printf（"%d\n",e）;
printf（"%d\n",i）;
printf（"%d\n",o）;
printf（"%d\n",u）;
return0;
}
5、算法提高逆序排列
问题描述
编写一个程序，读入一组整数（不超过20个），并把它们保存在一个整型数组中。
当用户输入0时，表示输入结束。
然后程序将把这个数组中的值按逆序重新存放，并打印出来。
例如：
假设用户输入了一组数据：
719-5620，那么程序将会把前五个有效数据保存在一个数组中，即719-562，然后把这个数组中的值按逆序重新存放，即变成了26-5197，然后把它们打印出来。
输入格式：
输入只有一行，由若干个整数组成，中间用空格隔开，最末尾的整数为0。
输出格式：
输出也只有一行，即逆序排列后的整数，中间用空格隔开，末尾没有空格。
输入输出样例
样例输入
719-5620
样例输出
26-5197
#include
#include
intmain（）
{
inta[20],i,j,t;
for（i=0;i<20;i++）
{scanf（"%d",&a[i]）;
if（a[i]==0）
{
break;
}
}
for（j=0;j
{
t=a[i-j-1];
a[i-j-1]=a[j];
a[j]=t;
}
for（j=0;j{printf（"%d",a[j]）;
if（j==i-1）
printf（"\b"）;
}
printf（"\n"）;
return0;
}
6、 算法提高第二大整数
问题描述
编写一个程序，读入一组整数（不超过20个），当用户输入0时，表示输入结束。
然后程序将从这组整数中，把第二大的那个整数找出来，并把它打印出来。
说明：
（1）0表示输入结束，它本身并不计入这组整数中。
（2）在这组整数中，既有正数，也可能有负数。
（3）这组整数的个数不少于2个。
输入格式：
输入只有一行，包括若干个整数，中间用空格隔开，最后一个整数为0。
输出格式：
输出第二大的那个整数。
输入输出样例
样例输入
58-1270
样例输出
7
#include
intmain（）
{
intt,mone,mtwo;
scanf（"%d",&t）;
mone=mtwo=-10000000;
while（t!
=0）
{
if（t>mone）
{mtwo=mone,mone=t;}
elseif（t>mtwo）mtwo=t;
scanf（"%d",&t）;
}
printf（"%d",mtwo）;
return0;
}
7、算法提高约数个数
输入一个正整数N（1
样例输入
12
样例输出
6
样例说明
12的约数包括：
1,2,3,4,6,12。
共6个
#include
intmain（）
{
intn,i,num=0;
scanf（"%d",&n）;
for（i=1;i<=n;i++）
if（n%i==0）num++;
printf（"%d",num）;
return0;
}
8、算法提高十进制数转八进制数
编写函数，其功能为把一个十进制数转换为其对应的八进制数。
程序读入一个十进制数，调用该函数实现数制转换后，输出对应的八进制数。
样例输入
9274
样例输出
22072
样例输入
18
样例输出
22
#include
intmain（）
{
intn;
scanf（"%d",&n）;
printf（"%o",n）;
return0;
}
9、 算法提高复数归一化
编写函数Normalize，将复数归一化，即若复数为a+bi，归一化结果为a/sqrt（a*a+b*b）+i*b/sqrt（a*a+b*b）。
使用结构体指针类型作为函数参数可能是必要的。
其中实部和虚部由键盘输入，输出为归一化结果，如果归一化结果的实部或虚部为小数的要求保留一位小数。
样例输入:
（格式说明：
34分别为以空格隔开的实数的实部和虚部）
34
样例输出
0.6+0.8i
样例输入
25
样例输出
0.4+0.9i
#include
#include
//a/sqrt（a*a+b*b）+i*b/sqrt（a*a+b*b）
intmain（）
{
inta,b;
scanf（"%d%d",&a,&b）;
printf（"%.1f+%.1fi",a/sqrt（a*a+b*b）,b/sqrt（a*a+b*b））;
return0;
}
10、 算法提高最大乘积
问题描述
对于n个数，从中取出m个数，如何取使得这m个数的乘积最大呢？
输入格式
第一行一个数表示数据组数
每组输入数据共2行：
第1行给出总共的数字的个数n和要取的数的个数m，1<=n<=m<=15，
第2行依次给出这n个数，其中每个数字的范围满足:
a[i]的绝对值小于等于4。
输出格式
每组数据输出1行，为最大的乘积。
样例输入
1
55
12342
样例输出
48
#include
#include
#include
intmax;
voidfun（int*val,intindex,intsize,intm,intcnt,intres）;
intmain（）
{
intn,m,x,i;
intval[15];
scanf（"%d",&x）;
while（x--）
{
scanf（"%d%d",&n,&m）;
for（i=0;i{
scanf（"%d",&val[i]）;
}
max=-10000000;
fun（val,0,n,m,0,1）;
printf（"%d\n",max）;
}
return0;
}
voidfun（int*val,intindex,intsize,intm,intcnt,intres）
{
if（m==cnt）
{
if（res>max）
{
max=res;
}
return;
}
if（index>=size）
{
return;
}
fun（val,index+1,size,m,cnt+1,res*val[index]）;
fun（val,index+1,size,m,cnt,res）;
}
11、 算法提高最小方差生成树
问题描述
给定带权无向图，求出一颗方差最小的生成树。
输入格式
输入多组测试数据。
第一行为N,M，依次是点数和边数。
接下来M行，每行三个整数U,V,W，代表连接U,V的边，和权值W。
保证图连通。
n=m=0标志着测试文件的结束。
输出格式
对于每组数据，输出最小方差，四舍五入到0.01。
输出格式按照样例。
样例输入
45
121
232
342
411
243
46
121
232
343
411
243
133
00
样例输出
Case1:
0.22
Case2:
0.00
数据规模与约定
1<=U,V<=N<=50,N-1<=M<=1000,0<=W<=50。
数据不超过5组。
该题暂时没有人完全正确，暂时没有该语言的参考程序。
锦囊1
使用最小生成树。
锦囊2
枚举最小生成树可能的边权平均值，将边权设置为原边权减去平均值的平方，然后求最小生成树。
12、算法提高道路和航路
问题描述
农夫约翰正在针对一个新区域的牛奶配送合同进行研究。
他打算分发牛奶到T个城镇（标号为1..T），这些城镇通过R条标号为（1..R）的道路和P条标号为（1..P）的航路相连。
每一条公路i或者航路i表示成连接城镇Ai（1<=A_i<=T）和Bi（1<=Bi<=T）代价为Ci。
每一条公路，Ci的范围为0<=Ci<=10,000；由于奇怪的运营策略，每一条航路的Ci可能为负的，也就是-10,000<=Ci<=10,000。
每一条公路都是双向的，正向和反向的花费是一样的，都是非负的。
每一条航路都根据输入的Ai和Bi进行从Ai->Bi的单向通行。
实际上，如果现在有一条航路是从Ai到Bi的话，那么意味着肯定没有通行方案从Bi回到Ai。
农夫约翰想把他那优良的牛奶从配送中心送到各个城镇，当然希望代价越小越好，你可以帮助他嘛？
配送中心位于城镇S中（1<=S<=T）。
输入格式
输入的第一行包含四个用空格隔开的整数T，R，P，S。
接下来R行，描述公路信息，每行包含三个整数，分别表示Ai，Bi和Ci。
接下来P行，描述航路信息，每行包含三个整数，分别表示Ai，Bi和Ci。
输出格式
输出T行，分别表示从城镇S到每个城市的最小花费，如果到不了的话输出NOPATH。
样例输入
6334
125
345
5610
35-100
46-100
13-10
样例输出
NOPATH
NOPATH
5
0
-95
-100
数据规模与约定
对于20%的数据，T<=100，R<=500，P<=500；
对于30%的数据，R<=1000，R<=10000，P<=3000；
对于100%的数据，1<=T<=25000，1<=R<=50000，1<=P<=50000。
锦囊1
使用最短路径。
锦囊2
将城镇看成结点，将公路和航路看成边，使用带堆优化的Dijkstra来求到每个城镇的最短路。
#include
#include
#include
#include
#include
#include
#include
#defineclr（a,b）memset（a,b,sizeof（a））
usingnamespacestd;
constintN=25050;
constintE=150500;
//邻接表
inth[N],v[E],w[E],nxt[E],el;
voidinitEdge（）{
clr（h,-1）;el=0;
}
voidaddEdge（intx,inty,intz）{
v[el]=y;w[el]=z;nxt[el]=h[x];h[x]=el++;
}
//belong[i]表示节点i所在的强连通分量；
//cnt表示强连通分量的个数；
intdfn[N],sta[N],low[N],belong[N];
inttop,cnt,ind,n;
boolvis[N];
voidTarjanSolve（intu）{
dfn[u]=low[u]=++ind;
vis[u]=true;
sta[++top]=u;
for（intp=h[u];~p;p=nxt[p]）{
inti=v[p];
if（!
dfn[i]）{
TarjanSolve（i）;
if（low[i]}
else
if（vis[i]&&dfn[i]low[u]=dfn[i];
}
if（dfn[u]==low[u]）{
++cnt;
while
（1）{
inti=sta[top--];
vis[i]=false;
belong[i]=cnt;
if（i==u）break;
}
}
}
voidTarjan（）{//注意节点是从几开始存的
clr（dfn,0）;
clr（vis,0）;
top=cnt=ind=0;
for（inti=1;i<=n;i++）//这里节点从1开始存，若从0开始存要改这里
if（!
dfn[i]）TarjanSolve（i）;
}
structEDGE{
intu,v,w;
boolflag;
EDGE（）{}
EDGE（intx,inty,intz,boolf）:
u（x）,v（y）,w（z）,flag（f）{}
}edge[E];
intedgel;
boolvisitable[N];
voiddfs（intx）{
visitable[x]=true;
for（inti=h[x];~i;i=nxt[i]）{
if（!
visitable[v[i]]）{
dfs（v[i]）;
}
}
}
intindegree[N];
//链表
intlh[N],lel,lv[E],lnxt[E];
voidinitLink（）{
clr（lh,-1）;lel=0;
}
voidaddLink（intx,inty）{
lv[lel]=y;lnxt[lel]=lh[x];lh[x]=lel++;
}
intdis[N];
booltag[N];
intmain（）{
intr,p,s;
while（~scanf（"%d%d%d%d",&n,&r,&p,&s））{
clr（visitable,0）;
initEdge（）;
edgel=0;
intx,y,z;
for（inti=0;iscanf（"%d%d%d",&x,&y,&z）;
addEdge（x,y,z）;
addEdge（y,x,z）;
edge[edgel++]=EDGE（x,y,z,false）;
}
for（inti=0;iscanf（"%d%d%d",&x,&y,&z）;
addEdge（x,y,z）;
edge[edgel++]=EDGE（x,y,z,true）;
}
Tarjan（）;
dfs（s）;
initEdge（）;
initLink（）;
clr（indegree,0）;
for（inti=0;iif（visitable[edge[i].u]&&visitable[edge[i].v]）{
addEdge（edge[i].u,edge[i].v,edge[i].w）;
if（edge[i].flag）{
++indegree[belong[edge[i].v]];
addLink（belong[edge[i].v],edge[i].v）;
}else{
addEdge（edge[i].v,edge[i].u,edge[i].w）;
}
}
}
stackzeroDegree;
priority_queue>que;
clr（vis,false）;
clr（tag,false）;
clr（dis,0x3f）;
dis[s]=0;
que.push（make_pair（0,s））;
while（!
que.empty（）||!
zeroDegree.empty（））{
if（que.empty（））{
intx=zeroDegree.top（）;zeroDegree.pop（）;
for（inti=lh[x];~i;i=lnxt[i]）{
inty=lv[i];
if（!
vis[y]）{
vis[y]=true;
que.push（make_pair（-dis[y],y））;
}
}
}else{
intx=que.top（）.second;que.pop（）;
if（tag[x]）continue;
tag[x]=true;
for（inti=h[x
升级会员 