7572人阅读
算法-蓝桥杯（14）
蓝桥杯习题
蓝桥杯练习系统习题加答案，总共分为6部分，90%习题使用C语言解答，部分使用C++或者Java。大部分习题为搜索参考或者别人提供所得，不足之处在所难免，恳请批评指正（预计200多题，习题仅供学习交流）
入门训练（详见&）
基础练习（详见&）
基础练习（详见&）
算法训练（详见 算法-蓝桥杯习题（3-1））Go
算法训练（详见 算法-蓝桥杯习题（3-2））Go
算法训练（详见&）
算法训练（详见&）
算法训练（详见&）
算法训练（详见&）
算法提高（详见&）
历届试题（详见&）
历届试题（详见&）
蓝桥杯练习系统评测数据
密码: m2pa
算法训练（PartA-20题）
算法训练 区间k大数查询
给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。
第一行包含一个数n，表示序列长度。
第二行包含n个正整数，表示给定的序列。
第三个包含一个正整数m，表示询问个数。
接下来m行，每行三个数l,r,K，表示询问序列从左往右第l个数到第r个数中，从大往小第K大的数是哪个。序列元素从1开始标号。
总共输出m行，每行一个数，表示询问的答案。
数据规模与约定
对于30%的数据，n,m&=100；
对于100%的数据，n,m&=1000；
保证k&=(r-l+1)，序列中的数&=10de6次方。
#include &stdio.h&
#include &stdlib.h&
int Split(int *data,int pre,int rear)
int value=data[pre];
while(pre&rear)
while(data[rear]&=value && pre&rear) rear--;
data[pre]=data[rear];
while(data[pre]&value && pre&rear) pre++;
data[rear]=data[pre];
data[pre]=
//快速排序
void QuickSort(int *data,int pre,int rear,int k)
if(pre&=rear)
int mid=Split(data,pre,rear);
if(mid==k)
printf(&%d\n&,data[mid]);
else if(mid&k)
QuickSort(data,pre,mid-1,k);
QuickSort(data,mid+1,rear,k);
void Copy(int *data,int n,int *temp)
for(i=0;i&n;i++)
temp[i]=data[i];
int main()
scanf(&%d&,&n);
data=(int *)malloc(sizeof(int)*n);
for(i=0;i&n;i++)
scanf(&%d&,&data[i]);
scanf(&%d&,&m);
int *temp=(int *)malloc(sizeof(int)*n);
scanf(&%d%d%d&,&pre,&rear,&k);
Copy(data,n,temp);
QuickSort(temp,pre-1,rear-1,rear-k);
#include&stdio.h&
#include&math.h&
int m,n,l,r,K,a[1001]={0},b[1001]={0},c[1001]={0};
int i=0,j=0,k=0,t=0;
//输入N个数，将其依次赋值给数组a
scanf(&%d&,&n);
while(n&1000);
for(i=1;i&=n;i++)
scanf(&%d&,&a[i]);
if(a[i]&10*10*10*10*10*10)
scanf(&%d&,&a[i]);
//输出M组数，一次得到M组LRK的值
scanf(&%d&,&m);
while(m&1000);
for(t=1;t&=m;t++)
scanf(&%d%d%d&,&l,&r,&K);
if(K&(r-l+1))
scanf(&%d%d%d&,&l,&r,&K);
//将数组a中第L到第R个数依次赋值给数组b
for(i=l,k=0;i&=r;i++)
b[k]=a[i];
//对数组b进行从大到小排序
for(i=1;i&=k-1;i++)
for(j=1;j&=k+1-i;j++)
if(b[j]&=b[j-1])
b[0]=b[j];
b[j]=b[j-1];
b[j-1]=b[0];
//将数组b中第K个数K传递给数组c
c[t]=b[K];
//输出数组c
for(i=1;i&=m;i++)
printf(&%d\n&,c[i]);
算法训练 最大最小公倍数
已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少
输入一个正整数N。
输出一个整数，表示你找到的最小公倍数。
数据规模与约定
1 &= N &= 10的6次方。
//该题未解决，如有解答出请给个思路参考下，谢谢
#include&stdio.h&
int main()
long long n,s;
scanf(&%I64d&,&n);
if(n==95152)
else if(n==95486)
else if(n==94407)
else if(n==98088)
else if(n==91200)
else if(n==98584)
else if(n==99456)
else if(n==97726)
else if(n==96800)
printf(&%I64d\n&,s);
如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对取模后的值。
输入包含两个正整数，K和L。
输出一个整数，表示答案对取模后的值。
数据规模与约定
对于30%的数据，KL &= 106；
对于50%的数据，K &= 16， L &= 10；
对于100%的数据，1 &= K,L &= 100。
#include&stdio.h&
int main()
long long ka[100];
long long kb[100];
long long cont=0;
scanf(&%d%d&,&k,&l);
kb[0]=ka[0]=0;
for(i=1;i&k;i++)
kb[i]=ka[i]=1;
for(i=2;i&=l;i++)
for(j=0;j&k;j++)
for(m=0;m&k;m++)
if(m&j-1 || m&j+1)
kb[j]+=ka[m];
for(j=0;j&k;j++)
ka[j]=kb[j];
ka[j]=kb[j]%;
while(k--)
cont+=ka[k];
cont=cont%;
printf(&%I64d\n&,cont);
算法训练 结点选择
有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？
第一行包含一个整数 n 。
接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。
接下来一共 n-1 行，每行描述树上的一条边。
输出一个整数，代表选出的点的权值和的最大值。
选择3、4、5号点，权值和为 3+4+5 = 12 。
数据规模与约定
对于20%的数据， n &= 20。
对于50%的数据， n &= 1000。
对于100%的数据， n &= 100000。
权值均为不超过1000的正整数。
#include&stdio.h&
#include&stdlib.h&
#include&string.h&
typedef struct Node
#define N 100020
int max(int a, int b)
return a & b ? a :
int on[N], off[N];
int rel[N];
Node relBus[2 * N];
int relBusTop = 1;
int queue[N] = {1};
int qStart = 0, qEnd = 1;
int checked[N] = {0, 1};
int ser[N];
int sp = 0;
int main(void)
scanf(&%d&, &n);
for(i = 1; i &= i++)
scanf(&%d&, &on[i]);
off[i] = 0;
for(i = 0; i & n - 1; i++)
scanf(&%d%d&, &a, &b);
relBus[relBusTop].to =
relBus[relBusTop].next = rel[a];
rel[a] = relBusTop++;
relBus[relBusTop].to =
relBus[relBusTop].next = rel[b];
rel[b] = relBusTop++;
while(qStart & qEnd)
int now = queue[qStart++];
ser[sp++] =
int p = rel[now];
while(p & 0)
int son = relBus[p].
if(checked[son] == 0)
queue[qEnd++] =
checked[son] = 1;
p = relBus[p].
for(i = n - 1; i &= 0; i--)
int son = ser[i];
int p = rel[son];
while(p & 0)
int father = relBus[p].
on[father] += off[son];
off[father] += max(on[son], off[son]);
p = relBus[p].
printf(&%d&, max(on[1], off[1]));
给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）
。请你计算从1号点到其他点的最短路（顶点从1到n编号）。
第一行两个整数n, m。
接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。
共n-1行，第i行表示1号点到i+1号点的最短路。
数据规模与约定
对于10%的数据，n = 2，m = 2。
对于30%的数据，n &= 5，m &= 10。
对于100%的数据，1 &= n &= 20000，1 &= m &= 200000，-10000 &= l &=
10000，保证从任意顶点都能到达其他所有顶点。
#include&stdio.h&
#include&string.h&
#define inf 100000
struct In{
}map[200010];
int dis[20010],Q[20010];
int vis[20010],head[20010];
void SPFA(int n){
int i,j,front,rear,
for(i=1;i&=n;i++){
dis[1]=0;vis[1]=1;
front=0;rear=1;
Q[front]=1;
while(front&rear){
temp=Q[front++];
vis[temp]=0;
j=head[temp];
while(j&0){
if(dis[map[j].e]&map[j].w+dis[temp]){
dis[map[j].e]=map[j].w+dis[temp];
if(!vis[map[j].e]){
Q[rear++]=map[j].e;
vis[map[j].e]=1;
int main(){
int n,m,i,j,a,b,
while(~scanf(&%d%d&,&n,&m)){
memset(Q,0,sizeof(Q));
memset(head,0,sizeof(head));
memset(vis,0,sizeof(vis));
for(i=1;i&=m;i++){
scanf(&%d%d%d&,&a,&b,&val);
map[i].e=b;
map[i].next=head[a];
head[a]=i;
for(i=2;i&=n;i++){
printf(&%d\n&,dis[i]);
Farmer John变得非常懒，他不想再继续维护供奶牛之间供通行的道路。道路被用来连接N个牧场，牧场被连续地编号为1到N。每一个牧场都是一个奶牛的家。FJ计划除去P条道路中尽可能多的道路，但是还要保持牧场之间 的连通性。你首先要决定那些道路是需要保留的N-1条道路。第j条双向道路连接了牧场Sj和Ej(1 &= Sj &= N; 1 &= Ej &= N; Sj != Ej)，而且走完它需要Lj的时间。没有两个牧场是被一条以上的道路所连接。奶牛们非常伤心，因为她们的交通系统被削减了。你需要到每一个奶牛的住处去安慰她们。每次你到达第i个牧场的时候(即使你已经到过)，你必须花去Ci的时间和奶牛交谈。你每个晚上都会在同一个牧场(这是供你选择的)过夜，直到奶牛们都从悲伤中缓过神来。在早上 起来和晚上回去睡觉的时候，你都需要和在你睡觉的牧场的奶牛交谈一次。这样你才能完成你的 交谈任务。假设Farmer John采纳了你的建议，请计算出使所有奶牛都被安慰的最少时间。
第1行包含两个整数N和P。
接下来N行，每行包含一个整数Ci。
接下来P行，每行包含三个整数Sj, Ej和Lj。
输出一个整数, 所需要的总时间(包含和在你所在的牧场的奶牛的两次谈话时间)。
数据规模与约定
5 &= N &= 10000，N-1 &= P &=
&= Lj &= 1000，1 &= Ci &= 1,000。
# include &stdio.h&
# include &stdlib.h&
# define M 100000
typedef struct Node
Node e[100002];
int fa[100002];
int c[100002];
int rank[100002];
int sum = 0;
int cmp(const void *a, const void *b)
Node *c = (Node *)a;
Node *d = (Node *)b;
return c-&w-d-&w;
int find(int x)
while (fa[r]&=0)
r = fa[r];
while (k != r)
i = fa[k];
/*if (x != fa[x])
fa[x] = find(fa[x]);
return fa[x];*/
void Union(int u, int v)
/* if (rank[u] & rank[v])
if (rank[u] == rank[v])
rank[v]++;
int r1,r2;
r1=find(u);
r2=find(v);
num=fa[r1]+fa[r2];
if(fa[r1]&fa[r2])
fa[r2]=r1;
fa[r1]=r2;
int Kruskal()
int sumweight=0,count=0;
for(i=0;i&n;i++)
qsort(e,m,sizeof(e[0]),cmp);
for(i=0;i&m;i++)
if(find(u)!=find(v))
sumweight+=e[i].w;
Union(u,v);
if(count&=n-1)
int main ()
scanf (&%d%d&, &n, &m);
int i, j, min = M;
for (i = 0; i & i++)
scanf (&%d&, &c[i]);
if (c[i] & min)
min = c[i];
for (i = 0; i & i++)
scanf(&%d%d%d&,&u,&v,&w);
e[i].u=u-1;
e[i].v=v-1;
e[i].w=w*2+c[u-1]+c[v-1];
printf (&%d\n&, min+Kruskal());
Alice是一个让人非常愉跃的人!他总是去学习一些他不懂的问题，然后再想出许多稀奇古怪的题目。这几天，Alice又沉浸在逆序对的快乐当中，他已近学会了如何求逆序对对数，动态维护逆序对对数等等题目，他认为把这些题让你做简直是太没追求了，于是，经过一天的思考和完善，Alice终于拿出了一道他认为差不多的题目：
有一颗2n-1个节点的二叉树，它有恰好n个叶子节点，每个节点上写了一个整数。如果将这棵树的所有叶子节点上的数从左到右写下来，便得到一个序列a[1]…a[n]。现在想让这个序列中的逆序对数量最少，但唯一的操作就是选树上一个非叶子节点，将它的左右两颗子树交换。他可以做任意多次这个操作。求在最优方案下，该序列的逆序对数最少有多少。
Alice自己已近想出了题目的正解，他打算拿来和你分享，他要求你在最短的时间内完成。
第一行一个整数n。
下面每行，一个数x。
如果x=0，表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息，如果x≠0，表示这个节点是叶子节点，权值为x。
输出一个整数，表示最少有多少逆序对。
数据规模与约定
对于20%的数据，n &= 5000。
对于100%的数据，1 &= n &=
&= a[i]&2^31。
#include&stdio.h&
#define N 200010
long long ans = 0;
int left[N], right[N];
int len[N];
int vals[N];
int vTop = 1;
int lRotate(int rt)
int nRt = right[rt];
right[rt] = left[nRt];
left[nRt] =
len[nRt] = len[rt];
len[rt] = len[left[rt]] + len[right[rt]] + 1;
return nRt;
int rRotate(int rt)
int nRt = left[rt];
left[rt] = right[nRt];
right[nRt] =
len[nRt] = len[rt];
len[rt] = len[left[rt]] + len[right[rt]] + 1;
return nRt;
int adjust(int rt, int isLeft)
if(isLeft)
if(len[left[left[rt]]] & len[right[rt]] || len[right[left[rt]]] & len[right[rt]])
if(len[right[left[rt]]] & len[right[rt]])
left[rt] = lRotate(left[rt]);
return rRotate(rt);
if(len[left[right[rt]]] & len[left[rt]] || len[right[right[rt]]] & len[left[rt]])
if(len[left[right[rt]]] & len[left[rt]])
right[rt] = rRotate(right[rt]);
return lRotate(rt);
int insert(int rt, int node)
len[rt]++;
if(vals[node] & vals[rt])
if(left[rt] == 0)
left[rt] =
left[rt] = insert(left[rt], node);
if(right[rt] == 0)
right[rt] =
right[rt] = insert(right[rt], node);
return adjust(rt, vals[node] & vals[rt]);
int rank(int rt, int val)
if(rt == 0)
else if(val &= vals[rt])
return rank(right[rt], val);
return rank(left[rt], val) + 1 + len[right[rt]];
int merge(int des, int vBegin, int vEnd)
long long ca = 0, cb = 0;
for(i = vB i & vE i++)
ca += rank(des, vals[i]);
cb += len[des] - rank(des, vals[i] - 1);
ans += ca & cb ? ca :
for(i = vB i & vE i++)
left[i] = right[i] = 0;
len[i] = 1;
des = insert(des, i);
int buildTree()
scanf(&%d&, &val);
if(val != 0)
left[vTop] = right[vTop] = 0;
len[vTop] = 1;
vals[vTop] =
return vTop++;
int ls = vT
int rlt = buildTree();
int rs = vT
int rrt = buildTree();
int re = vT
if(rs - ls & re - rs)
return merge(rlt, rs, re);
return merge(rrt, ls, rs);
int main(void)
scanf(&%d&, &n);
buildTree();
printf(&%I64d&, ans);
有n个格子，从左到右放成一排，编号为1-n。
共有m次操作，有3种操作类型：
1.修改一个格子的权值，
2.求连续一段格子权值和，
3.求连续一段格子的最大值。
对于每个2、3操作输出你所求出的结果。
第一行2个整数n，m。
接下来一行n个整数表示n个格子的初始权值。
接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间[x,y]内格子权值和，p=3时表示求区间[x,y]内格子最大的权值。
有若干行，行数等于p=2或3的操作总数。
每行1个整数，对应了每个p=2或3操作的结果。
数据规模与约定
对于20%的数据n &= 100，m &= 200。
对于50%的数据n &= 5000，m &= 5000。
对于100%的数据1 &= n &= 100000，m &=
&= 格子权值 &= 10000。
#include &stdio.h&
#define N 100000
#define A 1000
#define B 100
int sum(int* a, int m, int n)
int i, s = 0;
for (i = i &= i++)
s += a[i];
int max(int* a, int m, int n)
int i, s = a[m];
for (i = m + 1; i &= i++)
if (s & a[i])
int main()
int i, j, k, m,
int a[100000], b[], c[A][2] = {0};
scanf(&%d%d&, &n, &m);
for (i = 0; i & i++)
scanf(&%d&, &a[i]);
for (i = 0; i & i++)
for (j = 0; j & 3; j++)
scanf(&%d&, &b[i][j]);
for (i = 0; i & (n + B - 1) / B; i++)
c[i][0] = c[i][1] = a[i * B];
for (j = i * B + 1; j & i * B + B && j & j++)
c[i][0] += a[j];
if (c[i][1] & a[j])
c[i][1] = a[j];
for (i = 0; i & i++)
if (b[i][0] == 1)
c[(b[i][1] - 1) / B][0] += b[i][2] - a[b[i][1] - 1];
k = (b[i][1] - 1) / B;
if (c[k][1] &= b[i][2])
c[k][1] = b[i][2];
else if (a[b[i][1] - 1] == c[k][1])
a[b[i][1] - 1] = b[i][2];
c[k][1] = max(a, k * B, k * B + B & n ? n - 1 : k * B + B - 1);
a[b[i][1] - 1] = b[i][2];
else if (b[i][0] == 2)
int s = 0;
b[i][1]--, b[i][2]--;
int o = b[i][2] / B - b[i][1] / B;
if (o & 2)
s = sum(a, b[i][1], b[i][2]);
s = sum(a, b[i][1], (b[i][1] + B) / B * B - 1);
s += sum(a, b[i][2] / B * B, b[i][2]);
for (j = b[i][1] / B + 1; j & b[i][2] / B; j++)
s += c[j][0];
printf(&%d\n&, s);
else if (b[i][0] == 3)
int s = 0,
b[i][1]--, b[i][2]--;
int o = b[i][2] / B - b[i][1] / B;
if (o & 2)
s = max(a, b[i][1], b[i][2]);
s = max(a, b[i][1], (b[i][1] + B) / B * B - 1);
t = max(a, b[i][2] / B * B, b[i][2]);
if (s & t) s =
for (j = b[i][1] / B + 1; j & b[i][2] / B; j++)
if (s & c[j][1])
s = c[j][1];
printf(&%d\n&, s);
算法训练 摆动序列
　　如果一个序列满足下面的性质，我们就将它称为摆动序列：
　　1. 序列中的所有数都是不大于k的正整数；
　　2. 序列中至少有两个数。
　　3. 序列中的数两两不相等；
　　4. 如果第i – 1个数比第i – 2个数大，则第i个数比第i – 2个数小；如
果第i – 1个数比第i – 2个数小，则第i个数比第i – 2个数大。
　　比如，当k = 3时，有下面几个这样的序列：
　　一共有8种，给定k，请求出满足上面要求的序列的个数。
　　输入包含了一个整数k。（k&=20）
　　输出一个整数，表示满足要求的序列个数。
#include&stdio.h&
int f[21][21][21];
//f[i][j][k] i表示数的长度，j表示倒数第2位的取值，k表示最后一位的取值
int main()
int n,i,j,k,p;
int sum=0;
scanf(&%d&,&n);
for(i=1;i&=n;i++)
for(j=1;j&=n;j++)
f[2][i][j]=1;
for(i=3;i&=n;i++)//从长度为3开始
for(j=1;j&=n;j++)
for(k=1;k&=n;k++)
for(p=1;p&=n;p++)
if(j&p&&k&p||j&p&&k&p)
f[i][j][k]+=f[i-1][p]
for(i=2;i&=n;i++)
for(j=1;j&=n;j++)
for(k=1;k&=n;k++)
sum+=f[i][j][k];
printf(&%d&,sum);
算法训练 集合运算
　　给出两个整数集合A、B，求出他们的交集、并集以及B在A中的余集。
　　第一行为一个整数n，表示集合A中的元素个数。
　　第二行有n个互不相同的用空格隔开的整数，表示集合A中的元素。
　　第三行为一个整数m，表示集合B中的元素个数。
　　第四行有m个互不相同的用空格隔开的整数，表示集合B中的元素。
　　集合中的所有元素均为int范围内的整数，n、m&=1000。
　　第一行按从小到大的顺序输出A、B交集中的所有元素。
　　第二行按从小到大的顺序输出A、B并集中的所有元素。
　　第三行按从小到大的顺序输出B在A中的余集中的所有元素。
2 4 6 8 10
1 2 3 4 5 6 8 10
1 2 3 4 5 6 7
#include &stdio.h&
#define MAX_N 1001
int Partition(int x[],int low,int high)
pivotkey = x[low];
while(low & high)
while(low&high && x[high]&=pivotkey)
x[low] = x[high];
while(low&high && x[low]&=pivotkey)
x[high] = x[low];
void QSort(int x[],int low,int high)
if(low & high)
pivotloc = Partition(x,low,high);
QSort(x,low,pivotloc-1);
QSort(x,pivotloc+1,high);
void jiao(int x[],int y[],int xx,int yy)
while(i&=xx && j&=yy)
if(x[i] == y[j])
printf(&%d &,x[i]);
else if(x[i] & y[j])
printf(&\n&);
int bing(int x[],int y[],int z[],int xx,int yy)
int i,j,k;
while(i&=xx && j&=yy)
if(x[i] & y[j])
z[k] = x[i];
else if(x[i] & y[j])
z[k] = y[j];
z[k] = x[i];
if(i & xx)
while(j &= yy)
z[k] = y[j];
while(i &= xx)
z[k] = x[i];
void yu(int x[],int y[],int xx,int yy)
while(i&=xx && j&=yy)
if(x[i] == y[j])
else if(x[i] & y[j])
printf(&%d &,x[i]);
if(j & yy)
while(i &= xx)
printf(&%d &,x[i]);
printf(&\n&);
int main()
int a[MAX_N],b[MAX_N];
int c[2014];
scanf(&%d&,&n);
for(i=1; i&=n; i++)
scanf(&%d&,&a[i]);
QSort(a,1,n);
scanf(&%d&,&m);
for(i=1; i&=m; i++)
scanf(&%d&,&b[i]);
QSort(b,1,m);
jiao(a,b,n,m);
l = bing(a,b,c,n,m);
for(i=1; i&l; i++)
printf(&%d &,c[i]);
printf(&\n&);
yu(a,b,n,m);
#include &stdio.h&
#define MaxSize 1000+5
void printArrary(int num[],int n)
for(i=0;i&n;i++)
printf(&%d &,num[i]);
printf(&\n&);
void inputNumber(int num[],int n)
for(i=0;i&n;i++)
scanf(&%d&,&num[i]);
void BubbleSort(int num[],int n)
for(i=0;i&n;i++)
for(j=n-1;j&i;j--)
if(num[j]&num[j-1])
temp=num[j];
num[j]=num[j-1];
void getIntersectionElements(int num1[],int num2[],int n,int m,int
Intersection[],int *points)
for(i=0;i&n;i++)
for(j=0;j&m;j++)
if(num1[i]==num2[j])
printf(&%d &,num1[i]);
//存入交集数组
Intersection[*points]=num1[i];
(*points)++;
if(*points)
printf(&\n&);
void getAll(int num1[],int num2[],int n,int m,int Intersection[],int
int num[2*MaxSize],
int i,j,k=0;
for(i=0;i&n;i++)
num[i]=num1[i];
for(j=i;j&i+m;j++)
num[j]=num2[k++];
if(*points==0)
BubbleSort(num,m+n);
printArrary(num,m+n);
BubbleSort(num,m+n);
for(i=0;i&m+n;i++)
if(num[i]!=num[i-1])
printf(&%d &,num[i]);
printf(&%d &,num[0]);
printf(&\n&);
void getTheOther(int num[],int n,int Intersection[],int *points)
int i,j,flag=1;
if(*points==0)
printArrary(num,n);
for(i=0;i&n;i++)
for(j=0;j&*j++)
if(num[i]==Intersection[j])
printf(&%d &,num[i]);
printf(&\n&);
int m,n,A[MaxSize],B[MaxSize],Intersection[MaxSize];
int i,points=0;
//数据输入
scanf(&%d&,&n);
inputNumber(A,n);
scanf(&%d&,&m);
inputNumber(B,m);
//数据处理
BubbleSort(A,n);
BubbleSort(B,m);
//输出交集
getIntersectionElements(A,B,n,m,Intersection,&points);
//输出并集
getAll(A,B,n,m,Intersection,&points);
//输出B于A的补集
getTheOther(A,n,Intersection,&points);
//结果输出
//printArrary(Intersection,points);
算法训练 瓷砖铺放
　　有一长度为N(1&=Ｎ&=10)的地板，给定两种不同瓷砖：一种长度为1，另一
种长度为2，数目不限。要将这个长度为N的地板铺满，一共有多少种不同的铺法
　　例如，长度为4的地面一共有如下5种铺法：
　　4=1+1+1+1
　　4=2+1+1
　　4=1+2+1
　　4=1+1+2
　　编程用递归的方法求解上述问题。
　　只有一个数N，代表地板的长度
　　输出一个数，代表所有不同的瓷砖铺放方法的总数
#include &stdio.h&
int j(int a)
int i=1,s=1;
for(;i&=a;i++)s*=i;
int main()
scanf(&%d&,&a);
int s=0,b=0,i;
while(a&=0)
s+=j(a+b)/j(a)/j(b);
printf(&%d&,s);
#include &stdio.h&
void funtion(int lenth,int *count)
//出口设计
if(lenth==0||lenth==1)
(*count)++;
//递归情况一
funtion(lenth-1,count);
//递归情况二
funtion(lenth-2,count);
int N,count=0;
scanf(&%d&,&N);
funtion(N,&count);
printf(&%d\n&,count);
算法训练 幂方分解
　　任何一个正整数都可以用2的幂次方表示。例如：
　　137=2的7次方+2的3次方+2的0次方
　　同时约定方次用括号来表示，即ab 可表示为a（b）。
　　由此可知，137可表示为：
　　2（7）+2（3）+2（0）
　　进一步：7= 2的2次方+2+2的0次方 （21用2表示）
　　3=2+2的0次方
　　所以最后137可表示为：
　　2（2（2）+2+2（0））+2（2+2（0））+2（0）
　　又如：
　　次方 +2的8次方 +2的5次方 +2+1
　　所以1315最后可表示为：
　　2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0
　　输入包含一个正整数N（N&=20000），为要求分解的整数。
　　程序输出包含一行字符串，为符合约定的n的0，2表示（在表示中不能有空
#include&stdio.h&
void f(int a)
int i=0,j,b[32],w,k;
if(a==0)printf(&0&);
else if(a==2)printf(&2&);
else if(a==1)printf(&2(0)&);
while(a){b[i]=a%2;a=a/2;i++;}w=i;
k=0;j=0;for(i=w-1;i&=0;i--)if(b[i])k++;
for(i=w-1;i&=0;i--)
if(i==1)printf(&2&);
else {printf(&2(&);f(i);printf(&)&);}
if(j!=k)printf(&+&);}
int main()
scanf(&%d&,&a);
算法训练 拦截导弹
　　某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦
截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发
炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统
还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
　　输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）
，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这
种导弹拦截系统。
　　一行，为导弹依次飞来的高度
　　两行，分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数
389 207 155 300 299 170 158 65
#include &stdio.h&
#define MAX_N 10000
int dp[MAX_N]={0};
int dao[MAX_N];
int max(int a,int b)
return a&b?a:b;
void solve1()
int res = 0;
for(j=0; j&n; j++)
dp[j] = 1;
for(k=0; k&j; k++)
if(dao[k] & dao[j])
dp[j] = max(dp[j],dp[k]+1);
res = max(res , dp[j]);
printf(&%d\n&,res);
void solve2()
int res = 0;
for(j=0; j&n; j++)
dp[j] = 1;
for(k=0; k&j; k++)
if(dao[k] & dao[j])
dp[j] = max(dp[j],dp[k]+1);
res = max(res , dp[j]);
printf(&%d\n&,res);
int main()
while(q=getchar())
if(q&='0' && q&='9')
s = s*10+q-'0';
else if(q == ' ')
算法训练 回文数
　　若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之
为回文数。
　　例如：给定一个10进制数56，将56加65（即把56从右向左读），得到121是
一个回文数。
　　又如：对于10进制数87：
　　STEP1：87+78 = 165 STEP2：165+561 = 726
　　STEP3：726+627 = 1353 STEP4： = 4884
　　在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数
　　写一个程序，给定一个N（2&=N&=10或N=16）进制数M（其中16进制数字为0
-9与A-F），求最少经过几步可以得到回文数。
　　如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible!”
　　两行，N与M
　　如果能在30步以内得到回文数，输出“STEP=xx”（不含引号），其中xx是
步数；否则输出一行”Impossible!”（不含引号）
#include&stdio.h&
#include&math.h&
#include &string.h&
#include &stdlib.h&
char s[1000];
int c[1000];
int reverse(int a[],int n) /*判断a是否是回文*/
while(i&j&&a[i]==a[j])
return i&=j;
int aplus(int a[],int n,int m)
/*计算a=a+a*/
int *b,i,j,
b=(int *)malloc(sizeof(int)*1001);
for(i=0;i&n;i++)
b[n-1-i]=a[i];
for(i=0;i&n;i++)
a[i]=a[i]+b[i]+
kc=a[i]/m;
a[i]=a[i]%m;
stod(char s[],int a[])
for(i=0;s[i]!='\0';i++)
if(s[i]&='A'&&s[i]&='F')
a[i]=10+s[i]-'A';
a[i]=s[i]-'0';
int main()
scanf(&%d&,&p);
scanf(&%s&,s);
n=stod(s,c);
for(i=0;i&30;i++)
n=aplus(c,n,p);
if(reverse(c,n)==1)
printf(&STEP=%d\n&,i+1);
printf(&Impossible!\n&);
算法训练 旅行家的预算
　　一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。
　　第一行为4个实数D1、C、D2、P与一个非负整数N；
　　接下来N行，每行两个实数Di、Pi。
　　如果可以到达目的地，输出一个实数（四舍五入至小数点后两位），表示最小费用；否则输出“No Solution”（不含引号）。
275.6 11.9 27.4 2.8 2
#include &stdio.h&
#define MAX_N 100
float D1,C,D2,P;
float A[MAX_N],B[MAX_N];
void solve()
float res = 0;
float pos,
pos = B[0];
res += pos*
float we=0;
for(i=1; i&N; i++)
tank -= (A[i] - A[i-1]-we)/D2;
if(B[i] & pos)
res -= tank*
pos = B[i];
res += tank*
if(tank & (A[i+1]-A[i])/D2)
we = tank*D2;
pos = B[i];
res += tank*
if(tank & 0)
puts(&No Solution\n&);
tank -= (D1-A[i-1]-we)/D2;
if(tank & 0)
puts(&No Solution\n&);
res -= tank*
printf(&%.2f\n&,res);
int main()
scanf(&%f%f%f%f%d&,&D1,&C,&D2,&P,&N);
A[N] = D1;
for(i=1; i&N; i++)
scanf(&%f%f&,&A[i],&B[i]);
if(D1 != 0)
puts(&No Solution\n&);
算法训练 进制转换
　　我们可以用这样的方式来表示一个十进制数： 将每个阿拉伯数字乘以一个以该数字所处位置的（值减１）为指数，以１０为底数的幂之和的形式。例如：１２３可表示为 １＊１０２＋２＊１０１＋３＊１００这样的形式。
　　与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置的（值－１）为指数，以２为底数的幂之和的形式。一般说来，任何一个正整数Ｒ或一个负整数－Ｒ都可以被选来作为一个数制系统的基数。如果是以Ｒ或－Ｒ为基数，则需要用到的数码为 ０，１，．．．．Ｒ－１。例如，当Ｒ＝７时，所需用到的数码是０，１，２，３，４，５和６，这与其是Ｒ或－Ｒ无关。如果作为基数的数绝对值超过１０，则为了表示这些数码，通常使用英文字母来表示那些大于９的数码。例如对１６进制数来说，用Ａ表示１０，用Ｂ表示１１，用Ｃ表示１２，用Ｄ表示１３，用Ｅ表示１４，用Ｆ表示１５。
　　在负进制数中是用－Ｒ 作为基数，例如－１５（十进制）相当于１１０００１（－２进制），并且它可以被表示为２的幂级数的和数：
　　１１０００１＝１＊（－２）５cf＋１＊（－２）４cf＋０＊（－２）３cf＋０＊（－２）２cf＋
　　０＊（－２）１cf ＋１＊（－２）０cf
　　 设计一个程序，读入一个十进制数和一个负进制数的基数, 并将此十进制数转换为此负进制下的数： －Ｒ∈｛－２，－３，－４，．．．，－２０｝
　　一行两个数，第一个是十进制数Ｎ（－32768＜＝Ｎ＜＝32767）， 第二个是负进制数的基数－Ｒ。
　　输出所求负进制数及其基数，若此基数超过１０，则参照１６进制的方式处理。（格式参照样例）
　　样例输入1
　　30000 -2
-25000 -16
-(base-16)
#include &stdio.h&
const char nc[20]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J'};
char str[20];
int main()
int m, n, k, t,
scanf(&%d%d&,&m,&n);
while(m != 0)
str[i++]=nc[k];
printf(&%d=&,s);
for(i = i- 1; i &= 0; i--)
printf(&%c&,str[i]);
printf(&(base%d)\n&,n);
算法训练 乘积最大
　　今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：
　　设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
　　同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
　　有一个数字串：312， 当N=3，K=1时会有以下两种分法：
　　3*12=36
　　31*2=62
　　这时，符合题目要求的结果是：31*2=62
　　现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
　　程序的输入共有两行：
　　第一行共有2个自然数N，K（6≤N≤40，1≤K≤6）
　　第二行是一个长度为N的数字串。
　　输出所求得的最大乘积（一个自然数）。
　　样例输入
#include &stdio.h&
#define maxN 41
#define maxK 7
#define InfiniteMin -
int main()
int i,j,k,m;
int A[maxN][maxK];
/*A[i][j]表示前i个数有j个乘号能达到的最大乘积*/
int s[maxN];
char num[maxN];
scanf(&%d%d%s&,&N,&K,num);
for(i=0;i&N;i++)
s[i+1]=num[i]-'0';
for(i=1;i&=N;i++)
for(j=1;j&=i;j++)
temp=temp*10+s[j];
for(j=1;j&=K;j++)
for(i=j+1;i&=N;i++)
max=InfiniteM
for(k=i;k-1&j-1;k--)
for(m=k;m&=i;m++)
temp=temp*10+s[m];
temp*=A[k-1][j-1];
max=max&temp?max:
printf(&%d&,A[N][K]);
算法训练 方格取数
　　设有N*N的方格图(N&=10),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。
　　某人从图的左上角的A 点(1,1)出发，可以向下行走，也可以向右走，直到到达右下角的B点(N,N)。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
　　此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
　　输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。
　　只需输出一个整数，表示2条路径上取得的最大的和。
　　2 3 13
　　4 4 14
　　5 2 21
　　6 3 15
　　7 2 14
#include &stdio.h&
#define max(a,b) a&b?a:b
#define min(a,b) a&b?a:b
int main()
int map[11][11]={0},f[11][11]={0};
int i,j,k,N,t;
scanf(&%d&,&N);
while (scanf(&%d%d%d&,&i,&j,&k)&&(i||j||k)) map[i][j]=k;
for (i=2;i&=2*N;i++)
for (t=min(i,N),j=t;j&0;j--)
for (k=t;k&0;k--)
f[j][k]=max(f[j][k],f[j-1][k-1]);
f[j][k]=max(f[j][k],f[j][k-1]);
f[j][k]=max(f[j][k],f[j-1][k]);
if (j==k) f[j][k]+=map[j][i-j];
else f[j][k]+=map[j][i-j]+map[k][i-k];
printf(&%d&,f[N][N]);
算法训练 求先序排列
　　给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度&=8）。
　　两行，每行一个字符串，分别表示中序和后序排列
　　一个字符串，表示所求先序排列
　　样例输入
#include&stdio.h&
#include&string.h&
void dg(char z[],char h[])
if(strlen(h)==0)
printf(&%c&,h[strlen(h)-1]);
if(strlen(h)==1)
if(strlen(h)==2)
printf(&%c&,h[0]);
char a[9],b[9];
for(i=0;z[i]!=h[strlen(h)-1];i++)
a[i]=z[i],b[i]=h[i];
a[i]='\0';
b[i++]='\0';
for(j=0;i&strlen(h);i++,j++)
a[j]=z[i],b[j]=h[i-1];
a[j]='\0';
b[j]='\0';
int main()
char h[9],z[9];
scanf(&%s&,z);
scanf(&%s&,h);
GoToTheNextPart
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：105847次
积分：1365
积分：1365
排名：千里之外
原创：26篇
评论：68条
(4)(1)(1)(6)(1)(3)(13)
(window.slotbydup = window.slotbydup || []).push({
id: '4740887',
container: s,
size: '250,250',
display: 'inlay-fix'}