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;
}
 
​

本栏目推荐文章
• 算法设计与分析PTA考试（周六考研版）
• PTA-2023第十三次练习题目题解
• PTA7-3 平衡二叉树的根
• PTA 整除光棍
• NCHU PTA7-8次PTA题目集（成绩计算系列）以及期末考试
• 第三次blog-7-8次PTA题目集及期末考试总结
• pta7，8加期末
• 7-8次PTA题目集（成绩计算系列）以及期末考试
• 7-8次PTA和期末成绩总结
• 第7，8次pta作业以及期末考试的总结

ptapta7 pta4 pta6 pta7 pta pta1 题目pta 汽车pta pta4 pta 报告pta 三大pta