JLU数据结构荣誉课——第七次上机实验
一.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
作者 谷方明 单位 吉林大学 代码长度限制 16 KB 时间限制 100 ms 内存限制 10 MB
思路：
本题为模拟题，模拟栈的出入，先创建一个栈，循环输入给定序列的每一个元素，每输入一个数字，就从==未入过栈==的最小元素开始入栈，一直到当前数字入栈之后截至，然后弹出栈顶元素，当栈顶元素和当前元素不匹配时，flag置为false,然后等到输入完毕，输出判断结果。
操作：
1.引入pre指针，记录未入栈的最小元素。在每次循环结束后，用当前输入元素pre=ans+1进行更新，在pre>之后的ans后，入栈将停止。 2.入栈判断问题：在本程序中遇到样例如：
1 10000
1 10000 2 9999 3 9998 4 9997 5 9996 6 9995.....
在入栈不判断时，就会爆栈，导致段错误。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int SS[10001];
int top = 0;
int pre = 1;
bool flag = true;
int main()
{
int Size, n;
scanf("%d%d", &n, &Size);
for (int i = 1; i <= n; i++)
{
int num = 0;
scanf("%d", &num);
for (int j = 1; j <= num; j++)
{
int ans=0;
scanf("%d", &ans);
if(flag==true)//如果已经判断结束，就不再压栈，避免爆栈
for (int k = pre; k <= ans; k++)
{
SS[++top] = k;
}
if (top > Size)flag = false;
if (SS[top] != ans)flag = false;
if (top > 0)top--;
pre = ans + 1;
}
if (flag)printf("Yes\n");
else printf("No\n");
flag = true;top = 0;pre = 1;
}
return 0;
}
反思：爆栈问题，用stack内存超限也有可能是这个原因。
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
作者 谷方明 单位 吉林大学 代码长度限制 16 KB 时间限制 100 ms 内存限制 64 MB
思路：哈夫曼树的模拟,采用双堆。
代码如下：
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> >Q;
priority_queue<int>Q1;
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int ans;
scanf("%d", &ans);
Q1.push(ans);
Q.push(ans);
}
while (Q.size()!=1)
{
int ans1 = Q.top();
Q.pop();
int ans2 = Q.top();
Q.pop();
Q.push(ans1*ans2 + 1);
ans1 = Q1.top();
Q1.pop();
ans2 = Q1.top();
Q1.pop();
Q1.push(ans1*ans2 + 1);
}
printf("%d", Q.top() - Q1.top());
return 0;
}
代码2：
采用sort排序：
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
priority_queue<long long, vector<long long>, greater<long long> >Q;
long long a[10001];
bool cmp(long long &a,long long &b)
{
return a > b;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
Q.push(a[i]);
}
sort(a + 1, a + n + 1,cmp);
int i = 2;
while (Q.size() != 1)
{
long long ans1 = Q.top();
Q.pop();
long long ans2 = Q.top();
Q.pop();
Q.push(ans1*ans2 + 1);
a[1] = a[i++] * a[1] + 1;
}
printf("%lld\n", Q.top()- a[1]);
return 0;
}
反思：使用sort内存降低，但是时间略有增加。
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
作者 谷方明 单位 吉林大学 代码长度限制 16 KB 时间限制 1000 ms 内存限制 10MB
思路：
本题最大的难点是递归建树，在确定子树范围的时候要注意. 建树:
void make_tree(int pr1, int la1,int pr2,int la2,int root)
//pr1对应先根序列的第一个元素，la1对应宪根序列的最后一个元素
//pr1对应中根序列的第一个元素，la1对应中根序列的最后一个元素
//root为根结点的下边标
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int pre[20005];
int mid[20005];
int value[20005];
vector<int>mp[100001];
int visited[20005];
int n;
void make_tree(int pr1, int la1,int pr2,int la2,int root)
{
if (pr1 > la1||pr2>la2)return;
else
{
int k = pre[pr1];
for (int i = pr2; i <= la2; i++)
{
if (mid[i] == k)
{
k = i ; break;
}
}
mp[mid[root]].push_back(mid[k]);//将结点连到对应的根上
make_tree(pr1+1,pr1+k-pr2,pr2,k-1,k);//非常关键，根据中根的
//位置确定左右子树的建树范围
make_tree(pr1+k-pr2+1, la1, k + 1, la2, k);//非常关键
}
}
void DFS(int v)
{
if (visited[v])return;
else
{
visited[v] = 1;
for (int i = 0; i < mp[v].size(); i++)
{
int k = mp[v][i];
value[k] = value[v] + value[k];
DFS(k);
}
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &pre[i]);
}
for (int i = 1; i <= n; i++)
{
scanf("%d", &mid[i]);
}
make_tree(1,n,1,n,0);
for (int i = 1; i <= n; i++)
{
scanf("%d", &value[i]);
}
DFS(pre[1]);//深搜更新value
for (int i = 1; i <= n-1; i++)
{
printf("%d ", value[i]);
}
printf("%d\n", value[n]);
return 0;
}
反思：在处理区间长度的时候处理的不好，导致拿不到分数。
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
本题即为拓排序的改变，并加入了高精度加法运算，比较综合，但是思路明确。
- 首先对于最短时间的求解，就是关键路径的前半部分(求每个事件最早发生时间)，可以并入拓扑排序一起求解，在求解最早发生时间过程中，我们可以一并求出到每个点的关键方案数。假设每次更新最早发生时间的过程中，当前
p->VerAdj时间为最大值，最大值意味着当ve[i]+cost[p]比该值小时，i就作为p->VerAdj之前的关键方案，当ve[i]+cost[p]>ve[p->VerAdj]的时候，在更新最早发生时间的同时，将p->VerAdj的关键方案数变为i点的关键方案数(即改变最大假设值)；当ve[i]+cost[p]=ve[p->VerAdj]时，将i点的关键方案数加和到p->VerAdj上(即以当前最大假设值为基准)。 - 现在我们剖析关键方案数在本题中到底怎么数。 ==我们首先引入虚汇点，将点权转化为边权== 以样例为例：
graph LR
A((1))-- 1 --> B((2))
A --1--> C((3))
B --2--> D((4))
C--2 --> D
D--1-->E(虚结点5)
然后分别计算每个点的最早发生时间为(按下标排列，下同):
0,1,1,3,4
计算得，与每一点最早开始时间相同的路径条数(即该点方案数)为：
1,1,1,2,2
后继点的方案数由所有前继点符合关键方案条件加和得到。 再举一个极端的例子
graph LR
A((1)) --1-->F(虚结点)
B((2))--2-->F
C((3))--2-->F
D((4))--2-->F
E((5))--1-->F
在该例子中，存在五个点，零条边，由刚才的定义得到，关键方案数为三条，不能去刻意的排列组合。
代码如下：
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cstdlib>
using namespace std;
int ru[10001];//计算入度，拓扑排序使用
int chu[10001];//计算出度，建立虚汇点使用
int value[10001];//每一点的时间值
long long weight[10005];//每一点最早开始时间
vector<int>mp[10005];
queue<int>Q;//拓扑排序使用
int NUM[10005][105];//关键方案数，取代整数类型
int len[10005];//对应每个NUM的长度，方便计算
int n, m;
void BIP(int u, int v)
{
int M = max(len[u], len[v]);
int ans = 0;
for (int i = 1; i <= M; i++)
{
int k = (ans + NUM[v][i] + NUM[u][i]);
if (k >= 10)
{
ans = 1;
NUM[u][i] = k % 10;
}
else
{
ans = 0;
NUM[u][i] = k;
}
}
if (ans == 1) { NUM[u][M + 1] = 1; len[u] = M + 1; }
else len[u] = M;
}
void TopOrder()
{
int n1 = 0;
while (!Q.empty())
{
int k = Q.front();Q.pop();
for (int i = 0; i < mp[k].size(); i++)
{
int p = mp[k][i];
if (weight[k] + value[k] > weight[p])
{
weight[p] = weight[k] + value[k];
memset(NUM[p], 0, sizeof(NUM[p]));//更新假设操作
len[p] = 0;
BIP(p, k);//重置NUM[p]之后与NUM[k]加和
}
else if (weight[k] + value[k] == weight[p])BIP(p, k);//加和
if (!(--ru[p]))Q.push(p);
}
n1++;
}//现在n+1个点的weight为最大值，条数和集中在NUM[n+1]上
if (n1 != n) { printf("0"); exit(0); }
else
printf("%lld\n", weight[n + 1]);
for (int i = len[n + 1]; i >= 1; i--)
printf("%d", NUM[n + 1][i]);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &value[i]);
for (int i = 1; i <= m; i++)
{
int from, to;
scanf("%d%d", &from, &to);
mp[from].push_back(to);
ru[to]++; chu[from]++;
}
for (int i = 1; i <= n; i++)
{
if (ru[i] == 0)
{
Q.push(i);
NUM[i][1] = 1;//给入度为零的边的方案数赋值成1，作为起始方案值。
len[i] = 1;
}
if (!chu[i])
mp[i].push_back(n + 1);
}
TopOrder();
return 0;
}
反思:题目感觉给的定义有些许问题，可能是我理解错不到位🤣。
やっと終わった！！