CCF-CSP真题《202305-5 闪耀巡航》思路+python，c++满分题解

爱被打了一巴掌 2024-02-19 08:32 16阅读 0赞

> 想查看其他题的真题及题解的同学可以前往查看：[CCF-CSP真题附题解大全][CCF-CSP]

<table> 
 <tbody> 
  <tr> 
   <td>试题编号：</td> 
   <td>202305-5</td> 
  </tr> 
  <tr> 
   <td>试题名称：</td> 
   <td>闪耀巡航</td> 
  </tr> 
  <tr> 
   <td>时间限制：</td> 
   <td>5.0s</td> 
  </tr> 
  <tr> 
   <td>内存限制：</td> 
   <td>512.0MB</td> 
  </tr> 
  <tr> 
   <td>问题描述：</td> 
   <td> <h3>问题描述</h3> <p>西西艾弗岛旅游公司最近推出了一系列环绕西西艾弗岛的闪耀游轮航线。普通的航线通常是一条环线，以便乘客在漫长的旅途之后回到出发点；而闪耀航线则多为有惊无险的单程。因此，西西艾弗岛旅游公司也允许乘客自己选择一些能够返回起点的航线组合。具体而言，西西艾弗岛旅游公司推出的航线可以用仅包含小写字母的字符串表示，其中每一种字母代表航线中途经的一个目的地。例如，航线&nbsp;<code>aqua</code>&nbsp;表示从&nbsp;<code>a</code>&nbsp;出发，途经&nbsp;<code>q</code>&nbsp;和&nbsp;<code>u</code>，最终返回&nbsp;<code>a</code>&nbsp;的航线。西西艾弗岛旅游公司目前运营着&nbsp;N&nbsp;条这样的航线，分别用字符串&nbsp;s1,s2,⋯,sN&nbsp;表示。我们定义，一条航线的长度为相应的字符串长度减&nbsp;1，如航线&nbsp;<code>aqua</code>&nbsp;的长度为&nbsp;3。</p> <p>西西艾弗岛旅游公司为了鼓励乘客乘坐其游轮，推出了一项集章活动。乘坐其游轮途经部分目的地（可以是搭乘的航线的起点或终点）时，可以获得一枚印章。我们用字符串&nbsp;t&nbsp;表示所有参与集章活动的目的地。当乘客集齐&nbsp;t&nbsp;中所有字母对应的印章时，有机会抽取免费住宿豪华酒店等幸运大奖。</p> <p>为了确定集章活动给公司带来的预期利润，西西艾弗岛旅游公司想知道：对于每条航线&nbsp;si，从&nbsp;si&nbsp;的起点出发搭乘&nbsp;si&nbsp;到达&nbsp;si&nbsp;的终点，再经过多条航线（可以是&nbsp;0&nbsp;条）完成集章后返回&nbsp;si&nbsp;的起点，需要乘坐的航线组合的最小总长度。</p> <h3>输入格式</h3> <p>从标准输入读入数据。</p> <p>输入的第一行包含一个正整数&nbsp;N&nbsp;和一个字符串&nbsp;t，保证&nbsp;1≤N≤105，1≤|t|≤10，且&nbsp;t&nbsp;仅包含不重复的小写字母。</p> <p>接下来&nbsp;N&nbsp;行，每行包含一个字符串&nbsp;si，表示第&nbsp;i&nbsp;条航线。保证&nbsp;2≤|si|≤106，∑i=1N|si|≤106。</p> <h3>输出格式</h3> <p>输出到标准输出中。</p> <p>输出包含&nbsp;N&nbsp;行，每行输出一个正整数表示对应航线组合的最小总长度，或者输出&nbsp;<code>-1</code>&nbsp;表示不存在满足要求的航线组合。</p> <h3>样例输入</h3> 
    <blockquote> 
     <p>6 au<br> aqua<br> glass<br> hug<br> shiny<br> sparkling<br> youth</p> 
    </blockquote> <h3>样例输出</h3> 
    <blockquote> 
     <p>3<br> 14<br> 14<br> 14<br> 26<br> 14</p> 
    </blockquote> <h3>样例输入</h3> 
    <blockquote> 
     <p>7 i<br> nonstop<br> perfect<br> rocket<br> thrilling<br> train<br> trapper<br> tripper</p> 
    </blockquote> <h3>样例输出</h3> 
    <blockquote> 
     <p>16<br> 16<br> 11<br> -1<br> 16<br> 22<br> 11</p> 
    </blockquote> <h3>子任务</h3> <p>对于&nbsp;10%&nbsp;的数据，保证&nbsp;1≤N≤10，1≤|t|≤5。</p> <p>对于另外&nbsp;10%&nbsp;的数据，保证&nbsp;1≤N≤1000，|t|=1。</p> <p>对于另外&nbsp;20%&nbsp;的数据，保证&nbsp;1≤|t|≤5。</p> <p>对于&nbsp;100%&nbsp;的数据，保证&nbsp;1≤N≤105，1≤|t|≤10，2≤|si|≤106，∑i=1N|si|≤106，si&nbsp;和&nbsp;t&nbsp;仅包含小写字母，且&nbsp;t&nbsp;中字母不重复。</p> </td> 
  </tr> 
 </tbody> 
