# 方法
跟窮舉超像，就是設法模擬出答案的狀況
跟窮舉差別就在 -> 狀況通常都比較複雜一點點，要再多考慮一下
# 例題
# c006: 10550 - Combination Lock
# 內容
你今天的任務需要來開一個鎖（如右圖）。在鎖上有一個轉盤，上面有 40 個刻度（0 到 39 來代表）。開鎖的密碼由 3 個號碼組成，例如：15-25-8。要打開這種鎖要按照以下步驟：
- 順時鐘方向轉轉盤 2 整圈
- 繼續順時鐘方向轉直到到達第一個號碼上
- 逆時鐘方向轉轉盤一整圈
- 繼續逆時鐘方向轉直到到達第二個號碼
- 順時鐘方向轉轉盤直到到達第三個號碼
- 拉開鎖頭就可以打開了
給你一開始時轉盤的位置，還有開鎖的密碼，請你算出總共要轉多少度（degree，一整圈為 360 度）才能打開鎖（順時鐘方向加逆時鐘方向）。
# 思路
記得一件事: 轉盤順時針轉的時候數字是減少的
先把轉幾圈整的加到答案裡
問題剩下從起點順時針轉到 A，逆時針轉到 B，順時針轉到 C
起點順時針轉到 A = ((s-(a-40))%40)*9
其中 9 是每一格的角度
逆時針到 B = ((b+40)-a)%40) * 9
# 程式碼
#include<iostream> | |
using namespace std; | |
int main() | |
{ | |
int s; | |
int a,b,c; | |
int ans; | |
while(cin>>s>>a>>b>>c){ | |
if(s==0 && a==0 && b==0 && c==0) | |
return 0; | |
ans = 1080; | |
ans += ((s-(a-40))%40) * 9; | |
ans += (((b+40)-a)%40) * 9; | |
ans += ((b-(c-40))%40) * 9; | |
cout<<ans<<endl; | |
} | |
return 0; | |
} |
# c292: APCS2017-0304-3 數字龍捲風
# 內容
給定一個二維陣列，依照題目需要從中間逆時針或順時針向外 輸出答案
# 思路
就是很純的模擬
先從中間開始，把中間的那圈走完，再往外拓張，直到走完全圖
# 程式碼
#include <iostream> | |
using namespace std; | |
int main(){ | |
int N, nxt; | |
while (cin >> N) { | |
cin >> nxt; | |
int a[N][N]; | |
for (int i=0; i<N; i++){ | |
for (int j=0; j<N; j++){ | |
cin >> a[i][j]; | |
} | |
} | |
// 0 代表左 、1 代表上 、2 代表右 、3 代表下 | |
int direction[4][2] = <!--swig0-->; | |
int total_steps = N * N, steps = 1; | |
int repeat = 1, repeat_cnt = 0; | |
int r = N / 2, c = N / 2; // 從中心點出發 | |
cout << a[r][c]; | |
while (steps < total_steps){ | |
for (int i=0; i<repeat; i++){ | |
r += direction[nxt][0]; | |
c += direction[nxt][1]; | |
cout << a[r][c]; | |
steps++; | |
if (steps == total_steps) break; | |
} | |
repeat_cnt++; | |
if (repeat_cnt % 2 == 0){ | |
repeat++; | |
} | |
nxt = (nxt + 1) % 4; | |
} | |
cout << '\n'; | |
} | |
return 0; | |
} |
# c297: APCS-2016-1029-4 棒球遊戲
# 題目
有點長，所以只放連結喔～
# 思路
安打時，除了原本在壘包上的人要移動外，還要加上一個從本壘走出來的人。例如 2B：原本在壘上的人往前跑 2 個壘，而本壘的人跑到 2 壘。
打出 2 壘安打時，可以想成每個人都往前進一格兩次
打出 3 壘安打時，可以想成每個人都往前進一格三次
全壘打時，跑 4 個壘就相當於原本壘上的所有人皆得分，還要外加本壘出來的人的分數。
在用 queue 模擬時，沒有人的地方可以假設為數字 0，有人的地方假設為數字 1（或其他數字）。
跑壘時讀到人（也就是數字 1）=> 得分
部分模擬的題目，也可以到很難喔～這可是 APCS 的第四題ㄟ
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
map<int, queue<string> > mp;// 紀錄用，也可以用二維陣列代替 | |
int main(){ | |
int a, target; | |
string s; | |
for (int i=0; i<9; i++){ | |
cin >> a; | |
queue <string> q; | |
for (int j=0; j<a; j++){ | |
cin >> s; | |
q.push(s); | |
} | |
mp[i] = q; | |
} | |
cin >> target; | |
int out = 0, num = -1, score = 0; | |
int b1 = 0, b2 = 0, b3 = 0, b4 = 0; | |
while (1){ | |
int times = 0; // 跑壘數 | |
num = (num + 1) % 9; // 打者號碼 | |
string hit = mp[num].front(); | |
mp[num].pop(); | |
if (hit == "SO" || hit == "GO" || hit == "FO"){ | |
out += 1; | |
if (out == target) break; | |
if (out % 3 == 0){ | |
b1 = b2 = b3 = b4 = 0; | |
} | |
} else if (hit == "HR"){ | |
times = 4; | |
} else { | |
times = hit[0] - '0'; | |
} | |
// 跑壘 | |
for (int i=1; i<=times; i++){ | |
b4 = b3; | |
b3 = b2; | |
b2 = b1; | |
if (i == 1) b1 = 1; | |
else b1 = 0; | |
if (b4 == 1) { | |
score++; | |
} | |
} | |
} | |
cout << score << '\n'; | |
return 0; | |
} |
