February 24, 2025
最近在玩《逆转裁判》，在iOS上买了合集 Ace Attorney Trilogy（花了我$24.99大洋呢，今天降到$14.99了）。虽然画面重绘过了，高清了不少，官方中文版也加入了中文语音(异议!)，但本人不太喜欢搓玻璃，所以又开始倒腾模拟器，手上有周哥的RG35XX H和RG556（悄悄说RG34XX还在路上，不过它就不用遮罩了）。给556做了个遮罩（其实就是张图片，PS水平实在有限），应该也适用于其他1920×1080，GBA 6倍点对点的屏幕，只考虑掌机，所以没有加按钮，喜欢的可以自行拿走。
效果预览
Update: 2/24/2025
1-3终于全部通关了，最后一个故事太精彩了！送上几幅截屏，给这段旅程画上一个顿号。
Alice and Bob take turns playing a game, with Alice starting first.
There are n stones arranged in a row. On each player’s turn, while the number of stones is more than one, they will do the following:
x > 1, and remove the leftmost x stones from the row.The game stops when only one stone is left in the row.
The score difference between Alice and Bob is (Alice's score - Bob's score). Alice’s goal is to maximize the score difference, and Bob’s goal is the minimize the score difference.
Given an integer array stones of length n where stones[i] represents the value of the ith stone from the left, return the score difference between Alice and Bob if they both play optimally.
Example 1:
Input: stones = [-1,2,-3,4,-5] Output: 5 Explanation: - Alice removes the first 4 stones, adds (-1) + 2 + (-3) + 4 = 2 to her score, and places a stone of value 2 on the left. stones = [2,-5]. - Bob removes the first 2 stones, adds 2 + (-5) = -3 to his score, and places a stone of value -3 on the left. stones = [-3]. The difference between their scores is 2 - (-3) = 5.
Example 2:
Input: stones = [7,-6,5,10,5,-2,-6] Output: 13 Explanation: - Alice removes all stones, adds 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 to her score, and places a stone of value 13 on the left. stones = [13]. The difference between their scores is 13 - 0 = 13.
Example 3:
Input: stones = [-10,-12] Output: -22 Explanation: - Alice can only make one move, which is to remove both stones. She adds (-10) + (-12) = -22 to her score and places a stone of value -22 on the left. stones = [-22]. The difference between their scores is (-22) - 0 = -22.
Constraints:
n == stones.length2 <= n <= 105-104 <= stones[i] <= 104
Note: Naive DP (min-max) takes O(n2) which leads to TLE. The key of this problem is that each player takes k stones, but put their sum back as a new stone, so you can assume all the original stones are still there, but opponent has to start from the k+1 th stone.
Let dp[i] denote the max score diff that current player can achieve by taking stones[0~i] (or equivalent)
dp[n-1] = sum(A[0~n-1]) // Alice takes all the stones.
dp[n-2] = sum(A[0~n-2]) – (A[n-1] + sum(A[0~n-2])) = sum(A[0~n-2]) – dp[n-1] // Alice takes n-1 stones, Bob take the last one (A[n-1]) + put-back-stone.
dp[n-3] = sum(A[0~n-3]) – max(dp[n-2], dp[n-1]) // Alice takes n-2 stones, Bob has two options (takes n-1 stones or takes n stones)
…
dp[0] = A[0] – max(dp[n-1], dp[n-1], …, dp[1]) // Alice takes the first stone, Bob has n-1 options.
Time complexity: O(n)
Space complexity: O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua class Solution { public: int stoneGameVIII(vector<int>& stones) { const int n = stones.size(); for (int i = 1; i < n; ++i) stones[i] += stones[i - 1]; int ans = stones.back(); // take all the stones. for (int i = n - 2; i > 0; --i) ans = max(ans, stones[i] - ans); return ans; } }; |
Alice and Bob take turns playing a game, with Alice starting first.
There are n stones arranged in a row. On each player’s turn, they can remove either the leftmost stone or the rightmost stone from the row and receive points equal to the sum of the remaining stones’ values in the row. The winner is the one with the higher score when there are no stones left to remove.
Bob found that he will always lose this game (poor Bob, he always loses), so he decided to minimize the score’s difference. Alice’s goal is to maximize the difference in the score.
Given an array of integers stones where stones[i] represents the value of the ith stone from the left, return the difference in Alice and Bob’s score if they both play optimally.
Example 1:
Input: stones = [5,3,1,4,2] Output: 6 Explanation: - Alice removes 2 and gets 5 + 3 + 1 + 4 = 13 points. Alice = 13, Bob = 0, stones = [5,3,1,4]. - Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4]. - Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4]. - Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4]. - Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = []. The score difference is 18 - 12 = 6.
Example 2:
Input: stones = [7,90,5,1,100,10,10,2] Output: 122
Constraints:
n == stones.length2 <= n <= 10001 <= stones[i] <= 1000
For a sub game of stones[l~r] game(l, r), we have two choices:
Remove the left one: sum(stones[l + 1 ~ r]) – game(l + 1, r)
Remove the right one: sum(stones[l ~ r – 1]) – game(l, r – 1)
And take the best choice.
Time complexity: O(n^2)
Space complexity: O(n^2)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: int stoneGameVII(vector<int>& A) { const int n = A.size(); vector<vector<int>> cache(n, vector<int>(n, INT_MAX)); function<int(int, int, int)> dp = [&](int l, int r, int s) { if (l >= r) return 0; if (cache[l][r] == INT_MAX) cache[l][r] = max(s - A[r] - dp(l, r - 1, s - A[r]), s - A[l] - dp(l + 1, r, s - A[l])); return cache[l][r]; }; return dp(0, n - 1, accumulate(begin(A), end(A), 0)); } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: int stoneGameVII(vector<int>& A) { const int n = A.size(); vector<int> s(n + 1); for (int i = 0; i < n; ++i) s[i + 1] = s[i] + A[i]; vector<vector<int>> dp(n, vector<int>(n, 0)); for (int c = 2; c <= n; ++c) for (int l = 0, r = l + c - 1; r < n; ++l, ++r) dp[l][r] = max(s[r + 1] - s[l + 1] - dp[l + 1][r], s[r] - s[l] - dp[l][r - 1]); return dp[0][n - 1]; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
# Author: Huahua class Solution: def stoneGameVII(self, stones: List[int]) -> int: n = len(stones) s = [0] * (n + 1) for i in range(n): s[i + 1] = s[i] + stones[i] dp = [[0] * n for _ in range(n)] for c in range(2, n + 1): for l in range(0, n - c + 1): r = l + c - 1 dp[l][r] = max(s[r + 1] - s[l + 1] - dp[l + 1][r], s[r] - s[l] - dp[l][r - 1]) return dp[0][n - 1] |
Alice and Bob take turns playing a game, with Alice starting first.
There are n stones in a pile. On each player’s turn, they can remove a stone from the pile and receive points based on the stone’s value. Alice and Bob may value the stones differently.
You are given two integer arrays of length n, aliceValues and bobValues. Each aliceValues[i] and bobValues[i] represents how Alice and Bob, respectively, value the ith stone.
The winner is the person with the most points after all the stones are chosen. If both players have the same amount of points, the game results in a draw. Both players will play optimally.
Determine the result of the game, and:
1.-1.0.Example 1:
Input: aliceValues = [1,3], bobValues = [2,1] Output: 1 Explanation: If Alice takes stone 1 (0-indexed) first, Alice will receive 3 points. Bob can only choose stone 0, and will only receive 2 points. Alice wins.
Example 2:
Input: aliceValues = [1,2], bobValues = [3,1] Output: 0 Explanation: If Alice takes stone 0, and Bob takes stone 1, they will both have 1 point. Draw.
Example 3:
Input: aliceValues = [2,4,3], bobValues = [1,6,7] Output: -1 Explanation: Regardless of how Alice plays, Bob will be able to have more points than Alice. For example, if Alice takes stone 1, Bob can take stone 2, and Alice takes stone 0, Alice will have 6 points to Bob's 7. Bob wins.
Constraints:
n == aliceValues.length == bobValues.length1 <= n <= 1051 <= aliceValues[i], bobValues[i] <= 100Sort by the sum of stone values.
Time complexity: O(nlogn)
Space complexity: O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public: int stoneGameVI(vector<int>& A, vector<int>& B) { const int n = A.size(); vector<pair<int, int>> s(n); for (int i = 0; i < n; ++i) s.emplace_back(A[i] + B[i], i); sort(rbegin(s), rend(s)); int ans = 0; for (int i = 0; i < n; ++i) { int idx = s[i].second; ans += (i & 1 ? B[idx] : A[idx]) * (i & 1 ? -1 : 1); } return ans < 0 ? -1 : (ans > 0); } }; |
Alice and Bob take turns playing a game, with Alice starting first.
Initially, there are n stones in a pile. On each player’s turn, that player makes a move consisting of removing any non-zero square number of stones in the pile.
Also, if a player cannot make a move, he/she loses the game.
Given a positive integer n. Return True if and only if Alice wins the game otherwise return False, assuming both players play optimally.
Example 1:
Input: n = 1 Output: true Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.
Example 2:
Input: n = 2 Output: false Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).
Example 3:
Input: n = 4 Output: true Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).
Example 4:
Input: n = 7 Output: false Explanation: Alice can't win the game if Bob plays optimally. If Alice starts removing 4 stones, Bob will remove 1 stone then Alice should remove only 1 stone and finally Bob removes the last one (7 -> 3 -> 2 -> 1 -> 0). If Alice starts removing 1 stone, Bob will remove 4 stones then Alice only can remove 1 stone and finally Bob removes the last one (7 -> 6 -> 2 -> 1 -> 0).
Example 5:
Input: n = 17 Output: false Explanation: Alice can't win the game if Bob plays optimally.
Constraints:
1 <= n <= 10^5Let win(n) denotes whether the current play will win or not.
Try all possible square numbers and see whether the other player will lose or not.
win(n) = any(win(n – i*i) == False) ? True : False
base case: win(0) = False
Time complexity: O(nsqrt(n))
Space complexity: O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution { public: bool winnerSquareGame(int n) { vector<int> cache(n + 1, 0); // 0:Unknown, 1:Win, -1:Lose function<int(int)> win = [&](int n) -> int { if (n == 0) return -1; if (cache[n]) return cache[n]; for (int i = sqrt(n); i >= 1; --i) if (win(n - i * i) < 0) return cache[n] = 1; return cache[n] = -1; }; return win(n) > 0; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Solution { private int[] cache; public boolean winnerSquareGame(int n) { this.cache = new int[n + 1]; return this.win(n) > 0; } private int win(int n) { if (n == 0) return -1; if (this.cache[n] != 0) return this.cache[n]; for (int i = (int)Math.sqrt(n); i >= 1; --i) if (win(n - i * i) < 0) return this.cache[n] = 1; return this.cache[n] = -1; } } |
|
1 2 3 4 5 6 7 8 9 10 |
class Solution: def winnerSquareGame(self, n: int) -> bool: dp = [None] * (n + 1) dp[0] = False for i in range(0, n): if dp[i]: continue for j in range(1, n + 1): if i + j * j > n: break dp[i + j * j] = True return dp[n] |