Codeforces Round #570 (Div. 3) E. Subsequences (easy version) (搜索,STL)

题意:有一长度为\(n\)的字符串,要求得到\(k\)不同的它的子序列(可以是空串),每个子序列有\(|n|-|t|\)的贡献,求合法情况下的最小贡献.
题解:直接撸个爆搜找出所有子序列然后放到set里面搞一下就好了.

代码:

int n,k;

string str;

set<string> s;

queue<string> q;

void bfs(){

	s.insert(str);

	q.push(str);

	while(!q.empty()){

		string cur=q.front();

		q.pop();

		if(s.size()>=k) break;

		rep(i,0,(int)cur.size()-1){

			string tmp=cur;

			tmp.erase(i,1);

			if(s.count(tmp)==0){

				s.insert(tmp);

				q.push(tmp);

			}

			if(s.size()>=k) break;

		}

	}

}

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>n>>k;

    cin>>str;

    bfs();

    if(s.size()<k) {cout<<-1<<'\n';return 0;}

    int ans=0;

    for(auto w : s){

    	ans+=n-(int)w.size();

    }

    cout<<ans<<'\n';

    return 0;

}

巴特西

Codeforces Round #570 (Div. 3) E. Subsequences (easy version) (搜索,STL)

最新文章

热门文章