CodeForces 825D(贪心)

ゝ一纸荒年。 2022-06-06 14:16 156阅读 0赞

问题描述:

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| ≤ 106).

The second line contains string t (1 ≤ |t| ≤ 106).

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.

Example

Input

?aa?
    ab

Output

baab

Input

??b?
    za

Output

azbz

Input

abcd
    abacaba

Output

abcd

题目题意:问我们能够使得s串最多可以含有多少个t串，'?'可以换成任意字母，s串的任意俩个字母都可以交换位置，输出这个s串

题目分析:我们先处理出原始s串中每个字母的个数和'?'的个数，然后在同样处理't'串,现在我们只需要把'?'换成t串所需要的字母，我们先求出目前s串可以构成多少个t串，然后循环+1,依次去减需要换的字母，一直到'?'没有

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<string>
    #include<algorithm>
    using namespace std;
    
    string s,t;
    int a[30],v[30],ans[30];
    int main()
    {
        while (cin>>s>>t) {
            memset (a,0,sizeof (a));
            memset (v,0,sizeof (v));
            memset (ans,0,sizeof (ans));
            int cnt=0;
            for (int i=0;i<s.size();i++) {
                if (s[i]=='?') cnt++;
                else a[s[i]-'a'+1]++;
            }
            for (int i=0;i<t.size();i++)
                v[t[i]-'a'+1]++;
            int cur=0x3f3f3f3f;
            for (int i=1;i<=26;i++) {
                if (v[i]==0) continue;
                else cur=min(cur,a[i]/v[i]);//求出当前可以构成的个数
            }
            for (int i=cur+1;;i++) {//可以构成的个数
                for (int j=1;j<=26;j++) {
                    if (v[j]*i<=a[j]) continue;
                    else {//如果s串里面的不够
                        while (cnt>0&&v[j]*i!=a[j]) {//'?'换成所需字母
                            cnt--;
                            ans[j]++;
                            a[j]++;
                        }
                    }
                    if (cnt<=0) break;
                }
                if (cnt<=0) break;
            }
    
            for (int i=0;i<s.size();i++) {
                if (s[i]!='?') cout<<s[i];
                else {
                    for (int j=1;j<=26;j++) {
                        if (ans[j]!=0) {
                            printf("%c",'a'+j-1);
                            ans[j]--;
                            break;
                        }
                    }
                }
            }
    
            cout<<endl;
        }
        return 0;
    }