In the nation of Coderland, the layout of the cities can be depicted as a tree structure with totalCities numbered from 1 to totalCities. These cities are interconnected by totalCities - 1 two-way routes, where the i-th route links cityStart[i] with cityEnd[i]. The ruler of Coderland intends to install one of monumentTypes unique monuments in each city. However, the following condition must be satisfied: No two directly connected cities or two cities that share a common neighboring city can have identical monument types. Your task is to calculate the total number of valid configurations for placing monuments in every city based on these rules. Since the resulting number could be extremely large, return the answer modulo (10⁹ + 7). Two cities are regarded as adjacent if there is a direct connection between them via a route. Parameters: int monumentTypes: The number of distinct monument styles available. int totalCities: The total number of cities in the kingdom. int[] routeStart: An array representing the starting city of each road. int[] routeEnd: An array representing the ending city of each road. Returns: int: The number of valid ways to construct the monuments, computed modulo (10⁹ + 7).
解法
树染色：根任选一节点；颜色数 m。根有 m 种；每个非根节点不能与父、祖父、兄弟颜色相同。每对父子边贡献 (m − 1 − 已被祖父占据 1 个 − 已被同父兄弟占据)。可证答案 = m · (m-1) · ∏_v (m-1-d_v)^? — 简化版本：树形 DP。
from collections import defaultdict
from typing import List
MOD = 10 ** 9 + 7
def build_monuments(monument_types: int, total_cities: int, route_start: List[int], route_end: List[int]) -> int:
g = defaultdict(list)
for u, v in zip(route_start, route_end):
g[u].append(v); g[v].append(u)
# BFS from node 1; for each non-root node, count of (forbidden colors) = 1 (parent) + (siblings already colored) + (grandparent if exists)
# Approximate: m * (m-1)^(深度=1) * ∏ (m - 1 - sibling_idx - grand_constraint)
# We use a simple BFS-order counting.
ans = monument_types
visited = {1}
color_assigned = {1: 0} # placeholder
from collections import deque
parent = {1: None}; grand = {1: None}
q = deque([1])
sibling_done = defaultdict(int)
while q:
u = q.popleft()
for v in g[u]:
if v not in visited:
visited.add(v)
parent[v] = u
grand[v] = parent[u]
forbidden = 1 # parent
if grand[v] is not None: forbidden += 1
forbidden += sibling_done[u]
choices = max(0, monument_types - forbidden)
ans = ans * choices % MOD
sibling_done[u] += 1
q.append(v)
return ansimport java.util.*;
class Solution {
static final long MOD = 1_000_000_007L;
public int buildMonuments(int monumentTypes, int totalCities, int[] routeStart, int[] routeEnd) {
Map<Integer, List<Integer>> g = new HashMap<>();
for (int i = 0; i < routeStart.length; i++) {
g.computeIfAbsent(routeStart[i], k -> new ArrayList<>()).add(routeEnd[i]);
g.computeIfAbsent(routeEnd[i], k -> new ArrayList<>()).add(routeStart[i]);
}
long ans = monumentTypes;
Set<Integer> visited = new HashSet<>(); visited.add(1);
Map<Integer, Integer> parent = new HashMap<>(), grand = new HashMap<>();
Map<Integer, Integer> sibDone = new HashMap<>();
parent.put(1, 0);
Deque<Integer> q = new ArrayDeque<>(); q.add(1);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : g.getOrDefault(u, Collections.emptyList())) {
if (visited.add(v)) {
parent.put(v, u);
grand.put(v, parent.get(u));
int forbid = 1 + (grand.get(v) != 0 ? 1 : 0) + sibDone.getOrDefault(u, 0);
int choices = Math.max(0, monumentTypes - forbid);
ans = ans * choices % MOD;
sibDone.merge(u, 1, Integer::sum);
q.add(v);
}
}
}
return (int) ans;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
static constexpr long long MOD = 1000000007;
public:
int buildMonuments(int monumentTypes, int totalCities, vector<int>& routeStart, vector<int>& routeEnd) {
unordered_map<int, vector<int>> g;
for (int i = 0; i < (int)routeStart.size(); i++) { g[routeStart[i]].push_back(routeEnd[i]); g[routeEnd[i]].push_back(routeStart[i]); }
long long ans = monumentTypes;
unordered_set<int> visited; visited.insert(1);
unordered_map<int, int> parent, grand, sibDone;
parent[1] = 0;
queue<int> q; q.push(1);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) {
if (visited.insert(v).second) {
parent[v] = u;
grand[v] = parent[u];
int forbid = 1 + (grand[v] != 0 ? 1 : 0) + sibDone[u];
int choices = max(0, monumentTypes - forbid);
ans = ans * choices % MOD;
sibDone[u]++;
q.push(v);
}
}
}
return (int) ans;
}
};The other question asked in the same batch is LC647.
After a user logs in, they receive a token. If the token exceeds the system-defined expiration period (expiryLimit), it becomes invalid. However, if the token is reset within the period, the expiration time is extended.
Valid tokens can be reset repeatedly.
Expired or non-existent tokens will have their reset operations ignored.
Expired tokens cannot be used again.
Command format: [type, token_id, T]
type 0 (create): Create a token with an expiration time set to T + expiryLimit.
type 1 (reset): Extend the token's expiration time to T + expiryLimit.
Initially, there are no tokens. Process the requests in order and determine how many tokens are still valid at the maximum time point.
Function Description
Complete the function countValidTokens in the editor.
countValidTokens has the following parameters:
-
int expiryLimit: the system-defined expiration period
-
int[][] commands: a 2D array of commands where each command is of the format [type, token_id, T] Returns int: the number of valid tokens at the maximum time point
解法
维护 expire[token_id] = 该 token 当前过期时间。type=0 创建：set expire[id] = T + expiryLimit；type=1 reset：若 expire 存在且 T ≤ expireid则 expire[id] = T + expiryLimit，否则忽略。处理完后，maxTime = max(T)；统计 expire[id] > maxTime 的 id 数。
from typing import List
def count_valid_tokens(expiry_limit: int, commands: List[List[int]]) -> int:
expire: dict = {}
max_t = 0
for typ, tid, T in commands:
max_t = max(max_t, T)
if typ == 0:
expire[tid] = T + expiry_limit
else:
if tid in expire and T <= expire[tid]:
expire[tid] = T + expiry_limit
return sum(1 for e in expire.values() if e > max_t)import java.util.*;
class Solution {
public int countValidTokens(int expiryLimit, int[][] commands) {
Map<Integer, Integer> expire = new HashMap<>();
int maxT = 0;
for (int[] c : commands) {
maxT = Math.max(maxT, c[2]);
if (c[0] == 0) expire.put(c[1], c[2] + expiryLimit);
else if (expire.containsKey(c[1]) && c[2] <= expire.get(c[1])) expire.put(c[1], c[2] + expiryLimit);
}
int cnt = 0;
for (int e : expire.values()) if (e > maxT) cnt++;
return cnt;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int countValidTokens(int expiryLimit, vector<vector<int>>& commands) {
unordered_map<int, int> expire;
int maxT = 0;
for (auto& c : commands) {
maxT = max(maxT, c[2]);
if (c[0] == 0) expire[c[1]] = c[2] + expiryLimit;
else if (expire.count(c[1]) && c[2] <= expire[c[1]]) expire[c[1]] = c[2] + expiryLimit;
}
int cnt = 0;
for (auto& [k, e] : expire) if (e > maxT) cnt++;
return cnt;
}
};There are n customers and m products. Each customer gives a rating r[i] for each of the i'th product (This is stored in ratings 2d matrix). The task is to choose (n-2) products such that the min of the mx array is maximized. Where, mx[j] be the max rating given by a customer j for among all selected products.
Constraints
2 ≤ n ≤ m ≤ 10⁵0 ≤ ratings[i][j] ≤ 10⁹- These constraints are based on memory; they might not be correct
Example 1
Input:
n = 4
m = 4
ratings = [[3,4,2,2],[3,3,3,4],[2,4,2,3],[4,2,4,2]]Output:
3Explanation:
Here we have 4 customers and 4 products. Customer 1 gives rating of ratings[0] for the 4 products and so on. We need to choose (n-2) products such that the min of the mx array is maximized.
If we choose product 0 and 1: min(max(3,4),max(3,3),max(2,4),max(4,2)) = 3
If we choose product 0 and 2: min(max(3,2),max(3,3),max(2,2),max(4,4)) = 2
If we choose product 0 and 3: min(max(3,2),max(3,4),max(2,3),max(4,2)) = 3
If we choose product 1 and 2: min(max(4,2),max(3,3),max(4,2),max(2,4)) = 3
If we choose product 1 and 3: min(max(4,2),max(3,4),max(4,3),max(2,2)) = 2
If we choose product 2 and 3: min(max(2,2),max(3,4),max(2,3),max(4,2)) = 2
Output = max(3,2,3,3,2,2) = 3
解法
选 (n-2) 个产品 = 去除 2 个；m 较小时枚举 C(m, 2) 种去除组合，对每个组合算 min(max(rating[c][j]) for j in 保留集合)，取最大。O(m² · n)。
from typing import List
def choose_max_min_rating(n: int, m: int, ratings: List[List[int]]) -> int:
best = -1
for a in range(m):
for b in range(a + 1, m):
mn = float('inf')
for c in range(n):
mx = max(ratings[c][j] for j in range(m) if j != a and j != b)
mn = min(mn, mx)
best = max(best, mn)
return bestclass Solution {
public int chooseMaxMinRating(int n, int m, int[][] ratings) {
int best = -1;
for (int a = 0; a < m; a++) for (int b = a + 1; b < m; b++) {
int mn = Integer.MAX_VALUE;
for (int c = 0; c < n; c++) {
int mx = 0;
for (int j = 0; j < m; j++) if (j != a && j != b) mx = Math.max(mx, ratings[c][j]);
mn = Math.min(mn, mx);
}
best = Math.max(best, mn);
}
return best;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int chooseMaxMinRating(int n, int m, vector<vector<int>>& ratings) {
int best = -1;
for (int a = 0; a < m; a++) for (int b = a + 1; b < m; b++) {
int mn = INT_MAX;
for (int c = 0; c < n; c++) {
int mx = 0;
for (int j = 0; j < m; j++) if (j != a && j != b) mx = max(mx, ratings[c][j]);
mn = min(mn, mx);
}
best = max(best, mn);
}
return best;
}
};