JLU数据结构荣誉课——第二次上机实验
7-1 数列查询
已知数列的通项公式为:
f(n) = f(n-1)*11/10，f[1]=10.
通项从左向右计算，*和/分别表示整数乘法和除法。 现在，要多次查询数列项的值。
输入格式:
第1行，1个整数q，表示查询的次数， 1≤q≤10000. 第2至q+1行，每行1个整数i，表示要查询f(i)的值。
输入样例:
在这里给出一组输入。例如：
3
1
2
3
输出样例：
在这里给出相应的输出。例如：
10
11
12
作者 谷方明 单位 吉林大学 代码长度限制 16 KB 时间限制 10 ms 内存限制 1 MB 解法一： 在考场上时，没有考虑到这数字乘起来会有那么大，因此我直接开数组去存每个数量级的(11⁄10)^10，并且竟然把上式看成是double类型😅😅😅。
解法二： 和上种方法类似，考虑到数字较大我们不妨试一试，f[202]=195422668， f[203]=-214531794 好家伙😏 只要202位的数组就行， 那么，不妨循环存入相应次方的下标数组中，之后直接查找，代码如下：
#include<cstdio>
using namespace std;
int num[10003];
int main()
{
int n;
scanf("%d",&n);
int sum=10;
for(int i=1;i<=190;i++)
{
num[i]=sum;
sum*=11;
sum/=10;
}//循环计数
int num1;
for(int i=1;i<=n;i++)
{
scanf("%d",&num1);
printf("%d\n",num[num1]);
}//查找输出
return 0;
}
7-2 稀疏矩阵之和
矩阵A和B都是稀疏矩阵。请计算矩阵的和A+B.如果A、B不能做和，输出“Illegal！”
输入格式:
矩阵的输入采用三元组表示，先A后B。对每个矩阵：
第1行，3个整数N、M、t，用空格分隔，分别表示矩阵的行数、列数和非0数据项数，10≤N、M≤50000，t≤min(N,M).
第2至t+1行，每行3个整数r、c、v，用空格分隔，表示矩阵r行c列的位置是非0数据项v, v在32位有符号整型范围内。三元组默认按行列排序。
输出格式：
矩阵A+B，采用三元组表示，默认按行列排序，非零项也在32位有符号整型范围内。
输入样例:
10 10 3
2 2 2
5 5 5
10 10 20
10 10 2
2 2 1
6 6 6
输出样例:
10 10 4
2 2 3
5 5 5
6 6 6
10 10 20
作者 谷方明` `单位 吉林大学` `代码长度限制 16 KB` `时间限制 100 ms` `内存限制 10 MB
思路：三元组题目，但是坑太多了(对我来说)，首先是求和之后如果为零就删去不要，考场上没想到的我， 只有Illegal有分，其次是cin,cout卡了我时间。 下面是三元组代码：
struct Vertex
{
int r;
int c;
int weight;
}a[50001],b[50001],c[50001];
最核心的比较相加算法则采用双指针思想，让相加时指针随着在两数组所到位置移动，再最后将未加完的数组，按照顺序接到尾部。 代码如下：
#include<cstdio>
using namespace std;
struct Vertex
{
int r;
int c;
int weight;
}a[50001],b[50001],c[50001];
int main()
{
int r1,c1,num1;
scanf("%d%d%d",&r1,&c1,&num1);
for(int i=1;i<=num1;i++)
{
scanf("%d%d%d",&a[i].r,&a[i].c,&a[i].weight);
}
int r2,c2,num2;
scanf("%d%d%d",&r2,&c2,&num2);
if(r2!=r1||c2!=c1)
{
printf("Illegal!");
return 0;
}
for(int i=1;i<=num2;i++)
{
scanf("%d%d%d",&b[i].r,&b[i].c,&b[i].weight);
}
int n1=num1,n2=num2,n3=1;
int i1=1,i2=1;
while(n1!=0||n2!=0)//循环到一个数组加完为止
{
if(n1!=0&&n2!=0)
{
if(a[i1].r<b[i2].r)
{
c[n3].r=a[i1].r;
c[n3].c=a[i1].c;
c[n3++].weight=a[i1++].weight;
n1--;
}//a数组种数字充当元素
else if(a[i1].r>b[i2].r)
{
c[n3].r=b[i2].r;
c[n3].c=b[i2].c;
c[n3++].weight=b[i2++].weight;
n2--;
}//b数组中数字充当元素
else
{
if(a[i1].c<b[i2].c)
{
c[n3].r=a[i1].r;
c[n3].c=a[i1].c;
c[n3++].weight=a[i1++].weight;
n1--;
}
else if(a[i1].c>b[i2].c)
{
c[n3].r=b[i2].r;
c[n3].c=b[i2].c;
c[n3++].weight=b[i2++].weight;
n2--;
}
else
{
if(b[i2].weight+a[i1].weight!=0)
{
c[n3].r=a[i1].r;
c[n3].c=a[i1].c;
c[n3++].weight=b[i2].weight+a[i1].weight;
}
n2--;n1--;i1++;i2++;
}
}
}//a,b相加的元素充当元素，然后进行特判
else if(n1!=0&&n2==0)
{
while(n1!=0)
{
c[n3].r=a[i1].r;
c[n3].c=a[i1].c;
c[n3++].weight=a[i1++].weight;
n1--;
}
}
else
{
while(n2!=0)
{
c[n3].r=b[i2].r;
c[n3].c=b[i2].c;
c[n3++].weight=b[i2++].weight;
n2--;
}
}
}
printf("%d %d %d\n",r1,c1,n3-1);
for(int k=1;k<n3;k++)
{
printf("%d %d %d\n",c[k].r,c[k].c,c[k].weight);
}
return 0;
}
注意：本方法是在三元组排好序的情况下输出的
7-3 文字编辑
一篇文章由n个汉字构成，汉字从前到后依次编号为1，2，……，n。 有四种操作：
A i j表示把编号为i的汉字移动编号为j的汉字之前；
B i j表示把编号为i的汉字移动编号为j的汉字之后；
Q 0 i为询问编号为i的汉字之前的汉字的编号；
Q 1 i为询问编号为i的汉字之后的汉字的编号。
规定：1号汉字之前是n号汉字，n号汉字之后是1号汉字。
输入格式:
第1行，1个整数T，表示有T组测试数据， 1≤T≤9999.
随后的每一组测试数据中，第1行两个整数n和m，用空格分隔，分别代表汉字数和操作数，2≤n≤9999，1≤m≤9999；第2至m+1行，每行包含3个常量s、i和j，用空格分隔，s代表操作的类型，若s为A或B，则i和j表示汉字的编号，若s为Q，i代表0或1，j代表汉字的编号。
输出格式:
若干行，每行1个整数，对应每个询问的结果汉字编号。
输入样例:
在这里给出一组输入。例如：
1
9999 4
B 1 2
A 3 9999
Q 1 1
Q 0 3
输出样例: 在这里给出相应的输出。例如：
4
9998
作者 谷方明 单位 吉林大学 代码长度限制 16 KB 时间限制 1000 ms 内存限制 2 MB 思路：Donald E.Knuth的跳舞链，但是时间不够没调出来😫，这道题没啥大坑，对我来说比较友好，核心思想还是数据结构中的静态链表。
跳舞链：
left_[right_[num1]] = left_[num1];
right_[left_[num1]] = right_[num1];
用两个数组模拟静态链表：
int right_[10000];
int left_[10000];
交换算法(跳舞)
left_[right_[num1]] = left_[num1];
right_[left_[num1]] = right_[num1];
left_[num1] = num2;
right_[num1] = right_[num2];
left_[right_[num2]] = num1;
right_[num2] = num1;
代码如下：
#include<cstdio>
int right_[10000];
int left_[10000];
using namespace std;
int main()
{
int num;
scanf("%d",&num);
for (int i = 1; i <= num; i++)
{
int n, m;
scanf("%d%d",&n,&m);
for (int i = 1; i <= n; i++)
{
if (i != n)
right_[i] = i + 1;
else
right_[i] = 1;
if (i != 1)
left_[i] = i - 1;
else
left_[i] = n;
}
for (int j = 1; j <= m; j++)
{
char A;
int num1;
int num2;
scanf("%c",&A);
while(!(A>='A'&&A<='Z'))scanf("%c",&A);
scanf("%d%d",&num1,&num2);
if (A == 'Q'&&num1 == 1)
printf("%d\n",right_[num2]);
else if (A == 'Q'&&num1 == 0)
printf("%d\n",left_[num2]);
else if (A == 'B')
{
left_[right_[num1]] = left_[num1];
right_[left_[num1]] = right_[num1];
left_[num1] = num2;
right_[num1] = right_[num2];
left_[right_[num2]] = num1;
right_[num2] = num1;
}
else if (A == 'A')
{
left_[right_[num1]] = left_[num1];
right_[left_[num1]] = right_[num1];
right_[num1] = num2;
left_[num1] = left_[num2];
right_[left_[num2]] = num1;
left_[num2] = num1;
}
}
}
return 0;
}
7-4 幸福指数
人生中哪段时间最幸福?幸福指数可能会帮你发现。幸福指数要求：对自己每天的生活赋予一个幸福值，幸福值越大表示越幸福。一段时间的幸福指数就是：这段时间的幸福值的和乘以这段时间的幸福值的最小值。幸福指数最大的那段时间，可能就是人生中最幸福的时光。
输入格式:
第1行，1个整数n，， 1≤n≤100000,表示要考察的天数。
第2行，n个整数Hi，用空格分隔，Hi表示第i天的幸福值，0≤n≤1000000。
输出格式:
第1行，1个整数，表示最大幸福指数。
第2行，2个整数l和r，用空格分隔，表示最大幸福指数对应的区间[l,r]。如果有多个这样的区间，输出最长最左区间。
输入样例:
在这里给出一组输入。例如：
7
6 4 5 1 4 5 6
输出样例:
在这里给出相应的输出。例如：
60
1 3
作者 谷方明 单位 吉林大学 代码长度限制 16 KB 时间限制 100 ms 内存限制 64 MB 思路：上机的时候不会做，但是听了思路后，会敲了，但是为什么会有那么多的坑😭。
实现原理还是单调栈，但是这次不同，需要从左向右，从右向左寻找每个数的以自己为最小值邻域的区间，这是算法的关键。
错误：1.是要把数组范围看准，开的稍微大一点；2.要注意题中最长左序列，然后进行特判。3.最小值临界判断。4.int会爆掉，开long long
代码如下：
#include<cstdio>
using namespace std;
const int M=2100000000;
int left[100101];//左端极限位置
int right[100101];//右端极限位置
long long day[100101];//前缀序列和
int s_day[100101];//每一天的
int Stack[100101];//单调栈——一栈多用，注意清空
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&s_day[i]);
day[i]=day[i-1]+s_day[i];
}//维护前缀和
int ltop=0;
int rtop=n+1;
for(int i=1;i<=n;i++)
{
while(ltop!=0&&s_day[Stack[ltop]]>=s_day[i])
ltop--;
left[i]=Stack[ltop];
Stack[++ltop]=i;
}//单调栈从左往右
for(int i=1;i<=n;i++)
Stack[i]=0;
for(int i=n;i>=1;i--)
{
while(rtop!=(n+1)&&s_day[Stack[rtop]]>=s_day[i])
rtop++;
if(rtop!=(n+1))
right[i]=Stack[rtop];
else
right[i]=n+1;
Stack[--rtop]=i;
}//单调栈从右往左
long long MAX[3]={0};
for(int i=1;i<=n;i++)
{
if(MAX[0]<(long long)(day[right[i]-1]-day[left[i]])*s_day[i])
{
MAX[0]=(day[right[i]-1]-day[left[i]])*s_day[i];
MAX[1]=left[i]+1;
MAX[2]=right[i]-1;
}
else if(MAX[0]==(long long)(day[right[i]-1]-day[left[i]])*s_day[i])
{
if(right[i]-1-left[i]-1>MAX[2]-MAX[1])
{
MAX[0]=(day[right[i]-1]-day[left[i]])*s_day[i];
MAX[1]=left[i]+1;
MAX[2]=right[i]-1;
}
else if(left[i]+1<MAX[1])
{
MAX[0]=(day[right[i]-1]-day[left[i]])*s_day[i];
MAX[1]=left[i]+1;
MAX[2]=right[i]-1;
}
}
//特判，比较
}
printf("%lld\n%lld %lld\n",MAX[0],MAX[1],MAX[2]);
return 0;
}
太弱↭小了，没↑有力↓量