数据结构第二次实验

指导老师：Gu Fangming

7-1 数列查询 (100 分)

已知数列的通项公式为:

     f(n) = f(n-1)*11/10，f[1]=10. 

通项从左向右计算，*和/分别表示整数乘法和除法。 现在，要多次查询数列项的值。

输入格式:

第1行，1个整数q，表示查询的次数， 1≤q≤10000. 第2至q+1行，每行1个整数i，表示要查询f(i)的值。

输出格式:

q行，每行1个整数，表示f(i)的值。查询的值都在32位整数范围内。

输入样例:

在这里给出一组输入。例如：

3
1
2
3

输出样例:

在这里给出相应的输出。例如：

10
11
12

    我们知道指数是“爆炸的”，所以在整形内我们不需要算出很多项，直接打表查询便可。

// 5.12.2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

using namespace std;
int qw[50010][3];
int as[50010][3];
bool cmp(int a,int b){
    
    if (as[a][0] == as[b][0])
        return( as[a][1] < as[b][1]);
    else return (as[a][0] < as[b][0]);
}
int main()
{
    int qwer[2];
    int ti,me;
    int asd[2];
    
    cin >> qwer[0] >> qwer[1] >> ti;
    for (int i = 1; i <= ti; i++) {
        cin >> qw[i][0] >> qw[i][1] >> qw[i][2];
   }
    cin >> asd[0] >> asd[1] >> me;
    if (asd[0] != qwer[0] || asd[1] != qwer[1]) {
        cout << "Illegal!";
        return 0;
    }
    for (int i = 1; i <= me; i++) {
        cin >> as[i][0] >> as[i][1] >> as[i][2];
    }
    int now = me;
    for (int i = 1; i <= ti; i++) {
        int flag = 1;
        for (int j = 1; j <= me; j++) {
            if (qw[i][0] == as[j][0] && qw[i][1] == as[j][1]) {
                as[j][2] += qw[i][2];
                flag = 0;
                break;
            }
        }//
        if (flag) {
            now++;
            as[now][0] = qw[i][0];
            as[now][1] = qw[i][1];
            as[now][2] = qw[i][2];
        }
    }
    int now1 = now;
    for (int i = 1; i <= now; i++) {
        if (as[i][2] == 0) {
            now1--;
        }
    }

    cout << asd[0] << " " << asd[1] << " " << now1;
    int flag[50010];
    for (int i = 1; i <= now; i++) {
        flag[i]=i;
    }
    sort(flag+1, flag+now+1, cmp);
    for (int i = 1; i <= now; i++) {
        if (as[flag[i]][2] != 0) {
            cout << endl;
            cout << as[flag[i]][0] << " " << as[flag[i]][1] << " " << as[flag[i]][2];
        }
    }
}

 

 

7-2 稀疏矩阵之和 (100 分)

矩阵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

 储存两矩阵，再用合并排序的方式进行合并，维护双指针。

后两次遍历，先得项数，再得各项（优化方式，在输入第二个矩阵时直接计算出项数，可节省一次遍历）

// 5.12.2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include<stdio.h>
int qw[50010][3];
int as[50010][3];
int ww[100010];
int main()
{
    int qwer[2];
    int ti,me;
    int asd[2];
    scanf("%d%d%d", &qwer[0], &qwer[1], &ti);
    
    for (int i = 1; i <= ti; i++) {
       
        scanf("%d%d%d", &qw[i][0], &qw[i][1], &qw[i][2]);
   }

    scanf("%d%d%d", &asd[0] ,&asd[1] ,& me);
   
    for (int i = 1; i <= me; i++) {
      
        scanf("%d%d%d", &as[i][0], &as[i][1], &as[i][2]);
    }
    if (asd[0] != qwer[0] || asd[1] != qwer[1]) {
       printf("Illegal!");
        return 0;
    }
    //
    //  
    int i = 1, j = 1;
    int now1 = 0;
    while (j <= ti && me >= i) {
        int flag = 0;
        if (as[i][0] == qw[j][0] && as[i][1] == qw[j][1]) {
            if (as[i][2] + qw[j][2] != 0)
                now1++;

            i++; j++;
            continue;
        }
        else if (as[i][0] == qw[j][0]) {
            flag = as[i][1] < qw[j][1];
        }
        else
            flag = as[i][0] < qw[j][0];
        if (flag) {
            now1++;
            i++;
        }
        else {
            now1++;
            j++;
        }
    }
    if (i <= me) {
        for (int m = i; m <= me; m++) {
            now1++;
        }
    }
    if (j <= ti) {
        for (int m = j; m <= ti; m++) {
            now1++;
        }
    }
    //
    
    printf("%d %d %d", asd[0], asd[1], now1);
    i = 1; j = 1;

    while (j <= ti && me >= i) {
        int flag = 0;
        if (as[i][0] == qw[j][0] && as[i][1] == qw[j][1]) {
            if(as[i][2] + qw[j][2]!=0)
            
            printf("\n%d %d %d", as[i][0], as[i][1], as[i][2] + qw[j][2]);
            i++; j++;
            continue;
        }
        else if (as[i][0] == qw[j][0]) {
            flag = as[i][1] < qw[j][1];
        }
        else
            flag = as[i][0] < qw[j][0];
        if (flag) {
          
            printf("\n%d %d %d", as[i][0], as[i][1], as[i][2]);
            i++;
        }
        else {
          
            printf("\n%d %d %d", qw[j][0] , qw[j][1] , qw[j][2]);
            j++;
        }
    }
    if (i <=me) {
        for (int m = i; m <= me; m++) {
          
            printf("\n%d %d %d", as[m][0], as[m][1], as[m][2]);
        }
    }
    if (j <=ti) {
        for (int m = j; m <= ti; m++) {
          
            printf("\n%d %d %d", qw[m][0], qw[m][1], qw[m][2]);
        }
    }
}

