owned this note
owned this note
Published
Linked with GitHub
APCS進階班第2次模擬考解答
===
10038
題目:http://luckycat.kshs.kh.edu.tw/homework/q10038.htm
觀念:bruteforce (DFS)
難度:luckycat ★
```cpp
#include <bits/stdc++.h>
using namespace std;
int N, input[3005];
bool used[3005];
int main(){
while ( cin >> N ){
bool isJolly = true;
for ( int i = 0 ; i < N ; i++ ){
used[i] = false;
cin >> input[i];
}
for ( int i = 1 ; i < N ; i++ ){
int offset = abs( input[i] - input[i-1] );
if ( offset > 0 && offset < N ){
// 如果該距離已存在,代表不符合jolly格式
if ( !used[offset] )
used[offset] = true;
else{
isJolly = false;
break;
}
}
else{
isJolly = false;
break;
}
}
if ( isJolly )
cout << "Jolly" << endl;
else
cout << "Not jolly" << endl;
}
return 0;
}
```
---
11059 Maximum Product
題目:http://luckycat.kshs.kh.edu.tw/homework/q11059.htm
觀念:bruteforce (DFS)
難度:luckycat ★
```cpp
#include <iostream>
#include <string.h>
using namespace std;
int N;
long long arr[20], answer ;
void DFS( int now , long long product ){
if ( product > answer )
answer = product;
if ( now == N )
return;
DFS( now+1 , product * arr[now] );
}
int main(){
int c = 1;
while ( cin >> N ){
for ( int i = 0 ; i < N ; i++ )
cin >> arr[i];
answer = 0;
for ( int str = 0 ; str < N ; str++ )
DFS( str+1 , arr[str] );
cout << "Case #" << c++ << ": The maximum product is " << answer << "." << endl;
cout << endl;
}
return 0;
}
```
解題示意
![](https://i.imgur.com/cE7IkcT.png)
![](https://i.imgur.com/TC0Sp3z.jpg)
---
## 11520 Fill the Square
題目:[http://luckycat.kshs.kh.edu.tw/homework/q11520.htm](http://luckycat.kshs.kh.edu.tw/homework/q11520.htm)
觀念:greedy
難度:luckycat ★★
參考解答:
[http://programming-study-notes.blogspot.tw/2014/01/uva-11520-fill-square.html](http://programming-study-notes.blogspot.tw/2014/01/uva-11520-fill-square.html)
```cpp
#include <bits/stdc++.h>
using namespace std;
char square[12][12];
void fillChar (int n,int i,int j){
char filled = 'A';
bool up,left,right,down;
//嘗試A~Z之間的所有字母
while (filled <= 'Z'){
//此格的上下左右 '超過邊界' 或 '內容與此格不同'
if (i-1<0 || square[i-1][j]!=filled) up=1; else up=0;
if (i+1>=n || square[i+1][j]!=filled) down=1; else down=0;
if (j-1<0 || square[i][j-1]!=filled) left=1; else left=0;
if (j+1>=n || square[i][j+1]!=filled) right=1;else right=0;
//四邊的格子都與本格不衝突的話,就可以使用所選的字母
if (up && down && left && right){
square[i][j] = filled;
cout<<filled;
break;
}
else filled += 1; //換成下一個字母,例如:A -> B
}
}
int main()
{
//t是測資數量,n是正方形的邊長
int t,n,Case=1;
cin>>t;
while (t--)
{
cin>>n;
gets(square[0]);
for(int i=0;i<n;i++) gets(square[i]);
cout<<"Case "<<Case++<<endl;
//對每一個格子做greedy演算法
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if (square[i][j]!='.')
{
//如果此格已經有字母則輸出
cout<<square[i][j];
}
else
{
//還是空格子,決定該填上哪個字母
fillChar(n,i,j);
}
}
cout<<endl;
}
}
return 0;
}
```
---
12694 Meeting Room Arrangement
題目:http://luckycat.kshs.kh.edu.tw/homework/q12694.htm
觀念:Greedy
難度:luckycat ★★
```cpp
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int T, N;
struct Meeting{
int s, e;
}meeting[25];
bool cmp( Meeting A, Meeting B ){
return A.e < B.e;
}
int main(){
int s, e;
int ts, te;
cin >> T;
while ( T-- ){
N = 0;
while ( cin >> ts >> te ){
if ( ts == 0 && te == 0 ) break;
meeting[N].s = ts;
meeting[N].e = te;
N++;
}
sort( meeting, meeting+N , cmp );
int ans = 0, lastUsedTime = 0;
for ( int i = 0 ; i < N ; i++ )
if ( meeting[i].s >= lastUsedTime ){
ans++;
lastUsedTime = meeting[i].e;
}
cout << ans << endl;
}
return 0;
}
```
---
12694 Meeting Room Arrangement
題目:https://zerojudge.tw/ShowProblem?problemid=c463
觀念:Tree BFS
```cpp
/*
由下到上的方式計算節點的高度,原圖葉節點高度為0,
取出葉節點後其雙親節點高度為原來雙親節點高度與葉節點高度加1的較大值,
接著葉節點的雙親節點小孩個數少1,當雙親節點的子節點個數為0時,可以視為新的葉節點,
取出該雙親節點以相同方式計算其雙親節點的高度。
最後一個節點就是root,累加所有節點高度就可以獲得高度總和。
*/
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
const int MAX = 100001;
using namespace std;
int parent[MAX];//parent[i]=j,表示i的雙親為j
int degree[MAX];//紀錄節點深度
int childrenCount[MAX];//紀錄節點的子節點個數,子節點計算過後就減1
deque<int> todo;//儲存葉節點
int main()
{
int n,cnt,child;
long long int sum;//1+2+3+...+100000,會超出int範圍
while (cin>>n) {
sum = 0; // 這是用來存H(T)的結果
//初始化
for(int i = 0; i<MAX; i++ ){
degree[i] = -1;
childrenCount[i] = 0;
}
// 輸入每個節點的children
for (int i = 1; i<=n; i++) {
cin>>cnt;
if (cnt == 0){
todo.push_back(i);//葉節點
degree[i]=0;//葉節點深度為0
}else{
childrenCount[i]=cnt;
for(int j=0;j<cnt;j++){
cin>>child;
parent[child] = i;//使用陣列parent紀錄c的parent為i
}
}
}
int node;
while(!todo.empty()){
node = todo.front();//取出葉節點
todo.pop_front();
//取自己的深度與從子節點加1的較大值
degree[parent[node]]=max(degree[parent[node]],degree[node]+1);
//從todo中取出後,該節點的parent節點個數減1
childrenCount[parent[node]]--;
if (childrenCount[parent[node]] == 0){//當所有子節點都走訪過時
todo.push_back(parent[node]);//加入該節點到佇列
}
}
for (int i = 1; i<=n; i++) {
sum += degree[i];
}
cout << node << endl;//最後一個從t取出的就是root
cout << sum << endl;
}
}
```