http://webptt.com/rss.ashx?n=Prob_Solve2021-08-15T01:53:59+08:00https://webptt.com/m.aspx?n=/bbs/Prob_Solve/M.1712735151.A.A6B.html2024-04-10T15:45:51+08:002024-04-19T09:32:27+08:00petingo<pre>大家早 :D 小弟日前遇到這個問題，想了幾天還沒想到暴力以外的做法 希望版上的大神可以出手相救 -- 給定一個無向有權圖，求將各個節點兩兩分組的方式 </pre>https://webptt.com/m.aspx?n=/bbs/Prob_Solve/M.1711712753.A.A71.html2024-03-29T19:45:53+08:002024-04-01T10:43:18+08:00stimim<pre>令兩個輸入為數列 a[] 和 b[] 令最佳的 b[] 順序為 B[] // sorted(b) == sorted(B) // answer == niceness(B) niceness(B) 是陣列中相鄰兩個數的差，對每個 B[i] ，有三個 case: 1. B[i] is a local maximum: </pre>https://webptt.com/m.aspx?n=/bbs/Prob_Solve/M.1711686700.A.EAA.html2024-03-29T12:31:40+08:002024-03-29T12:33:12+08:00Pttgambler<pre>最近在 Leetcode 上面看到有人分享的一題線上測驗， 想了一段時間都沒有想出暴力解以外的做法，所以來這裡問看看。 https://leetcode.com/discuss/interview-question/4902893/recent-goldman-sachs-oa-questionanybody-with-a-optimal-approach In a tranquil village school, there are two students named Ramu and Sonu, each possessing a collection of N distinct chalks. Each student's chalks are </pre>https://webptt.com/m.aspx?n=/bbs/Prob_Solve/M.1700958983.A.D64.html2023-11-26T08:36:23+08:002023-12-25T22:49:13+08:00waynes2230<pre>1.如圖6/5 1/1 42/0 要怎麼算成是6 2.及6/5 </pre>https://webptt.com/m.aspx?n=/bbs/Prob_Solve/M.1700901609.A.997.html2023-11-25T16:40:09+08:002023-11-25T16:40:08+08:00mamaya3<pre>這算是整數分割的變形 假設有N個賽局 連續的勝或負的次數用數字表示 可以分割該N數為連加法 例如5次賽局分別為 勝負負勝勝 則為 1+2+2 勝首局時 則偶數項(連輸的次數)不能大於n-1 負首局時 則奇數項(連輸的次數)不能大於n-1 </pre>https://webptt.com/m.aspx?n=/bbs/Prob_Solve/M.1684651548.A.D09.html2023-05-21T14:45:48+08:002023-05-22T08:20:44+08:00seanwu<pre>部份引言恕刪 : 看不懂第36行寫這樣的理論基礎是什麼? 為什麼這時候就知道要再減一? : 而且他檢查的是第一根input edge的node, 跟traverse的順序也不一樣..... : 做了個實驗 如果我只是把case裡面的編號4跟5對調 跟原圖是一模一樣 traverse順序 : 也一樣 不過這段code會wrong answer........ </pre>https://webptt.com/m.aspx?n=/bbs/Prob_Solve/M.1684610032.A.563.html2023-05-21T03:13:52+08:002023-05-21T03:37:15+08:00saladim<pre>https://leetcode.com/problems/shortest-cycle-in-a-graph/ 最近在解這題 我自己是用DFS+BFS解掉 但是performance不是很好 所以看了一下最快的某個解法 但是其中有一行看不懂為什麼是這樣寫 附上他的code跟其中一個case(因為最快解法的出現次序會變動): https://pastebin.com/sQWG6L8q </pre>https://webptt.com/m.aspx?n=/bbs/Prob_Solve/M.1679026710.A.022.html2023-03-17T12:18:30+08:002023-03-26T18:20:28+08:00birdjack<pre>簡單講一下馬丁格爾法 就是假設在一個勝率50%的壓大小的賭局中， 每輸一次就加倍前一次的下注，贏了就重置回1個籌碼 這樣本金如果切成(2^n)-1就可以玩n次， 問題是想要求在N個賽局中遇到連輸n次的機率 </pre>https://webptt.com/m.aspx?n=/bbs/Prob_Solve/M.1671036045.A.1A3.html2022-12-15T00:40:45+08:002022-12-15T23:56:17+08:00answermangtr<pre>業務的邏輯是這樣的 出貨的計算是以棧板為單位 而可以擺放在同一棧板的物品有一套邏輯 在此基礎下 希望每次將多筆不同物品的訂單 合併棧板 達到節省棧板的目的 </pre>https://webptt.com/m.aspx?n=/bbs/Prob_Solve/M.1670940379.A.031.html2022-12-13T22:06:19+08:002022-12-13T22:08:32+08:00fightforlive<pre>不確定是否能在這版問這個問題 如有違反板規,再請告知 底下這一個為什麼不是spatial invariance? T[x(n1, n2)] = c(n1, n2)*x(n1, n2) = y(n1, n2) 就算我shift不是也可以得到和原本一樣的圖形? </pre>https://webptt.com/m.aspx?n=/bbs/Prob_Solve/M.1666489257.A.DAB.html2022-10-23T09:40:57+08:002022-12-21T02:37:32+08:00yhliu<pre>有專門的統計版，再不然還有數學版，這問題放在那裡更適當。 假設選的號碼（此例的 2,3,5,7,11,13）是固定的。 T = Z1+...+Z6, Zi 是從 1~49 隨機選出的，E[Zi] = (1+49)/2 = 25 所以 E[T] = E[Z1]+...+E[Z6] = 25*6 = 150 Zi 之間有相關，但這不影響期望值，只影響 T 的變異數計算。 </pre>https://webptt.com/m.aspx?n=/bbs/Prob_Solve/M.1666325714.A.221.html2022-10-21T12:15:14+08:002022-10-21T12:15:13+08:00Jerrychiang<pre>手機排版抱歉 同事問了一個問題我實在不知道怎麼解，放上來請各位先進指導， 樂透彩從1-49中任取6個號碼（取後不放回），小明選了2.3.5.7.11.13六個號，變數x是小明選中的號碼數量，變數T是樂透抽出的六個號碼加總（ex 樂透抽出5.10.15.20.25.30，X=1，T=105) Q1: T的期望值E[T]，小明六個號碼都中的期望值E[T|X=6]，以及全部沒中的期望值E[T|X=0] Q2: X和T是否獨立 </pre>https://webptt.com/m.aspx?n=/bbs/Prob_Solve/M.1665051987.A.E7B.html2022-10-06T18:26:27+08:002022-10-07T08:01:50+08:00fj208<pre>有紅、橙、黃、綠、藍、靛 紫，七種顏色的球。 有一台發球機，可以一次發出三顆球，但沒有固定順序。 從現在開始發球，以三顆為一組，不停的發，請問同時發出三顆都是紅色球的機率是多少？ ----- Sent from JPTT on my Samsung SM-A528B. </pre>https://webptt.com/m.aspx?n=/bbs/Prob_Solve/M.1651745431.A.553.html2022-05-05T18:10:31+08:002022-05-06T00:39:16+08:00ddavid<pre>x1 = (m - n) # 第 1 抽時價值為 v2 的球數量 第 1 次抽取隨機事件 X1 = v1 機率 (n / (n + x1)) v2 機率 (x1 / (n + x1)) E(X1) = (n/(n + x1))v1 + (x1/(n + x1))v2 xi = (m - n) if X(i-1) = v1 # 前次抽到 v1 球會 reset 所有球 </pre>https://webptt.com/m.aspx?n=/bbs/Prob_Solve/M.1650988937.A.08C.html2022-04-27T00:02:17+08:002022-06-26T08:53:54+08:00hackerick4<pre>一個箱子有 m 顆球，其中前1～n顆球價值為v1，後續 m-n 顆球價值為 v2。 抽取k次，取後 不放回。 但如果取到 v1 價值的球，就要把剛剛取過的球再放回去箱子，下次抽的時候就是 回歸 m 顆球的條件 請問這樣的命題，如果不跑模擬的狀況之下，v1球的期望值是多少 我能想到的是用生成函數去解遞迴，但計算量十分龐大，有沒有高手可以分享做法呢？ </pre>https://webptt.com/m.aspx?n=/bbs/Prob_Solve/M.1643023362.A.417.html2022-01-24T19:22:42+08:002022-01-25T17:14:45+08:00xxxx9659<pre>最近在想一個問題，想要用一個整數，來代表一種組合 然後把 C(28, 5) 的所有組合，快速輪詢過一遍 C(28, 5) = 98280 有點大不好舉例，拿 C(6, 3) = 20 來當例子 var state = 56; //代表二進位的 111000 do { </pre>https://webptt.com/m.aspx?n=/bbs/Prob_Solve/M.1642783241.A.5F3.html2022-01-22T00:40:41+08:002022-06-01T01:21:37+08:00mathYU<pre>https://i.imgur.com/mqIQLd2.jpg https://i.imgur.com/WIReibv.jpg 不太懂哪裡rotation出了問題 剛才用線上模擬avl tree確認過了 這樣建立沒錯，但是leaf node之和沒有答案可選 </pre>https://webptt.com/m.aspx?n=/bbs/Prob_Solve/M.1634992539.A.64E.html2021-10-23T20:35:39+08:002021-10-23T20:47:10+08:00DJWS<pre>問題: https://www.spoj.com/problems/DIVCNT1/ 解答: https://yhx-12243.github.io/OI-transit/records/spojDIVCNT1.html 演算法: 給定一條凸曲線，用Stern-Brocot Tree找到一條折線，緊貼曲線上方。 我的疑問: 如何證明二分法找到的向量，恰好緊貼曲線上方? ------------------------------------------------------------------------------ </pre>https://webptt.com/m.aspx?n=/bbs/Prob_Solve/M.1633163200.A.87C.html2021-10-02T16:26:40+08:002022-06-24T10:17:24+08:00fishxd1096<pre>各位好，最近因為想練習C語言，因此在實作一些Tree的結構和演算法 剛才在測試AVL是否有bug時 發現有一個case同時是LL和LR狀況 那我目前邏輯是： 如果同時是LL和LR就當作LL case去右旋 </pre>https://webptt.com/m.aspx?n=/bbs/Prob_Solve/M.1628963639.A.030.html2021-08-15T01:53:59+08:002021-08-15T10:20:45+08:00nevikw39<pre>各位電神安安 o'_'o Sum of Three Values 應該算是很經典的題目，其簡化版本 Sum of Two Values 常見的解 法有兩種，分別是用雜湊表及 two pointer 有趣的是在 CSES 上使用 std::unordered_map 及 GNU PBDS 的 gp_hash_table 分別各有 一筆測資 TLE, 反而改用 BST 才 AC, 證實 log 只是常數 XD </pre>