owned this note
owned this note
Published
Linked with GitHub
# APCS 2025/06
>C++ 版本由我本人 @Yilin0121 撰寫
>Python 版本由 @Chuen666666 提供
## [1. 小心陷阱](https://zerojudge.tw/ShowProblem?problemid=q836)
### 思路
我們每次都會走k步，當k <= 0時就會結束，所以我們可以用while迴圈來寫，只要k > 0就重複執行，只要我們現在的位置是x1或x2的倍數，k就減掉y1或y2，最後算出的位置就是答案
### 完整程式碼
#### C++
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const long long INF = numeric_limits<int>::max();
int main() {
int k, x1, y1, x2, y2;
cin >> k >> x1 >> y1 >> x2 >> y2;
int now = k;
while (k > 0) {
if (now % x1 == 0) k -= y1;
if (now % x2 == 0) k -= y2;
now += max(0, k);
}
cout << now;
}
```
#### Python
```python=
k = int(input())
x1, y1 = map(int, input().split())
x2, y2 = map(int, input().split())
i = 0
while k > 0:
i += k
if i % x1 == 0:
k -= y1
if i % x2 == 0:
k -= y2
print(i)
```
## [2. 轉盤得分](https://zerojudge.tw/ShowProblem?problemid=q837)
### 思路
記下每個字串的開始位置，扣掉每次的轉動距離，就是新的起點。
:::info
C++的要特別注意善用(((i + pos[j]) % n) + n) % n，不然有可能是負數而Run-time error
:::
### 完整程式碼
#### C++
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const long long INF = numeric_limits<int>::max();
int main() {
int m, n, k;
cin >> m >> n >> k;
vector<string> s(m);
for (auto &x : s) cin >> x;
vector<int> pos(m, 0);
int ans = 0;
while (k--) {
for (int i = 0;i < m;i++) {
int x;
cin >> x;
pos[i] -= x;
}
for (int i = 0;i < n;i++) {
int a[26] = {}, MAX = 0;
for (int j = 0;j < m;j++) {
MAX = max(MAX, ++a[s[j][(((i + pos[j]) % n) + n) % n] - 'a']);
}
ans += MAX;
}
}
cout << ans;
}
```
#### Python
```python=
from collections import Counter
m, n, k = map(int, input().split())
s = [input().strip() for _ in range(m)]
pos = [0] * m
total = 0
for _ in range(k):
shifts = list(map(int, input().split()))
for i in range(m):
pos[i] -= shifts[i]
for i in range(n):
chars = [s[j][(i + pos[j]) % n] for j in range(m)]
count = Counter(chars)
total += max(count.values())
print(total)
```
## [3. 貪心闖關](https://zerojudge.tw/ShowProblem?problemid=q838)
### 思路
我們用一個維持「嚴格遞減」的棧來模擬每次搬最小再把沙包加到右邊的過程:對於每個關卡的沙包數x，只要棧頂w≤x就表示它是當前最小的，按題意要先搬空它(把w加到答案)，並把這批沙包累加到 x；反覆彈棧直到棧頂>x。此時，若合併後的x還不超過限制t，就把它當作新棧頂壓進棧中，保持棧的遞減性。全部讀完後，把棧中剩餘的沙包數一次性加到答案即得最終結果。
### 完整程式碼
#### C++
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int long long
const long long INF = numeric_limits<int>::max();
signed main() {
IO
int n, t;
cin >> n >> t;
vector<int> st;
int ans = 0;
for (int i = 0;i < n;i++) {
int x;
cin >> x;
while (!st.empty() and st.back() <= x) {
ans += st.back();
x += st.back();
st.pop_back();
}
if (x <= t) st.push_back(x);
}
for (auto x : st) ans += x;
cout << ans;
}
```
#### Python
```python=
n, t = map(int, input().split())
st = []
ans = 0
for _ in range(n):
x = int(input())
while st and st[-1] <= x:
ans += st[-1]
x += st[-1]
st.pop()
if x <= t:
st.append(x)
print(ans + sum(st))
```
## [4. 分組遊戲](https://zerojudge.tw/ShowProblem?problemid=q839)
### 思路
我們先把整張圖畫出來，每個點之間都會有距離，那我們只要遍歷每個點，只要與其中一個點的距離小於m我們就把他們歸類為同一組，嘗試最多可以分成幾組，只要分出的組別大於k，代表可以成功地分出k組，所以我們只需要二分搜出m，就可以算出答案。
### 完整程式碼
#### C++
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const long long INF = numeric_limits<int>::max();
int n, k;
vector<vector<pair<int, int>>> v;
bool f(int m) {
bitset<505> vis;
int cnt = 0;
for (int i = 1;i <= n;i++) {
if (vis[i]) continue;
queue<int> q;
cnt++;
q.push(i);
while (!q.empty()) {
auto t = q.front();
q.pop();
for (auto [nt, x] : v[t]) {
if (vis[nt]) continue;
if (x >= m) continue;
vis[nt] = 1;
q.push(nt);
}
}
}
return cnt >= k;
}
int main() {
IO
cin >> n >> k;
v.resize(n + 1);
int l = INF, r = 0, ans;
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= n;j++) {
int x;
cin >> x;
if (i != j) v[i].push_back({j, x});
r = max(r, x);
l = min(l, x);
}
}
while (l <= r) {
int m = (l + r) / 2;
if (f(m)) {
l = m + 1;
ans = m;
}
else r = m - 1;
}
cout << ans;
}
```
#### Python
```python=
from collections import deque
def f(m):
vis = [False] * (n + 1)
cnt = 0
for i in range(1, n + 1):
if vis[i]: continue
cnt += 1
q = deque([i])
while q:
t = q.popleft()
for nt, x in v[t]:
if vis[nt] or x >= m: continue
vis[nt] = True
q.append(nt)
return cnt >= k
n, k = map(int, input().split())
v = [[] for _ in range(n+1)]
l = float('inf')
r = 0
for i in range(1, n+1):
row = list(map(int, input().split()))
for j in range(1, n+1):
x = row[j-1]
if i != j:
v[i].append((j, x))
r = max(r, x)
l = min(l, x)
ans = -1
while l <= r:
m = (l+r) // 2
if f(m):
ans = m
l = m + 1
else:
r = m - 1
print(ans)
```
Google Drive
Gist
Clipboard
Sign in with Wallet
