owned this note
owned this note
Published
Linked with GitHub
APCS進階班第1次模擬考解答
===
* [d096: 00913 - Joana and the Odd Numbers](#d096)
* [b265: Q11286 - Conformity](#b265)
* [c002: 10696 - f91](#c002)
* [c123: 00514 - Rails](#c123)
* [b266: 矩陣翻轉(APCS官網例題)](#b266)
# <a id='b266'>b266: 矩陣翻轉(APCS官網例題)</a>
https://zerojudge.tw/ShowProblem?problemid=b266
範例輸入:([解答連結](http://rs-vb.blogspot.tw/2016/09/apcs-10532-c.html))
```
3 2 3 <- 3列 2行 3個翻轉或旋轉指令
1 1 <- 以下3列是矩陣
3 1
1 2
1 0 0 <- 0是旋轉(順時針) 1是翻轉(上下翻轉)
3 2 2
3 3
2 1
1 2
0 1
```
範例輸出:
```
3 2 <- 下面矩陣的row跟col
1 1 <- 矩陣資料
1 3
2 1
2 3 <- 下面矩陣的row跟col
2 1 3 <- 矩陣資料
1 2 3
```
範例解釋
```
輸入資訊如下
3 2 3
1 1
3 1
1 2
1 0 0
代表結果的矩陣B是這樣
1 1
3 1
1 2
B是A矩陣經過1(上下顛倒)->0(順時針旋轉)->0(順時針旋轉)
所以要求出A必須將 1 0 0 給回朔
```
解答
```csharp
#include < iostream >
#include < vector >
using namespace std;
const int MaxN = 10;
int a[2][MaxN][MaxN];
int rc[2]; //列高、行寬
void rev0(int s, int w) //逆旋轉
{
int r = rc[w], c = rc[1 - w];
int i, j;
for (i = 0; i < r; ++i)
for (j = 0; j < c; ++j)
a[1 - s][c - 1 - j][i] = a[s][i][j];
}
void rev1(int s, int w) //逆翻轉
{
int r = rc[w], c = rc[1 - w];
int i, j;
for (i = 0; i < r; ++i)
for (j = 0; j < c; ++j)
a[1 - s][r - 1 - i][j] = a[s][i][j];
}
void print(int s, int w) //印矩陣
{
int r = rc[w], c = rc[1 - w];
int i, j;
cout << r << ' ' << c << endl;
for (i = 0; i < r; ++i) {
cout << a[s][i][0];
for (j = 1; j < c; ++j)
cout << ' ' << a[s][i][j];
cout << endl;
}
}
int main(void) {
int i, j, k, r, c, m;
bool first = true;
while (cin >> r >> c >> m) {
rc[0] = r;
rc[1] = c;
for (i = 0; i < r; ++i)
for (j = 0; j < c; ++j)
cin >> a[0][i][j];
int s = 0, w = 0;
// print(s,w); // 測試用印出
int d[MaxN];
for (i = 0; i < m; ++i) cin >> d[i];
for (i = m - 1; i >= 0; --i) {
if (d[i] == 0) {
rev0(s, w); // 旋轉
w = 1 - w;
} else rev1(s, w); // 翻轉
s = 1 - s;
// print(s,w); // 測試用印出
}
if (first) first = false;
else cout << endl;
print(s, w);
}
return 0;
}
```
Allen註解版
```csharp
#include <iostream>
using namespace std;
const int MaxN = 10;
int data[MaxN][MaxN];
int cmd[MaxN];
int row, col;
void reverse_cmd0() //逆旋轉(逆時針旋轉)
{
int i, j;
int newData[MaxN][MaxN];
//逆時針旋轉
for (i = 0; i < row; i++) {
for (j = 0; j < col; j++) {
newData[j][i] = data[i][col - j - 1];
}
}
//把row與col交換
int temp = row;
row = col;
col = temp;
//把新的陣列回傳給data
for (i = 0; i < row; i++)
for (j = 0; j < col; j++)
data[i][j] = newData[i][j];
}
void reverse_cmd1() //逆翻轉(翻轉逆跟不膩都是一樣的)
{
int i, j;
int newData[MaxN][MaxN];
//上下顛倒
for (i = 0; i < row; i++)
for (j = 0; j < col; j++)
newData[i][j] = data[row - i - 1][j];
//把新的陣列回傳給data
for (i = 0; i < row; i++)
for (j = 0; j < col; j++)
data[i][j] = newData[i][j];
}
void print() //印矩陣
{
int i, j;
cout << row << ' ' << col << endl;
for (i = 0; i < row; ++i) {
for (j = 0; j < col; ++j)
cout << data[i][j] << " ";
cout << endl;
}
}
int main(void) {
int i, j, m;
while (cin >> row >> col >> m) {
//依序輸入所有矩陣的資料
for (i = 0; i < row; ++i)
for (j = 0; j < col; ++j)
cin >> data[i][j];
//輸入操作矩陣的指令(0或1)
for (i = 0; i < m; ++i) cin >> cmd[i];
//從最後一個指令開始解析,因為我們要讓整個矩陣變成原矩陣
for (i = m - 1; i >= 0; --i) {
if (cmd[i] == 0) {
reverse_cmd0(); // 逆時針旋轉
} else {
reverse_cmd1(); // 翻轉
}
}
print();
cout << endl;
}
return 0;
}
```
---
# <a id='c002'>c002: 10696 - f91</a>
zerojudge: https://zerojudge.tw/ShowProblem?problemid=c002
uva: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1637
• If N ≤ 100, then f91(N) = f91(f91(N + 11));
• If N ≥ 101, then f91(N) = N − 10.
---
```csharp
#include < iostream >
using namespace std;
int f91(int);
int main() {
int n;
while (cin >> n && n != 0) {
cout << "f91(" << n << ") = " << f91(n) << endl;
}
}
int f91(int num) {
if (num <= 100) return f91(f91(num + 11)); //遞迴
else return num - 10; //終止條件
}
```
---
# <a id='c123'>c123: 00514 - Rails</a>
https://zerojudge.tw/ShowProblem?problemid=c123
解答
```csharp
//By SCJ
//uva 514
#include < bits / stdc++.h >
using namespace std;
int main() {
int n;
bool fir = 0;
while (cin >> n, n != 0) {
while (1) {
bool fg = 0;
int t, cnt = 2;
stack < int > s;
s.push(1);
bool ok = 1; //預設是ok
//
for (int i = 0; i < n; ++i) {
cin >> t; //輸入每個車廂
if (t == 0) { //輸入0代表造跳出
fg = 1;
break;
}
while (cnt <= n && (s.empty() || s.top() != t)) {
s.push(cnt++);
}
if (s.empty() || s.top() != t) {
//不ok
ok = 0;
} else {
s.pop();
}
}
//輸入0所以跳出
if (fg) break;
if (ok) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
cout << endl;
}
}
```
Allen翻譯版本
```csharp
//uva 514
#include < bits / stdc++.h >
using namespace std;
int main() {
//n代表要輸入幾個火車廂
int n;
while (cin >> n, n != 0) {
while (1) {
bool flag = 0; //flag=1代表要跳出目前的測試模式
int train;
int cnt = 2; //代表要駛入車站的車廂號碼
stack < int > stk; //火車站
stk.push(1); //先讓第一節車廂開進火車站
bool ok = true; //預設是ok,預設是會成功的,中途遇到錯誤再改成ok=false
for (int i = 0; i < n; ++i) {
cin >> train; //輸入每個車廂
if (train == 0) { //輸入0代表要跳出
flag = 1;
break;
}
//還有未進站的火車 且 目前車站的車頭不是我們要的
while (cnt <= n && (stk.empty() || stk.top() != train)) {
//if(stk.empty())cout<<"車站沒車"<<endl;
//cout<<"火車("<<cnt<<")進站"<<endl;
stk.push(cnt++);
}
//如果車站是空的 或 要出站的火車不是我們要的
if (stk.empty() || stk.top() != train) {
//代表出車失敗,ok = false
ok = false;
} else {
//成功出車,把火車送出停靠站,往B前進
//cout<<"火車("<<stk.top()<<")出站"<<endl;
stk.pop();
}
}
//輸入0所以跳出
if (flag) break;
if (ok) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
cout << endl;
}
}
```
---
# <a id='b265'>b265: Q11286 - Conformity</a>
[https://zerojudge.tw/ShowProblem?problemid=b265](https://zerojudge.tw/ShowProblem?problemid=b265)
需要用到 struct, sort, 且較難想的題目
```csharp
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int N;
struct Student {
int course[5];
}
student[10005];
//比較兩個學生的所有課程編號大小
bool cmp(Student A, Student B) {
for (int i = 0; i < 5; i++)
if (A.course[i] != B.course[i])
return A.course[i] < B.course[i];
return false;
}
//檢測兩個學生的所有課程是否一樣
bool same(int x, int y) {
for (int i = 0; i < 5; i++)
if (student[x].course[i] != student[y].course[i])
return false;
return true;
}
int main() {
//N位學生
while (cin >> N) {
if (N == 0) break;
int x;
//輸入每位學生所選的課程,最後把課程先排序
for (int i = 1; i <= N; i++) {
for (int j = 0; j < 5; j++) {
cin >> student[i].course[j];
}
sort(student[i].course, student[i].course + 5);
}
//將學生們也進行排序,依照他們所選的課當依據
sort(student + 1, student + N + 1, cmp);
//longest代表最多人選的課程組合,有多少人選
//now暫存的變數,紀錄相同的課程組合,重複出現幾次
//ans是最後的答案
int longest = 1, now = 1, ans = 0;
//掃過每位學生,找出最多人選的組合,總共有多少人選
for (int i = 2; i <= N; i++) {
if (same(i, i - 1)) {
now++; //該位同學與前一位同學的選課一模一樣,課程重複次數增加
if (now > longest)
longest = now; //新的最熱門課程誕生
} else
now = 1; //該位學生與前位學生的選課不同,重複次數重新計算
}
now = 1;
//最熱門課程只有一人,代表大家選的都不同,每位學生的組合都是最熱門的組合
//檢查最多人選的課程是否不只一種組合,如果longest是3,裡面有兩個課程組合各有3人選的話
//那就是3+3,答案就是6
//裡面比較特別的是當每種組合都不同(longest==1)時,要把答案先+1
for (int i = 2; i <= N; i++) {
if (same(i, i - 1)) {
now++;
} else
now = 1;
if (now == longest)
ans += longest;
}
if(longest==1) ans++;
cout << ans << endl;
}
return 0;
}
```
---
# <a id='d096'>d096: 00913 - Joana and the Odd Numbers</a>
[https://zerojudge.tw/ShowProblem?problemid=d096](https://zerojudge.tw/ShowProblem?problemid=d096)
```csharp
#include <iostream>
using namespace std;
int main() {
long long n, ans, row, lineStarter, lastOdd;
while (cin >> n) {
//算出n個奇數該出現在第幾列,也就是row
row = (1 + n) / 2;
//算出第row列的開頭數字是多少
lineStarter = (row - 1) * (row - 1) * 2 + 1;
//該列的最後一個奇數的算法
lastOdd = lineStarter + 2 * (n - 1);
//lastOdd+(lastOdd-2)+(lastOdd-4) = lastOdd*3 -6
ans = lastOdd * 3 - 6;
cout << ans << endl;
}
return 0;
}
```