文章目錄

• T1：1-02E. JM的西伯利亞特快專遞
• • 題目
  • 題解
  • code
• T2：壽司晚宴
• • 題目
  • 題解
  • code
• T3：荷馬史詩
• • 題目
  • 題解
  • code

T1：1-02E. JM的西伯利亞特快專遞

題目

今天JM收到了一份來自西伯利亞的特快專遞，里面裝了一個字符串 s ，僅包含小寫英文字母。于是JM決定跟qz和寒域爺一起玩一個游戲：

JM手里拿著字符串 s，qz手里拿著字符串 t ，寒域爺手里拿著字符串 u ，初始時t和u均為空。有兩種操作：
將字符串 s 的首部字符取出，插入字符串 t 的尾部。
將字符串 t 的尾部字符取出，插入字符串 u 的尾部。

JM，qz和寒域爺隨意地進行上述兩種操作，直到字符串s和t均為空時才停止。現在JM想知道，他們能得到的字典序最小的字符串 u 是什么。

注意，對于一個字符串s，其長度為n，其中字符的下標為1，2…n，則我們定義s的首部字符為$s_1$，尾部字符為 $s_n$

輸入格式
一行一個字符串s。
輸出格式
一行一個字符串u表示答案。

樣例
樣例輸入
cbaa
樣例輸出
aabc
數據范圍與提示
$1\le |s|\le 10^5$

題解

字典序最小的話也就是說對于一個字符串，越小的字母就要盡可能越早離開$s$
仔細讀題會發現其實就是下圖的過程：

也就是說$t$只是起一個中轉站的作用，且性質與棧一樣，所以我們想到了↓

用一個雙關隊列或者棧來儲存當遍歷到$i$位時，還剩余在$s$里面的字母
接著我們來考慮對于一個字母$x$它將面臨哪些選擇？
　1.當$x<q.back()$，意思就是當前字母比已遍歷的且沒有丟進$u$的最后一個字母小，
　根據規則我們肯定想$x$先出來，所以就可以直接放在隊列的最后面
　
　2.當$x>=q.back()$，如果這個時候仍然選擇放在隊列后面，
　那么不管后面如何操作，$x$一定比$q.back()$先出來，字典序會變小，
　所以就要先把前面$<x$的字母丟出去
如果你認為這樣就能$AC$，那你真的是想多了，仔細想想剛才的情況二，我們太過于粗魯

zzcadbde——>abdcdezz
錯誤答案：acbddezz

為什么會出現這種情況，很簡單，因為在判斷$c,d$時，我們忽略了$d$后面還有個字典序更小的$b$
因此為了解決這種情況，就定義一個后綴數組，$pre[i]$表示$i?n$中字典序最小的字母是什么，
那么我們只需要用$c$和$d$的$pre$進行比較即可，也就相當于用$c$去和$b$比較，就可以預知到后面的走向

code

#include <cstring> #include <cstdio> #include <deque> using namespace std; #define MAXN 100005 deque < char > q; char s[MAXN], pre[MAXN]; int len;int main() {scanf ( "%s", s );len = strlen ( s );pre[len] = 'z' + 1;for ( int i = len - 1;i >= 0;i -- )pre[i] = min ( s[i], pre[i + 1] );for ( int i = 0;i < len;i ++ ) {if ( q.empty() )q.push_back ( s[i] );else if ( ! q.empty() && q.back() > s[i] )q.push_back ( s[i] );else {while ( ! q.empty() ) {if ( q.back() <= s[i] && q.back() <= pre[i] ) {printf ( "%c", q.back() );q.pop_back();}elsebreak;}q.push_back ( s[i] );}}while ( ! q.empty() ) {printf ( "%c", q.back() );q.pop_back();}return 0; }

T2：壽司晚宴

題目

為了慶祝NOI的成功開幕，主辦方為大家準備了一場壽司晚宴。小G和小W作為參加NOI的選手，也被邀請參加了壽司晚宴。

