Educational Codeforces Round 89 (Rated for Div. 2)---B. Shuffle(1300分+简单合并区间)

简介: 算法

17.png

题意:

给你一个由n个整数a1, a2, …, an组成的数组。最初ax=1,所有其他元素都等于0。

你必须进行m次操作。在第i次操作中,你选择两个指数c和d,使li≤c,d≤ri,并交换ac和ad。

计算指数k的数量,以便有可能选择操作,使ak=1。

大概就是说通过m次操作,能把哪几个位置换成1,可以看成ax是被染色的,只要在区间的块都能被染色,求最大的被染色的块。


思路:

先找到第一个包含x的区间,这个区间里的所有数都可以被染色,感觉可以当区间合并做

一开始我的区间只有个一点,m的最大范围只有100个,所以100个区间合并,求在x的区间长度,但是合并有原则得按照顺序合并,当前遍历到的区间不能和之后出现的区间合并,只能和之前的合并,所以只需要合并x和出现过x的区间即可

复杂度大概是O(m^2*t)大概1e6

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
struct node {
    int l,r;
}mo[maxn];
int main()
{
    int n,i,j,t,m,x;
    cin>>t;
    while(t--)
    {
        int l1,r1;
        cin>>n>>x>>m;
        int cnt=0;
        mo[cnt].r=x;
        mo[cnt++].l=x;
        for(i=0;i<m;i++)
        {
            cin>>l1>>r1;
            int flag=0;
            for(j=0;j<1;j++)
            {
                if((l1>=mo[j].l&&l1<=mo[j].r)||(r1<=mo[j].r&&r1>=mo[j].l)||(l1<=mo[j].l&&r1>=mo[j].r))
                {
                    mo[j].l=min(mo[j].l,l1);
                    mo[j].r=max(mo[j].r,r1);
                }
            }
        }
        for(i=0;i<cnt;i++)
        {
            if(x>=mo[i].l&&x<=mo[i].r)
            {
                cout<<mo[i].r-mo[i].l+1<<endl;
                break;
            }
        }
    }
    return 0;
}
相关文章
|
人工智能 测试技术
Codeforces Round #746 (Div. 2) C. Bakry and Partitioning
Codeforces Round #746 (Div. 2) C. Bakry and Partitioning
85 0
|
C++
【PAT甲级 - C++题解】1145 Hashing - Average Search Time
【PAT甲级 - C++题解】1145 Hashing - Average Search Time
82 0
Codeforces Round #746 (Div. 2) C - Bakry and Partitioning(dfs 异或技巧 思维)
Codeforces Round #746 (Div. 2) C - Bakry and Partitioning(dfs 异或技巧 思维)
96 0
|
人工智能 Windows
Educational Codeforces Round 113 (Rated for Div. 2) C - Jury Meeting (思维 组合数)
Educational Codeforces Round 113 (Rated for Div. 2) C - Jury Meeting (思维 组合数)
97 0
Codeforces Round #747 (Div. 2) D. The Number of Imposters(扩展域并查集 带权并查集)
Codeforces Round #747 (Div. 2) D. The Number of Imposters(扩展域并查集 带权并查集)
113 0
|
人工智能
Educational Codeforces Round 113 (Rated for Div. 2) B. Chess Tournament(思维 构造)
Educational Codeforces Round 113 (Rated for Div. 2) B. Chess Tournament(思维 构造)
88 0