1 条题解

  • 0
    @ 2026-11-15 22:53:17

    统计每个大写字母在字符串中出现的次数,然后每次遇到 * 时,将其替换为当前出现次数最少的字母。可以用优先队列实现,也可以直接遍历 2626 个字母查找。整体时间复杂度为 O(n)\mathcal O(n)。

    代码:

    #include <iostream>
    #include <string>
    #include <queue>
    #include <cstring>
    
    using namespace std;
    typedef long long ll;
    
    struct Item {
    	int ch, freq;
    	bool operator<(const Item &o) const {
    		return freq > o.freq;
    	}
    };
    
    int main() {
    	int cases;
    	cin >> cases;
    	while(cases--) {
    		string str;
    		cin >> str;
    		int freq[26] = {};
    		int len = str.size();
    		priority_queue<Item> pq;
    		for(int i=0;i<len;++i){
    			if(str[i]!='*') ++freq[str[i]-'A'];
    		}
    		for(int i=0;i<26;++i){
    			pq.push({i,freq[i]});
    		}
    		for(int i=0;i<len;++i){
    			if(str[i]=='*'){
    				auto x=pq.top(); pq.pop();
    				++freq[x.ch];
    				pq.push({x.ch,freq[x.ch]});
    			}
    		}
    		ll res=0;
    		for(int i=0;i<26;++i)
    			res+=1LL*(len-freq[i])*freq[i];
    		cout<<res/2<<'\n';
    	}
    }
    
    • 1

    信息

    ID
    223
    时间
    1000ms
    内存
    512MiB
    难度
    3
    标签
    递交数
    2
    已通过
    1
    上传者