篇文章由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个整数，对应每个询问的结果汉字编号。

跳舞链了这是 ，可用左右两数组维护汉字间的位置关系。

#include <cstdio>
#pragma warning(disable : 4996)
int zuo[10010], you[10010];
int main() {
	int jcy;
	scanf("%d", &jcy);
	while (jcy--) {
	    int n, q;
	scanf("%d%d", &n, &q); 
	for (int i = 1; i <= n; i++) { 
			zuo[i] = i - 1;
			you[i] = i + 1;
		}
	zuo[1] = n;
	you[n] = 1;
	while (q--) {
	char ope[2]; 
	scanf("%s", ope);	
		int i, j; 
		scanf("%d%d", &i, &j);
		if (ope[0] == 'A') { 
	you[zuo[i]] = you[i];
			zuo[you[i]] = zuo[i]; 
			you[i] = j;
			zuo[i] = zuo[j];
			you[zuo[i]] = i;
			zuo[you[i]] = i; 
			}
else if (ope[0] == 'B') { 
				you[zuo[i]] = you[i];
				zuo[you[i]] = zuo[i]; 
				zuo[i] = j;
				you[i] = you[j];
				you[zuo[i]] = i;
				zuo[you[i]] = i; 
			}
	else if(ope[0]=='Q'){ 
		if (i == 0) { 
					printf("%d\n", zuo[j]);
				}
		else { 
					printf("%d\n", you[j]);
				}
			}
		}
	}
	return 0;
}

 

 

人生中哪段时间最幸福?幸福指数可能会帮你发现。幸福指数要求：对自己每天的生活赋予一个幸福值，幸福值越大表示越幸福。一段时间的幸福指数就是：这段时间的幸福值的和乘以这段时间的幸福值的最小值。幸福指数最大的那段时间，可能就是人生中最幸福的时光。

输入格式:

第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

以最小值点为遍历基本（而不以区间），使用单调栈 可以更快得到所需区间来加速，（卡区间的是较小值，所以使用递减栈），再加上算好了和，又得到区间下标，问题就迎刃而解了。

 

#pragma warning(disable : 4996)
#include <stdio.h>
#include<stack>
using namespace std;
int p[100010];
long long int k[100010];
int left[100010], right[100010];
stack<int> qqq,ppp;
long long int jj=0;
int lef=1, ri=1;
int main() {
	int n;
	int j; int t;
	scanf("%d", &n);
	p[0] = -1;
	k[0] = 0;
	k[n + 1] = -1;
	p[n + 1] = -1;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &p[i]);
		k[i] = k[i - 1] + p[i];
	}
	qqq.push(0);
	ppp.push(n+1);
	for (int i = 1; i <= n; i++) {
		while (p[qqq.top()] > p[i]) 
			qqq.pop();
		left[i] = qqq.top()+1;
		qqq.push(i);
	}
	for (int i = n; i > 0; i--) {
		while (p[ppp.top()] > p[i])
			ppp.pop();
		right[i] = ppp.top()-1;
		ppp.push(i);
	}
	for (int i = 1; i <= n; i++) {
		long long tmp = (k[right[i]] - k[left[i]-1])*p[i];
		if (tmp > jj) {
			jj = tmp;
			lef = left[i];
			ri = right[i];
		}
		else if (tmp == jj) {
			if (right[i] - left[i] > ri - lef)
			{
				lef = left[i];
				ri = right[i];
			}
		}
	}
	printf("%lld\n", jj);
	printf("%d %d", lef, ri);
}