class Solution {
public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
int max = Arrays.stream(workerTimes).max().getAsInt();
long cnt, l = 1;
long r = ((long) max * mountainHeight * (mountainHeight + 1)) / 2;
while (l < r) {
long mid = l + (r - l) / 2;
cnt = 0;
for (int t : workerTimes) {
long work = mid / t;
long delta = 1 + 4 * 2 * work;
long k = (long) ((-1 + (Math.sqrt(delta))) / 2);
cnt += k;
}
if (cnt >= mountainHeight) r = mid;
else l = mid + 1;
}
return r;
}
}
LmaoSuVuong
#6,902
Java:
func getHappyString(n int, k int) string {
order:=0
res:=""
var backtrack func(sb string) bool
backtrack = func(sb string) bool {
if len(sb) == n {
order++
if order == k {
res = sb
return true
}
return false
}
for _, c := range []byte{'a', 'b', 'c'} {
if len(sb) == 0 || sb[len(sb)-1] != c {
if backtrack(sb + string(c)) {
return true
}
}
}
return false
}
backtrack("")
return res
}
function minNumberOfSeconds(height: number, wt: number[]): number {
let l = 1n;
let r = BigInt(1e16);
let res = r;
const h = BigInt(height);
while (l <= r) {
const m = (l + r) / 2n;
let cur = 0n;
for (let time of wt) {
let t = BigInt(time);
let l1 = 0n, r1 = BigInt(2e5);
let st = 0n;
while (l1 <= r1) {
const x = (l1 + r1) / 2n;
const val = t * x * (x + 1n) / 2n;
if (val <= m) {
st = x;
l1 = x + 1n;
} else {
r1 = x - 1n;
}
}
cur += st;
if (cur >= h) break;
}
if (cur >= h) {
res = m;
r = m - 1n;
} else {
l = m + 1n;
}
}
return Number(res);
}
Đoạn while thứ 2 chỉ cần đi vòng for là đc vì nó là số mũ mà. Tới upper bound break ra là được. Ko cần tới cái công thức kia luôn. Xử lí edge case là workers i = 1 nữa là ổn.
À đù tự gạch, đọc lộn là worker + worker*2 + worker*3 + .... chứ ko phải là worker+ worker^2 + worker^3 + ...
Đoạn while thứ 2 chỉ cần đi vòng for là đc vì nó là số mũ mà. Tới upper bound break ra là được. Ko cần tới cái công thức kia luôn. Xử lí edge case là workers i = 1 nữa là ổn.
À đù tự gạch, đọc lộn là worker + worker*2 + worker*3 + .... chứ ko phải là worker+ worker^2 + worker^3 + ...
class Solution {
public:
int _c;
int _k;
int _n;
string _ret;
void bt(string& s) {
if (_c>_k)
return;
if (s.size() == _n) {
_c++;
if (_c == _k)
_ret = s;
return;
}
if (s.back() == 'a') {
s.push_back('b');
bt(s);
s.back() = 'c';
bt(s);
s.pop_back();
} else if (s.back() == 'b') {
s.push_back('a');
bt(s);
s.back() = 'c';
bt(s);
s.pop_back();
} else if (s.back() == 'c') {
s.push_back('a');
bt(s);
s.back() = 'b';
bt(s);
s.pop_back();
}
}
string getHappyString(int n, int k) {
_k = k;
_n = n;
for (int i=0; i<3; i++) {
string s;
s.push_back(i + 'a');
bt(s);
}
return _ret;
}
};
nchhnchh
#6,906
Python:
class Solution:
def getHappyString(self, n: int, k: int) -> str:
result = []
self.valid = False
temp = []
def backtracking(idx):
if idx == n:
result.append(''.join(temp))
if len(result) == k:
self.valid = True
return
for c in ['a', 'b', 'c']:
if idx == 0 or temp[-1] != c:
temp.append(c)
backtracking(idx+1)
if self.valid:
return
temp.pop()
backtracking(0)
return '' if len(result) < k else result[-1]
pentagon_68
#6,907
Code:
class Solution {
public String getHappyString(int n, int k) {
char[] arr = new char[]{'a','b','c'};
List<String> str = new ArrayList<>();
dfs(arr, str, new StringBuilder(), n,k);
// System.out.println(str);
if(k > str.size()) return "";
return str.get(k-1);
}
public void dfs(char[] arr, List<String> s, StringBuilder curr, int n, int k){
if(curr.length() ==n) {
s.add(curr.toString());
return;
}
for(char c : arr){
if(curr.length() > 0 && curr.charAt(curr.length() - 1) == c) continue;
curr.append(c);
dfs(arr, s, curr, n, k);
if(curr.length()> 0)
curr.deleteCharAt(curr.length()-1);
}
}
}
ligerre
#6,908
Python:
class Fancy:
def __init__(self):
self.arr = []
self.mul_const = 1
self.add_const = 0
self.modulo = 10**9 +7
def power(self,val,p):
if p == 0:
return 1
res = self.power(val,p//2)**2
if p%2==0:
return res % self.modulo
else:
return res*val % self.modulo
def append(self, val: int) -> None:
val = (val+self.modulo-self.add_const) % self.modulo
self.arr.append((val,self.mul_const))
def addAll(self, inc: int) -> None:
self.add_const = (self.add_const + inc) % self.modulo
def multAll(self, m: int) -> None:
self.mul_const = (self.mul_const*m) % self.modulo
self.add_const = (self.add_const*m) % self.modulo
def getIndex(self, idx: int) -> int:
if idx>=len(self.arr):
return -1
val,m = self.arr[idx]
val = (val*self.mul_const) % self.modulo
val = (val*self.power(m,self.modulo-2)) % self.modulo
return (val+self.add_const) % self.modulo
# Your Fancy object will be instantiated and called as such:
# obj = Fancy()
# obj.append(val)
# obj.addAll(inc)
# obj.multAll(m)
# param_4 = obj.getIndex(idx)
LmaoSuVuong
#6,909
giờ lười tới mức psdeucode cho ai nó fill syntax vào r các bác ạ
Reactions:
JakovichTimViec
JakovichTimViec
#6,910
phải ngâm cứu vụ modular inverse chứ cũng chả nhớ nó.
C#:
public class Fancy
{
long multi = 1, addi = 0;
List<int> l = new();
List<(long, long)> debt = new();
int MOD = 1000000007;
public Fancy() { }
public void Append(int val)
{
l.Add(val);
debt.Add((multi, addi));
}
public void AddAll(int inc)
{
addi = (addi + inc) % MOD;
}
public void MultAll(int m)
{
addi = (addi * m) % MOD;
multi = (multi * m) % MOD;
}
public int GetIndex(int idx)
{
if (idx >= l.Count)
return -1;
var (multi_debt, addi_debt) = debt[idx];
long val = (l[idx] - addi_debt + MOD) % MOD;
val = val * ModInverse(multi_debt) % MOD;
val = val * multi % MOD;
val = (val + addi) % MOD;
return (int)val;
}
long ModInverse(long a)
{
long b = MOD - 2;
long res = 1;
a %= MOD;
while (b > 0)
{
if ((b & 1) == 1)
res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
}
Đúng rồi. Nếu append trước thì chỉ cần tính x*m + s. Giờ giả sử bác có m và s, và nếu append số v thì v có dạng x*m + s. Tìm x.
Reactions:
anoldvozer1710.v2
anoldvozer1710.v2
#6,915
đề bài đ gì đọc khó hiểu vậy
Reactions:
nchhnchh and JakovichTimViec
The Silent
#6,916
Code:
class Solution {
public int largestSubmatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length, res = 0;
int[][] grid = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0)
grid[i][j] = matrix[i][j];
else if (matrix[i][j] == 1)
grid[i][j] = 1 + grid[i - 1][j];
}
}
for (int i = 0; i < m; i++) {
Arrays.sort(grid[i]);
for (int j = 0; j < n; j++) {
int width = n - j;
res = Math.max(res, grid[i][j] * width);
}
}
return res;
}
}
Phó GOAT
#6,917
C++:
class Solution {
public:
int largestSubmatrix(vector<vector<int>>& matrix) {
int res = 0, m = matrix.size(), n = matrix[0].size();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (i > 0 && matrix[i][j] == 1) matrix[i][j] = matrix[i - 1][j] + 1;
for (auto row : matrix) {
std::sort(row.begin(), row.end());
for (int i = n - 1, len = 1; i >= 0 && row[i] > 0; i--, len++) res = std::max(res, row[i] * len);
}
return res;
}
};
Bài hôm qua chả hiểu con mẹ gì
JakovichTimViec
#6,918
C#:
public class Solution
{
public int LargestSubmatrix(int[][] matrix)
{
int n = matrix.Length;
int m=matrix[0].Length;
for (int i = 1; i < n; i++)
for (int j = 0; j < m; j++)
if (matrix[i][j] != 0)
matrix[i][j] = matrix[i - 1][j] + 1;
int rtn = 0;
for(int i=0;i<n;i++)
{
Array.Sort(matrix[i]);
int max = matrix[i][^1];
if (max == 0)
continue;
for(int j=0;j<m;j++)
max = Math.Max((m-j) * matrix[i][j], max);
rtn=Math.Max(rtn, max);
}
return rtn;
}
}
anoldvozer1710.v2
#6,919
code ngây thơ, nhìn quê điên
JavaScript:
function largestSubmatrix(matrix: number[][]): number {
const m = matrix.length, n = matrix[0].length;
const arr = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] === 1) {
arr[i][j] = (arr[i - 1][j] || 0) + 1;
} else arr[i][j] = 0
}
}
let res = 0;
for (let i = 1; i <= m; i++) {
let map = new Map();
let col = 0;
for (let j = 1; j <= n; j++) {
if (arr[i][j]) {
map.set(arr[i][j], (map.get(arr[i][j]) || 0) + 1);
col++
}
}
if (!col) continue;
const keys = Array.from(map.keys()).sort((a,b) => a - b);
let cur = 0, total = 0;
for (let i = 0; i < keys.length; i++) {
cur = Math.max(cur, keys[i] * (col - total))
total += map.get(keys[i]);
}
res = Math.max(res, cur)
}
return res;
};
The Silent
#6,920
Code:
class Solution {
public int countSubmatrices(int[][] grid, int k) {
int m = grid.length, n = grid[0].length, res = 0;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) dp[i][0] = grid[i][0] + dp[i - 1][0];
for (int j = 1; j < n; j++) dp[0][j] = grid[0][j] + dp[0][j - 1];
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = grid[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) if (dp[i][j] <= k) res++;
}
return res;
}
}
