LJH-coding

CSES 1203 Visiting Cities 題目概述 求出給你一張有向帶權圖，保證一定有一條路能夠從 111 走到 nnn ，請你求出 111 到 nnn 最短路上必經的點。 題解 對於那些必經的點 ppp ，一定滿足 dis(1,p)=dis(p,n)dis(1, p) = dis(p, n)dis(1,p)=dis(p,n) ，其中 dis(u,v)dis(u, v)dis(u,v) 為 u→vu \to vu→v 的最短路徑長度。 還有滿足 ways(1,p)⋅ways(p,n)=ways(1,n)ways(1, p) \cdot ways(p, n) = ways(1, n)ways(1,p)⋅ways(p,n)=ways(1,n)，其中 ways(u,v)ways(u, v)ways(u,v) 為 u→vu \to vu→v的路徑數，由於路徑數量會很多，所以可以選一個數字取模，但因為有進行取模的動作，所以不保證答案一定正確。 而每次檢查就是把 111 和 nnn 各做為起點去跑 dijkstra ，然後看有沒有符合條件，多產生幾組模數多檢查幾次降低錯誤率就好。 AC ...

CSES 1160 Planets Queries II 題目概述 給你一張邊權皆為 111 的有向圖，每個節點的出度為 111 ，接下來有多筆詢問，每次詢問任兩點之間的最短距離。 題解 由於出度都是一，所以把圖構造出來之後，不難發現他的反圖就會是多個水母圖 (水母森林？) ，而我們如果把環都縮成一個點的話，水母森林就會變成一般的森林了，而如果詢問的兩點如果有解的話，那一定就是下面其中一種情況 在同一個環上 (也就是同一棵樹上的根節點) uuu 不在環上 ， vvv 在環上 (uuu 可以一直往上爬，直到爬到根節點後，變成求兩點都在環上的距離) uuu 是 vvv 的子孫 (uuu 可以一直往上爬，直到爬到 vvv 的位置) 而其他種情況都是無解的，所以我們來觀察一下該如何解決上面這幾種情況 都在同一個環上：設環上的其中一點為起點，則在找環時先預處理環上每個點和起點的距離是多少，假設 uuu 到起點的距離是 aaa ，而 vvv 到起點的距離是 bbb ，環的大小為 sss ，則他們兩點之間的距離為 a−bmod  sa-b \mod sa−bmods uuu不在環上，vvv在環 ...

