摘要： Problem E 題意: 戳這里 長度為$n$的串 ,串的字符集為$A$ 還有一個序列$B$,元素個數為$m$, 保證$B_{1}<B_{2}<...<B_{m}$ 現在定義一種操作,每次 可以選擇一個$B_{i}$，使串先翻轉，再把除了前$B_{i}$和后$B_{i}$的串翻轉回來. 定義兩個串 閱讀全文

摘要： 題意: 給定$x,y,n,a_{0},m,g$. 定義$a_{i}=x*a_{i-1}+y\ mod\ m$ 求$a_{n}\ mod\ g$ $n,m,x,y,a<=10^{18},g<=10^{8}$ 題解: 當n較小,可以直接算出$a_{n}$ 可以得到$a_{n}$的通項公式 $a_{n}= 閱讀全文

摘要： 題意: 給定$n$,對于$[2,n]$中的每個正整數,從中選出兩個集合,使得兩個集合各自的LCM互質,答案對$p$取模. $n<=500,p<=1^{9}$ 題解: 暴力做法,預處理出$<=n$的所有素因子. 進行狀壓DP,$dp[i][a][b]$表示前$i$個點,所選集合中的素因子集合分別為$a 閱讀全文

摘要： 題意: 給定一棵$n$節點的有根樹,現在有兩種操作. $1)$給定$x$,詢問$x$節點到根路徑上沒被標記的點的個數,并把路徑上所有點標記. $2)$給定$x$,詢問$x$子樹內被標記的點的個數,并把子樹內所有點的標記撤銷. $n<=10^{5}$ 題解: 題目要求維護點到根的路徑以及點的子樹的信息 閱讀全文

摘要： 題意: 有一些變量$x_{i}$,給出$n$個形如"$i,j,e$"的約束條件,判斷能否存在一個$x$的賦值方案滿足所有約束. $e=0$ 表示$x_{i}=x_{j}$ $e=1$ 表示$x_{i}≠x_{j}$ $n<=10^{5},i,j<=10^{9},e={0,1}$ 題解: 先處理所有$ 閱讀全文

摘要： 題意： 有一個$n*m$的矩陣.現在要在矩陣中寫三個字母"N","O","I",求出寫下合法字母的格子的權值和的最大值. 書寫規則如下: $n<=150,m<=500,-200<=A[i][j]<=200$ 題解: 此題的$n,m$范圍較小,可以考慮DP. 分段考慮. 字母"O"和"I"都可以用簡單 閱讀全文

摘要： 2017-05-03(197) ▲22:15:08 HNOI2015 接水果 整體二分+BIT 對于第K小的問題可以轉化為二分,多個詢問那就整體二分,把問題變為計數問題.考慮問題的轉化,路徑(a,b)的子路徑(c,d),假如cd的lca不是端點,那么a,b一定分別在c,d的兩個子樹內部,用dfs區間 閱讀全文

摘要： 2017-04-01周六(165) ▲22:28:43 BZOJ1497 最小割模型 注意邊數*2!!! 2017-04-10周一(166) 學考考完我又是一條好漢!!十月再戰!! ▲21:30:56 WC2007 剪刀石頭布 費用流建模/正難則反 題目求最多有多少個"石頭剪刀布"的情況. 對于(a 閱讀全文

摘要： 2017-03-01周三(121) ▲07:57:49 CTSC2010 D1T3 性能優化 NTT變形/快速冪 ▲14:06:15 QTREE4 邊分治/堆/構造虛點 對于求解"路徑",可以考慮邊分治,這是很好的選擇.每次找到一條邊,保證邊分成的兩棵子樹sz的較大值最小.然后求解一定經過這條邊的答 閱讀全文

摘要： 2017-01-10 周二(72) ▲18:26:53 UOJ130 荷馬史詩(NOI2015) 哈弗曼樹/優先隊列:得到最優解的方法:先把每個點作為大小為1的樹,每次從所有樹里選擇兩個權值最小的合并成一個樹.直到最后只剩下一棵樹.為了維護最長長度最小,只要讓優先隊列維護兩維,一是權值,二是長度,每 閱讀全文