2023 DS midterm day3

NCU
,

Data Structure Midterm wed writeup

PA 多項式加法

Description

一個多項式可用下列通式表示：
f(x) = Cnxn+ Cn-1xn-1+ … + C1x1+ C0x0，
其中 Cn表示 x 的 n 次項係數， Cn為包含零的任意正負整數，而 n 為包含零的任意正整數。

而多項式加法為：同次項目，係數相加。(項數可能增加，需注意溢位問題！)
Ex：(3x3+ 5x2+ 5)+(-5x2+ 7x + 3)

1
2
3
4
3x3+5x2+5
+      -5x2+7x +3
────────────────
3x3+7x +8

不會出現相加後最終答案為0的情況

Input

使用者輸入的格式如下 :
4 //表示第一個多項式的非零項個數
3 5 //表示第一個非零項的係數與項次：3x5
2 3 //表示第二個非零項的係數與項次：2x3
9 2 //表示第三個非零項的係數與項次：9x2
25 0 //表示第四個非零項的係數與項次：25x0
5 //表示第二個多項式的非零項個數
7
-2 3
5
-4 1
7

Output

將通式 Cnxn+ Cn-1xn-1+ … + C1x1+ C0x0以 Cnx^n+Cn-1x^n-1+ …+C1x+C0形式列出(x1輸出x，x0不顯示)，
第一行為 A 多項式，
第二行為 B 多項式，
第三行為 A + B 的多項式結果。

Sample Input 1

1
2
3
4
5
6
7
8
9
10
11
4
3 5
2 3
9 2
25 0
5
7 4
-2 3
5 2
-4 1
7 0

Sample Output 1

1
2
3
3x^5+2x^3+9x^2+25
7x^4-2x^3+5x^2-4x+7
3x^5+7x^4+14x^2-4x+32

PB 迴文

Description

輸入兩整數，找出兩整數區間內所有具有回文結構的數字。比如說，輸入 80 100 ，則輸出為 88 99 。 100 200 ，則輸出為 101 111 121 131 141 151 161 171 181 191 。若沒有則輸出 0 。

區間範圍不包含輸入的數字，比如說，輸入88 90，則輸出為0。

Input

輸入 兩整數a,b( 0 <a<b< 500 )。

Output

輸出為 區間內所有具有回文結構的數字 。

Sample Input 1

1
80 100

Sample Output 1

1
88 99

PA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

int a,b;
vector<int> s1,s2,ans,t1,t2;
 
signed main(){
  for(int i=0;i<1000000;i++){
    s1.push_back(0);
    s2.push_back(0);
    ans.push_back(0);
  }
    cin>>a;
  for(int i=0;i<a;i++){
    int c,x;
    cin>>c>>x;
    s1[x]=c;
  }
  t1=s1;
    cin>>b;
    for(int i=0;i<b;i++){
    	int c,x;
    cin>>c>>x;
    s2[x]=c;
  }
  t2=s2;
  for(int i=s1.size();i>=0;i--){
    if(s1[i]!=0){
      ans[i]=s1[i]+s2[i];
      s1[i]=0;s2[i]=0;
    }
  }
  for(int i=s2.size();i>=0;i--){
    if(s2[i]!=0){
      ans[i]=s2[i]+s1[i];
      s1[i]=0;s2[i]=0;
    }
  }
  
  bool outed=0;
  for(int i=t1.size();i>=0;i--){
    if(t1[i]!=0){
      if(outed){
        if(t1[i]>0)cout<<'+';
      }
      outed=1;
      cout<<t1[i];
      if(i>1)cout<<"x^";
      else if(i==1) cout<<"x";
      if(i>1)cout<<i;
    }
  }
  cout<<endl;
  outed=0;
  for(int i=t2.size();i>=0;i--){
    if(t2[i]!=0){
      if(outed){
        if(t2[i]>0)cout<<'+';
      }
      outed=1;
      cout<<t2[i];
      if(i>1)cout<<"x^";
      else if(i==1) cout<<"x";
      if(i>1)cout<<i;
    }
  }
  cout<<endl;
  outed=0;
  for(int i=ans.size();i>=0;i--){
    if(ans[i]!=0){
      if(outed){
        if(ans[i]>0)cout<<'+';
      }
      outed=1;
      cout<<ans[i];
      if(i>1)cout<<"x^";
      else if(i==1) cout<<"x";
      if(i>1)cout<<i;
    }
  }
  cout<<endl;
}

PB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

int haha[58]={1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,303,313,323,333,343,353,363,373,383,393,404,414,424,434,444,454,464,474,484,494};

bool piyan[501];

signed main(){
    for(auto i:haha){
        piyan[i]=1;
    }
    int a,b;
    cin>>a>>b;
    bool has=0;
    bool spc=0;
    for(int i=a+1;i<b;i++){
        if(piyan[i]){
            if(spc)cout<<' ';
            cout<<i;
            spc=1;
            has=1;
        }
    }
    if(!has){
        cout<<0<<endl;
    }
    else{
        cout<<endl;
    }
}