记录编号	453615	评测结果	AAWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWAW
题目名称	愉快的logo设计	最终得分	6
用户昵称	Fisher.	是否通过	未通过
代码语言	C++	运行时间	0.871 s
提交时间	2017-09-21 21:46:33	内存使用	24.31 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
/*
	暴力想法：
		枚举每个点为环的起点，暴力每个点每个点匹配；然后统计出所有需要改的数
		最后与minn比较取最小；
	缺点：重复匹配，多次计算重复的位置；
	优化：
		前缀和优化：
		对2*n的序列；分别计算JOI的前缀和；
		然后枚举起点时，可以快速计算可以不改的数量；
		然后得到答案；
	有一点：最后4^k的元素，我是暴力匹配的；
	也许会TLE？不知道，试试吧； 
	^
	|
	|
	就是这个地方，读题读不明白，后来问了yl，知道了最后一段4^k不需要计算了；
	那就不需要暴力...答案就是n-len-sum；
	n是总长，len是一段长，即最后一段的长，sum是前三段不需要改的； 
*/
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
const int maxk=20;
const int maxn=1048596;
int k,n=1;
string c;
int s[maxn<<1][3];//前缀和； 
int minn=0x7fffffff;
int main(){
	freopen("JOI.in","r",stdin);
	freopen("JOI.out","w",stdout);
	k=read();
	n=(n<<2*k);
	cin>>c;
	c=c+c;
	c=' '+c;
	for(int i=1;i<=2*n;i++){
		s[i][0]+=s[i-1][0];
		s[i][1]+=s[i-1][1];
		s[i][2]+=s[i-1][2];
		if(c[i]=='J')s[i][0]++;
		if(c[i]=='O')s[i][1]++;
		if(c[i]=='I')s[i][2]++;
	}
	int len=(1<<2*(k-1));
	for(int i=1;i<=n;i++){//枚举起点； 
		int sum=0;
		sum+=s[i+len-1][0]-s[i-1][0];
		sum+=s[i+2*len-1][1]-s[i+len-1][1];
		sum+=s[i+3*len-1][2]-s[i+2*len-1][2];
		//cout<<i<<" "<<sum<<endl;
		minn=min(minn,n-len-sum);
	}
	//for(int i=1;i<=2*n;i++)
	//	cout<<i<<" "<<s[i][0]<<" "<<s[i][1]<<" "<<s[i][2]<<endl;
	printf("%d\n",minn);
	return 0;
}