->点我进原题
-> 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;
}