PMpro's blog

摘要： 前情提要： 怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？怎么辦？ 閱讀全文

摘要： [POI 2012] BON-Vouchers 考慮從倍數(shù)出發(fā)，如果值域是 \(m\)，\(mH(m)\)，是 \(O(m \ln)\) 的。 那么本題是否可以直接做？答案是不行，對于一個(gè)倍數(shù) \(k\)，之前 \(k\) 的倍數(shù)取到的數(shù)可能再次枚舉到，無法拿走（不計(jì)入貢獻(xiàn)），因此復(fù)雜度是不對的。 閱讀全文

摘要： 完工。 首先組合數(shù)的公式可以通過下降冪來表達(dá)： \[\large \begin{aligned} {n \choose k} &= \frac{n^{k\downarrow}}{k!}(n \in \mathbb{R})\\ *n^{k\downarrow}&=n\times (n-1) \time 閱讀全文

摘要： 考慮我們有 \(40\) 分的 \(O(n^2k)\) 暴力，是顯然的。 考慮 \(20\) 的 \(a_{i} < 2^8\)，考慮“去除不影響轉(zhuǎn)移代價(jià)的狀態(tài)。考慮到底是什么影響了轉(zhuǎn)移的代價(jià)？（主條目：性質(zhì)的發(fā)現(xiàn)）”，發(fā)現(xiàn)是 \(s_{i}\) 和 \(s_{j}\) 影響了轉(zhuǎn)移的代價(jià)，那么考慮將 閱讀全文

摘要： LCP 詐騙題，觀察到答案 <= 3。 枚舉 \(i\)，若 \(a_{1}\ne b_{i+1}\)，且存在 \(j(j>i+1)\) 使得 \(c_{j} \ne a_{1},c_{j} \ne b_{i+1}\)，即可以取到 \(0\)。 對于 \(1\) 同樣的套路記錄兩個(gè)字符討論一下即可。 閱讀全文

摘要： 一個(gè)長度為 \(n\) 的大數(shù)，用 \(S_1S_2S_3 \cdots S_n\)表示，其中 \(S_i\) 表示數(shù)的第 \(i\) 位, \(S_1\) 是數(shù)的最高位。告訴你一些限制條件，每個(gè)條件表示為四個(gè)數(shù)，\(l_1,r_1,l_2,r_2\)，即兩個(gè)長度相同的區(qū)間，表示子串 \(S_{l_ 閱讀全文

摘要： Day 1 萌萌噠 一個(gè)長度為 \(n\) 的大數(shù)，用 \(S_1S_2S_3 \cdots S_n\)表示，其中 \(S_i\) 表示數(shù)的第 \(i\) 位, \(S_1\) 是數(shù)的最高位。告訴你一些限制條件，每個(gè)條件表示為四個(gè)數(shù)，\(l_1,r_1,l_2,r_2\)，即兩個(gè)長度相同的區(qū)間，表示 閱讀全文

摘要： 考慮一個(gè)大數(shù)，如何對他取模 \(X\)？ \[\large \begin{aligned} n=10^{0}x_{0}+10^{1}x_{1}+10^{2}x_{2}+...+10^{k}x_{k} \end{aligned} \]只需要對每一位單獨(dú)考慮即可。 閱讀全文

摘要： C1. Hacking Numbers (Easy Version) 首先考慮 digit 這個(gè)操作可以將未知數(shù) \(x\) 的值域減小很多。在兩次 digit 過后，數(shù)的值域?yàn)?\([1,16]\)，接下來我們希望它變成一個(gè)固定的數(shù)，我們知道，減操作如果為非正數(shù)就不會(huì)進(jìn)行，利用這點(diǎn)，我們可以對原數(shù) 閱讀全文

摘要： A. [R11A]出現(xiàn)奇數(shù)次的偶數(shù) 我們開一個(gè) map 記錄每個(gè)數(shù)的出現(xiàn)次數(shù)。 把數(shù)組遍歷一遍看一個(gè)數(shù)如果又是偶數(shù)出現(xiàn)次數(shù)又是奇數(shù)就更新答案，最后輸出即可。 預(yù)計(jì)時(shí)間 \(\le 1min\)。 B. [R11B]前三小 我們記錄二元組 \((x,y)\) 表示第 \(x\) 個(gè)數(shù)出現(xiàn)位置是 \(y 閱讀全文