题解：P14406 [JOISC 2015] 愉快的标志设计 / En-JOI-able Logo Design

比较小清新的题目。

发现题目给出的序列很明显就是由

4

个更小的序列组合而来的，所以我们自然而然的想到递归搜索。

不难发现，对于前

3

个小序列，代价都是一样的算法，只要看有多少个合法的，再用区间长度减去就行了。

但是对于最后一种序列，我们发现和当前处理的序列是属于同一种类型，但是问题规模更小。所以对于最后一种序列我们递归求解就好了。

分析时间：求解前

3

种序列可以用前缀和预处理，这里是

\Theta(1)

的。对于递归求解部分，明显和递归深度有关，每次递归深度减一，规模变为原先的

\frac{1}{4}

，总共就是

\Theta(k)

的时间。所以单次求解的时间复杂度就是

\Theta(k)

。

因为可以从任意起点出发，我们破环成链，预处理前缀和，再枚举起点，总共枚举

\Theta(4^k)

次，单次

\Theta(k)

，总复杂度就是

\Theta(4^k\times k)

的，可以通过。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define V vector
#define FOR(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define pb push_back
const int INF=1e9+10;
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int k;cin>>k;
	string s;cin>>s;
	int n=(1<<(2*k));
	V<int>num(2*n+1),sumj(2*n+1,0),sumo(2*n+1,0),sumi(2*n+1,0);
	FOR(i,1,n) num[i]=num[i+n]=s[i-1];
	FOR(i,1,2*n){
		sumj[i]=sumj[i-1]+(num[i]=='J');
		sumo[i]=sumo[i-1]+(num[i]=='O');
		sumi[i]=sumi[i-1]+(num[i]=='I');
	}
	function<int(int,int)>dfs=[&](int dep,int l){
		if(dep==0) return 0;
		int l1=l+(1<<(2*(dep-1))),l2=l1+(1<<(2*(dep-1))),l3=l2+(1<<(2*(dep-1)));
		int ans1=sumj[l1-1]-sumj[l-1];
		int ans2=sumo[l2-1]-sumo[l1-1];
		int ans3=sumi[l3-1]-sumi[l2-1];
		return l3-l-(ans1+ans2+ans3)+dfs(dep-1,l3);
	};
	int ans=INF;
	FOR(i,1,n){
		ans=min(ans,dfs(k,i));
	}
	cout<<ans;
	return 0;
}

题解：P14406 [JOISC 2015] 愉快的标志设计 / En-JOI-able Logo Design

文章操作

代码

相关推荐

评论

题解：P14406 [JOISC 2015] 愉快的标志设计 / En-JOI-able Logo Design