Codeforces Round #650 (Div. 3) E. Necklace Assembly (暴力)

题意:有一个字符串,要求使用其中字符构造一个环(不必全部都用),定义一个环是k美的,如果它转\(k\)次仍是原样,现在给你\(k\),要求最长的k美环的长度.
题解:我们首先看\(k\),如果一个环转\(k\)的因子次是美的,那么\(k\)次也一定是美的,然后再看环,假如一个环最少转\(d\)次是美的,那么这个环的长度\(n\)一定能被\(d\)整除.也就是这个环有\(d\)种不同的数,每种数有\(n/d\)个.其实也就可以把看作是一个循环节构成的,画一画也就知道了.

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <unordered_set>

#include <unordered_map>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

const int INF = 0x3f3f3f3f;

using namespace std;

typedef pair<int,int> PII;

typedef pair<ll,ll> PLL;

int t;

int n,k;

string s;

map<char,int> mp;

vector<int> v;

int main() {

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

	cin>>t;

	 while(t--){

	 	mp.clear();

	 	v.clear();

	 	cin>>n>>k;

	 	cin>>s;

	 	for(int i=0;i<n;++i){

	 		mp[s[i]]++;

	 	}

	 	for(int i=1;i<=k;++i){

	 		if(k%i==0){

	 			v.pb(i);

	 		}

	 	}

	 	int ans=0;

	 	for(int i=1;i<=n;++i){

	 		for(auto w:v){

	 			if(w%i==0){

	 				ans=max(ans,i);    //worst situation

	 			}

	 			if(i%w==0){

	 				int d=i/w;

	 				int cnt=0;

	 				for(char j='a';j<='z';++j){

	 					cnt+=mp[j]/d;

	 				}

	 				if(cnt>=w){

	 					ans=max(ans,i);

	 				}

	 			}

	 		}

	 	}

	 	cout<<ans<<endl;

	 }

    return 0;

}

巴特西

Codeforces Round #650 (Div. 3) E. Necklace Assembly (暴力)

最新文章

热门文章