# SCIST S4 Week 4
:::info
時間：12/24 9:00 ~ 17:00
主題：實作技巧與模擬
:::
[TOC]
## 課程內容
- 實作技巧與模擬
- 講義連結：https://hackmd.io/@sa072686/cp/%2F%40sa072686%2FrJpY0i7PS
## 建表
### [Kattis Trik](https://open.kattis.com/problems/trik)
撰寫者：小麥
雖然用簡單的條件判斷 + 陣列模擬就可以解決了
但這邊還是用建表的技巧實作看看
:::spoiler 參考程式碼
```cpp
#include<iostream>
using namespace std;
int mv[3][2] = {{0, 1}, {1, 2}, {0, 2}};
bool cup[3] = {1, 0, 0}; // 球所在的位置
int main(){
string s;
cin >> s;
for (int i = 0; i < s.size(); i++){
int tp = s[i] - 'A';
swap (cup[ mv[tp][0] ], cup[ mv[tp][1] ]);
}
for (int i = 0; i < 3; i++)
if (cup[i]) cout << i + 1 << '\n';
return 0;
}
```
:::
---
### [AtCoder abc202_b (基本練習)](https://atcoder.jp/contests/abc202/tasks/abc202_b)
---
### [Kattis t9spelling (基本練習)](https://open.kattis.com/problems/t9spelling)
---
### [UVa 11223 (基本練習)](http://domen111.github.io/UVa-Easy-Viewer/?11223)
---
### [Kattis astrologicalsign](https://open.kattis.com/problems/astrologicalsign)
這一題就是課堂上講的判斷星座的題目，只要自己手動把表打出來就好。
最後再去用 for 迴圈判斷有沒有在範圍內。
:::spoiler 參考程式碼
```cpp=
```
:::
---
### [AtCoder abc075_b](https://atcoder.jp/contests/abc075/tasks/abc075_b)
撰寫者：Eason
這題要求每一格附近有多少個地雷，有兩種實作方法
- 第一種：找地雷所在的位置，把地雷周圍的座標計數加一
- 第二種：將每個位置的周圍都掃一遍，再將周圍地雷個數紀錄到該位置
以下會用第一種實作，其實不管哪一種方法，都是要用二維陣列實作，我們可以利用「將移動方向建表」來降低實作的複雜程度。
| (x, y) | -1 | 0 | 1 |
| :----: | :-----: | :-----: | :-----: |
| -1 | (-1, -1) | (0, -1) | (1, -1) |
| 0 | (-1, 0) | (0, 0) | (1, 0) |
| 1 | (-1, 1) | (0, 1) | (1, 1) |
將自己設為 (0, 0)，周圍的座標就可以像上表那樣表示，code 裡面的第 5、6 行就是將上表寫成程式碼的樣子。所以接下來我要找一個位置周圍的座標時，就可以用一個迴圈把 x_mv、y_mv 掃過一遍即可（第 27 行）。
這個實作技巧在之後的 BFS 會很常出現，學員務必要熟悉。
:::spoiler code
```cpp=
#include<iostream>
using namespace std;
// 八個方位的表示，可配合題解中的表格（由左而右，由上而下）
const int x_mv[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
const int y_mv[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
string g[55];
int ans[55][55];
int h, w;
bool in_scope (int a, int b){ // 檢查 a, b 是否超出範圍
return a >= 0 && a < h && b >= 0 && b < w;
}
int main(){
cin >> h >> w;
for (int i = 0; i < h; i++){
cin >> g[i];
}
for (int i = 0; i < h; i++){
for (int j = 0; j < w; j++){
if (g[i][j] == '#'){
ans[i][j] = -1;
for (int k = 0; k < 8; k++){
int ti = i + y_mv[k];
int tj = j + x_mv[k];
if (in_scope(ti, tj) && ans[ti][tj] != -1){
ans[ti][tj]++;
}
}
}
}
}
for (int i = 0; i < h; i++){
for (int j = 0; j < w; j++){
if (ans[i][j] == -1) cout << '#';
else cout << ans[i][j];
}
cout << '\n';
}
return 0;
}
```
:::
---
### [Kattis nineknights](https://hackmd.io/@sa072686/Kattis_nineknights)
撰寫者：Eason
解法跟 [AtCoder abc075_B](https://atcoder.jp/contests/abc075/tasks/abc075_b) 差不多，，稍微改一下表的內容，要記得多判斷 k 的數量。
:::spoiler code
```cpp=
#include<iostream>
using namespace std;
const int x_mv[8] = {-2, -1, 1, 2, -2, -1, 1, 2};
const int y_mv[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
string g[10];
bool in_scope (int a, int b){
return a >= 0 && a < 5 && b >= 0 && b < 5;
}
int main(){
for (int i = 0; i < 5; i++){
cin >> g[i];
}
bool is_valid = true;
int cnt = 0;
for (int i = 0; i < 5; i++){
for (int j = 0; j < 5; j++){
if (g[i][j] == 'k'){
cnt++;
for (int k = 0; k < 8; k++){
int ti = i + y_mv[k];
int tj = j + x_mv[k];
if (in_scope(ti, tj) && g[ti][tj] == 'k'){
is_valid = false;
}
}
}
}
}
if (is_valid && cnt == 9) cout << "valid\n";
else cout << "invalid\n";
return 0;
}
```
:::
---
### [AtCoder abc096_c (基本練習)](https://atcoder.jp/contests/abc096/tasks/abc096_c)
---
### [UVa 10500 (基本練習)](http://domen111.github.io/UVa-Easy-Viewer/?10500)
---
### [UVa 118 (延伸挑戰)](http://domen111.github.io/UVa-Easy-Viewer/?118)
---
### [ZJ k731](https://zerojudge.tw/ShowProblem?problemid=k731)
---
### [Kattis majstor (基本練習)](https://open.kattis.com/problems/majstor)
---
### [Kattis marko (延伸挑戰)](https://open.kattis.com/problems/marko)
---
### [Kattis soundex (延伸挑戰)](https://open.kattis.com/problems/soundex)
---
### [ZJ a020](https://zerojudge.tw/ShowProblem?problemid=a020)
撰寫者：Eason
將題目給的 A~Z 對應的數字建成表，然後就按照題目講得實作即可
:::spoiler code
```cpp=
#include<iostream>
using namespace std;
// A~Z 對應到的數字
int num[30] = {10, 11, 12, 13, 14, 15, 16, 17, 34, 18, 19, 20, 21, 22, 35, 23, 24, 25, 26, 27, 28, 29, 32, 30, 31, 33};
int main(){
string s;
cin >> s;
int idx = s[0] - 'A';
int sum = num[idx] / 10;
sum += (num[idx] % 10) * 9;
for (int i = 1; i <= 8; i++){
sum += (s[i] - '0') * (9 - i);
}
sum += s[9] - '0';
if (sum % 10) cout << "fake\n";
else cout << "real\n";
return 0;
}
```
:::
---
### [UVa 10082](http://domen111.github.io/UVa-Easy-Viewer/?10082)
---
### [Kattis goodmorning (延伸挑戰)](https://open.kattis.com/problems/goodmorning)
---
### [Kattis playfair (基本練習)](https://open.kattis.com/problems/playfair)
---
### [Kattis printingcosts (基本練習)](https://open.kattis.com/problems/printingcosts)
---
### [Kattis anewalphabet (基本練習)](https://open.kattis.com/problems/anewalphabet)
---
### [Kattis bela (基本練習)](https://open.kattis.com/problems/bela)
---
### [Kattis keylogger](https://open.kattis.com/problems/keylogger)
---
### [Kattis parentgap (基本練習)](https://open.kattis.com/problems/parentgap)
---
### [ZJ j123 (基本練習)](https://zerojudge.tw/ShowProblem?problemid=j123)
---
### [UVa 706 (延伸挑戰)](http://domen111.github.io/UVa-Easy-Viewer/?706)
---
### [Kattis tetris (延伸挑戰)](https://hackmd.io/@sa072686/Kattis_tetris)
---
### [Kattis queens (基本練習)](https://hackmd.io/@sa072686/Kattis_queens)
## 窮舉
### [ZJ b840](https://zerojudge.tw/ShowProblem?problemid=b840)
撰寫者：小麥
窮舉每個點當作左上角的起點，然後用兩層for迴圈窮舉所有子矩形的大小(長&寬) 再遍歷
所以最後程式長相會是有6個for迴圈包在一起
時間複雜度：$O(n^6)$
$n \leq 20$ 所以 $n^6$ 的計算量可以在 1 秒內跑完!
補充：
先用建立二維前綴和，在枚舉起點和終點。
時間複雜度：$O(n^2)$
:::spoiler 參考程式碼
```cpp=
#include <iostream>
using namespace std;
int nums[20][20];
int prefixSum[20 + 1][20 + 1];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> nums[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
prefixSum[i][j] = (prefixSum[i-1][j] - prefixSum[i-1][j-1]) + prefixSum[i][j-1] + nums[i-1][j-1];
}
}
int maxi = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int o = i; o <= n; o++) {
for (int k = j; k <= n; k++) {
int sum = prefixSum[o][k] - prefixSum[o][j-1] - prefixSum[i-1][k] + prefixSum[i-1][j-1];
if (sum > maxi) {
maxi = sum;
}
}
}
}
}
cout << maxi << '\n';
return 0;
}
```
:::
---
### [Kattis doggopher (基本練習)](https://hackmd.io/@sa072686/Kattis_doggopher)
---
### [ZJ f312](https://zerojudge.tw/ShowProblem?problemid=f312)
撰寫者：小麥
先從第一個工廠有最多的員工開始，第一個工廠-1，第二個工廠就+1，一直到第一個工廠到0為止
:::spoiler 參考程式碼
```cpp=
#include <iostream>
using namespace std;
int main() {
int A1, B1, C1;
int A2, B2, C2;
int n;
cin >> A1 >> B1 >> C1;
cin >> A2 >> B2 >> C2;
cin >> n;
int maxi = -1000000;
int left_pointer = n;
int right_pointer = 0;
while (right_pointer != n + 1) {
int Y1 = A1 * (left_pointer * left_pointer) + B1 * left_pointer + C1;
int Y2 = A2 * (right_pointer * right_pointer) + B2 * right_pointer + C2;
int sum = Y1 + Y2;
if (maxi < sum) {
maxi = sum;
}
left_pointer--;
right_pointer++;
}
cout << maxi << '\n';
return 0;
}
```
:::
---
### [UVa 100 (基本練習)](http://domen111.github.io/UVa-Easy-Viewer/?100)
---
### [Kattis bubbletea (基本練習)](https://open.kattis.com/problems/bubbletea)
撰寫者：fishhh
這個問題要解決的是，在給定一定金額的情況下，最多能夠邀請多少位學生參加奶茶派對。
奶茶店提供多種茶和配料，每種都有不同的價格，但不是每種茶和配料的組合都是合法的。
- 一杯奶茶的價格等於茶的價格加上配料的價格。
- 一個學生只能喝一杯奶茶，且每杯奶茶都只能搭配一種茶和一種配料。
- **不是每種茶都能與所有的配料搭配，這會在輸入的時候給。**
- PVH首先要為自己買一杯奶茶。
例如：
```
3
10 20 30
5
1 2 3 4 5
1 4 5
2 1 3 5
3 1 2 4
42
```
表示有三種茶，價格分別是 10、20 和 30；有五種配料，價格分別是 1、2、3、4 和 5。接下來的信息表示：
- 第一種茶可以搭配第四和第五種配料。
- 第二種茶可以搭配第一、第三和第五種配料。
- 第三種茶可以搭配第一、第二和第四種配料。
- PVH有42元，問題是他最多能夠為多少位學生購買奶茶。在這個例子中，可以發現最便宜的組合是第一種茶搭配第四種配料，總價14。這樣PVH還剩下28元，他可以再為兩位學生購買奶茶，因此答案是3。
:::spoiler 參考程式碼
```cpp=
#include<iostream>
using namespace std;
int main(){
int sm=999,g,k,i,n,m,money,tea[2000],topping[2000];
cin>>n;
for(i=0;i<n;i++){
cin>>tea[i];
}
cin>>m;
for(i=0;i<m;i++){
cin>>topping[i];
}
for(i=0;i<n;i++){
cin>>k;
while(k--){
cin>>g;
g--;
if(topping[g]+tea[i]<sm)sm=topping[g]+tea[i];
}
}
cin>>money;
if(money/sm==0){
cout<<0;
return 0;
}
cout<<money/sm-1<<"\n";
}
```
:::
---
### [ZJ f606](https://zerojudge.tw/ShowProblem?problemid=f606)
撰寫者：fishhh
這一題可能需要讀懂他的題意?
那就是方案總花費為每個伺服器傳送到每個城市的加總
直接按題目要求處理即可
因為第$i$個伺服器要傳到城市$j$的流量(也就是$Q[i][j]$)是固定的，所以先把它存起來
而每一個方案會有不同配置方式，所以每一個方案計算需要的總花費，最後再取最小值即可
:::spoiler 參考程式碼
```cpp=
#include "iostream"
using namespace std;
#define int long long
signed main(){
int n,m,k;
int q[51][51]={};
cin>>n>>m>>k;
for(int y=0;y<n;y++){
for(int x=0;x<m;x++){
cin>>q[x][y];
}
}
int minn=1e9;
while(k--){
int ans=0;
int sum[60][60]={};
int l;
for(int i=0;i<n;i++){
cin>>l;
for(int v=0;v<m;v++){
sum[l][v]+=q[v][i];
}
}
for(int y=0;y<m;y++){
for(int x=0;x<m;x++){
if(x==y){
ans+=sum[x][y];
}
else if(sum[x][y]<=1000){
ans+=sum[x][y]*3;
}
else{
ans+=3000;
ans+=(sum[x][y]-1000)*2;
}
}
}
// cout<<ans<<" ";
minn= min(minn,ans);
}
cout<<minn;
}
```
:::
---
### [Kattis refrigerator (基本練習)](https://open.kattis.com/problems/refrigerator)
---
### [Kattis damagedequation (基本練習)](https://open.kattis.com/problems/damagedequation)
---
### [Kattis icpcawards (基本練習)](https://open.kattis.com/problems/icpcawards)
---
### [AtCoder abc216_b](https://hackmd.io/@sa072686/AtCoder_abc216_b)
撰寫者：fishhh
透過兩個迴圈來枚舉是否有兩個人的名字和姓氏相同，需要注意到 for 迴圈會不會枚舉到相同的兩個人。
:::spoiler 參考程式碼
```cpp=
#include "iostream"
using namespace std;
string s[1010],t[1010];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i]>>t[i];
}
bool yes = 0;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(s[i]==s[j]&&t[i]==t[j]){
yes = 1;
}
}
}
if(yes==1){
cout<<"Yes\n";
}
else{
cout<<"No\n";
}
}
```
:::
---
### [Kattis musicalscales (延伸挑戰)](https://open.kattis.com/problems/musicalscales)
---
### [Kattis dodecaphony](https://hackmd.io/@sa072686/Kattis_dodecaphony)
---
### [Kattis geneticsearch (基本練習)](https://open.kattis.com/problems/geneticsearch)
---
### [UVa 12289 (基本練習)](http://domen111.github.io/UVa-Easy-Viewer/?12289)
---
### [UVa 608](http://domen111.github.io/UVa-Easy-Viewer/?608)
---
### [Kattis klockan2 (延伸挑戰)](https://open.kattis.com/problems/klockan2)
---
### [UVa 11059](http://domen111.github.io/UVa-Easy-Viewer/?11059)
---
### [UVa 626 (基本練習)](http://domen111.github.io/UVa-Easy-Viewer/?626)
---
### [UVa 11236 (延伸挑戰)](http://domen111.github.io/UVa-Easy-Viewer/?11236)
---
### [UVa 592 (延伸挑戰)](https://hackmd.io/@sa072686/UVa_592)
---
### [Kattis odds (基本練習)](https://hackmd.io/@sa072686/Kattis_odds)
---
### [AtCoder abc207_c (基本練習)](https://hackmd.io/@sa072686/AtCoder_abc207_c)
---
### [AtCoder abc112_c (延伸挑戰)](https://atcoder.jp/contests/abc112/tasks/abc112_c)
---
### [Kattis lektira](https://hackmd.io/@sa072686/Kattis_lektira)
---
### [Kattis names (基本練習)](https://open.kattis.com/problems/names)
---
### [Kattis peg (延伸挑戰)](https://open.kattis.com/problems/peg)
---
### [Kattis glitchbot](https://hackmd.io/@sa072686/Kattis_glitchbot)
## 模擬
### [UVa 127 (延伸挑戰)](http://domen111.github.io/UVa-Easy-Viewer/?127)
---
### [Kattis traveltheskies (基本練習)](https://open.kattis.com/problems/traveltheskies)
---
### [Kattis acm (基本練習)](https://open.kattis.com/problems/acm)
---
### [ZJ e287](https://zerojudge.tw/ShowProblem?problemid=e287)
---
### [ZJ h081](https://zerojudge.tw/ShowProblem?problemid=h081)
撰寫者：fishhh
根據題意模擬。可以稍微注意一下要如何記錄目前手中持有股票的狀態。
:::spoiler
```cpp=
#include <iostream>
using namespace std;
int main() {
int n, D;
cin >> n >> D;
int a[n];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int x = a[0], y = 0;
int ans = 0;
for (int i = 1; i < n; i++) {
if (x != -1) {
//有股票
if (a[i] >= x + D) {
ans += a[i] - x; //獲利
x = -1; //清空持股
y = a[i]; //紀錄上一次的賣出價格
}
} else {
//沒有股票
if (a[i] <= y - D) {
x = a[i]; //買進股票的價格
}
}
}
cout << ans << "\n";
return 0;
}
```
:::
---
### [Kattis keytocrypto](https://open.kattis.com/problems/keytocrypto)
---
### [UVa 151 (基本練習)](http://domen111.github.io/UVa-Easy-Viewer/?151)
---
### [UVa 133 (基本練習)](http://domen111.github.io/UVa-Easy-Viewer/?133)
---
### [ZJ h082 (基本練習)](https://zerojudge.tw/ShowProblem?problemid=h082)
---
### [Kattis coconut (延伸挑戰)](https://open.kattis.com/problems/coconut)
---
### [ZJ f580 (延伸挑戰)](https://zerojudge.tw/ShowProblem?problemid=f580)
---
### [Kattis coffeecupcombo](https://open.kattis.com/problems/coffeecupcombo)
---
### [ZJ g596 (基本練習)](https://zerojudge.tw/ShowProblem?problemid=g596)
---
### [Kattis ferryloading4](https://open.kattis.com/problems/ferryloading4)
---
### [ZJ c297 (基本練習)](https://zerojudge.tw/ShowProblem?problemid=c297)
---
### [Kattis turtlemaster](https://hackmd.io/@sa072686/Kattis_turtlemaster)
---
### [UVa 10443 (基本練習)](http://domen111.github.io/UVa-Easy-Viewer/?10443)
---
### [ZJ f313](https://zerojudge.tw/ShowProblem?problemid=f313)
撰寫者：fishhh
記得開兩個陣列來進行模擬，一個是目前的狀態，一個是未來的狀態。
在一個回合結束後再把未來的狀態取代掉目前的狀態。
:::spoiler
```cpp=
#include<iostream>
using namespace std;
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
int main(){
fastio;
int r,c,k,m;
int num[51][51]={0},tmp[51][51]={0};
cin>>r>>c>>k>>m;
for(int x=0;x<r;x++){
for(int y=0;y<c;y++){
cin>>num[x][y];
}
}
for(int i=0;i<m;i++){
for(int y=0;y<r;y++){
for(int x=0;x<c;x++){
tmp[y][x]=(num[y][x]>=0)*(num[y][x]/k);
}
}
for(int x=0;x<r;x++){
for(int y=0;y<c;y++){
if(num[x][y]==-1){
continue;
}
if(x==0){
num[x][y]+=tmp[x+1][y];
num[x+1][y]-=tmp[x+1][y];
}
else if(x==r){
num[x][y]+=tmp[x-1][y];
num[x-1][y]-=tmp[x-1][y];
}
else{
num[x][y]+=tmp[x+1][y];
num[x+1][y]-=tmp[x+1][y];
num[x][y]+=tmp[x-1][y];
num[x-1][y]-=tmp[x-1][y];
}
if(y==0){
num[x][y]+=tmp[x][y+1];
num[x][y+1]-=tmp[x][y+1];
}
else if(y==c){
num[x][y]+=tmp[x][y-1];
num[x][y-1]-=tmp[x][y-1];
}
else{
num[x][y]+=tmp[x][y+1];
num[x][y+1]-=tmp[x][y+1];
num[x][y]+=tmp[x][y-1];
num[x][y-1]-=tmp[x][y-1];
}
}
}
}
int big=0,small=999;
for(int x=0;x<r;x++){
for(int y=0;y<c;y++){
if(num[x][y]>big){
big=num[x][y];
}
if(num[x][y]<small&&num[x][y]!=-1){
small=num[x][y];
}
}
}
cout<<small<<endl<<big;
}
```
:::
---
### [ZJ g276 (基本練習)](https://zerojudge.tw/ShowProblem?problemid=g276)
Sign in with Wallet
Connect another wallet