p1. 購物車#
Solution#
對於每個客人都去紀錄商品 \(a\) 跟 \(b\) 的增減狀況就好，其他商品可以直接丟掉不管。
AC code
signed main() {
hyper;
int a, b, n, cnt = 0;
cin >> a >> b >> n;
rep(i,0,n) {
int x, af = 0, bf = 0;
while(cin >> x && x != 0) {
if(abs(x) == a) af += x;
else if(abs(x) == b) bf += x;
}
if(af > 0 && bf > 0) ++cnt;
}
cout << cnt << '\n';
}
p2. 骰子#
Solution#
開個 struct 直接模擬就好。
AC code
struct Dice {
int f, b, l, r, u, d;
Dice(): f(4), b(3), l(5), r(2), u(1), d(6) {}
void rollF() { int t=f; f=u; u=b; b=d; d=t; }
void rollR() { int t=r; r=u; u=l; l=d; d=t; }
};
signed main() {
hyper;
int n, m, x, y;
Dice a[21];
cin >> n >> m;
while(m--) {
cin >> x >> y;
if(y == -1) a[x].rollF();
else if(y == -2) a[x].rollR();
else swap(a[x], a[y]);
}
rep1(i,1,n) cout << a[i].u << ' ';
cout << '\n';
}
p3. 圓環出口#
Solution#
這題要快速的找到下一個停留的位置，所以直接模擬肯定會 TLE。下一個停留的位置其實就是要從目前位置開始的前綴和找 \(\ge q\) 的最小值，直接做二分搜就可以了。另外，因為他是環狀的，一種簡單的處理方式是把陣列複製一份接在後面，變成總長度 \(2n\) 的新陣列，再對這個新陣列做一樣的事情，這樣可以確保在 wrap 回 index 0 的時候還是可以處理好連續的資訊（前綴和）。時間複雜度 \(O(m \log n)\)
AC code
int search(int a[], int l, int r, int t, int pos) {
while(l < r) {
int m = (l+r)/2;
if(a[m]-a[pos-1] < t) l = m+1;
else r = m;
}
return l;
}
signed main() {
hyper;
int n, m, p[MN];
cin >> n >> m;
rep(i,0,n) cin >> p[i];
int ps[MN*2]; ps[0] = 0;
rep1(i,1,n) ps[i] = ps[i-1] + p[i-1];
rep1(i,1,n) ps[n+i] = ps[n+i-1] + p[i-1];
int pos = 1;
while(m--) {
int q; cin >> q;
int r = search(ps, pos, n*2, q, pos);
pos = r % n + 1;
}
cout << pos-1 << '\n';
}
p4. 病毒演化#
Solution#
這題看起來一臉樹上 dp，想一下會發現字串的每個位置其實是獨立的，所以可以分開做，只要一次處理一個字元。定義狀態 \(dp(i, j)\) 表示節點 \(i\) 是字元 \(j \in \{A, U, C, G\}\) 時，以 \(i\) 為根的子樹的答案。轉移的時候固定 \(j\)，從每個小孩四個可能字元挑最小的加總（為了方便，如果字元是固定的就把其他不可能的字元答案設成 \(\infty\) 這樣就一定不會選到）。時間複雜度 \(O(mn)\)。
AC code
int dp[MN][4], mpn[128];
vector<int> e[MN];
string s[MN];
void dfs(int u, int t) {
rep(i,0,4) dp[u][i] = 0;
if(s[u][t] != '@') {
rep(i,0,4) {
if(mpn[s[u][t]] == i) continue;
dp[u][i] = INF;
}
}
if(e[u].size() == 0) return;
for(int v: e[u]) {
dfs(v, t);
rep(i,0,4) {
int mn = INF;
rep(j,0,4) mn = min(mn, dp[v][j] + (i!=j));
dp[u][i] += mn;
}
}
}
signed main() {
hyper;
mpn['A'] = 0, mpn['U'] = 1, mpn['C'] = 2, mpn['G'] = 3;
int n, m, u, v, root, ans = 0;
cin >> n >> m;
rep(i,0,n) {
cin >> u >> v;
if(u == v) root = u;
else e[v].push_back(u);
cin >> s[u];
}
rep(i,0,m) {
dfs(root, i);
ans += min({dp[root][0], dp[root][1], dp[root][2], dp[root][3]});
}
cout << ans << '\n';
}