</table>

**真题来源：**[闪耀巡航][Link 1]

> 感兴趣的同学可以如此编码进去进行练习提交

**c++满分题解：**

#include <bits/stdc++.h>
    using namespace std;
    using LL = long long;
     
    const LL inf = 1e18;
     
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);cout.tie(0);
        int n;
        string t;
        cin >> n >> t;
        vector<int> id(26, -1);
        int cnt = 0;
        for(auto &i : t){
            id[i - 'a'] = cnt;
            ++ cnt;
        }
        vector<vector<array<int, 3>>> edge(26);
        vector<array<int, 4>> query(n);
        for(int i = 0; i < n; ++ i){
            string s;
            cin >> s;
            int st = s.front() - 'a';
            int ed = s.back() - 'a';
            int sign = 0;
            int len = s.size() - 1;
            for(auto &i : s){
                if (id[i - 'a'] != -1){
                    sign |= (1 << id[i - 'a']);
                }
            }
            edge[ed].push_back({st, len, sign});
            query[i] = {st, ed, sign, len};
        }
        int up = (1 << cnt);
        vector<vector<vector<LL>>> dis(26, vector<vector<LL>>(26, vector<LL>(up, inf)));
        for(int i = 0; i < 26; ++ i){
            dis[i][i][up - 1] = 0;
            priority_queue<array<LL, 3>> team;
            team.push({0, i, up - 1});
            while(!team.empty()){
                array<LL, 3> top = team.top();
                team.pop();
                LL distance = -top[0];
                int u = top[1], sign = top[2];
                if (dis[i][u][sign] != distance)
                    continue;
                for(auto &e : edge[u]){
                    int v = e[0], len = e[1], si = e[2];
                    int nxtsign = (sign ^ (sign & si));
                    if (dis[i][v][nxtsign] > distance + len){
                        dis[i][v][nxtsign] = distance + len;
                        team.push({-dis[i][v][nxtsign], v, nxtsign});
                    }
                }
            }
        }
        for(int i = 0; i < n; ++ i){
            LL ans = inf;
            int sign = query[i][2];
            for(int s = sign; s; s = (s - 1) & sign)
                ans = min(ans, dis[query[i][0]][query[i][1]][s]);
            ans = min(ans, dis[query[i][0]][query[i][1]][0]);
            if (ans == inf)
                ans = -1;
            else 
                ans += query[i][3];
            cout << ans << '\n';
        }
     
        return 0;
    }

**运行结果：**![e5161353043748839088056ed4cd7e59.png][]

[CCF-CSP]: https://blog.csdn.net/weixin_53919192/article/details/124893395?spm=1001.2014.3001.5502
[Link 1]: http://118.190.20.162/view.page?gpid=T166
[e5161353043748839088056ed4cd7e59.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/8d8dc2c953fd40d58bc01bc323f442a3.png