在晚宴上，主辦方為大家提供了n?1種不同的壽司，編號1,2,3,?,n-1，其中第種壽司的美味度為i+1（即壽司的美味度為從2到n）。

現在小G和小W希望每人選一些壽司種類來品嘗，他們規定一種品嘗方案為不和諧的當且僅當：小G品嘗的壽司種類中存在一種美味度為x的壽司，小W品嘗的壽司中存在一種美味度為y的壽司，而x與y不互質

現在小G和小W希望統計一共有多少種和諧的品嘗壽司的方案（對給定的正整數p取模）。注意一個人可以不吃任何壽司

輸入格式
從文件dinner.in中讀入數據。
輸入文件的第1行包含2個正整數n，p中間用單個空格隔開，表示共有n種壽司，最終和諧的方案數要對p取模。

輸出格式
輸出到文件dinner.out中。
輸出一行包含1個整數，表示所求的方案模p的結果。

輸入輸出樣例
輸入
3 10000
輸出
9

輸入
4 10000
輸出
21

輸入
100 100000000
輸出
3107203
說明/提示
【數據范圍】

【時限1s，內存512M】

題解

猜測：一般這種方案數還帶模$99\%$都是$dp$
兩者選的壽司互質，充要條件就是兩人選的壽司的質因子是不重復的，就可以用狀壓判斷質因子，證實了$dp$猜測
首先我們打個質數表，發現$500$以內的質數個數為$95$
但是我們再用計算機一算$21?23=483,23?29=667$，也就是說$500$以內的數最多只會有一個質因數$>22$，所以就可以單獨提出來考慮，沒有就為0
那么剩下的小質因子數就只有$8$個（$2,3,5,7,11,13,17,19$）

設$dp[i][j][k]$表示在選第$i$個壽司時，甲選的質因子集合是$j$，乙選的質因子集合是$k$，則有
$$dp[i][j|food[i].s][k]+=dp[i?1][j][k](k\&food[i].s==0)$$
$$dp[i][j][k|food[i].s]+=dp[i?1][j][k](j\&food[i].s==0)$$
前提都是另外一個所選的質因子中沒有當前食物的質因子，接著發現$i$只與$i?1$有關，所以用滾動將之滾成二維，簡單吧跳過

接著我們要處理一下大質因子這個玩意兒，設$fg[j][k],fw[j][k]$
對于每一段大質因子相同的數，我們在這一段開始的時候把$dp$的值賦給$fg$和$fw$，然后在這一段內部用上面的遞推方法繼續搞
$$fg[j|s][k]+=dp[j][k](k\&s==0)$$
$$fw[j][k|s]+=dp[j][k](j\&s==0)$$
$s$表示小質因子的集合
最后在重新丟給$dp$即可
$$dp[j][k]=fg[j][k]+fw[j][k]?dp[j][k]$$
因為有可能這個食物兩個人都不選，那么$dp$就分別被$fg,fw$統計了，最后就是多統計了一次，減掉就行了

具體的代碼部分解釋在$code$中

