E. Necklace Assembly
题意
给出 n个珠子(n小于2000) 珠子有26个品种用小写字母表示
现在要求取出尽量多的珠子串成项链 要求这串项链在顺时针旋转k个单位(一个珠子一个单位)时
每个位置的珠子种类仍和原来相同
问最长拿出多少个珠子使得它符合这种要求
题解
发现n较小 于是枚举答案 判断正确性
通过举例发现 当枚举到需要i个珠子时
要构成旋转k个单位仍不变的项链
一定是每两个相同种类珠子间隔x=gcd(i,k)个
可以延伸到其他与圆 周期性相关的题 可以考虑gcd
于是就能够计算出需要多少个相同种类的珠子来构成当前长度的项链
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
# define endl '\n'
# define Turnoff std::ios::sync_with_stdio(false)
const int Max=1e5+5;
const int Mod=998244353;
int have[30];
int main() {
Turnoff;
int t;cin>>t;
while(t--){
int n,k;cin>>n>>k;
string s;cin>>s;int ans=1;
memset(have,0,sizeof have);
for(auto i:s)have[i-'a']++;
for(int len=2;len<=n;len++){
int bios=__gcd(len,k);
int need=(len/bios),cnt=0;
for(int i=0;i<26;i++){
cnt+=have[i]/need;
}
if(cnt>=bios)ans=max(ans,len);
}
cout<<ans<<endl;
}
}
|