「日常训练」ZgukistringZ（Codeforces Round #307 Div. 2 B）

题意与分析（CodeForces 551B）

这他妈哪里是日常训练，这是日常弟中弟。

题意是这样的，给出一个字符串Ａ，再给出两个字符串B,C，求Ａ中任意量字符交换后（不限制次数）能够得到的使Ｂ，C作为子串不重叠且出现次数最多的串。

看起来很简单对吧，做法也很简单，先排序字符，然后枚举合法的B串能在A串中出现的次数，看能有几个C串，然后求个最优解就行了。是不是很简单？然后WA了十几发，各种捉bug，太杀妈了。

这份代码看起来贼简单，这是我写的第三版了。。。。

这种字符串题目太苦手了QAQ

代码

#include <bits/stdc++.h>

#define MP make_pair

#define PB emplace_back

#define fi first

#define se second

#define ZERO(x) memset((x), 0, sizeof(x))

#define ALL(x) (x).begin(),(x).end()

#define rep(i, a, b) for (repType i = (a); i <= (b); ++i)

#define per(i, a, b) for (repType i = (a); i >= (b); --i)

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

using namespace std;

using ll=long long;

using repType=ll;

map<char,ll> ma,mb,mc;

string a,b,c;

int main()

{

    cin>>a>>b>>c;

    rep(i,0,ll(a.length())-1)

	ma[a[i]]++;

    rep(i,0,ll(b.length())-1)

	mb[b[i]]++;

    rep(i,0,ll(c.length())-1)

	mc[c[i]]++;

    ll bcnt=a.length()-1;

    for(auto it:mb)

    {

	bcnt=min(bcnt,ma[it.fi]/it.se);

    }

    //cout<<bcnt<<endl;

    int sumcnt=-1,max_b=0,max_c=0;

    rep(i,0,bcnt)

    {

		ll ccnt=a.length()-1;

		for(auto it:mc)

		{

			int tmp=ma[it.fi];

			if(mb.find(it.fi)!=mb.end()) tmp-=i*mb[it.fi];

			ccnt=min(ccnt,tmp/it.se);

			if(ccnt<0) ccnt=0;

		}

		if(i+ccnt>sumcnt)

		{

			sumcnt=i+ccnt;

			max_b=i;

			max_c=ccnt;

			//cout<<max_b<<" "<<max_c<<endl;

		}

	}

    rep(i,1,max_b) cout<<b;

    rep(i,1,max_c) cout<<c;

    for(auto it:ma)

    {

		ll cnt=it.se;

		if(mb.find(it.fi)!=mb.end()) cnt-=max_b*mb[it.fi];

		if(mc.find(it.fi)!=mc.end()) cnt-=max_c*mc[it.fi];

		rep(i,1,cnt) cout<<it.fi;

    }

    cout<<endl;

    return 0;

}