題意：二維平面上有一堆氣球匕坯，你可以選擇一行x一列y践磅，給出一個常數(shù)r粹断。你能獲取到所有橫坐標在x，x+r，x-r和縱坐標在y，y+r每辟，y-r的所有氣球。求最大的氣球獲取數(shù)干旧。 題解...
發(fā)簡信
IP屬地：廣東
-
2019排±浚客第九場F題（Popping Balloons）貪心 + multiset / 線段樹
-
2019徘郏客第九場A題 (The power of Fibonacci) 斐波那契循環(huán)節(jié)
題意：給出斐波那契數(shù)列, 。給兩個數(shù)n椎眯，m挠将。求 題解：考慮皮薩諾周期 ， 注意到 , 并且 盅视。于是, 捐名。7812500是一個不大的數(shù)，預處理前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牛客第八場J題 (Just Jump) 隔板法 + 容斥
題意：你要從0跳到L森缠，每一步距離不能小于d拔鹰，并且下面有m組(t,p)代表一次攻擊，你不能在第t次調(diào)到位置p贵涵。求方案數(shù)格郁。() 題解：首先不考慮m次攻擊，可以用dp求出答案： 独悴。...
-
2019爬椋客第八場A題 (All-one Matrices) 單調(diào)棧題意：給一個01矩陣，求其中極大全1子矩陣的個數(shù)刻炒，極大指的是這個矩陣不能再往擴展决采。 題解：枚舉每個子矩陣的底邊，維護一個單調(diào)棧（嚴格遞增）坟奥。 如上圖所示树瞭，棧中維護往上拓展的高...
-
2019牛客第七場E題 (Find the median) 思維
題意：給n個操作爱谁，每次和 （1e9范圍內(nèi)）即往數(shù)組里面插所有 的所有數(shù)晒喷，求每次操作后的中位數(shù) 題解：區(qū)間離散化然后二分答案，因為小于中位數(shù)的數(shù)字恰好有個访敌，這顯然具有單調(diào)性凉敲。那...
-
2019牛客第七場H題 (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ù)群嗤，復雜度是 菠隆，其中，n是 的階（在這里n=p-1） ——fro...
-
HDU-6624 （杭電多校第5場 fraction）輾轉相除
題意：給定x和p狂秘，求一個最小的b使得存在一個 并且骇径。 題解：由于 ， 那么 , , 于是 者春，從而 破衔。那么我們就是要求一個最小的b，這就可以通過輾轉相除（出題人管這叫輾轉相除...
-
2019徘蹋客第六場G題 (Is Today Friday) 暴力
題意：給你一串日期晰筛，這些日期都是星期五。但是每個字符都被加密了拴袭，以一種簡單的映射（根據(jù)題意读第，是一個雙射）規(guī)則比如A映射到0，B映射到1拥刻。要求一個合法的字典序最小的映射怜瞒。日期的...
-
2019牛客第五場G題 (subsequence 1) DP
題意：給一個數(shù)字字符串s和t般哼，求s中有多少個子序列比t更大 題解：如果子序列比t更長吴汪，那么只要開頭不是0都可以，暴力枚舉做這件事就好了蒸眠。問題在于子序列和t等長的情形漾橙。從前往后...
-
2019牛客第五場 F (maximum clique 1) 二分圖最大獨立集/網(wǎng)絡流
題意：給n (n≤5000) 個不同的數(shù)字楞卡，在這n個數(shù)字的集合中找到一個最大的子集使得這個子集中的元素滿足如下的性質(zhì)：子集中任何兩個數(shù)字都至少有兩個bit位不同（Hammin...
-
2019潘耍客第五場E題(independent set1) 圖論+狀壓DP
題意：給一個圖有n個點m條邊()脾歇，求這張圖的所有Induced subgraph（誘導子圖？）的最大獨立集大小的和 題解：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ù)，陪域為復數(shù)的函數(shù)代咸。我們主要研究定義域為正整數(shù)蹈丸，值域為整數(shù)的函數(shù)。 積性函數(shù)：滿足 若a, b互質(zhì)呐芥，...