當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

HUST-2015 Multi-University Training Contest 9

發布時間：2023/12/10 编程问答 63 豆豆

生活随笔收集整理的這篇文章主要介紹了 HUST-2015 Multi-University Training Contest 9 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

2015 Multi-University Training Contest 9 solutions BY xudyh

1001.Expression

記 $dp_{l,r}dp?l,r??表示l,rl,r這段數能形成的答案總和。$

枚舉最后一步操作 $kk，如果是乘法，答案為dp_{l,k}*dp_{k+1,r}dp?l,k???dp?k+1,r??，由于分配率這個會乘開來。如果是加法那么是dp_{l,r}*(r-k-1)!+dp_{k+1,r}*(k-l)!dp?l,r???(r?k?1)!+dp?k+1,r???(k?l)!，即要乘上右邊k+1,rk+1,r這些數所有可行的方案數，減法同理。最后乘上{r-l-2 \choose k-l}(?k?l?r?l?2??)，即把兩邊操作合起來的方案數。$

答案為 $dp_{1,n}dp?1,n??。$

1002.Hack it!

首先我們將4個位置合并成一塊，可以放"(())"或者"()()"。記這兩個部分對應的權值分別為 $w_1,w_2w?1??,w?2??(對rr取模后)，那么如果第一個串里放"(())"，第二個串里放"()()"，這樣對答案f(a)-f(b)f(a)?f(b)的貢獻是w_1-w_2w?1???w?2??，否則對答案的貢獻為00或者w_2-w_1w?2???w?1??。$

這樣能得到 $25002500個塊，假設每塊的貢獻值為c_1,c_2,\cdots,c_{2500}c?1??,c?2??,?,c?2500??。于是我們要構造d_1,d_2,\cdots,d_{2500}d?1??,d?2??,?,d?2500??，其中d_i\in {-1,0,1}d?i??∈{?1,0,1}，使得\sum_{i=1}^{2500} c_id_i=0∑?i=1?2500??c?i??d?i??=0。$

使用優先隊列維護這些數，每次刪掉最大的兩個，然后把他們的差插入到優先隊列中，直到出現兩個相同的數為止，然后還原方案。在隨機數據的條件下是能跑得出解的。

感性認識一下，就是做完一輪后，大概每個數的大小為原范圍除掉

1003.GCD Tree

對于單組詢問，考慮從大到小枚舉公約數，假設當前是d，那么將d和它倍數之間連邊即可，所以只要考慮(i,j)這樣的邊，其中j是i的倍數。

對于多組數據，從1枚舉到n，然后加入他向因子連的所有邊，使用LCT維護最大生成樹即可。

時間復雜度 $O(n\log^2n)O(nlog?2??n)。$

1004.Too Simple

首先要求每個 $f_if?i??是個排列，否則如果某個f_if?i??將兩個數映射向同一個數，那么最后這兩個數得到的值一定相同。$

如果還剩一個位置為 $-1?1，那么這個排列是唯一確定的，假設X*f_i*Y=IX?f?i???Y=I，那么f_i=X^{-1}*Y^{-1}f?i??=X??1???Y??1??.$

所以假設有 $c(c\geq 1)c(c≥1)個-1?1，那么答案為(n!)^{c-1}(n!)?c?1??個可行的方案。$

注意特判所有函數都已知的情況。

1005.Arithmetic Sequence

首先預處理出來出 $ii這個位置向前d_1d?1??的等差序列和向后d_2d?2??的等差數列能延續到多長，記作l_i,r_il?i??,r?i??。$

如果 $d_1\neq d_2d?1??≠d?2??，那么枚舉中間位置，答案為l_i*r_il?i???r?i??。$

如果 $d_1=d_2d?1??=d?2??，枚舉開始位置，答案為r_ir?i??。$

1006.Persistent Link/cut Tree

考慮爆搜，樹 $ii生成后，兩兩點對路徑分成兩部分，一部分不經過中間的邊，那么就是a_ia?i??和b_ib?i??的答案，如果經過中間的邊，首先計算中間這條邊出現的次數，也就是a_i,b_ia?i??,b?i??子樹大小的乘積。對于a_ia?i??，對答案的貢獻為所有點到c_ic?i??的距離和乘上b_ib?i??的子樹大小。b_ib?i??同理。$

那么轉化為計算在樹 $ii中，所有點到某個點jj的距離和。假設jj在a_ia?i??內，那么就轉化成了a_ia?i??內jj這個點的距離總和加上b_ib?i??內所有點到d_id?i??的總和加上d_id?i??到jj的距離乘上子樹b_ib?i??的大小，稱作第一類詢問。$

這樣就化成了在樹 $ii中兩個點jj和kk的距離，如果在同一棵子樹中，可以遞歸下去，否則假設jj在a_ia?i??中kk在b_ib?i??中，那么距離為jj到c_ic?i??的距離加上kk到d_id?i??的距離加上l_il?i??，稱作第二類詢問。$

然后對兩類詢問全都記憶化搜索即可。

接著考慮計算一下復雜度。

對于第二類詢問，可以考慮詢問的過程類似于線段樹，只會有兩個分支，中間的部分已經記憶化下來，不用再搜，時間復雜度

我們分析一下復雜度，首先對于第一類詢問，在 $b_ib?i??中到d_id?i??的點距離和已經由前面的詢問得到，那么就轉化為一個第一類詢問和一個第二類詢問，最多會被轉化成O(m)O(m)個第二類詢問。$

