数据结构第七次上机实验解题报告
7-1 序列调度 (100 分)
有一个N个数的序列A：1，2，……，N。有一个后进先出容器D，容器的容量为C。如果给出一个由1到N组成的序列，那么可否由A使用容器D的插入和删除操作得到。
输入格式:
第1行，2个整数T和C，空格分隔，分别表示询问的组数和容器的容量，1≤T≤10，1≤C≤N。
第2到T+1行，每行的第1个整数N，表示序列的元素数，1≤N≤10000。接下来N个整数，表示询问的序列。
输出格式:
T行。若第i组的序列能得到，第i行输出Yes；否则，第i行输出No,1≤i≤T。
输入样例:
在这里给出一组输入。例如：
2 2
5 1 2 5 4 3
4 1 3 2 4
输出样例:
在这里给出相应的输出。例如：
No
Yes
解答：根据题意这道题是用出栈和入栈操作实现序列，在程序中用一个栈去模拟生产序列的过程即可，要特别注意对栈的大小的处理。
具体代码如下：
#include<bits/stdc++.h>
using namespace std;
stack<int>q;
int i,j,k,num;
int a[10010];
int main() {
int n,t,len,min0 = 1;
cin>>t>>len;
for(k=0;k<t;k++)
{
min0=1;
cin>>n;
int flag=1;
for (i=0;i<n;i++)
{
cin>>a[i];
}
for(i=0;i<n;i++)
{
if (a[i]>=min0)
{
for (j=min0;j<=a[i];j++)
{
q.push(j);
num++;
}
if(num>len)
{
flag=0;
}
min0=a[i]+1;
}
else
{
if (q.top()!=a[i])
{
flag=0;
}
}
q.pop();
num--;
}
if (flag) {
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
}
}
7-2 最大最小差 (100 分)
对n 个正整数，进行如下操作：每一次删去其中两个数 a 和 b，然后加入一个新数：a*b+1，如此下去直到 只剩下一个数。所有按这种操作方式最后得到的数中，最大的为max，最小的为min，计算max-min。
输入格式:
第1行：n，数列元素的个数，1<=n<=16。
第2行：n 个用空格隔开的数x，x<=10。
输出格式:
1行，所求max-min。
输入样例:
在这里给出一组输入。例如：
3
2 4 3
输出样例:
在这里给出相应的输出。例如：
2
解答：由题意可知，每次取当前所有数中最小的两个相乘加一再放回得到的值一定是最大的，每次取当前所有数中最大的两个相乘加一再放回得到的值一定是最小的，所以用递增递减两个优先队列来存储数据，每次取队头两个数相乘加一再入队，最后得到的即所求。
具体代码如下：
#include<bits/stdc++.h>
using namespace std;
int max0,min0;
priority_queue <int,vector<int>,greater<int>>q1;
priority_queue <int,vector<int>,less<int>>q2;
int main()
{
int n,i,t,t1,t2;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&t);
q1.push(t);
q2.push(t);
}
for(i=0;i<n-1;i++)
{
t1=q1.top(),q1.pop();
t2=q1.top(),q1.pop();
q1.push(t1*t2+1);
t1=q2.top(),q2.pop();
t2=q2.top(),q2.pop();
q2.push(t1*t2+1);
}
max0=q1.top();
min0=q2.top();
printf("%d",max0-min0);
}
7-3 二叉树最短路径长度 (100 分)
给定一棵二叉树T，每个结点赋一个权值。计算从根结点到所有结点的最短路径长度。路径长度定义为：路径上的每个顶点的权值和。
输入格式:
第1行，1个整数n，表示二叉树T的结点数，结点编号1..n，1≤n≤20000。
第2行，n个整数，空格分隔，表示T的先根序列，序列中结点用编号表示。
第3行，n个整数，空格分隔，表示T的中根序列，序列中结点用编号表示。
第4行，n个整数Wi，空格分隔，表示T中结点的权值，-10000≤Wi≤10000，1≤i≤n。
输出格式:
1行，n个整数，表示根结点到其它所有结点的最短路径长度。
输入样例:
在这里给出一组输入。例如：
4
1 2 4 3
4 2 1 3
1 -1 2 3
输出样例:
在这里给出相应的输出。例如：
1 0 3 3
解答：由题意可得本题的关键在于如何利用先根序列和中根序列建树，建完树对树进行一次BFS即可，先根的第一个一定是根，中根序列中根的左侧即根的左子树，右侧即根的右子树，由此递归建树。
#include<bits/stdc++.h>
using namespace std;
int n,i,j;
int lefts[20010],rights[20010];
int cost[20010];
queue<int> que;
int tree(int a[],int b[],int n);
int main()
{
int a[20010],b[20010];
cin>>n;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
scanf("%d",&b[i]);
for(i=1;i<=n;i++)
scanf("%d",&cost[i]);
tree(a+1,b+1,n);
que.push(1);
while(!que.empty())
{
j=que.front();
que.pop();
if(lefts[j])
{
cost[lefts[j]]+=cost[j];
que.push(lefts[j]);
}
if(rights[j])
{
cost[rights[j]]+=cost[j];
que.push(rights[j]);
}
}
for(i=1;i<=n;i++)
{
printf("%d",cost[i]);
if(i!=n)printf(" ");
else printf("\n");
}
}
int tree(int a[],int b[],int n)
{
int t=a[0],k;
if(n==0)return 0;
for(k=0;k<n;k++)
{
if(b[k]==t)
break;
}
lefts[t]=tree(a+1,b,k);
rights[t]=tree(a+k+1,b+k+1,n-k-1);
return t;
}7-4 方案计数 (100 分)
组装一个产品需要 n 个零件。生产每个零件都需花费一定的时间。零件的生产可以并行进行。有些零件的生产有先后关系，只有一个零件的之前的所有零件都生产完毕，才能开始生产这个零件。如何合理安排工序，才能在最少的时间内完成所有零件的生产。在保证最少时间情况下，关键方案有多少种，关键方案是指从生产开始时间到结束时间的一个零件生产序列，序列中相邻两个零件的关系属于事先给出的零件间先后关系的集合，序列中的每一个零件的生产都不能延期。
输入格式:
第1行，2个整数n和m，用空格分隔，分别表示零件数和关系数，零件编号1..n，1≤n≤10000, 0≤m≤100000 。
第2行，n个整数Ti，用空格分隔，表示零件i的生产时间，1≤i≤n，1≤Ti≤100 。
第3到m+2行，每行两个整数i和j，用空格分隔，表示零件i要在零件j之前生产。
输出格式:
第1行，1个整数，完成生产的最少时间。
第2行，1个整数，关键方案数，最多100位。
如果生产不能完成，只输出1行，包含1个整数0.
输入样例:
在这里给出一组输入。例如：
4 4
1 2 2 1
1 2
1 3
2 4
3 4
输出样例:
在这里给出相应的输出。例如：
4
2
解答： 由题意可得该题考察关键路径，注意统计方案数可能有100位，要写一个大整数加法避免溢出。
具体代码如下：
#include<bits/stdc++.h>
using namespace std;
class ll;
int in[20010],out[20010];
int cost[20010],p[20010];
int i,l,x,y,t;
queue<int> q;
vector<pair<int,int> > e[20010];
class ll
{
public:
friend ll operator +(ll& a,ll& b);
friend ostream& operator <<(ostream& out,const ll& tem);
int num[200],top;
ll operator +=(ll& a)
{
*this=*this+a;
return *this;
}
ll(ll const& tem)
{
this->top=tem.top;
memset(this->num,0,sizeof(this->num));
for(int i=0;i<top;i++)
{
this->num[i]=tem.num[i];
}
}
ll(int t=0)
{
top=0;
memset(num,0,sizeof(num));
while(t){
num[top++]=t%10;
t=t/10;
}
}
};
ll operator +(ll& a,ll& b)
{
ll c;
int top;
if(a.top<b.top)
top=b.top;
else top=a.top;
for(i=0;i<top;i++)
{
int tem=a.num[i]+b.num[i];
c.num[i]+=tem;
tem=c.num[i]/10;
c.num[i]%=10;
c.num[i+1]+=tem;
if(i+1==top&&tem)top++;
}
c.top=top;
return c;
}
ostream& operator <<(ostream& out,ll& tem)
{
for(int i=tem.top-1;i>=0;i--)
{
out<<tem.num[i];
}
if(tem.top==0)out<<"0";
return out;
}
int topo[20010],top;
int ee[20010],el[20010];
ll sum[20010];
int main()
{
int n,m;
cin>>n>>m;
for(i=1;i<=n;i++)
{
scanf("%d",&cost[i]);
}
for(i=0;i<m;i++)
{
scanf("%d %d",&x,&y);
e[x].push_back({y,cost[y]});
out[x]++;
in[y]++;
p[y]++;
}
for(i=1;i<=n;i++)
{
if(!in[i]){
e[0].push_back({i,cost[i]});
in[i]++;
p[i]++;
out[0]++;
}
if(!out[i])
{
e[i].push_back({n+1,0});
in[n+1]++;
p[n+1]++;
out[i]++;
}
}
q.push(0);
while(!q.empty())
{
t=q.front();
top++;
topo[top]=t;
q.pop();
for(l=0;l<e[t].size();l++)
{
pair<int,int> tem=e[t][l];
int u=tem.first,w=tem.second;
p[u]--;
if(!p[u])q.push(u);
if(ee[t]+w>ee[u]){
ee[u]=ee[t]+w;
}
}
}
for(i=0;i<=n+1;i++)
el[i]=ee[n+1];
while(top)
{
int tem=topo[top--];
for(int l=0;l<e[tem].size();l++)
{
pair<int,int> vw=e[tem][l];
int v=vw.first,w=vw.second;
if(el[v]-w<el[tem])
{
el[tem]=el[v]-w;
}
}
}
q.push(0);
sum[0]=1;
while(!q.empty())
{
t=q.front();
q.pop();
for(l=0;l<e[t].size();l++)
{
pair<int,int> tem=e[t][l];
int u=tem.first,w=tem.second;
in[u]--;
if(!in[u])
q.push(u);
if(ee[t]==el[u]-w)
{
sum[u]+=sum[t];
}
}
}
if(sum[n+1].top!=0)
cout<<ee[n+1]<<endl;
cout<<sum[n+1]<<endl;
}