【玲瓏杯1054】【暴力＋列挙の約】String cut
転送ゲート:http://www.ifrog.cc/acm/problem/1054
考え方:
まずこのような性質を知っています.文字を削除した後の文字列の循環節長は必ずnnの約数です.すべての文字を列挙して削除し、各約数に対して循環節が可能かどうかを判断します.複雑度O(nlogn)
コード:
1054-String cut
Time Limit:4 s メモリLimit:64 MByte
Submissions:151 Solved:54
DESCRIPTION
A string cut cc means the string can be divided into cc same substring.Such as string:abbab.Because it can be divied into ab+ab+ab,the string cut of it 33.Giyou string string string str.you.need to deletwitwitter.
INPUT
The re are multiple test cases.The first line is a number T(
T ≦10 T ≦10)、which means the number of cases.For each case、a line has a integer
n(1<=n==10001)n(1<=n==10001)、which is the length of string.next line a string
str str (which just include lowercase)
OUT
one line---the biggaest string cut.
SAMPLE INPUT
23 ab 5 aba
SAMPLE OUTUT
24
SOLUT ION
“玲瓏杯”ACM試合Round夝4
考え方:
まずこのような性質を知っています.文字を削除した後の文字列の循環節長は必ずnnの約数です.すべての文字を列挙して削除し、各約数に対して循環節が可能かどうかを判断します.複雑度O(nlogn)
コード:
#include
#include
#include
#include
using namespace std;
#define rep(i,k,n) for(int i=k;i<=n;i++)
#define rrep(i,k,n) for(int i=k;i>=n;i--)
#define pl(x) cout << #x << "= " << x << endl;
template void read(T&num) {
char CH; bool F=false;
for(CH=getchar();CH'9';F= CH=='-',CH=getchar());
for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());
F && (num=-num);
}
const int N=1e5+10;
string s;
int main(){
int T;
read(T);
while(T--){
int n;
read(n);
// if(n==1) return 0*puts(0);
cin>>s;
int mx=0;
rep(i, 0, n-1){
string ss = s.substr(0, i);
ss = ss+s.substr(i+1, n-i);
// cout< 1054-String cut
Time Limit:4 s メモリLimit:64 MByte
Submissions:151 Solved:54
DESCRIPTION
A string cut cc means the string can be divided into cc same substring.Such as string:abbab.Because it can be divied into ab+ab+ab,the string cut of it 33.Giyou string string string str.you.need to deletwitwitter.
INPUT
The re are multiple test cases.The first line is a number T(
T ≦10 T ≦10)、which means the number of cases.For each case、a line has a integer
n(1<=n==10001)n(1<=n==10001)、which is the length of string.next line a string
str str (which just include lowercase)
OUT
one line---the biggaest string cut.
SAMPLE INPUT
23 ab 5 aba
SAMPLE OUTUT
24
SOLUT ION
“玲瓏杯”ACM試合Round夝4