pta
7-1-1 查询子序列和
对N个整数的序列，查询子序列和
${\textstyle \sum_{k = i}^{j}A_{k}(1≤i,j≤N)}$
输入格式:
第1行，两个整数：N和Q，表示整数的个数和查询的次数，1≤N≤100000，0≤Q≤100000.
第2行，N个用空格分开的整数 x ， │x│≤20000.
第3至Q+2行，每行两个整数i和j，表示所求子序列和的区间[i，j]，1≤i≤j≤N，保证所有区间都合法。
输出格式:
Q行,每行一个整数，表示相应子序列的和
输入样例:
5 3
1 2 3 4 5
1 5
2 4
3 5
输出样例:
在这里给出相应的输出。例如：
15
9
12
#include<iostream>
using namespace std;
const int N = 100000;
int n, q;
int sum[N+10];
int main() {
int l, r,tmp;
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >>tmp;
if (i > 1) {
sum[i] = sum[i - 1] + tmp;
}
else {
sum[i] = tmp;
}
}
for (int i = 1; i <= q; i++) {
cin >> l >> r;
cout << sum[r] - sum[l - 1]<<endl;
}
return 0;
}
7-1-2 数列查询
分数 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
#include<stdio.h>
int a[10000];
int main(){
int q;
int j,i;
scanf("%d",&q);
int n;
int m=0;
a[0]=10;
for(j=0;j<q;j++){
scanf("%d",&n);
if(n>m)
{
for(i=1;i<=n-1;i++)
{
a[i]=a[i-1]*11/10;
}
printf("%d\n",a[n-1]);
m=n;
}
else
printf("%d\n",a[n-1]);
}
return 0;
}
7-1-3 估算运行空间
分数 100
作者 谷方明
单位 吉林大学
一个代码的存储部分如下：
int n,m;
int vertex[MAXN];
int g[MAXN][MAXN];
假设：在32为操作系统（OS）下运行，只考虑如上代码段，不考虑程序自身存储空间等，给定MAXN，计算该算法的运行空间，其中空间的单位为Mb，1Mb = 10^6字节（Byte）。
输入格式:
一行，包含1个正整数，表示算法输入的最大取值MAXN，n <=10^6.
输出格式:
一个整数，表示该算法的运行空间估算值，该值向上取整。
输入样例:
在这里给出一组输入。例如：
10000
输出样例:
在这里给出相应的输出。例如：
401
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string.h>
using namespace std;
int main() {
int max,sum=0;
scanf("%d", &max);
sum = ceil( (1.0*max*max+max+2)*4/1000000 );
printf("%d",sum);
return 0;
}
7-1-4 估算运行时间
分数 100
作者 谷方明
单位 吉林大学
一个算法的基本运算：交换两个整数的值，时间复杂度为 T = n(n-1)/2。其中，交换使用3个赋值运算实现。
假设：交换运算时间超过整个算法的1/3，在单核通用计算机上运行，给定n的最大取值，估算该算法的最大运行时间，时间向上取整为秒。
输入格式:
行，包含1个正整数n，表示算法输入的最大取值，n <=10^8。
输出格式:
个整数，表示该算法的最大运行时间的估计.
输入样例:
在这里给出一组输入。例如：
10000
输出样例:
在这里给出相应的输出。例如：
5
#include <iostream>
#include <cmath>
int main() {
long long n;
std::cin >> n; // 输入算法的最大取值
long long time = (long long)ceil((1.0*(n*n-n) / 2) *9 *0.00000001); // 计算最大运行时间的估计
std::cout << (time) << std::endl; // 向上取整，并输出结果
return 0;
}
7-1-5 冰雹猜想
分数 100
作者 谷方明
单位 吉林大学
70年代中期，美国各所名牌大学校园内，人们都像发疯一般，夜以继日，废寝忘食地玩弄一种数学游戏。这个游戏十分简单：任意写出一个正整数N，并且按照以下的规律进行变换：
如果是个奇数，则下一步变成3N+1。
如果是个偶数，则下一步变成N/2。
不单单是学生，甚至连教师、研究员、教授与学究都纷纷加入 。为什么这种游戏的魅力经久不衰？因为人们发现，无论N是怎样一个数字，最终都无法逃脱回到谷底1。准确地说，是无法逃出落入底部的4-2-1循环，永远也逃不出这样的宿命。
这就是著名的“冰雹猜想”。
给出一个正整数N，计算全部变换过程（称作“雹程”）的步数。
输入格式:
一行，1个正整数N，N <=10^6.输出保证合法。
输出格式:
一个整数，为所求步数。
输入样例:
在这里给出一组输入。例如：
27
输出样例:
在这里给出相应的输出。例如：
111
#include<iostream>
#include<cmath>
using namespace std;
int main() {
int n;
cin >> n;
int step = 0;
while (n != 1) {
if (n % 2 == 0) {
n = n / 2;
}
else {
n = 3 * n + 1;
}
step++;
}
cout << step;
return 0;
}
7-1-6 素数
分数 100
作者 谷方明
单位 吉林大学
判断正整数 N 是否为素数。
规定：自然数1既不是素数也不是合数。
输入格式:
一行，包含1个正整数N，N <= 2^31 - 1.输入保证合法。
输出格式:
一行。如果N为素数，输出Yes，否则输出No.
输入样例:
在这里给出一组输入。例如：
2
输出样例:
在这里给出相应的输出。例如：
Yes
#include<iostream>
#include<cmath>
using namespace std;
int main() {
int n;
cin >> n;
if (n == 1) {
cout << "No" << endl;
return 0;
}
if (n == 2) {
cout << "Yes" << endl;
return 0;
}
for (int i = 2; i <= int(ceil(sqrt(n))); i++) {
if (n % i == 0) {
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
return 0;
}
7-2-1 算术表达式计算
分数 100
作者 谷方明
单位 吉林大学
任务: 计算算术表达式的值。
算术表达式按中缀给出，以=号结束，包括+,-,,/四种运算和(、)分隔符。运算数的范围是非负整数，没有正负符号，小于等于109 。
计算过程中,如果出现除数为0的情况,表达式的结果为”NaN” ; 如果中间结果超出32位有符号整型范围,仍按整型计算，不必特殊处理。
输入保证表达式正确。
输入格式:
一行，包括1个算术表达式。算术表达式的长度小于等于1000。
输出格式:
一行，算术表达式的值 。
输入样例:
在这里给出一组输入。例如：
(1+30)/3=
输出样例:
在这里给出相应的输出。例如：
10
#include<iostream>
#include<map>
#include<stack>
using namespace std;
const int N = 1000;
map<char, int>mp;
stack<int>num;
stack<char>ysf;
char s[N + 10];
//除零return0；
bool ys(int a, int b, int& c, char fh) {
switch (fh)
{
case '+':
c = a + b;
break;
case '-':
c = a - b;
break;
case '*':
c = a * b;
break;
case '/':
if (b == 0) {
return 0;
}
else {
c = a / b;
}
break;
default:
break;
}
return 1;
}
int main() {
mp['*'] = 1;
mp['/'] = 1;
mp['+'] = 0;
mp['-'] = 0;
mp['('] = -1;
scanf("%s", s);
//printf("%s", s);//scanf不会读回车
int i = 0;
while (s[i] != '=') {
switch (s[i])
{
case '(':
ysf.push('(');
break;
case ')':
if (ysf.empty()) {
break;
}
while (ysf.top() != '(') {
int a2 = num.top();
num.pop();
int a1 = num.top();
num.pop();
int res = 0;
if (ys(a1, a2, res, ysf.top()) == 0) {
cout << "NAN";
return 0;
}
num.push(res);
if (ysf.empty()) {
break;
}
ysf.pop();
}
if (ysf.top() == '(') {
//cout << "correct" << endl;
ysf.pop();
}
break;
case '+':
if (ysf.empty()) {
ysf.push('+');
break;
}
while (mp[ysf.top()] >= mp['+']) {
int a2 = num.top();
num.pop();
int a1 = num.top();
num.pop();
int res = 0;
if (ys(a1, a2, res, ysf.top()) == 0) {
cout << "NAN";
return 0;
}
num.push(res);
if (ysf.empty()) {
break;
}
ysf.pop();
}
ysf.push('+');
break;
case '-':
if (ysf.empty()) {
ysf.push('-');
break;
}
while (mp[ysf.top()] >= mp['-']) {
int a2 = num.top();
num.pop();
int a1 = num.top();
num.pop();
int res = 0;
if (ys(a1, a2, res, ysf.top()) == 0) {
cout << "NAN";
return 0;
}
num.push(res);
if (ysf.empty()) {
break;
}
ysf.pop();
}
ysf.push('-');
break;
case '*':
if (ysf.empty()) {
ysf.push('*');
break;
}
while (mp[ysf.top()] >= mp['*']) {
int a2 = num.top();
num.pop();
int a1 = num.top();
num.pop();
int res = 0;
if (ys(a1, a2, res, ysf.top()) == 0) {
cout << "NAN";
return 0;
}
num.push(res);
if (ysf.empty()) {
break;
}
ysf.pop();
}
ysf.push('*');
break;
case '/':
if (ysf.empty()) {
ysf.push('/');
break;
}
while (mp[ysf.top()] >= mp['/']) {
int a2 = num.top();
num.pop();
int a1 = num.top();
num.pop();
int res = 0;
if (ys(a1, a2, res, ysf.top()) == 0) {
cout << "NAN";
return 0;
}
num.push(res);
if (ysf.empty()) {
break;
}
ysf.pop();
}
ysf.push('/');
break;
default:
int dig = 0;
while (s[i] >= '0' and s[i] <= '9') {
dig = dig * 10 + s[i] - '0';
i++;
}
num.push(dig);
i--;
break;
}
i++;
}
while(!ysf.empty()) {
int a2 = num.top();
num.pop();
int a1 = num.top();
num.pop();
int res = 0;
if (ys(a1, a2, res, ysf.top()) == 0) {
cout << "NAN";
return 0;
}
num.push(res);
if (ysf.empty()) {
break;
}
ysf.pop();
}
cout << num.top();
return 0;
}
7-2-2 括号配对II
分数 100
作者 谷方明
单位 吉林大学
高级语言程序设计中的各种括号应该匹配，例如：“(” 与 “)”匹配、“[”与 “]” 匹配、“{”与 “}” 匹配等。
输入一字符文件，判断其中的括号是否匹配。假设括号没有优先级差别。
输入格式:
多行，字符个数不超过 65536。
输出格式:
一个单词，表示字符文件中括号匹配的结果，匹配输出“yes”，否则输出“no”.
输入样例:
在这里给出一组输入。例如：
( { } )
输出样例:
在这里给出相应的输出。例如：
yes
#include<iostream>
#include<cstdio>
#include<stack>
#include<string>
#include<queue>
using namespace std;
int main() {
stack<char>s;
s.push('#');
string input, res;
while (getline(cin, input)) {
res += input;
}
for (int i = 0; i < res.length(); i++)
{
switch (res[i])
{
case '(':
s.push('(');
break;
case ')':
if (s.top() != '(') {
cout << "no";
return 0;
}
else {
s.pop();
}
break;
case '{':
s.push('{');
break;
case '}':
if (s.top() != '{') {
cout << "no";
return 0;
}
else {
s.pop();
}
break;
case '[':
s.push('[');
break;
case ']':
if (s.top() != '[') {
cout << "no";
return 0;
}
else {
s.pop();
}
break;
default:
break;
}
}
if (s.top() == '#') {
cout << "yes";
}else{
cout << "no";
}
return 0;
}
7-2-3 Blah数集
分数 100
作者 谷方明
单位 吉林大学
大数学家高斯小时候偶然发现一种有趣的自然数集合Blah。以a为基的集合Ba定义如下：
a是集合Ba的基，且a是Ba的第一个元素；
若x在集合Ba中，则2x+1和3x+1也都在Ba中；
没有其它元素在集合Ba中。
现在小高斯想知道如果将集合Ba中元素按照升序排列，第n个元素会是多少？
输入格式:
多行，每行包括两个数，集合的基a(1<=a<=50)以及所求元素序号n(1<=n<=1000000)
输出格式:
对于每个输入，输出集合Ba的第n个元素值
输入样例:
在这里给出一组输入。例如：
1 5
25 100000
输出样例:
在这里给出相应的输出。例如：
9
34503679
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
using namespace std;
int main() {
int n, q;
while (cin >> n >> q) {
queue<int>q1;
queue<int>q2;
queue<int>res;
res.push(n);
int cnt = q-1;
while (cnt--) {
q1.push(2 * res.front() + 1);
q2.push(3 * res.front() + 1);
res.push(min(q1.front(), q2.front()));
if (q1.front() < q2.front()) {
q1.pop();
}
else if (q1.front() > q2.front()) {
q2.pop();
}
else {
q1.pop();
q2.pop();
}
res.pop();
}
cout << res.front() << endl;
}
return 0;
}
7-2-4 左侧最近小数
分数 100
作者 谷方明
单位 吉林大学
对N个非负整数的序列，查询元素Ai
左侧最近的小于Ai的整数(1≤i≤N)，如果不存在，输出 -1
输入格式:
第1行，1个整数N，表示整数的个数，(1≤N≤100000)。
第2行，N个整数，每个整数x 都满足 0 ≤ x ≤2000000000。
输出格式:
1行,N个整数，表示每个元素Ai左侧最近的小于Ai的整数(1≤i≤N)。
输入样例:
6
1 2 5 3 4 6
输出样例:
-1 1 2 2 3 4
using namespace std;
int main() {
int n, a[100010];
stack<int> s;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
if (s.empty() == 1 && i < n - 1)cout << -1 << " ";
else if (s.empty() == 1)cout << -1;
else if (i < n - 1) { cout << s.top() << " "; }
else { cout << s.top(); }
s.push(a[i]);
while (s.empty() == 0 && s.top() >= a[i + 1]) {
s.pop();
}
}
return 0;
}
7-2-5 区间最小值I
分数 100
作者 谷方明
单位 吉林大学
对N个整数的序列，从左到右连续查询 M 长度子序列 Ai,Ai+1
,...,Ai−M+1(1≤i，M≤N)的最小值。
输入格式:
第1行，两个整数：N和M，表示整数的个数和区间长度，1≤N≤100000.
第2行，N个整数，每个整数x 都满足 │x│≤2000000000。
输出格式:
1行, 用空格分隔的N-M+1个整数，对应从左到右所有连续M长度子序列的最小值。
输入样例:
6 3
1 2 5 3 4 6
输出样例:
1 2 3 3
#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
const int N = 100000;
int a[N + 10];
int que[N + 10];
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int f, r;
//注意：不要先将前m个数排序，不让中间会出问题
//例如 521346 -> 125346的答案就会出问题
f = 0;//r为队尾后的空元素下标
r = 0;
for (int i = 0; i < n; i++) {
while (f < r && que[f] < i - m + 1) {
f++;
}
while (f<r && a[que[r - 1]]>a[i])
{
r--;
}
que[r++] = i;
//注意！！！！！
//i<m-1时前m个的最小值还没确定
if (i < m-1) {
continue;
}
if (i < n - 1) {
cout << a[que[f]] << ' ';
}
else {
cout << a[que[f]];
}
}
return 0;
}
7-3-1 线性表I
分数 100
作者 谷方明
单位 吉林大学
小唐正在学习线性表，他不会写线性表的基本操作。请身为大牛的你帮帮他吧。要对线性表做如下m个操作。
(1) 在第k个位置插入数据x : I k x
(2) 删除第k个位置的数据 ： E k
(3) 修改第k个位置的数据为x：U k x
(4) 查询第k个位置的数据 ： Q k
输入格式:
第1行，一个整数m，表示操作的个数，1≤m≤10000.
第2至m+1行，每行1个操作。操作的规定如题目描述。1≤k≤m，|x|≤100000000.若查询操作不合法，则返回-1；若其它操作不合法，则放弃该操作。
输入确保数据符合规定。
输出格式:
若干行,每行一个整数，依次表示查询操作的结果。
输入样例:
8
I 1 1
I 2 2
Q 2
U 1 100
E 2
Q 2
I 4 4
Q 2
输出样例:
2
-1
-1
#include<vector>
#include<iostream>
#include<deque>
using namespace std;
const int N = 10000;
int s[N+10];
int main() {
int m;
cin >> m;
int cnt = 0;
while (m--) {
char t;
cin >> t;
switch (t)
{
int k, x;
case 'I':
//(1) 在第k个位置插入数据x : I k x
cin >> k >> x;
if (k <= 0 || k-1 > cnt) {
break;
}
for (int i = cnt; i >= k; i--) {
s[i] = s[i - 1];
}
s[k - 1] = x;
cnt++;
break;
case 'E':
//(2) 删除第k个位置的数据 ： E k
cin >> k;
if (k <= 0 || k > cnt) {
break;
}
for (int i = k - 1; i < cnt-1; i++) {
s[i] = s[i + 1];
}
cnt--;
break;
case 'U':
//(3) 修改第k个位置的数据为x：U k x
cin >> k >> x;
if (k <= 0 || k > cnt) {
break;
}
s[k-1] = x;
break;
case 'Q':
//(4) 查询第k个位置的数据 ： Q k
cin >> k;
if (k <= 0 || k > cnt) {
cout << -1<<endl;
break;
}
cout << s[k-1]<<endl;
break;
default:
break;
}
}
return 0;
}
7-3-2 报数游戏
分数 100
作者 谷方明
单位 吉林大学
n个人围成一圈，从1开始依次编号，做报数游戏。 现指定从第1个人开始报数，报数到第m个人时，该人出圈，然后从其下一个人重新开始报数，仍是报数到第m个人出圈，如此重复下去，直到所有人都出圈。总人数不足m时将循环报数。请输出所有人出圈的顺序。
输入格式:
一行，两个整数n和m。n表示游戏的人数，m表示报数出圈的数字，1≤n≤50000，1≤m≤100.
输出格式:
一行，n个用空格分隔的整数，表示所有人出圈的顺序
输入样例:
在这里给出一组输入。例如：
5 2
输出样例:
在这里给出相应的输出。例如：
2 4 1 5 3
#include<vector>
#include<iostream>
#include<deque>
using namespace std;
/*
*/
int main() {
int n,m;
cin >>n>> m;
deque<int>res;
for (int i = 0; i < n; i++) {
res.push_back(i + 1);
}
int t = 1;
while (!res.empty()) {
if (t == m) {
if (res.size() == 1) {
cout << res.front();
}
else {
cout << res.front() << ' ';
}
res.pop_front();
t = 1;
}
else {
int tm = res.front();
res.pop_front();
res.push_back(tm);
t++;
}
}
return 0;
}
7-3-3 文字编辑
分数 100
作者 谷方明
单位 吉林大学
一篇文章由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
#include<vector>
#include<iostream>
#include<deque>
using namespace std;
//输入格式:
//第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
const int N = 9999;
int f[N + 10];
int b[N + 10];
int main() {
int t, n, m, i, j;
char s;
cin >> t;
while (t--) {
cin >> n >> m;
for( int i = 1;i <= n; i++ ){
f[i] = i - 1;
b[i] = i + 1;
}
b[n] = 1;
f[1]= n ;
while (m--) {
cin >> s >> i >> j;
/*
A i j表示把编号为i的汉字移动编号为j的汉字之前；
B i j表示把编号为i的汉字移动编号为j的汉字之后；
Q 0 i为询问编号为i的汉字之前的汉字的编号；
Q 1 i为询问编号为i的汉字之后的汉字的编号。
规定：1号汉字之前是n号汉字，n号汉字之后是1号汉字。
*/
switch (s)
{
case 'A':
if (i == f[j]) {
break;
}
f[b[i]] = f[i];
b[f[i]] = b[i];
b[f[j]] = i;
f[i] = f[j];
f[j] = i;
b[i] = j;
break;
case 'B':
if (i == b[j]) {
break;
}
f[b[i]] = f[i];
b[f[i]] = b[i];
f[b[j]] = i;
b[i] = b[j];
f[i] = j;
b[j] = i;
break;
case 'Q':
if (i == 0) {
cout << f[j] << endl;
}
if (i == 1) {
cout << b[j] << endl;
}
break;
default:
break;
}
}
}
return 0;
}
7-3-4 线性表II
分数 100
作者 谷方明
单位 吉林大学
小唐正在学习线性表，他又遇到了线性表的操作问题。请身为大牛的你再帮帮他吧。具体来说，要对线性表做如下操作。
（1） 在表头插入数据x : I 1 x
（2） 在表尾插入数据x : I 2 x
（3） 在当前位置后插入x ： I 3 x
（4） 查询数据x是否存在： Q x
（5） 删除表头结点: E 1
（6） 删除表尾结点： E 2
（7） 删除当前位置的结点： E 3
当前位置：初始化为0或特殊值；插入操作后为插入的结点；查询操作，存在则为找到的第一个结点，不存在则不改变；如果当前结点被删除，当前位置回归初始值。
输入格式:
第1行，一个整数m，表示操作的个数，1≤m≤100000.
第2至m+1行，每行1个操作。操作的规定如题目描述。|x|≤100000000.若操作不合法，则放弃该操作。
输入确保数据符合规定。
输出格式:
若干行,每行一个整数，依次表示查询操作的结果。如果存在，输出1，否则输出0。
查询操作不超过20个
输入样例:
在这里给出一组输入。例如：
9
I 1 1
I 2 2
I 3 3
Q 3
E 3
E 3
E 1
E 2
Q 10
输出样例:
在这里给出相应的输出。例如：
1
0
7-4-1 高精度数加法
分数 100
作者 谷方明
单位 吉林大学
高精度数是指大大超出了标准数据类型能表示的范围的数，例如10000位整数。很多计算问题的结果都很大，因此，高精度数极其重要。
一般使用一个数组来存储高精度数的所有数位，数组中的每个元素存储该高精度数的1位数字或多位数字。
请尝试计算：N个高精度数的加和。这个任务对于在学习数据结构的你来说应该是小菜一碟。
。
输入格式:
第1行，1个整数N，表示高精度整数的个数，(1≤N≤10000)。
第2至N+1行，每行1个高精度整数x, x最多100位。
输出格式:
1行,1个高精度整数，表示输入的N个高精度数的加和。
输入样例:
在这里给出一组输入。例如：
3
12345678910
12345678910
12345678910
输出样例:
在这里给出相应的输出。例如：
37037036730
7-4-2 二叉树最长路径
分数 100
作者 谷方明
单位 吉林大学
给定一棵二叉树T，求T中的最长路径的长度，并输出此路径上各结点的值。若有多条最长路径，输出最右侧的那条。
输入格式:
第1行，1个整数n，表示二叉树有n个结点， 1≤n≤100000.
第2行，2n+1个整数，用空格分隔，表示T的扩展先根序列， -1表示空指针，结点用编号1到n表示。
输出格式:
第1行，1个整数length，length表示T中的最长路径的长度。
第2行，length+1个整数，用空格分隔，表示最右侧的最长路径。
输入样例:
在这里给出一组输入。例如：
5
1 2 -1 -1 3 4 -1 -1 5 -1 -1
输出样例:
在这里给出相应的输出。例如：
2
1 3 5
#include<iostream>
#include<string.h>
using namespace std;
struct tree {
int data;
tree* le;
tree* r;
};
tree* createNode(int data) {
tree* newNode = new tree();
newNode->data = data;
newNode->le = nullptr;
newNode->r = nullptr;
return newNode;
}
tree* createTree() {
int data;
cin >> data;
if (data == -1) {
return nullptr;
}
tree* newNode = createNode(data);
//cout << "Enter left child of " << data << ": ";
newNode->le = createTree();
//cout << "Enter right child of " << data << ": ";
newNode->r = createTree();
return newNode;
}
int getDepth(tree* root) {
if (root == nullptr) {
return 0;
}
int leftDepth = getDepth(root->le);
int rightDepth = getDepth(root->r);
return max(leftDepth, rightDepth) + 1;
}
void findMaxDepthPath(tree* root, int depth, int maxDepth, int* path) {
if (root == nullptr || depth > maxDepth) {
return;
}
path[depth] = root->data;
if (depth == maxDepth) {
for (int i = 0; i < maxDepth; i++) {
cout << path[i] << " ";
}
cout << path[maxDepth];
cout << endl;
exit(0);
return;
}
findMaxDepthPath(root->r, depth + 1, maxDepth, path);
findMaxDepthPath(root->le, depth + 1, maxDepth, path);
}
int main() {
int n;
//cout << "Enter the number of nodes: ";
cin >> n;
if (n <= 0) {
//cout << "Invalid number of nodes." << endl;
return 0;
}
// cout << "Enter the values for each node (-1 for no child): " << endl;
tree* root = createTree();
int maxDepth = getDepth(root) - 1;
int* path = new int[maxDepth + 1];
//cout << "Paths of maximum depth " << maxDepth << ": " << endl;
cout << maxDepth<<endl;
findMaxDepthPath(root, 0, maxDepth, path);
delete[] path;
return 0;
}
7-4-3 稀疏矩阵之和
分数 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
//矩阵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
#include<iostream>
using namespace std;
struct ThreeNode
{
int row, column;
int data;
};
typedef struct {
int MaxRow, MaxColumn;
int MaxNum;
ThreeNode Data[50005];
}Matrix;
Matrix A, B,res;
void MatrixPlus() {
int a = 0;
int b = 0;
int c = 0;
res.MaxColumn = A.MaxColumn; res.MaxRow = A.MaxRow;
while (a<A.MaxNum&&b<B.MaxNum)
{
if (A.Data[a].row < B.Data[b].row) {
if (res.Data[c].data += A.Data[a].data) {
res.Data[c].column = A.Data[a].column;
res.Data[c].row = A.Data[a].row;
c++;
}
a++;
}
else if(A.Data[a].row > B.Data[b].row){
if (res.Data[c].data += B.Data[b].data) {
res.Data[c].column = B.Data[b].column;
res.Data[c].row = B.Data[b].row;
c++;
}
b++;
}
else {
if (A.Data[a].column < B.Data[b].column) {
if (res.Data[c].data += A.Data[a].data) {
res.Data[c].column = A.Data[a].column;
res.Data[c].row = A.Data[a].row;
c++;
}
a++;
}
else if (A.Data[a].column > B.Data[b].column) {
if (res.Data[c].data += B.Data[a].data) {
res.Data[c].column = B.Data[b].column;
res.Data[c].row = B.Data[b].row;
c++;
}
b++;
}
else {
if (res.Data[c].data += (B.Data[b].data + A.Data[a].data)) {
res.Data[c].column = B.Data[b].column;
res.Data[c].row = B.Data[b].row;
c++;
}
a++; b++;
}
}
}
while (a < A.MaxNum ) {
if (res.Data[c].data += A.Data[a].data) {
res.Data[c].column = A.Data[a].column;
res.Data[c].row = A.Data[a].row;
c++;
}
a++;
}
while (b < B.MaxNum) {
if (res.Data[c].data += B.Data[b].data) {
res.Data[c].column = B.Data[b].column;
res.Data[c].row = B.Data[b].row;
c++;
}
b++;
}
printf("%d %d %d\n", res.MaxRow, res.MaxColumn, c);
for (int i = 0; i < c; i++) {
printf("%d %d %d", res.Data[i].row, res.Data[i].column, res.Data[i].data);
//if(i!=c.nums)
printf("\n");
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m, t;
cin >> n >> m >> t;
A.MaxRow = n; A.MaxColumn = m; A.MaxNum = t;
for (int i = 0; i < t; i++) {
int r, c, v;
cin >> r >> c >> v;
A.Data[i].row = r;
A.Data[i].column = c;
A.Data[i].data = v;
}
cin >> n >> m >> t;
B.MaxRow = n; B.MaxColumn = m; B.MaxNum = t;
if (A.MaxColumn != B.MaxColumn || A.MaxRow != B.MaxRow) {
cout << "Illegal!";
return 0;
}
for (int i = 0; i < t; i++) {
int r, c, v;
cin >> r >> c >> v;
B.Data[i].row = r;
B.Data[i].column = c;
B.Data[i].data = v;
}
MatrixPlus();
return 0;
}
7-4-4 序列调度
分数 100
作者 谷方明
单位 吉林大学
有一个N个数的序列A：1，2，……，N。有一个后进先出容器D，容器的容量为C。如果给出一个由1到N组成的序列，那么可否由A使用容器D的插入和删除操作得到。
输入格式:
第1行，2个整数T和C，空格分隔，分别表示询问的组数和容器的容量，1≤T≤10，1≤C≤N。
第2到T+1行，每行的第1个整数N，表示序列的元素数，1≤N≤10000。接下来N个整数，表示询问的序列。
输出格式:
T行。若第i组的序列能得到，第i行输出Yes；否则，第i行输出No,1≤i≤T。
输入样例:
在这里给出一组输入。例如：
2 2
5 1 2 5 4 3
4 1 3 2 4
输出样例:
在这里给出相应的输出。例如：
No
Yes
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
stack<int>q;
int i,j,k,num;
int a[10010];
int main() {
int n,t,len,min0 = 1;
cin>>t>>len;
for(k=0;k<t;k++)
{
min0=1;
cin>>n;
int flag=1;
for (i=0;i<n;i++)
{
cin>>a[i];
}
for(i=0;i<n;i++)
{
if (a[i]>=min0)
{
for (j=min0;j<=a[i];j++)
{
q.push(j);
num++;
}
if(num>len)
{
flag=0;
}
min0=a[i]+1;
}
else
{
if (q.top()!=a[i])
{
flag=0;
}
}
q.pop();
num--;
}
if (flag) {
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
}
return 0;
}