冰楓論壇

 找回密碼
 立即註冊
搜索
查看: 988|回覆: 0

[心得] [演算法心得] Codeforces. String Problem

[複製鏈接]

7

主題

0

好友

11

積分

新手上路

Rank: 1

UID
320966
帖子
146
主題
7
精華
0
積分
11
楓幣
756
威望
11
存款
0
贊助金額
0
推廣
0
GP
31
閱讀權限
10
性別
保密
在線時間
9 小時
註冊時間
2021-9-30
最後登入
2022-7-6
發表於 2022-5-16 14:02:31 |顯示全部樓層
本帖最後由 jimmyhealer 於 2022-5-16 14:03 編輯

嗨大家好~ 我是新加入論壇的萌新,之後可能會每日更新一下演算法心得,那目前會在 c/c++ 版,如果大家很熱絡的話再申請 演算法/競賽程式 版吧!

--------------------------------------------------- 正文開始 ---------------------------------------------------

題目名稱: String Problem
題目網站: Codefoces
題目網址: https://codeforces.com/problemset/problem/33/B
題目內容:

Boy Valera likes strings. And even more he likes them, when they are identical. That's why in his spare time Valera plays the following game. He takes any two strings, consisting of lower case Latin letters, and tries to make them identical. According to the game rules, with each move Valera can change one arbitrary character Ai in one of the strings into arbitrary character Bi, but he has to pay for every move a particular sum of money, equal to Wi. He is allowed to make as many moves as he needs. Since Valera is a very economical boy and never wastes his money, he asked you, an experienced programmer, to help him answer the question: what minimum amount of money should Valera have to get identical strings.

題目大意:

給你兩個字串,和一些轉換字元的規則及費用。
問你花最小的錢,讓兩個字串相等。

範例輸入 #1:
uayd
uxxd
3
a x 8
x y 13
d c 3

範例輸出 #1:
21
uxyd

範例輸入 #2:
a
b
3
a b 2
a b 3
b a 5

範例輸出 #2:
2b
--------------------------------------------------- 題解心得 ---------------------------------------------------

第一眼看到要最小花費,又有轉換以為是 DP,後來仔細想想字串前後沒有關係,所以直接單獨看一個字元的最小轉換花費。
接著可以思考如何找出最小花費,仔細研究轉換規則後可以轉成有向圖,有向圖就可以找最短路徑。

例如:
a → b → e  (10)
c → e         (20)
如上面這種情況,a 跟 c 要轉換成同一個字元 可以轉換成 e ,而花費會是 30。

AC code (30ms, 1.6 MB)
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define INF 0x3f3f3f3f
  4. #define MOD 1000000007
  5. #define io iOS::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6. using namespace std;
  7. const int MXN = 30;

  8. int path[MXN][MXN];
  9. int dis[MXN];

  10. void dijkstra(int s){
  11.   memset(dis, INF, sizeof(dis));
  12.   dis[s] = 0;
  13.   priority_queue<pair<int, int>, vector<pair<int, int> > , greater<pair<int, int> > > pq;
  14.   pq.push({dis[s], s});
  15.   while(!pq.empty()){
  16.     auto [w, u] = pq.top(); pq.pop();
  17.     for(int v = 0; v < 26; ++v){
  18.       if(dis[v] > dis[u] + path[u][v]){
  19.         dis[v] = dis[u] + path[u][v];
  20.         pq.push({dis[v], v});
  21.       }
  22.     }
  23.   }
  24. }

  25. void sol(){
  26.   ll ans = 0, n = 0, m = 0, k = 0;
  27.   string s1, s2;
  28.   cin >> s1 >> s2;
  29.   cin >> n;
  30.   memset(path, INF, sizeof(path));
  31.   for(int i = 0; i < n; ++i){
  32.     char u, v;
  33.     int w;
  34.     cin >> u >> v >> w;
  35.     if(w < path[u - 'a'][v - 'a'])
  36.       path[u - 'a'][v - 'a'] = w;
  37.   }
  38.   for(int i = 0; i < 26; ++i){
  39.     dijkstra(i);
  40.     for(int j = 0; j < 26; ++j){
  41.       path[i][j] = dis[j];
  42.     }
  43.   }

  44.   if(s1.size() != s2.size()){
  45.     cout << "-1";
  46.     return;
  47.   }

  48.   for(int i = 0; i < (int)s1.size(); ++i){
  49.     int tmp = INF;
  50.     char tmpc = s1[i];
  51.     for(int j = 0; j < 26; ++j){
  52.       if(tmp > path[s1[i] - 'a'][j] + path[s2[i] - 'a'][j]){
  53.         tmp = path[s1[i] - 'a'][j] + path[s2[i] - 'a'][j];
  54.         tmpc = j + 'a';
  55.       }
  56.     }
  57.     s1[i] = tmpc;
  58.     ans += tmp;
  59.   }
  60.   if(ans > INF){
  61.     cout << "-1\n";
  62.     return;
  63.   }
  64.   cout << ans << '\n';
  65.   cout << s1 << '\n';
  66. }

  67. int main(){
  68.   io
  69.   int t = 1;
  70.   while(t--){
  71.     sol();
  72.   }
  73. }

複製代碼
[發帖際遇]: jimmyhealer 超爽der,在口袋撿到 1 楓幣 幸運榜 / 衰神榜
複製連結並發給好友,以賺取推廣點數
簡單兩步驟,註冊、分享網址,即可獲得獎勵! 一起推廣文章換商品、賺$$
高級模式
B Color Image Link Quote Code Smilies |上傳

廣告刊登意見回饋關於我們管群招募本站規範DMCA隱私權政策

Copyright © 2011-2024 冰楓論壇, All rights reserved

免責聲明:本網站是以即時上載留言的方式運作,本站對所有留言的真實性、完整性及立場等,不負任何法律責任。

而一切留言之言論只代表留言者個人意見,並非本網站之立場,用戶不應信賴內容,並應自行判斷內容之真實性。

小黑屋|手機版|冰楓論壇

GMT+8, 2024-6-20 18:08

回頂部