2021-05-24

 数据结构第二次实验

指导老师: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);
}

 

上一篇:【DeepCV】学习率设定和优化器选取LR&Optimizer


下一篇:A*(A star)搜索总结