題意：二維平面上有一堆氣球，你可以選擇一行x一列y，給出一個常數(shù)r。你能獲取到所有橫坐標(biāo)在x，x+r，x-r和縱坐標(biāo)在y，y+r，y-r的所有氣球。求最大的氣球獲取數(shù)。 題解...
發(fā)簡信
IP屬地：廣東
-
2019?？偷诰艌鯢題（Popping Balloons）貪心 + multiset / 線段樹
-
2019牛客第九場A題 (The power of Fibonacci) 斐波那契循環(huán)節(jié)
題意：給出斐波那契數(shù)列, 。給兩個數(shù)n，m。求 題解：考慮皮薩諾周期 ， 注意到 , 并且 。于是, 。7812500是一個不大的數(shù)，預(yù)處理前7812500項的前綴和，然...
-
HDU - 6655 （杭電多校第七場 Just Repeat ）卡常題
題意：兩個人玩游戲：初始時分別有n和m張牌，每張牌有一個顏色。你不能出對面出過的顏色，沒有牌可以出的失敗。問誰會贏 題解：想法很簡單，對于每一種顏色i，玩家A有Ai 張牌，玩...
-
HDU - 6646 （杭電多校第七場 A + B = C ）思維
題意：給出a，b，c。求x，y，z滿足 。 題解：先把a，b，c去掉末尾的0得到A, B, C。這樣我們要解的方程就是： 。 如果 ， 那么有 ， 因為A和B的末尾都不是0 ...
-
2019?？偷诎藞鯦題 (Just Jump) 隔板法 + 容斥
題意：你要從0跳到L，每一步距離不能小于d，并且下面有m組(t,p)代表一次攻擊，你不能在第t次調(diào)到位置p。求方案數(shù)。() 題解：首先不考慮m次攻擊，可以用dp求出答案： 。...
-
2019?？偷诎藞鯝題 (All-one Matrices) 單調(diào)棧題意：給一個01矩陣，求其中極大全1子矩陣的個數(shù)，極大指的是這個矩陣不能再往擴展。 題解：枚舉每個子矩陣的底邊，維護(hù)一個單調(diào)棧（嚴(yán)格遞增）。 如上圖所示，棧中維護(hù)往上拓展的高...
-
2019?？偷谄邎鯡題 (Find the median) 思維
題意：給n個操作，每次和 （1e9范圍內(nèi)）即往數(shù)組里面插所有 的所有數(shù)，求每次操作后的中位數(shù) 題解：區(qū)間離散化然后二分答案，因為小于中位數(shù)的數(shù)字恰好有個，這顯然具有單調(diào)性。那...
-
2019?？偷谄邎鯤題 (Pair) 數(shù)位DP
題意：給三個數(shù)a,b,c，求pair<x,y> ，其中 ，并且滿足下列至少一條條件： 題解：由于兩個數(shù)都是位運算，考慮數(shù)位dp。又因為兩個情況都沒有包含等號，所以考慮都不滿...
-
HDU-6635 （杭電多校第6場 Nonsense Time）最長上升子序列
題意：給n個數(shù)字表示一個長度為n的數(shù)組a，再給出一個長度為n的數(shù)組k，k[i] 表示數(shù)組a的a[k[i]] 在第i時刻后可用。輸出n個數(shù)，表示第i個時刻的最長上升子序列的長度...
-
HDU-6632 （杭電多校第5場 discrete logarithm problem）Pohlig–Hellman algorithm
題意：已知a，b，p，求x使得, 并且 題解：利用Pohlig-Hellman Algorithm來做離散對數(shù)，復(fù)雜度是 ，其中，n是 的階（在這里n=p-1） ——fro...
-
HDU-6624 （杭電多校第5場 fraction）輾轉(zhuǎn)相除
題意：給定x和p，求一個最小的b使得存在一個 并且。 題解：由于 ， 那么 , , 于是 ，從而 。那么我們就是要求一個最小的b，這就可以通過輾轉(zhuǎn)相除（出題人管這叫輾轉(zhuǎn)相除...
-
2019?？偷诹鶊鯣題 (Is Today Friday) 暴力
題意：給你一串日期，這些日期都是星期五。但是每個字符都被加密了，以一種簡單的映射（根據(jù)題意，是一個雙射）規(guī)則比如A映射到0，B映射到1。要求一個合法的字典序最小的映射。日期的...
-
2019?？偷谖鍒鯣題 (subsequence 1) DP
題意：給一個數(shù)字字符串s和t，求s中有多少個子序列比t更大 題解：如果子序列比t更長，那么只要開頭不是0都可以，暴力枚舉做這件事就好了。問題在于子序列和t等長的情形。從前往后...
-
2019?？偷谖鍒?F (maximum clique 1) 二分圖最大獨立集/網(wǎng)絡(luò)流
題意：給n (n≤5000) 個不同的數(shù)字，在這n個數(shù)字的集合中找到一個最大的子集使得這個子集中的元素滿足如下的性質(zhì)：子集中任何兩個數(shù)字都至少有兩個bit位不同（Hammin...
-
2019?？偷谖鍒鯡題(independent set1) 圖論+狀壓DP
題意：給一個圖有n個點m條邊()，求這張圖的所有Induced subgraph（誘導(dǎo)子圖？）的最大獨立集大小的和 題解：n出到26顯然是為了卡掉naive的 的做法，所以我...
-
2019牛客第五場C題(generator2) BSGS
題意：給出 ，已知序列 滿足 ，再給出Q組詢問每次一個數(shù) ，求最小的index使得 , 不存在則輸出-1 題解：令, 于是有, 于是yi就成了一個等比數(shù)列。這樣我們就發(fā)現(xiàn)本題...
-
HDU-6623 (杭電多校第4場Minimal Power of Prime)
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=6623題意：對一個數(shù)質(zhì)因數(shù)分解，求得到的指數(shù)項中最小的那個值，數(shù)字小于 ，數(shù)據(jù)...
-
HDU-6621 （杭電多校第4場 K-th Closest Distance） 線段樹+二分
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=6621比賽的時候覺得是主席樹然后瘋狂T，最后發(fā)現(xiàn)是比別人多了次二分然后在本機上...
-
數(shù)論專題（寒假Day 5）
Day5 數(shù)論 一些定義和性質(zhì) , 只有 種取值 數(shù)論函數(shù)：定義域為正整數(shù)，陪域為復(fù)數(shù)的函數(shù)。我們主要研究定義域為正整數(shù)，值域為整數(shù)的函數(shù)。 積性函數(shù)：滿足 若a, b互質(zhì)，...