首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#13158

买还是不买 小红想用自己喜欢的彩色珠子做一条珠串,于是去一家小店买珠子。店里有很多条彩色的珠串,但店主只卖整串,不拆散零售珠子。于是小红为了得到自己喜欢颜色的珠…

买还是不买

小红想用自己喜欢的彩色珠子做一条珠串,于是去一家小店买珠子。店里有很多条彩色的珠串,但店主只卖整串,不拆散零售珠子。于是小红为了得到自己喜欢颜色的珠子,就得买很多条现成的珠串,回家拆了自己拼。

由于店里有上百条珠串,小红只好求助于你,请你写个程序,帮她看看是否有可能买到所有她喜欢颜色的珠子,并且使得多余的珠子尽可能少。

为简单起见,我们用数字 0 到 9、以及英文的 26 个字母的大小写来表示珠子的颜色(即珠子最多有 62 种颜色)。

在样例 1 中,买第 2 条和最后两条珠串是最划算的,因为这样只有 3 颗珠子是多余的。

在样例 2 中,把全部三条珠串都买下也不行,因为还少三颗 R 珠。

时间限制:9000,内存限制:65536

输入

输入第一行给出小红想要的珠串。下一行给出正整数 N(≤ 100),随后 N 行,每行给出店里的一条珠串。所有珠串中的珠子不超过 1000 颗。

输出

如果能凑出小红想要的珠串,则在一行中输出 Yes、空格、最少的多余珠子的个数;否则输出 No、空格、凑不出来的珠子的个数。

样例输入1

RYg5
8
gY5Ybf
8R5
12346789
gRg8h
5Y37
pRgYgbR52
8Y
8g

样例输出1

Yes 3

样例输入2

YrRR8RRrY
3
ppRGrrYB225
8ppGrrB25
Zd6KrY

样例输出2

No 3
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//答案来源于AI #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; #include &lt;string&gt; #include &lt;climits&gt; using namespace std; const int MAX_COLOR = 62; int getIndex(char c) {     if (c &gt;= '0' &amp;&amp; c &lt;= '9')         return c - '0';     else if (c &gt;= 'A' &amp;&amp; c &lt;= 'Z')         return 10 + (c - 'A');     else if (c &gt;= 'a' &amp;&amp; c &lt;= 'z')         return 36 + (c - 'a');     return -1; } struct Bead {     int len;     vector&lt;int&gt; cnt;     string s;     Bead(string str) : s(str), len(str.size()), cnt(MAX_COLOR, 0) {         for (char c : str) {             int idx = getIndex(c);             if (idx != -1) {                 cnt[idx]++;             }         }     } }; vector&lt;Bead&gt; beads; vector&lt;int&gt; target(MAX_COLOR, 0); vector&lt;int&gt; total(MAX_COLOR, 0); vector&lt;vector&lt;int&gt;&gt; suffix; int best = INT_MAX; int total_target = 0; int N; void dfs(int idx, vector&lt;int&gt; need, int cur_len) {     if (cur_len &gt;= best) {         return;     }     int sum_need = 0;     bool all_zero = true;     for (int c = 0; c &lt; MAX_COLOR; c++) {         if (need[c] &gt; 0) {             all_zero = false;             sum_need += need[c];         }     }     if (all_zero) {         best = cur_len;         return;     }     if (idx &gt;= N) {         return;     }     for (int c = 0; c &lt; MAX_COLOR; c++) {         if (need[c] &gt; suffix[idx][c]) {             return;         }     }     if (cur_len + sum_need &gt;= best) {         return;     }     dfs(idx + 1, need, cur_len);     bool useful = false;     for (int c = 0; c &lt; MAX_COLOR; c++) {         if (beads[idx].cnt[c] &gt; 0 &amp;&amp; need[c] &gt; 0) {             useful = true;             break;         }     }     if (useful) {         vector&lt;int&gt; new_need = need;         for (int c = 0; c &lt; MAX_COLOR; c++) {             if (new_need[c] &gt; 0) {                 new_need[c] = max(0, new_need[c] - beads[idx].cnt[c]);             }         }         dfs(idx + 1, new_need, cur_len + beads[idx].len);     } } int main() {     string target_str;     getline(cin, target_str);     total_target = target_str.size();     for (char c : target_str) {         int idx = getIndex(c);         if (idx != -1) {             target[idx]++;         }     }     cin &gt;&gt; N;     cin.ignore();     beads.reserve(N);     for (int i = 0; i &lt; N; i++) {         string s;         getline(cin, s);         beads.push_back(Bead(s));     }     for (int i = 0; i &lt; MAX_COLOR; i++) {         total[i] = 0;     }     for (int i = 0; i &lt; N; i++) {         for (int c = 0; c &lt; MAX_COLOR; c++) {             total[c] += beads[i].cnt[c];         }     }     int shortage = 0;     bool overall_meet = true;     for (int c = 0; c &lt; MAX_COLOR; c++) {         if (target[c] &gt; total[c]) {             overall_meet = false;             shortage += (target[c] - total[c]);         }     }     if (!overall_meet) {         cout &lt;&lt; "No " &lt;&lt; shortage &lt;&lt; endl;         return 0;     }     sort(beads.begin(), beads.end(), [](const Bead&amp; a, const Bead&amp; b) {         return a.len &lt; b.len;     });     suffix.resize(N, vector&lt;int&gt;(MAX_COLOR, 0));     for (int c = 0; c &lt; MAX_COLOR; c++) {         suffix[N - 1][c] = beads[N - 1].cnt[c];     }     for (int i = N - 2; i &gt;= 0; i--) {         for (int c = 0; c &lt; MAX_COLOR; c++) {             suffix[i][c] = beads[i].cnt[c] + suffix[i + 1][c];         }     }     best = INT_MAX;     dfs(0, target, 0);     cout &lt;&lt; "Yes " &lt;&lt; best - total_target &lt;&lt; endl;     return 0; }</pre><p><br/></p>
这道题暂未补解析。