---
# System prepended metadata

title: DDJ a601 ~ a700
tags: [編號]

---

##### 遇到好漂亮的題目~~或是莫名其妙的題目~~再打，不然等我有空再說。

:::info
`水` : 水題，或是莫名其妙的題目。
`典` : 相關內容是經典題目。
`好` : 好題，對於該內容有好的引導或實作，或著是寫的方法超漂亮。
`初` : 適合剛接觸該內容的解題者。
`進` : 該題在運用相關內容時相對進階。
:::

如果沒有標就代表他不再上述內容，**但這不代表他是破題**。
##### 對於定義的方式本文作者有最終解釋權。

---

# `水` [a660: 春香信仰](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a660)

如果你還沒看提敘，恭喜你，少浪費了時間。

我直接放 $AC \; code$。

```cpp
#include<iostream>
using namespace std ;
int main(){
	cout << "0403" ;
}
```

# `初` [a681: B. 吳乙己](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a681)

單純的前綴和，不會的可以看[這裡](https://hackmd.io/@PoteLiu/Skqat6htJg)。

不過要注意一個點，因為把 $t$ 給加總，他有機率超過 `int` 的範圍，所以要改用 `long long` 。

### 補充
這樣 :
```cpp=
int arr[n] ;
int pre[n + 1] = { } ; 

for(int i = 0 ; i < n ; i++){
    cin >> arr[i]  ;
}
    
for (int i = 1 ; i <= n ; i++) {
    pre[i] = pre[i - 1] + arr[i - 1] ;
}
```

可以合併這樣 :
```cpp=
int arr[n] ;
int pre[n + 1] = { } ;

for (int i = 1 ; i <= n ; i++) {
    cin >> arr[i - 1] ;
    pre[i] = pre[i - 1] + arr[i - 1] ;
}
```

還可以優化成這樣，減少記憶體的消耗 :
```cpp=
int pre[n + 1] = {} ;

for (int i = 1 ; i <= n ; i++) {
    cin >> t ;
    pre[i] = pre[i - 1] + t ;
}
```

# `好` [a695: C. 一筆畫問題](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a695)

這題其實在考圖論 ---- 歐拉路徑的概念。

關於他的定義，其實提示也有寫了。

1. 通過所有的點且一筆畫。
2. 有 $0$ 個或 $2$ 個點的度是奇數。（度指的是每個點有幾條邊連到它。）

因此可以知道，有0個點是奇度，他會回到原點 ; 有2個點是奇度，他的起終點不同 ; 有大於 $2$個奇度，無法一筆畫完。

---

畫圖應該比較好理解。

### 0個點是奇度
```mediawiki
1 ─── 2
|     |
|     |
4 ─── 3
```
每點皆有兩條邊，可以一筆畫完且回到原點。

### 2個點是奇度
```mediawiki
1 - 2 - 3 - 4 - 5
```
$1$、$5$ 為奇度，其餘皆為偶度，可以一筆畫完且起終點不同。

### 大於2個點是奇度
```mediawiki
1-2   3-4
```
四點皆為奇度，不能一筆畫完。

---

因此最直觀的作法就是把每點 $x,y$ 放進去時，把該位置的陣列加一，最後遍歷判斷每點是否為奇數，再判斷奇數點是否為 $0$ 或 $1$ ，然後輸出 `yes` 或 `no`。

# 