code

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define LL long long #define MAXN 505 int p[10] = { 0, 2, 3, 5, 7, 11, 13, 17, 19, 0 }; struct node {int val, big, s;void init () {int tmp = val;big = s = 0;for ( int i = 1;i <= 8;i ++ ) {if ( tmp % p[i] == 0 ) {s |= ( 1 << ( i - 1 ) );while ( tmp % p[i] == 0 )tmp /= p[i];}}if ( tmp != 1 )big = tmp;} }food[MAXN]; int n; LL result, mod; LL dp[MAXN][MAXN], fg[MAXN][MAXN], fw[MAXN][MAXN];bool cmp ( node x, node y ) {return x.big < y.big; }int main() {scanf ( "%d %lld", &n, &mod );for ( int i = 2;i <= n;i ++ ) {food[i].val = i;food[i].init();}sort ( food + 2, food + n + 1, cmp );dp[0][0] = 1;//初始化，兩人什么都不選也算一種情況 for ( int i = 2;i <= n;i ++ ) {if ( i == 2 || food[i].big ^ food[i - 1].big || ! food[i].big ) {memcpy ( fg, dp, sizeof ( dp ) );memcpy ( fw, dp, sizeof ( dp ) );}for ( int j = 255;j >= 0;j -- )//j枚舉的是小G選擇的質因子 for ( int k = 255;k >= 0;k -- ) {//k枚舉的是小W選擇的質因子 if ( j & k )//有重復肯定是不合法的 continue;if ( ( food[i].s & k ) == 0 )//該質因子沒有被小W選擇可以被小G選擇 fg[j | food[i].s][k] = ( fg[j | food[i].s][k] + fg[j][k] ) % mod;if ( ( food[i].s & j ) == 0 )//該質因子沒有被小G選擇可以被小W選擇fw[j][k | food[i].s] = ( fw[j][k | food[i].s] + fw[j][k] ) % mod;}if ( i == n || food[i].big ^ food[i + 1].big || ! food[i].big ) {for ( int j = 0;j <= 255;j ++ )for ( int k = 0;k <= 255;k ++ )dp[j][k] = ( fg[j][k] + fw[j][k] - dp[j][k] + mod ) % mod;}}for ( int i = 0;i <= 255;i ++ )for ( int j = 0;j <= 255;j ++ )result = ( result + dp[i][j] ) % mod;printf ( "%lld", result );return 0; }

T3：荷馬史詩

題目

追逐影子的人，自己就是影子 ——荷馬
Allison 最近迷上了文學。她喜歡在一個慵懶的午后，細細地品上一杯卡布奇諾，靜靜地閱讀她愛不釋手的《荷馬史詩》。但是由《奧德賽》和《伊利亞特》 組成的鴻篇巨制《荷馬史詩》實在是太長了，Allison 想通過一種編碼方式使得它變得短一些。

一部《荷馬史詩》中有n種不同的單詞，從1到n進行編號。其中第i種單 詞出現的總次數為wi。Allison 想要用k進制串si來替換第i種單詞，使得其滿足如下要求：

對于任意的 1 ≤ i, j ≤ n ， i ≠ j ，都有：si不是sj的前綴。

現在 Allison 想要知道，如何選擇si，才能使替換以后得到的新的《荷馬史詩》長度最小。在確保總長度最小的情況下，Allison 還想知道最長的si的最短長度是多少？

一個字符串被稱為k進制字符串，當且僅當它的每個字符是 0 到 k ? 1 之間（包括 0 和 k ? 1 ）的整數。

字符串 str1 被稱為字符串 str2 的前綴，當且僅當：存在 1 ≤ t ≤ m ，使得str1 = str2[1…t]。其中，m是字符串str2的長度，str2[1…t] 表示str2的前t個字符組成的字符串。

輸入格式
輸入的第 1 行包含 2 個正整數 n, k ，中間用單個空格隔開，表示共有 n種單詞，需要使用k進制字符串進行替換。
接下來n行，第 i + 1 行包含 1 個非負整數wi ，表示第 i 種單詞的出現次數

輸出格式
輸出包括 2 行
第 1 行輸出 1 個整數，為《荷馬史詩》經過重新編碼以后的最短長度。
第 2 行輸出 1 個整數，為保證最短總長度的情況下，最長字符串 si 的最短長度。

輸入輸出樣例
輸入
4 2
1
1
2
2
輸出
12
2

輸入
6 3
1
1
3
3
9
9
輸出
36
3
說明/提示
【樣例說明 1】
用 X(k) 表示 X 是以 k 進制表示的字符串。
一種最優方案：令 00(2) 替換第 1 種單詞， 01(2) 替換第 2 種單詞， 10(2) 替換第 3 種單詞，11(2) 替換第 4 種單詞。在這種方案下，編碼以后的最短長度為：
1 × 2 + 1 × 2 + 2 × 2 + 2 × 2 = 12
最長字符串si的長度為 2 。
一種非最優方案：令 000(2) 替換第 1 種單詞，001(2) 替換第 2 種單詞，01(2)替換第 3 種單詞，1(2) 替換第 4 種單詞。在這種方案下，編碼以后的最短長度為：
1 × 3 + 1 × 3 + 2 × 2 + 2 × 1 = 12
最長字符串 si 的長度為 3 。與最優方案相比，文章的長度相同，但是最長字符串的長度更長一些

