题解：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) 的，可以通过。

代码

#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;
}