Written by @Yue_chen

题意：

给n个字符串，可以任意两两拼接无限次，最多能拼多少个“603”

思路：

由样例可知，603串必须仅包含603串，如6031、9603等都是不合法的；

因此，记录603的所有子串“603”，“60”，“03”，“6”，“0”，“3”；

然后进行贪心，优先选择用最长的串:

ans += cnt("603");

ans += min(cnt("60"), cnt("3"));

ans += min(cnt("6"), cnt("03"));

ans += min({cnt("6"), cnt("0"), cnt("03")});

计算的时候记得将已经统计的串去除，cnt为该串出现的次数，可以使用map，哈希等方式保存。

时间复杂度O(nlog2****n)

AC代码：

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve() {
    map<string, int> mp;
    int n; cin>>n;
    
    for(int i=1; i<=n; ++i) {
        string s; cin>>s;
        mp[s]++;
    }
    
    i64 ans = 0;
    ans += mp["603"];
    
    int mn = min(mp["60"], mp["3"]);
    ans += mn;
    mp["60"] -= mn;
    mp["3"] -= mn;
    
    mn = min(mp["6"], mp["03"]);
    ans += mn;
    mp["6"] -= mn;
    mp["03"] -= mn;
    
    mn = min({mp["6"], mp["0"], mp["3"]});
    ans += mn;
    
    cout<<ans<<"\n";
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int t=1;// cin>>t;
    while (t--) solve();
    return 0;
}