【JLU数据结构荣誉课】第二次上机实验

->点我进原题
-> 7-1 数列查询
-> 7-2 稀疏矩阵之和
-> 7-3 文字编辑
-> 7-4 幸福指数

7-1 数列查询 (100 分)


代码长度限制 \(16 KB\)
时间限制 \(10 ms\)
内存限制 \(1 MB\)


Description

已知数列的通项公式为:

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

通项从左向右计算,* 和 / 分别表示整数乘法和除法。

现在,要多次查询数列项的值。

Input

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

Output

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

Sample Input

3
1
2
3

Sample Output

10
11
12

思路

看这个时间和空间就是为了卡每查询一次递归一次的做法的,所以我们直接将 \(10^{5}\) 次的值求出存入 \(f\) 数组即可达到 \(O(n)\) 计算,\(O(1)\) 查询。

代码

#include<cstdio>
#include<cctype>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define rg register
#define ll long long
using namespace std;
inline int read(){
	rg int f = 0, x = 0;
	rg char ch = getchar();
	while(!isdigit(ch))	f |= (ch == '-'), ch = getchar();
	while( isdigit(ch))	x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f? -x: x;
}
int f[100001];
int main(){
	int n = read();
	f[1] = 10;
	for(rg int i = 2; i <= 100000; ++i){
		f[i] = f[i - 1] * 11 / 10;
	}
	for(rg int i = 1; i <= n; ++i){
		int q = read();
		printf("%d\n", f[q]);
	}
	return 0;
}




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


代码长度限制 \(16 KB\)
时间限制 \(100 ms\)
内存限制 \(10 MB\)


Description

矩阵 \(A\) 和 \(B\) 都是稀疏矩阵。请计算矩阵的和 \(A+B\).如果 \(A\)、\(B\) 不能做和,输出“Illegal!”

Input

矩阵的输入采用三元组表示,先 \(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位有符号整型范围内。三元组默认按行列排序。

Output

矩阵 \(A+B\),采用三元组表示,默认按行列排序,非零项也在32位有符号整型范围内。

Sample Input

10 10 3
2 2 2
5 5 5
10 10 20
10 10 2
2 2 1
6 6 6

Sample Output

10 10 4
2 2 3
5 5 5
6 6 6
10 10 20

思路

纯模拟题。直接开大矩阵数组空间是不够的,所以要用三元组去存矩阵。要注意当两矩阵的长宽一样时才可以相加,其余都不合法;同时答案要用行列递增排序输出,所以要排一下序;最容易漏掉的一点是只输出非0结果的位置,所以例如 \(a [2] [2] = 1\)、\(b [2] [2] = -1\) 这种,相加后 \(c [2] [2] = 0\) 是不允许输出的。

代码

#include<cstdio>
#include<cctype>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#define rg register
#define ll long long
using namespace std;
inline int read(){
	rg int f = 0, x = 0;
	rg char ch = getchar();
	while(!isdigit(ch))	f |= (ch == '-'), ch = getchar();
	while( isdigit(ch))	x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f? -x: x;
}
struct node{
	int x, y;
	int data;
}f[100001], g[100001], h[100001], ans[100001];
map<ll, int> mp, book;
inline bool cmp(node a, node b){
	if(a.x == b.x)	return a.y < b.y;
	return a.x < b.x;
}
int main(){
	int t1 = 0, t2 = 0;
	int tot = 0;
	int n = read(), m = read(), t = read();
	for(rg int i = 1; i <= t; ++i){
		f[++t1].x = read();
		f[t1].y = read();
		f[t1].data = read();
		mp[f[t1].x * 100000 + f[t1].y] += f[t1].data;
	}
	int r = read(), c = read(), v = read();
	if(n != r || m != c){
		printf("Illegal!\n");
		return 0;
	}
	for(rg int i = 1; i <= v; ++i){
		g[ ++t2].x = read();
		g[t2].y = read();
		g[t2].data = read();
		mp[g[t2].x * 100000 + g[t2].y] += g[t2].data;
	}
	for(rg int i = 1; i <= t; ++i){
		if(mp[f[i].x * 100000 + f[i].y] == 0)	continue;
		ans[++tot].x = f[i].x;
		ans[tot].y = f[i].y;
		ans[tot].data = mp[f[i].x * 100000 + f[i].y];
		book[f[i].x * 100000 + f[i].y] = 1;
	}
	for(rg int i = 1; i <= v; ++i){
		if(book[g[i].x * 100000 + g[i].y])	continue;
		if(mp[g[i].x * 100000 + g[i].y] == 0)	continue;
		ans[++tot].x = g[i].x;
		ans[tot].y = g[i].y;
		ans[tot].data = mp[g[i].x * 100000 + g[i].y];
	}
	printf("%d %d %d\n", n, m, tot);
	sort(ans + 1, ans + tot + 1, cmp);
	for(rg int i = 1; i <= tot; ++i){
		printf("%d %d %d\n", ans[i].x, ans[i].y, ans[i].data);
	}
	return 0;
}




7-3 文字编辑 (100 分)


代码长度限制 \(16 KB\)
时间限制 \(1000 ms\)
内存限制 \(2 MB\)


Description

一篇文章由 \(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\) 号汉字。

Input

第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\) 代表汉字的编号。

Output

若干行,每行1个整数,对应每个询问的结果汉字编号。

Sample Input

1
9999 4
B 1 2
A 3 9999
Q 1 1
Q 0 3

