/ ALGORITHM

倍增 二分

Description

倍增二分,就是先倍增再二分:先逐渐扩大区间来确定一个含有答案的小区间,再在这个小区间里二分确定答案。常用于大数据范围的二分,或者需要二分次数很多的问题,可以用倍增来进行优化。

Problem A

source: HDU 6109

tips: 此题需要确定每一个不合法的约束条件的位置,如果每次二分整个区间,时间复杂度可能就很大了。所以我们可以先采用倍增的方法确定一个含有不合法条件的小区间,再二分查找它,这样时间上能优化很多。

Solution

int L, f[MaxN],a[MaxN],b[MaxN],c[MaxN];
int finds(int x)
{
    return f[x]==x?x:f[x]=finds(f[x]);
}
void Uni(int x, int y)
{
    x = finds(x), y = finds(y);
    if(x==y) return;
    f[x] = y;
}
bool check(int l, int r)
{
    for(int i=l;i<=r;i++) f[a[i]] = a[i],f[b[i]] = b[i];
    for(int i=l;i<=r;i++) if(c[i]==1) Uni(f[a[i]], f[b[i]]);
    for(int i=l;i<=r;i++) 
    if(c[i]==0 && finds(a[i]) == finds(b[i]) ) return false;
    return true;
}
vector<int> ans;
void solve()
{
    ans.clear();
    int s = 1;
    while(s<=L)
    {
        int k = 0;
        while( s+(1<<k)-1 <=L && check(s,s+(1<<k)-1)) k++;
        int r = min(s+(1<<k)-1,L);
        if(check(s,r)) break;
        else
        {
            int l = s;
            while(l<r)
            {
                int mid = (l+r)/2;
                if(check(s,mid)) l = mid+1;
                else r = mid; 
            }
            ans.pb(l-s+1);
            s = l+1;
        }
    }
    printf("%d\n", ans.size());
    for(auto x : ans) printf("%d\n", x);

}

int main()
{
    while(~scanf("%d", &L))
    {
        for(int i=1;i<=L;i++)
            read(a[i]), read(b[i]), read(c[i]);
        solve();
    }
}

Problem B

source: 玲珑学院 1112

tips: 做法和上题类似。