所以每個詢問復雜度是 $O(m^2)O(m?2??)，總復雜度O(m^3)O(m?3??)。$

1007.Travelling Salesman Problem

首先如果

如果

構造方法是這樣，首先RRRRDLLLLD這樣的路徑走到這個格子所在行或者上一行，然后DRUR這樣走到這個格子的所在列或者前一列，然后繞過這個格子。然后走完這兩行，接著按LLLLDRRRR這樣的路徑往下走。

1008.Goldbach's Conjecture

首先考慮一下如果一個數 $x=\prod_{i=1}^k p_i^{e_i},p_1<p_2<\cdots<p_kx=∏?i=1?k??p?i?e?i????,p?1??<p?2??<?<p?k??，那么充要條件就是每個p_i-1p?i???1能被前面的一些因子表示出來，也就是p_i\leq d(\prod_{j=1}^{i-1}p_j^{e_j})+1p?i??≤d(∏?j=1?i?1??p?j?e?j????)+1。$

可以直觀理解一下，如果 $p_i-1p?i???1不能被表示前面的因子出來肯定是不行的。否則這樣一定能連續的表示出11到因子和的所有數，可以考慮類似p_ip?i??進制表示，c*p_i^kc?p?i?k??前面的系數cc用那些小的因子去湊，這樣就行了。$

然后如果 $mm是好數，那么mn(1\leq n\leq 2m)mn(1≤n≤2m)也是好數，因為m-1m?1能用除了mm以外的因子拼出來，那么d(m)\geq m-1+m=2m-1d(m)≥m?1+m=2m?1，類似于上述的理由，mnmn也是好數。$

如果 $mm和m+2m+2都是好數，那么m^2+2m?2??+2到3m^23m?2??之間的數能被表示成mx+(m+2)ymx+(m+2)y的形式，其中1\leq x\leq 2m,1\leq y\leq 2(m+2)1≤x≤2m,1≤y≤2(m+2)，這個可以考慮線性不定方程的通解。$

所以只要預處理出一系列

1009.Random Inversion Machine

這題改自去年鞍山賽區的Random Inversion Machine，去掉了每段分別排序這個條件，所以這題的做法復雜得多。

首先轉化成，對于所有劃分 $c_1,c_2,\cdots,c_lc?1??,c?2??,?,c?l??，枚舉所有c_{i-1}\leq a_i<b_i\leq c_ic?i?1??≤a?i??<b?i??≤c?i??，然后所有(a_i,b_i)(a?i??,b?i??)為逆序的概率。$

比如 $k=3k=3，劃分成了[1,3],[4,6][1,3],[4,6]，假設X_{i,j}X?i,j??為i,ji,j為逆序對的隨機變量，那么E((X_{1,2}+X_{1,3}+X_{2,3})(X_{4,5}+X_{4,6}+X_{5,6}))E((X?1,2??+X?1,3??+X?2,3??)(X?4,5??+X?4,6??+X?5,6??))，這個東西可以展開。比如其中某項E(X_{1,2}X_{4,5})E(X?1,2??X?4,5??)，那么就相當于1,21,2為逆序對4,54,5為逆序對的概率。$

然后用有向邊表示大小關系，如果 $ii連向jj，那么代表有ii位置的數小于jj位置的數。那么一開始給定的限制p_1,p_2,\cdots,p_mp?1??,p?2??,?,p?m??形成了一條鏈，稱為主鏈。$

對于前面算某些位置為逆序對的概率，相當于多加了很多限制，也就是連了很多額外的邊。概率就為給這個圖上面的點隨機標號，然后大小關系滿足邊的指向的概率。

考慮每段選的兩個數，如果都在主鏈上，那么一定無解，因為不可能為逆序對。如果都不在主鏈上，那么概率為

如果所有邊都連入主鏈，那么整個圖就形成了有根樹的結構，這樣的圖的概率為每個點子樹大小乘積的倒數，因為每個點都要在子樹里最小。

對于連出主鏈的邊，可以這樣轉化不連這條邊形成的圖對應的概率減去將這條邊反向之后圖對應的概率。因為兩個數

我們可以使用 $dpdp來做上述過程，dp_{i,j,k}dp?i,j,k??表示前ii個數，劃分成jj段，然后主鏈上連入了kk條邊，轉移的時候枚舉當前一段的右端點rr，然后枚舉這一段里面選了那兩個數，然后按照前面所講的概率分別轉移。對于連出去的邊，按不加這條邊的概率轉移向dp_{r,j+1,k}dp?r,j+1,k??，將這條邊取反后的概率乘上-1?1轉移向dp_{r,j+1,k+1}dp?r,j+1,k+1??。因為知道多少個點連入了主鏈，所以可以知道每個主鏈上的數對應的概率。$

然后如果

總復雜度 $O(n^4)O(n?4??)。$

1010.Sometimes Naive

對于詢問

使用樹鏈剖分，然后維護一下每個點輕鏈兒子的子樹權值和的平方即可。

修改操作時，每次從一條重鏈跳到另一條重鏈時，修改一下跳進去那個點的權值和。

查詢操作時，如果在同一條重鏈上用線段樹可以解決，注意不同重鏈之間不要重復計算即可。最后加上LCA以上的那棵子樹。

轉載于:https://www.cnblogs.com/wzb-hust/p/4853461.html

總結

以上是生活随笔為你收集整理的HUST-2015 Multi-University Training Contest 9的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： ffmpeg hevc 10bit bt
下一篇： The temporary upload