程式碼
#include <iostream>
using namespace std;
string decode(int len, int seq[], string s)
{
string result = s;
for (int i = 0; i < len; i++)
{
result[i] = s[seq[i] - 1];
}
return result;
}
int main()
{
string s;
int n, k;
cin >> n;
int* seq = new int[n + 1];
for (int i = 0; i < n; i++)
cin >> seq[i];
cin >> s >> k;
for (int i = 0; i < k; i++)
s = decode(n, seq, s);
cout << s;
return 0;
}
在程式執行的時候才決定呼叫哪個function。
與一般的繼承class的function overload不同，如果一個function是virtual的，那麼在執行的時候會去判斷物件屬於哪個class，然後呼叫該class定義的function。
如果base class裡宣告某function為virtual，那麼繼承的class的某function也為virtual，無需特別宣告。
有時候base class可能還無法實作某些function，但又需要先把功能定義清楚，該怎麼辦呢?
這時候就用到純虛擬函式，它是沒有函式實體的。例:
virtual void Area()=0;
而所有繼承自base class的class都需要自己定義Area的內容。
如果一個class存在pure virtual function，那麼該class就是抽象類別，它不能於主程式中被宣告、使用。
也因此繼承它的class要自己override 這些 pure virtual function，不然也會被視為抽象類別，也一樣法把被使用。
程式碼
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
while (cin >> n)
{
int count = 0, top, tmp;
vector<int> m;
cin >> tmp;
m.push_back(tmp);
for (int i = 1; i < n; i++)
{
cin >> tmp;
if (tmp != m.back()) m.push_back(tmp);
}
for (int i = 1; i < m.size()-1; i++)
{
if (m[i - 1] < m[i] && m[i] > m[i + 1])
count++;
}
cout << count << endl;
}
return 0;
}
程式碼:
#include <iostream>
using namespace std;
int main()
{
int n, flag1, flag2;
cin >> n;
flag1 = n - (n / 2000) * 200;
flag2 = n - (n / 1000) * 100;
if (flag1 <= flag2) cout << flag1 << " 0";
else cout << flag2 << " 1" << endl;
return 0;
}
程式碼:
#include <iostream>
using namespace std;
int main()
{
int n, points,studentN;
cin >> n >> points;
int* ans = new int[n];
for (int i = 0; i < n; i++)
cin >> ans[i];
cin >> studentN;
while (studentN--)
{
int score = 0, p;
for (int i = 0; i < n; i++)
{
cin >> p;
if (p == ans[i]) score += points;
}
cout << score << endl;
}
}
strum: 撥弄(吉他)
tangle: 糾纏的
dress-up: 盛裝打扮的
quaint: 古雅的
train wreck: 糟透了
程式碼
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
int main()
{
int n, x, command;
while (cin >> n)
{
stack<int> st;
queue<int> q;
priority_queue<int> pq;
bool isStack = true, isQueue = true, isPQ = true;
while (n--)
{
cin >> command >> x;
if (!isStack && !isQueue && !isPQ) continue;
if (command == 1)
{
st.push(x); q.push(x); pq.push(x);
}
else
{
if (st.empty()||st.top() != x) isStack = false;
if (q.empty()||q.front() != x) isQueue = false;
if (pq.empty()||pq.top() != x) isPQ = false;
st.pop(); q.pop(); pq.pop();
}
}
if (!isStack && !isQueue && !isPQ) cout << "impossible" << endl;
else if (isStack && !isQueue && !isPQ) cout << "stack" << endl;
else if (!isStack && isQueue && !isPQ) cout << "queue" << endl;
else if (!isStack && !isQueue && isPQ) cout << "priority queue" << endl;
else cout << "not sure" << endl;
}
return 0;
}
pinch yourself: 掐自己一下（表示某事太好或太奇怪，簡直令人難以置信）
lookout: 觀景處
take the time: 花費力氣(做某事)
使用時機
當一個class繼承自不同的多個class時，會繼承到他們的資料定義。這時可能會有重複的資料被繼承到，造成運作不符合預期，例如:
#include <iostream>
using namespace std;
class CA //common base class of CB and CC
{
public:
int x;
CA(int a = 0) { x = a; }
};
class CB :public CA
{
public:
int y;
CB(int a = 0, int b = 0) :CA(a) { y = b; }
};
class CC :public CA
{
public:
int z;
CC(int a = 0, int b = 0) :CA(a) { z = b; }
};
class CD : public CB, public CC
{
public:
int w;
CD(int a = 0, int b = 0, int c = 0, int d = 0 ,int e = 0) :CB(a, b), CC(c, d) {
w = e;
}
void ShowVal() {
cout << "x = " << CB::x << " y = " << y
<< " x = " << CC::x << " z = " << z;
cout << " w = " << w << endl;
}
};
int main()
{
CD obj(5, 4, 3, 2, 1);
obj.ShowVal(); //what happens?
return 0;
}輸出為: x = 5 y = 4 x = 3 z = 2 w = 1
如果改以virtual 方式繼承，相同的資料只會用到同一塊記憶體。例如:
#include <iostream>
using namespace std;
class CA //common base class of CB and CC
{
public:
int x;
CA(int a = 0) { x = a; }
};
class CB : virtual public CA
{
public:
int y;
CB(int a = 0, int b = 0) :CA(a) { y = b; }
};
class CC : virtual public CA
{
public:
int z;
CC(int a = 0, int b = 0) :CA(a) { z = b; }
};
class CD : public CB, public CC
{
public:
int w;
CD(int a = 0, int b = 0, int c = 0, int d = 0
,int e = 0) : CA(a), CB(a, b), CC(c, d) {
w = e;
}
void ShowVal() {
cout << "x = " << CB::x << " y = " << y
<< " x = " << CC::x << " z = " << z;
cout << " w = " << w << " x = " << x << endl;
}
};
int main()
{
CD obj(5, 4, 3, 2, 1);
obj.ShowVal(); //what happens?
return 0;
}
輸出為: x = 5 y = 4 x = 5 z = 2 w = 1 x = 5
呼叫順序
constructors
first, virtual base classes in declaration order
then, other base classes in declaration order
destructors
in the reverse order of the constructors
程式碼
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Student
{
public:
string name, sentence;
int _class, index;
};
bool cmp(Student s1, Student s2)
{
if (s1._class < s2._class) return true;
if (s1._class > s2._class) return false;
if (s1.index < s2.index) return true;
else return false;
}
int main()
{
int n;
while (cin >> n)
{
vector<Student> school;
for (int i = 0; i < n; i++)
{
Student tmp;
cin >> tmp.name >> tmp._class >> tmp.index >> tmp.sentence;
school.push_back(tmp);
}
sort(school.begin(), school.end(), cmp);
for (int i = 0; i < school.size(); i++)
{
cout << school[i]._class << " " << school[i].index << " " << school[i].name << endl<< school[i].sentence;
if (i != school.size() - 1)cout << endl;
}
}
return 0;
}
revolt: 反抗、反叛
Get the best of sb: 被某人(負面)影響
chokey: 禁閉室
bar: 鐵欄杆
horde: 一群人
chalk: 粉筆
jumping at our own shadows: 易受驚嚇的
suppertime: 晚餐時間
I beg your pardon: 不好意思、能再重說一次嗎?
airspace: 領空
torn up: 磨損
debris: 碎屑
asphalt: 柏油
landfall: 登陸
crack: 身心疲憊、精神崩潰
chilli: 辣味肉豆
pick up: 增加
turbulence: 不穩定氣流、顛簸
canoodle: 親熱
pace: 步調
seat back: 座椅靠背
tray table: (可折攏的)餐桌
taxiing: 滑行
pilot: 飛行員
mortician: 殯葬業者
lift off: 起飛
charter: 包機
grab a drink: 喝一杯
think highly of: 認為...很了不起、對...評價很高
stay grounded: 雙關: 1)務實、腳踏實地 2)字面上的待在地上
air-to-air: 空對空的
inlet: 海灣
bay: 海灣
nothing goes as planned: 事與願違
fella: 夥計們
cockpit: 駕駛艙
long distance relationship: 異地戀
northeast tip: 東北角
commemorate: 紀念、緬懷
Atlantic: 大西洋的
cod: 鱈魚
kettle: 開水壺
cove: 小海灣
sun is setting: 日落
解題心得:
注意優先順序。
程式碼:
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
using namespace std;
int priority(char c)
{
if (c == '*' || c == '/') return 0;
if (c == '+' || c == '-') return 1;
else return 2;
}
int main()
{
string s;
while (getline(cin, s))
{
stringstream ss(s);
stack<char> st;
st.push('(');
s += ")";
for (int l = 0; l < s.size(); l++)
{
if (s[l] == ' ') continue;
if (s[l] == '(') st.push('(');
else if (s[l] == ')')
{
while (st.top() != '(')
{
cout << st.top() << " ";
st.pop();
}
st.pop();
}
else if ('a' <= s[l] && s[l] <= 'z')
{
cout << s[l] << " ";
}
else
{
while (priority(st.top()) <= priority(s[l]))
{
cout << st.top() << " ";
st.pop();
}
st.push(s[l]);
}
}
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
}
return 0;
}
解題心得:
就.....資料結構實作。
參考文章:Min Heap and Max Heap Implementation in C++
程式碼:
#include<iostream>
using namespace std;
class maxHeap
{
public:
maxHeap()
{
size = 0;
for (int i = 0; i < 1025; i++) arr[i] = 0;
}
int arr[1025];
int size;
int parent(int i) { return (i - 1) / 2; }
int find_left(int i) { return 2 * i + 1; }
int find_right(int i) { return 2 * i + 2; }
int getSize() { return size; }
bool isEmpty() { return size == 0; }
void heap_down(int i)
{
int left = find_left(i), right = find_right(i);
int largest = i;
if (left < this->size && arr[left] > arr[i])
largest = left;
if (right < this->size && arr[right] > arr[largest])
largest = right;
if (largest != i)
{
swap(arr[i], arr[largest]);
heap_down(largest);
}
}
void heap_up(int i)
{
if (i != 0 && arr[parent(i)] < arr[i])
{
swap(arr[i], arr[parent(i)]);
heap_up(parent(i));
}
}
void push(int n)
{
arr[this->size] = n;
this->size++;
heap_up(this->size - 1);
}
void pop()
{
arr[0] = arr[this->size - 1];
this->size--;
heap_down(0);
}
int top() { return arr[0]; }
};
class minHeap
{
public:
minHeap()
{
size = 0;
for (int i = 0; i < 1025; i++) arr[i] = 0;
}
int arr[1025];
int size;
int parent(int i) { return (i - 1) / 2; }
int find_left(int i) { return 2*i + 1; }
int find_right(int i) { return 2 * i + 2; }
int getSize() { return size; }
bool isEmpty() { return size == 0; }
void heap_down(int i)
{
int left = find_left(i), right = find_right(i);
int smallest = i;
if (left < this->size && arr[left] < arr[i])
smallest = left;
if (right < this->size && arr[right] < arr[smallest])
smallest = right;
if (smallest != i)
{
swap(arr[i], arr[smallest]);
heap_down(smallest);
}
}
void heap_up(int i)
{
if (i != 0 && arr[parent(i)] > arr[i])
{
swap(arr[i], arr[parent(i)]);
heap_up(parent(i));
}
}
void push(int n)
{
arr[this->size] = n;
this->size++;
heap_up(this->size - 1);
}
void pop()
{
arr[0] = arr[this->size - 1];
this->size--;
heap_down(0);
}
int top() { return arr[0]; }
};
int main()
{
int n;
while (cin >> n)
{
minHeap heap1;
maxHeap heap2;
while (n--)
{
int num;
cin >> num;
heap1.push(num);
heap2.push(num);
}
for (int i = 0; i < heap1.size; i++)
{
if (i != heap1.size-1) cout << heap1.arr[i] << " ";
else cout << heap1.arr[i] << endl;
}
for (int i = 0; i < heap2.size; i++)
{
if (i != heap2.size - 1) cout << heap2.arr[i] << " ";
else cout << heap2.arr[i] << endl;
}
}
return 0;
}
put in effort: 盡力
heaps of: 很多
ancient history: 陳年舊事
for ages: 很久
living hell: 活受罪
peal:(鈴)大聲鳴響
listen up: something you say to make people listen to you (大家注意了、聽我這邊)
a thing or two: 一些事情、知識
step out of line: 行為不妥
speciality: 常做的事(?)
teacher's pet: 老師的寵兒
Don't got much baggage to lay at your feet: 不會為你帶來太多負擔
to spare: 有多的
lease: 租借
moat: 護城河
nickel: 五分美金
worn out: 筋疲力盡
breadline: 等候領取施捨食物的隊伍
eviction: 驅逐
chord: 和弦
sour note: 刺耳的音符
flue: 煙道
teeny: 很小的
crackle: 劈啪作響
incendiary: 能引起燃燒的
draw a line in the sand: 守住底線
make a stand: 進行抵抗
spar: 出擊
act tough: 來硬的
called their bluff: 質疑對方、挑戰對方
front man: 樂團主唱
have the world at one's feet: 極為成功
time flies: 時光飛逝
ring true: 聽起來像是真的
redeem: 贖回、挽救
so dear: 多麼珍貴的
strife: 爭吵
burn one's bridge: 自斷退路、破釜沉舟
(網路上這句有很多不同的翻譯，這裡選一個順眼的: 用他破釜沉舟的意志)