【樣例說明 2】
一種最優方案：令 000(3) 替換第 1 種單詞，001(3) 替換第 2 種單詞，01(3) 替換第 3 種單詞， 02(3) 替換第 4 種單詞， 1(3) 替換第 5 種單詞， 2(3) 替換第 6 種單詞。

【提示】
選手請注意使用 64 位整數進行輸入輸出、存儲和計算。
【時限1s，內存512M】

題解

$知識儲備$
哈夫曼樹
給定$N$個權值作為$N$個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近

哈夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的路徑長度是從樹根到每一結點的路徑長度之和

應用有哈夫曼編碼

多叉哈夫曼樹
哈夫曼樹也可以是$k$叉的，只是在構造$k$叉哈夫曼樹時需要先進行一些調整。構造哈夫曼樹的思想是每次選$k$個權重最小的元素來合成一個新的元素，該元素權重為$k$個元素權重之和。但是當$k>2$時，按照這個步驟做下去可能到最后剩下的元素少于$k$個。
解決這個問題的辦法是假設已經有了一棵哈夫曼樹(且為一棵滿k叉樹)，則可以計算出其葉節點數目為$(k?1)nk+1$,式子中的$nk$表示子節點數目為$k$的節點數目。于是對給定的$n$個權值構造k叉哈夫曼樹時,可以先考慮增加一些權值為$0$的葉子節點，使得葉子節點總數為$(k?1)nk+1$這種形式,然后再按照哈夫曼樹的方法進行構造即可
——以上均來自百度百科

---

讀完這道題，你就會發現和上面的知識儲備對應起來，所以這道題對于一個了解哈夫曼樹的人就是一道裸題，對于別人就是。。。

類比于NOIP2004 合并果子
——摘自luogu某dalao

看了這句話后，可能許多人都有重見天日的感覺，我也這么認為，這句話真的揭示了這道題的本質

code

#include <queue> #include <cstdio> using namespace std; #define int long long #define MAXN 1000005 struct node {int w, h;node () {}node ( int W, int H ) {w = W;h = H;} }; bool operator < ( node a, node b ) {if ( a.w != b.w )return a.w > b.w;return a.h > b.h; } priority_queue < node > q; int n, k, cnt, result; int w[MAXN];signed main() {scanf ( "%lld %lld", &n, &k );for ( int i = 1;i <= n;i ++ ) {scanf ( "%lld", &w[i] );q.push( node ( w[i], 0 ) );}if ( ( n - 1 ) % ( k - 1 ) )//要判斷是否需要加空節點，不然cnt會算錯 cnt = ( k - 1 ) - ( n - 1 ) % ( k - 1 );//( n - 1 ) % ( k - 1 )是最后一次合并不足k的個數，減掉才是要加的空節點 for ( int i = 1;i <= cnt;i ++ )q.push( node ( 0, 0 ) );cnt += n;while ( cnt > 1 ) {int sum = 0, maxh = 0;for ( int i = 1;i <= k;i ++ ) {sum += q.top().w;maxh = max ( maxh, q.top().h );q.pop();}result += sum;q.push( node ( sum, maxh + 1 ) );cnt -= ( k - 1 );}printf ( "%lld\n%lld\n", result, q.top().h );return 0; }

就完了，有問題歡迎評論，點個贊唄~

總結

以上是生活随笔為你收集整理的周末狂欢赛4（1-02E. JM的西伯利亚特快专递，寿司晚宴，荷马史诗）的全部內容，希望文章能夠幫你解決所遇到的問題。

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