Codeforces 869 Div. 2 題解 A. Politics 題目概述 有 NNN 個人需要參與 MMM 場投票，每場投票的方式如下： 每個人可以投同意或反對票，當同意票 >>> 反對票時，投反對票的人會被淘汰；當反對票 <<< 同意票時，投同意票的被淘汰；當同意和反對票數相同時，則全部人都淘汰。 而現在你是第一為參與者，你知道了這 MMM 場投票的結果，也就是每個人的選擇，現在你可以在開始投票前淘汰一些人，使得最後留下來的人最多，並且你自己 (第一位參賽者) 必須要留下來，請問最後留下來的人數一共是多少。 題解 第一位參賽者一定要留下來，那如果投票跟第一位參賽者不同的只有可能造成某一些人被淘汰，所以留下來的參賽者意見一定要跟第一位參賽者一致，所以就數有幾個人投票跟第一位參賽者相同就行。 這裡是用 std::map 紀錄 AC Code 1234567891011void solve(){ int n,k; cin>>n>>k; vector<string>v(n); map<str ...

稀疏表 (Sparse Table) 概念 將原序列從arrarrarr第iii個開始長度為2j2^j2j的連續子序列的答案用陣列儲存起來。 那要怎麼存呢？這裡會用到一點DPDPDP的想法，令dpi,jdp_{i,j}dpi,j​為原本定義的答案 初始狀態dp0=arrdp_{0} = arrdp0​=arr dpi,j=cmp(dpi−1,j,dpi−1,j+2i−1)dp_{i,j} = cmp(dp_{i-1,j},dp_{i-1,j+2^{i-1}})dpi,j​=cmp(dpi−1,j​,dpi−1,j+2i−1​) cmpcmpcmp為合併兩個答案的函式，如果是區間最大值的話就用max⁡\maxmax，如果是最小值就用min⁡\minmin 用法 預處理 用剛剛推出來的轉移式去做就好了 1234567891011vector<vector<int>>mat(30);void build(const vector<int>&v){ int n = v.size(); mat[0] = a; for(int ...

二分搜尋法 (Binary Search) Usage 比線性還要更快速的查找方式 (查找的數列必須具有單調性！) 概念 假設有個數列a = {1,3,4,6,7,8,10,13,14}，我們要在裡面尋找4這個數字，我們就可以試著用"二分搜"去做。 注意！a數列是單調遞增的，如果不具有遞增或遞減性的數列是不能做二分搜的喔。 實作 給予一個包含n{\displaystyle n}n個帶值元素的陣列A{\displaystyle A}A或是記錄A0,⋯ ,An−1{\displaystyle A_{0},\cdots ,A_{n-1}}A0​,⋯,An−1​ ，使A0≤⋯≤An−1{\displaystyle A_{0}\leq \cdots \leq A_{n-1}}A0​≤⋯≤An−1​ ，以及目標值T{\displaystyle T}T，還有下列用來搜尋T{\displaystyle T}T在A{\displaystyle A}A中位置的子程式。 令L{\displaystyle L}L為0{\displaystyle 0}0，R{\disp ...

Codeforces 702F T-Shirts 題目 https://codeforces.com/contest/702/problem/F 有NNN個商品，每個商品都有他的質量與價格，接下來有MMM個顧客，第iii個顧客的預算為aia_iai​，且每個顧客的購買策略都是：優先買質量最高的商品，如果質量都相同的話就選價格低的優先，且每個商品都限買一次。 每個客人購買商品都是獨立的事件，請問每個客人最多能買到幾個商品。 Solution 我們可以先把商品依照質量和價格按照購買策略排序，先從質量由大排到小，如果質量一樣就由價錢小排到大，然後每個客人都當作是一筆詢問，而我們可以依照排序好的商品去更新每個詢問的答案，假設目前商品價格是CCC，那我們就把詢問中≥C\ge C≥C的值給扣掉CCC，然後詢問的答案就+1+1+1，代表買了這個商品。 那這樣如果暴力做的話時間複雜度會是爛掉的O(NM)O(NM)O(NM)，所以我們可以想辦法優化他，首先，我們可以將詢問由小排到大，這樣找第一個大於等於CCC的值的位置到最後一個值的位置都要−C-C−C，然後他們的答案要+1+1+1，這裡會需要支援區間修 ...

AtCoder Beginner Contest 288 pD 題目 https://atcoder.jp/contests/abc288/tasks/abc288_d 給定一個長度為nnn的序列aaa和一個數字kkk，然後有qqq筆詢問，每筆詢問會有一個區間範圍l,rl,rl,r，問你{al,...,ar}\{a_l,...,a_r\}{al​,...,ar​}能不能進行數次操作，使得{al,...,ar}\{a_l,...,a_r\}{al​,...,ar​}都變成000，此操作如下。 在{al,...,ar}\{a_l,...,a_r\}{al​,...,ar​}中，選出一個長度為kkk的子區間，將該子區間的每個數字都增加任意正整數ccc 如(3,−1,1,−2,2,0)(3,-1,1,-2,2,0)(3,−1,1,−2,2,0)，可以進行三次操作： 將1∼31\sim 31∼3都加上444，使得序列變成(3,3,5,2,2,0)(3,3,5,2,2,0)(3,3,5,2,2,0) 將2∼52\sim 52∼5都加上−2-2−2，使得序列變成(3,3,3,0,0,0)(3, ...

Codeforces 1661B Getting Zero 題目 https://codeforces.com/contest/1661/problem/B 給你nnn個數字，每個數字vvv可以有兩種操作。 v:=(v+1)%32768v:=(v+1)\%32768v:=(v+1)%32768 v:=(2×v)%32768v:=(2\times v)\%32768v:=(2×v)%32768 其中%\%%是取餘數的意思。 請你輸出對於每個數字，最少需要操作幾次才能把該數字變成0。 Solution 不難發現，每個數字需要操作的最多次數是151515次，為什麼呢？因為327683276832768是222的151515次方，所以對於所有數字vvv，v×215≡0(mod32768)v\times 2^{15}\equiv 0 (mod 32768)v×215≡0(mod32768) 然後我們就可以試著用dpdpdp來解這題了，令dp(i,j)dp(i,j)dp(i,j)為目前數字為iii並且已經操作了jjj次，然後要讓iii變成000的最少方法數是多少。 則dp(i,j)=min(( ...

AtCoder Beginner Contest 289 pE 題目 https://atcoder.jp/contests/abc289/tasks/abc289_e 有兩個人，分別在節點111和節點nnn，兩個人每次移動都可以移動到相鄰的節點，並且兩個人移動到的節點顏色必須相異，求第一個人移動到nnn且第二個人移動到111的最短路。 Solution 這題我賽中是想到多源點BFS，只是後來發現每個點可能不只會被同一個人經過一次，所以就燒雞了。 賽後同學提示可以把兩個人所在的位置看成一個狀態，所以就往dp的方向去想了，dp[i][j]dp[i][j]dp[i][j]代表第一個人從111走到iii且第二個人從nnn走到jjj的最短路徑。 初始狀態dp[1][n]=0dp[1][n] = 0dp[1][n]=0，然後只要跑一次最短路求出dp[n][1]dp[n][1]dp[n][1]就好了，這裡是用dijkstra演示 AC Code 12345678910111213141516171819202122232425262728293031323334353637383940414243 ...

2021 NTHU NCPC pre Contest Hive 題目 http://adalab.cs.nthu.edu.tw/contest/26/problem/W2-5 有一個由六邊形格子所組成的圖，每個格子上都會有一些點數，然後給你兩組起點和終點，問你這兩組點連線且連線不相交的情況下最小點數和是多少，如果無解請輸出−1-1−1 Solution 這題的官解是輪廓線DP，但其實我們可以用一些剪枝的技巧來AC掉這題 能越快走到的就先走，不要繞遠路。大概就是像下面這張圖一樣 而剪的方式就是紀錄每個格子的degree，如果他相鄰格子的degree數總和≥2\ge 2≥2的話就可以不用走了，就像圖中畫叉叉的地方一樣，因為那樣走一定會是繞遠路 而其他的小剪枝像是目前答案>\gt>目前找到的最小值就可以不用再走了 枚舉完第一條後第二條就可以用其他最短路算法去求，這裡是用dijkstra AC code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849 ...