You are trying to purchase a car and will be visiting a number of locations N (represented as points), each labeled i (1 ≤ i ≤ N). There are M roads connecting the points together, and road j (1 ≤ j ≤ M) of length d_j bidirectionally connects points u_j and v_j.
The car comes with a fuel tank that has a capacity of L, moving 1 unit of distance for every 1 unit of fuel it expends.
Some of the points have a gas station. g_i = 1 if there is a gas station at point i, and g_i = 0 if there is no gas station. If you reach a point with a gas station without running out of fuel you are able to fill up your car's tank. (If you run out of fuel just as you reach a point with a gas station, you can still fill up.) If you run out of gas before reaching a gas station then you have no option but to call a tow truck to transport your vehicle.
You reside at location 1, which has a gas station. Your challenge is to create a program that computes the number of locations you can visit without running out of fuel. You must also return home at the end of the journey. You are free to take whichever path you like in order to reach a destination and to refuel at any particular gas station however many times you like.
Function Description
Complete the function computeNumberOfLocations in the editor.
computeNumberOfLocations has the following parameters:
-
N: an integer, the number of locations
-
M: an integer, the number of roads
-
L: an integer, the fuel tank capacity
-
int g[N]: an array of integers indicating the presence of gas stations
-
int roads[M][2]: a 2D array of integers where each element is a pair of integers representing a road Returns int: the number of locations you can visit without running out of fuel
Constraints
1 ≤ N, M ≤ 100000, integer1 ≤ L ≤ 10⁹, integerg_i is 0 or 1 (1 ≤ i ≤ N) -> g_i = 1 indicates that there is a gas station at point i;;; -> g_i = 0 indicates that there is NOT a gas station at point iu_j ≤ v_j + 1 (1 ≤ j ≤ M - 1), integer1 ≤ u_j Roads are on a straight line. put differently: M = N - 1, u_j = j, v_j = j + 1 (1 The only gas station is located at point 1. g_2 = 0, ..., g_N = 0- `[Multi Gas stations & Line Case] (accounts for 18% of cases) -> Roads are on a straight line. M = N -1, u_j = j, v_j = j + 1 (1
解法
把每个加油站看作超级节点，相邻两个加油站间距离 d 若 d ≤ L 则可单次直达。预处理：以所有加油站为源做多源 Dijkstra，得到每个非加油站点到最近加油站的距离 dist[v]。一个点 v 可达且能回家 ⇔ 存在通过加油站网络的路径，使得整段路径中相邻加油站距离 ≤ L，且 v 到最近加油站距离 ≤ L/2(去回都靠该满箱)。算法：先用 Dijkstra 求两两加油站间最短路再连边，再在加油站图上做并查集，最后统计所属连通块内非加油站点中 dist[v] ≤ L/2 的个数。复杂度 O((N+M) log N)。
from typing import List
import heapq
def compute_number_of_locations(N: int, M: int, L: int,
g: List[int], roads: List[List[int]]) -> int:
adj = [[] for _ in range(N + 1)]
for u, v, d in roads:
adj[u].append((v, d))
adj[v].append((u, d))
INF = float("inf")
dist = [INF] * (N + 1)
src = [(0, i) for i in range(1, N + 1) if g[i - 1] == 1]
nearest = [-1] * (N + 1)
pq = []
for d, s in src:
dist[s] = 0
nearest[s] = s
heapq.heappush(pq, (0, s, s))
while pq:
d, u, root = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in adj[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
nearest[v] = root
heapq.heappush(pq, (nd, v, root))
parent = list(range(N + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, v, d in roads:
if g[u - 1] and g[v - 1] and d <= L:
parent[find(u)] = find(v)
elif nearest[u] != -1 and nearest[v] != -1:
if dist[u] + d + dist[v] <= L:
parent[find(nearest[u])] = find(nearest[v])
home_root = find(1)
count = 0
for v in range(1, N + 1):
if g[v - 1] == 0:
if nearest[v] != -1 and find(nearest[v]) == home_root and 2 * dist[v] <= L:
count += 1
return countimport java.util.*;
class Solution {
int[] parent;
int computeNumberOfLocations(int N, int M, int L, int[] g, int[][] roads) {
List<long[]>[] adj = new List[N + 1];
for (int i = 0; i <= N; i++) adj[i] = new ArrayList<>();
for (int[] r : roads) {
adj[r[0]].add(new long[]{r[1], r[2]});
adj[r[1]].add(new long[]{r[0], r[2]});
}
long[] dist = new long[N + 1];
int[] nearest = new int[N + 1];
Arrays.fill(dist, Long.MAX_VALUE);
Arrays.fill(nearest, -1);
PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
for (int i = 1; i <= N; i++) if (g[i - 1] == 1) {
dist[i] = 0; nearest[i] = i;
pq.add(new long[]{0, i, i});
}
while (!pq.isEmpty()) {
long[] cur = pq.poll();
long d = cur[0]; int u = (int) cur[1], root = (int) cur[2];
if (d > dist[u]) continue;
for (long[] e : adj[u]) {
long nd = d + e[1];
if (nd < dist[(int) e[0]]) {
dist[(int) e[0]] = nd; nearest[(int) e[0]] = root;
pq.add(new long[]{nd, e[0], root});
}
}
}
parent = new int[N + 1];
for (int i = 0; i <= N; i++) parent[i] = i;
for (int[] r : roads) {
int u = r[0], v = r[1], d = r[2];
if (g[u - 1] == 1 && g[v - 1] == 1 && d <= L) union(u, v);
else if (nearest[u] != -1 && nearest[v] != -1 && dist[u] + d + dist[v] <= L) union(nearest[u], nearest[v]);
}
int homeRoot = find(1), count = 0;
for (int v = 1; v <= N; v++) {
if (g[v - 1] == 0 && nearest[v] != -1 && find(nearest[v]) == homeRoot && 2L * dist[v] <= L) count++;
}
return count;
}
private int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
private void union(int a, int b) { parent[find(a)] = find(b); }
}class Solution {
public:
vector<int> parent;
int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
void unite(int a, int b) { parent[find(a)] = find(b); }
int computeNumberOfLocations(int N, int M, int L, vector<int>& g, vector<vector<int>>& roads) {
vector<vector<pair<int, long long>>> adj(N + 1);
for (auto& r : roads) {
adj[r[0]].push_back({r[1], r[2]});
adj[r[1]].push_back({r[0], r[2]});
}
vector<long long> dist(N + 1, LLONG_MAX);
vector<int> nearest(N + 1, -1);
priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<>> pq;
for (int i = 1; i <= N; i++) if (g[i - 1] == 1) {
dist[i] = 0; nearest[i] = i;
pq.push({0, i, i});
}
while (!pq.empty()) {
auto [d, u, root] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (auto& [v, w] : adj[u]) {
long long nd = d + w;
if (nd < dist[v]) { dist[v] = nd; nearest[v] = root; pq.push({nd, v, root}); }
}
}
parent.assign(N + 1, 0);
iota(parent.begin(), parent.end(), 0);
for (auto& r : roads) {
int u = r[0], v = r[1], d = r[2];
if (g[u - 1] && g[v - 1] && d <= L) unite(u, v);
else if (nearest[u] != -1 && nearest[v] != -1 && dist[u] + d + dist[v] <= L) unite(nearest[u], nearest[v]);
}
int homeRoot = find(1), count = 0;
for (int v = 1; v <= N; v++) {
if (g[v - 1] == 0 && nearest[v] != -1 && find(nearest[v]) == homeRoot && 2 * dist[v] <= L) count++;
}
return count;
}
};1D Othello is a board game played with Othello tiles and a horizontal grid. The game is played as follows: The game pieces are tiles in which one side is black and the other side is white. There are two players. One player plays black tiles (the black side of the tiles), the other plays white tiles (the white side of the tiles). The game begins with two tiles next to each other.The left tile is black and the right tile is white. The players take turns placing a tile on the board. A player cannot pass their turn. Tiles can only be placed next to a tile that is already on the board. Therefore, there are only two positions in which a tile can be placed on each turn (to the left or right of the tiles already on the board). After placing a tile, the player flips all of the tiles between the new tile and the nearest same-color tile. If the tile next to the new tile is the same color or there are no same-color tiles, the player does not flip any tiles. The player must place a tile even when he cannot flip any tiles. A transcript of 1D Othello is written in a string consisting of L and R. If the i-th letter of the transcript is L, that means a tile (a black tile when i is an odd number and a white tile when i is an even number) was placed to the left of the tiles already on the board, and if it is R that means a tile was placed to the right of the tiles already on the board. You are given a transcript S of the game. Please display the respective number of black and white tiles at conclusion of the game.
解法
直接模拟。用双端队列 deque 维护盘面：初始 [B, W]。第 i 步(从 1 开始)放置颜色 = B if i % 2 == 1 else W，方向看 S[i-1]：L 则放最左、R 则放最右；放完后翻转 “新 tile 到最近同色 tile” 之间的所有 tile。最终统计黑白计数。复杂度 O(|S|²) 最坏(翻转)，但 |S| 通常较小。
from typing import Tuple
from collections import deque
def count_tiles(S: str) -> Tuple[int, int]:
board = deque(["B", "W"])
for i, side in enumerate(S, 1):
color = "B" if i % 2 == 1 else "W"
if side == "L":
arr = list(board)
arr.insert(0, color)
for j in range(1, len(arr)):
if arr[j] == color:
for k in range(1, j):
arr[k] = color
break
board = deque(arr)
else:
arr = list(board)
arr.append(color)
for j in range(len(arr) - 2, -1, -1):
if arr[j] == color:
for k in range(j + 1, len(arr) - 1):
arr[k] = color
break
board = deque(arr)
black = sum(1 for c in board if c == "B")
white = len(board) - black
return black, whiteimport java.util.*;
class Solution {
int[] countTiles(String S) {
Deque<Character> board = new ArrayDeque<>();
board.add('B'); board.add('W');
for (int i = 1; i <= S.length(); i++) {
char color = (i % 2 == 1) ? 'B' : 'W';
char side = S.charAt(i - 1);
List<Character> arr = new ArrayList<>(board);
if (side == 'L') {
arr.add(0, color);
for (int j = 1; j < arr.size(); j++) {
if (arr.get(j) == color) {
for (int k = 1; k < j; k++) arr.set(k, color);
break;
}
}
} else {
arr.add(color);
for (int j = arr.size() - 2; j >= 0; j--) {
if (arr.get(j) == color) {
for (int k = j + 1; k < arr.size() - 1; k++) arr.set(k, color);
break;
}
}
}
board = new ArrayDeque<>(arr);
}
int black = 0, total = board.size();
for (char c : board) if (c == 'B') black++;
return new int[]{black, total - black};
}
}class Solution {
public:
pair<int, int> countTiles(string S) {
deque<char> board{'B', 'W'};
for (size_t i = 1; i <= S.size(); ++i) {
char color = (i % 2 == 1) ? 'B' : 'W';
char side = S[i - 1];
vector<char> arr(board.begin(), board.end());
if (side == 'L') {
arr.insert(arr.begin(), color);
for (size_t j = 1; j < arr.size(); ++j) {
if (arr[j] == color) {
for (size_t k = 1; k < j; ++k) arr[k] = color;
break;
}
}
} else {
arr.push_back(color);
for (int j = (int) arr.size() - 2; j >= 0; --j) {
if (arr[j] == color) {
for (size_t k = j + 1; k < arr.size() - 1; ++k) arr[k] = color;
break;
}
}
}
board.assign(arr.begin(), arr.end());
}
int black = 0, total = board.size();
for (char c : board) if (c == 'B') ++black;
return {black, total - black};
}
};