4.7总结

1.FBI树（不该犯的重大问题：看清输入格式！！！）

一开始要先理清思路：对每个树结点判断F/B/I树，不会超时。

对一个01字符串，每次二分即可求得子树。

后序遍历，只需按照左-右-根的顺序建树并输出，二者可以放在同一函数里。

#include
using namespace std;
string s;
void maketree(int l,int r){
    if(r>l){
        maketree(l,(l+r)/2);
        maketree((l+r+1)/2,r);
    }    
    int B=1,I=1;
    for(int i=0;i<=r-l;i++){
        if(s[l+i]=='1'){
            B=0;
        }else if(s[l+i]=='0'){
            I=0;
        }
    }
    if(B) cout<<'B';
    else if(I) cout<<'I';
    else cout<<'F';
}
int main(){
    freopen("fbi.in","r",stdin);
    freopen("fbi.out","w",stdout);
    int n;
    cin>>n>>s;
    maketree(0,s.size()-1);
    return 0;
}

2.货币系统

给出所需面值和已有货币面值，求有几种组成方案。

这个题卡在（顺序不同，但量相同）的去重上了，其实一开始的思路正确，后面浪费了很多不必要的时间。

这类题两种DP方式，“加法”和“减法”，这个题用加法思路会更明确。假如F[j]表示面值j的方案数，f[j]+=f[j-a[i]] 这个式子能够保证会取到所有的方案数（）

#include
#define FOR(i,a,b) for(long long i = (a);i <= (b);i++)
using namespace std;
int a[10005],f[10005],b[10005],n,m,ans;
int main(){
    freopen("money.in","r",stdin);
    freopen("money.out","w",stdout);
    scanf("%d%d",&n,&m);
    FOR(i,1,n) scanf("%d",&a[i]);
    f[0]=1;
    FOR(i,1,n) FOR(j,a[i],m) f[j]+=f[j-a[i]];
    cout<endl;
    return 0;
}

 3.合并果子

老生常谈的问题了，不过，很快能想到的优先队列维护不是最优解，O（n）做法如下：

#include
#define FOR(i,a,b) for(int i = (a);i <= (b);i++)
using namespace std;
queue<long long> q1,q2;
long long tong[100005],n,ans;
int main(){    
    freopen("fruit.in","r",stdin);
    freopen("fruit.out","w",stdout);
    cin>>n;
    FOR(i,1,n){    
        int x;
        scanf("%d",&x);
        tong[x]++;
    }
    FOR(i,1,100000){    
        while(tong[i]){    
            tong[i]--;
            q1.push(i);
        }
    }
    FOR(i,1,n-1){    
        long long x,y;
        if((q1.front()q2.empty())
        {    x=q1.front();
            q1.pop();
        }
        else
        {    x=q2.front();
            q2.pop();
        }
        if((q1.front()q2.empty())
        {    y=q1.front();
            q1.pop();
        }
        else
        {    y=q2.front();
            q2.pop();
        }
        ans+=(x+y);//ans加值
        q2.push(x+y);//将合并的果子加入到q2。
    }
    printf("%d",ans);
    return 0;
}

队列q1存放正常果子，q2存放合并后的果子，取两个队列中的最小与次小值。好处就是两个队列都不需要额外排序，（当然预处理需要桶排）按此流程节省排序时间。