Codeforces-1454F Array Partition


Problem

Portal


Thoughts

这道题的思想其实很像2020牛客多校第九场的E题,当题目给了多种变量的时候,不妨固定其中的一个,然后尝试将另一个优化,之后枚举固定的一个就可以了。
枚举其中的一个断点肯定是无法避免的,我们假设枚举的第一个断点记为 x,此时 max(1 , x) 是已经确定了的,第一步先要去找到 y 的位置,使得 min(x + 1 , x + y) == max(1 , x) 才行,不难看出的一个小结论是,对于一段前缀的最值来说,是具有单调性的,更具体的来说,前缀最大值随着下标的递增,这个值只会更大而不会减小,前缀最小值亦然,所以对于第二个断点 y 我们可以直接二分去查找,此时我们已经确定下来了第一个断点 x 的位置,设第一段的最大值为 mmax1,第二段的最小值为 mmin,第三段的最大值为 mmax2,此时分四种情况讨论即可。

  • mmax1 < mmin:此时最小值的前缀偏大,需要扩大长度,故 l = mid + 1
  • mmax1 > mmin:同上,r = mid - 1
  • mmax1 < mmax2:此时最大值的后缀偏大,需要减小长度,故 l = mid + 1
  • mmax1 > mmax2:同上,r = mid - 1

Accepted Code

const int N = 2e5 + 10;

int n, a[N];
int FMin[N][20], FMax[N][20]; // F[i][j]表示以i为起点,连续2^j个数里的最值
void Init()
{
    for (int i = 1; i <= n; i++) FMin[i][0] = FMax[i][0] = a[i];
    for (int j = 1; (1<<j) <= n; j++) // 按区间长度递增顺序递推 2^j : 2^1 2^2 2^3 ... 
    {
        for (int i = 1; i + (1<<j) - 1 <= n; i++) // 区间起点
        {
            //i后面2^j个数中的最大值等于左右两半长度位2^(j - 1)的子区间中最大值中的较大值
            //[i, i + 2^(j - 1) - 1]和[i + 2^(j - 1), i + 2^(j - 1) + 2^(j - 1) - 1]
            FMin[i][j] = min(FMin[i][j-1], FMin[i + (1<<(j-1))][j-1]);
            FMax[i][j] = max(FMax[i][j-1], FMax[i + (1<<(j-1))][j-1]);
        }
    }
}
int query_max(int l, int r)
{
    int k = log2(r-l+1); // 区间长度 >= 2^k  2^k个数将区间等分成两块 
    // 从左起点往右走2^k,从右终点往左走2^k,取两区间最大值中的较大值 
    return max(FMax[l][k], FMax[r-(1<<k)+1][k]); // 查询最小值用min即可
}
int query_min(int l, int r)
{
    int k = log2(r-l+1); // 区间长度 >= 2^k  2^k个数将区间等分成两块 
    // 从左起点往右走2^k,从右终点往左走2^k,取两区间最大值中的较大值 
    return min(FMin[l][k], FMin[r-(1<<k)+1][k]); // 查询最小值用min即可
}

signed main()
{
#ifdef duipai
    freopen("E:\\Computer major\\Algorithm competition\\duipai\\in.txt","r",stdin);
    freopen("E:\\Computer major\\Algorithm competition\\duipai\\out1.txt","w",stdout);
#endif

#ifdef debugger
    freopen("E:\\Computer major\\Cpp\\Dev-cpp\\in.txt","r",stdin);
#endif

    int T;
    cin >> T;

    while(T -- )
    {
        cin >> n;
        for(int i = 1 ; i <= n ; i ++ ) sc("%d", &a[i]);
        Init();

        bool flag = 0;
        for(int i = 1 ; i <= n - 2 ; i ++ )
        {
            int mmax1 = query_max(1, i);
            int l = i + 1, r = n - 1, mid;
            while(l <= r)
            {
                mid = l + r >> 1;
                int mmin = query_min(i + 1, mid);
                int mmax2 = query_max(mid + 1, n);

                if(mmin < mmax1 || mmax2 < mmax1) r = mid - 1;
                else if(mmin > mmax1 || mmax2 > mmax1) l = mid + 1;
                else
                {
                    flag = 1;
                    break;
                } 
            }
            if(flag) 
            {
                puts("YES");
                pf("%d %d %d\n", i, mid - i, n - mid);
                break;    
            }
        }

        if(!flag) puts("NO");
    } 

    return 0;
}

Author: Mrhh
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source Mrhh !
评论
 Previous
Codeforces-1454E Number of Simple Paths Codeforces-1454E Number of Simple Paths
写在前面,对于一个图,他有n个点,n条边,那我们称之为基环树(环套树)。基环树的基本操作,找环: 无向图:拓扑排序,然后遍历度大于1的都是环上的点。(只有一个环,直接放到vector) 有向图:直接dfs标记,放到vector。 Pro
Next 
2020 China Collegiate Programming Contest WeiHai Site-D 2020 China Collegiate Programming Contest WeiHai Site-D
结论题… ProblemPortal Thoughts思路一:首先我们可以发现c如果是一个质数的话,一定是不成立的,因为质数无法分解,那么相乘的数的质因子中必定有c,那么累乘必定大于c。那么如果c是一个合数,根据唯一分解定理,但凡表达式中
  TOC