Sample Output

4
9998

思路

纯模拟题。类似约瑟夫问题,这次我们用链表来处理。记录一个 \(last\) 数组和一个 \(next\) 数组,先初始化为对应位置,再根据题目所述每一步修改、查询即可。

代码

#include<cstdio>
#include<cctype>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define rg register
#define ll long long
using namespace std;
inline int read(){
	rg int f = 0, x = 0;
	rg char ch = getchar();
	while(!isdigit(ch))	f |= (ch == '-'), ch = getchar();
	while( isdigit(ch))	x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f? -x: x;
}
int main(){
	int t = read();
	while(t--){
		int n = read(), m = read();
		int next[100001], last[100001];
		for(rg int i = 1; i <= n; ++i)	next[i] = i + 1, last[i] = i - 1;
		next[n] = 1;
		last[1] = n;
		for(rg int i = 1; i <= m; ++i){
//			for(rg int i = 1; i <= n; ++i){
//				cout << last[i] << ' ' << next[i] << endl;
//			} 
			char ch[1];
			scanf("%s", ch);
//			cout << ch;
			int a = read(), b = read();
			if(ch[0] == 'A'){
				if(last[b] == a)	continue;
				next[last[a]] = next[a];
				last[next[a]] = last[a];
				last[a] = last[b];
				last[b] = a;
				next[last[a]] = a;
				next[a] = b;
			}
			if(ch[0] == 'B'){
				if(next[b] == a)	continue;
				next[last[a]] = next[a];
				last[next[a]] = last[a];
				next[a] = next[b];
				next[b] = a;
				last[next[a]] = a;
				last[a] = b;
			}
			if(ch[0] == 'Q'){
				if(a)	printf("%d\n", next[b]);
				if(!a)	printf("%d\n", last[b]);
			}
		}
	}
	return 0;
}
/*
1 
10 3
A 3 10
Q 1 1
Q 0 3
*/




7-4 幸福指数 (100 分)


代码长度限制 \(16 KB\)
时间限制 \(100 ms\)
内存限制 \(64 MB\)


Description

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

Input

第1行,1个整数 \(n\),\(1≤n≤100000\) ,表示要考察的天数。

第2行,\(n\) 个整数 \(Hi\),用空格分隔,\(Hi\) 表示第 \(i\) 天的幸福值,\(0≤Hi≤1000000\)。

Output

第1行,1个整数,表示最大幸福指数。

第2行,2个整数 \(l\) 和 \(r\),用空格分隔,表示最大幸福指数对应的区间 \([l,r]\) 。如果有多个这样的区间,输出最长最左区间。

Sample Input

7
6 4 5 1 4 5 6

Sample Output

60
1 3

思路

题目说所求最大幸福指数是一段区间的和乘以这段区间的最小值,而题目数据是 \(10^{6}\), 所以不能 \(O(n^{2})\) 的枚举端点,故使用单调栈。以每个点的值为最小值,向左向右找出以他为最小值的最长区间,正向维护一个递增的单调栈,查询当前第 \(i\) 个点左边第一个比它小的值存入 \(li\) ,再逆向维护一个递增的单调栈,查询当前第 \(i\) 个点右边第一个比它小的值存入 \(ri\),\(l+1\) 到 \(r-1\) 即为以每个点为最小值的最长区间,再进行 \(O(n)\) 扫描对最大值和区间特判进行更新即可。

代码

#include<cstdio>
#include<cctype>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#define rg register
#define ll long long
using namespace std;
inline int read(){
	rg int f = 0, x = 0;
	rg char ch = getchar();
	while(!isdigit(ch))	f |= (ch == '-'), ch = getchar();
	while( isdigit(ch))	x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f? -x: x;
}
const int inf = 0x7fffffff;
int n;
ll sum[100001];
int l[100001], r[100001];
int stk[100001], top = 0;
int ml = 0, mr = 0;
ll maxn = -1;
inline int a(int n){
	return sum[n] - sum[n - 1];
}
signed main(){
	n = read(); 
	sum[0] = 0;
	for(rg int i = 1; i <= n; ++i){
		sum[i] = sum[i - 1] + read();
	}
	top = 0;
	stk[0] = 0;
	for(rg int i = 1; i <= n; ++i){
		while(top && a(stk[top]) >= a(i))	top --;
		l[i] = stk[top];
		stk[++ top] = i;
	}
	top = 0;
	stk[0] = n + 1;
	for(rg int i = n; i >= 1; --i){
		while(top && a(stk[top]) >= a(i))	top --;
		r[i] = stk[top];
		stk[++ top] = i;
	}
	for(rg int i = 1; i <= n; ++i){
		ll tmp = (sum[r[i] - 1] - sum[l[i]]) * a(i);
		if(maxn < tmp){
			maxn = tmp;
			ml = l[i] + 1;
			mr = r[i] - 1;
		} else if(maxn == tmp){
			if(mr - ml + 1 < ((r[i] - 1) - (l[i] + 1) + 1)){
				ml = l[i] + 1;
				mr = r[i] - 1;
			} else if(mr - ml + 1 == ((r[i] - 1) - (l[i] + 1) + 1)){
				if(ml > l[i] + 1){
					ml = l[i] + 1;
					mr = r[i] - 1;
				}
			}
		}
	}
	printf("%lld\n%d %d", maxn, ml, mr);
	return 0;
}

上一篇:CRC32算法C#中的实现


下一篇:目标跟踪文章综述