cf Educational Codeforces Round 25 C

cf Educational Codeforces Round 25 C - Multi-judge Solvingz

本文主要是介绍cf Educational Codeforces Round 25 C - Multi-judge Solvingz，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题：
D. Suitable Replacement
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given two strings s and t consisting of small Latin letters, string s can also contain ‘?’ characters.

Suitability of string s is calculated by following metric:

Any two letters can be swapped positions, these operations can be performed arbitrary number of times over any pair of positions. Among all resulting strings s, you choose the one with the largest number of non-intersecting occurrences of string t. Suitability is this number of occurrences.

You should replace all ‘?’ characters with small Latin letters in such a way that the suitability of string s is maximal.

Input
The first line contains string s (1 ≤ |s| ≤ 10^6).

The second line contains string t (1 ≤ |t| ≤ 10^6).

Output
Print string s with ‘?’ replaced with small Latin letters in such a way that suitability of that string is maximal.

If there are multiple strings with maximal suitability then print any of them.

Examples

input
?aa?
ab
output
baab
input
??b?
za
output
azbz
input
abcd
abacaba
output
abcd

Note
In the first example string “baab” can be transformed to “abab” with swaps, this one has suitability of 2. That means that string “baab” also has suitability of 2.

In the second example maximal suitability you can achieve is 1 and there are several dozens of such strings, “azbz” is just one of them.

In the third example there are no ‘?’ characters and the suitability of the string is 0.

中文：
给你两个字符串s和t，其中s当中每个字符的位置可以随意改变。且s中包含‘？’字符。
现在问你可以将s变成任意一个字符，那么s当中最多可以有多个子串t？

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string s,t;
ll hs[26],ht[26],tmp[26],mark;
int main()
{ios::sync_with_stdio(false);while(cin>>s>>t){memset(hs,0,sizeof(hs));memset(ht,0,sizeof(ht));memset(tmp,0,sizeof(tmp));mark=0;if(t.size()>s.size()){for(auto &x:s)if(x=='?'){x='a';}cout<<s<<endl;continue;}for(auto x:t)ht[x-'a']++;for(auto x:s){if(x=='?')mark++;elsehs[x-'a']++;}int l=0,r=(s.size()/t.size()),m;while(r-l>=0){m=(r+l)/2;int flag=0;int res=mark;for(int i=0;i<26;i++){if(ht[i]*m-hs[i]>0)res-=(ht[i]*m-hs[i]);if(res<0){flag=1;break;}}if(flag==1)//缩小r=m-1;elsel=m+1;}//取rfor(int i=0;i<26;i++){if(ht[i]*r-hs[i]>=0)ht[i]=(ht[i]*r-hs[i]);elseht[i]=0;}for(int i=0;i<s.size();i++){if(s[i]=='?'){for(int j=0;j<26;j++){if(ht[j]>0){ht[j]--;s[i]=('a'+j);break;}}}}for(auto &x:s)if(x=='?')x='z';cout<<s<<endl;}return 0;
}