NOIP真题题解（二）二分

Dear 丶 2021-11-22 10:02 339阅读 0赞

## 1. NOIP2010提高组 关押罪犯 ##

#### 来源：NOIP2003提高组 [https://ac.nowcoder.com/acm/contest/258/C][https_ac.nowcoder.com_acm_contest_258_C] ####

#### (二分，染色法判断二分图) O((N+M)logC) ####

*  将罪犯当做点，罪犯之间的仇恨关系当做点与点之间的无向边，边的权重是罪犯之间的仇恨值。  
    那么原问题变成：将所有点分成两组，使得各组内边的权重的最大值尽可能小。  
    我们在 \[ 0 , 1 0 9 \] \[0, 10^9\] \[0,109\] 之间枚举最大边权 l i m i s t limist limist, 当 l i m i s t limist limist固定之后，剩下的问题就是：
    
     *  判断能否将所有点分成两组，使得所有权值大于 limit 的边都在组间，而不在组内。也就是判断由所有点以及所有权值大于 limit 的边构成的新图是否是二分图。
 *  判断二分图可以用染色法，时间复杂度是 O ( N + M ) O( N + M) O(N\+M), 其中 N 是点数，M 是边数，可以参考AcWing 860. 染色法判定二分图。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70]

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std; const int N = 20010,
       M = 200010;
    
    int n, m;
    int h[N], e[M], w[M], ne[M], idx;
    int color[N];
    
    void add(int a, int b, int c)
    { 
       e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    }
    
    bool dfs(int u, int c, int limit)
    { 
       color[u] = c;
       for (int i = h[u]; ~i; i = ne[i])
       { 
           if (w[i] <= limit) continue;
           int j = e[i];
           if (color[j])
           { 
               if (color[j] == c) return false;
           }
           else if (!dfs(j, 3 - c, limit)) return false;
       }
    
       return true;
    }
    
    bool check(int limit)
    { 
       memset(color, 0, sizeof color);
    
       for (int i = 1; i <= n; i++)
           if (color[i] == 0)
               if (!dfs(i, 1, limit))
                   return false;
       return true;
    }
    
    int main()
    { 
       scanf("%d%d", &n, &m);
    
       memset(h, -1, sizeof h);
       while (m--)
       { 
           int a, b, c;
           scanf("%d%d%d", &a, &b, &c);
           add(a, b, c);
           add(b, a, c);
       }
    
       int l = 0, r = 1e9;
       while (l < r)
       { 
           int mid = l + r >> 1;
           if (check(mid)) r = mid;
           else l = mid + 1;
       }
    
       printf("%d\n", l);
       return 0;
    }

## 2. 聪明的质检员 ##

#### 来源：NOIP2011提高组 [https://ac.nowcoder.com/acm/contest/259/B][https_ac.nowcoder.com_acm_contest_259_B] ####

#### 算法知识点：二分，前缀和 ####

#### 复杂度： O(n^2) ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 1]

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
     
    typedef long long LL; const int N = 200010;
     
    int n, m;
    LL S;
    int w[N], v[N];
    int l[N], r[N];
    int cnt[N];
    LL sum[N];
     
    LL get(int W)
    { 
        for (int i = 1; i <= n; i++)
            if (w[i] >= W)
            { 
                sum[i] = sum[i - 1] + v[i];
                cnt[i] = cnt[i - 1] + 1;
            }
        else
        { 
            sum[i] = sum[i - 1];
            cnt[i] = cnt[i - 1];
        }
     
        LL res = 0;
        for (int i = 0; i < m; i++) res += (cnt[r[i]] - cnt[l[i] - 1]) *(sum[r[i]] - sum[l[i] - 1]);
        return res;
    }
     
    int main()
    { 
        scanf("%d%d%lld", &n, &m, &S);
        for (int i = 1; i <= n; i++) scanf("%d%d", &w[i], &v[i]);
        for (int i = 0; i < m; i++) scanf("%d%d", &l[i], &r[i]);
     
        int l = 0, r = 1e6 + 1;
        while (l < r)
        { 
            int mid = l + r + 1 >> 1;
            if (get(mid) >= S) l = mid;
            else r = mid - 1;
        }
     
        printf("%lld\n", min(abs(get(r) - S), abs(S - get(r + 1))));
     
        return 0;
    }

## 3.借教室 ##

#### 来源：NOIP2012提高组 [https://ac.nowcoder.com/acm/contest/260/B][https_ac.nowcoder.com_acm_contest_260_B] ####

#### 算法知识点：二分，差分 ####

#### 复杂度： O((n + m)logm ####

#### 解题思路： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 2]

### C++代码 ###

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
     
    typedef long long LL; const int N = 1000010;
     
    int n, m;
    int r[N], d[N], s[N], t[N];
    LL b[N];
     
    bool check(int k)
    { 
        for (int i = 1; i <= n; i++) b[i] = r[i];
     
        for (int i = 1; i <= k; i++)
        { 
            b[s[i]] -= d[i];
            b[t[i] + 1] += d[i];
        }
     
        LL res = 0;
        for (int i = 1; i <= n; i++)
        { 
            res += b[i];
            if (res < 0) return true;
        }
     
        return false;
    }
     
    int main()
    { 
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) scanf("%d", &r[i]);
        for (int i = n; i; i--) r[i] -= r[i - 1];
     
        for (int i = 1; i <= m; i++) scanf("%d%d%d", &d[i], &s[i], &t[i]);
     
        int l = 1, r = m;
        while (l < r)
        { 
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
     
        if (check(r))
        { 
            puts("-1");
            printf("%d\n", r);
        }
        else puts("0");
     
        return 0;
    }

## 4. 跳石头 ##

#### 来源：NOIP2015提高组 [https://ac.nowcoder.com/acm/contest/263/A][https_ac.nowcoder.com_acm_contest_263_A] ####

#### 算法知识点：二分，贪心 ####

#### 复杂度：O(NlogL) ####

#### 解题思路： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 3]

### C++代码 ###

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std; const int N = 50010;
     
    int L, n, m;
    int d[N];
     
    bool check(int mid)
    { 
        int last = 0, cnt = 0;
        for (int i = 1; i <= n; i++)
            if (d[i] - last < mid) cnt++;
            else last = d[i];
        return cnt <= m;
    }
     
    int main()
    { 
        scanf("%d%d%d", &L, &n, &m);
        for (int i = 1; i <= n; i++) scanf("%d", &d[i]);
        d[++n] = L;
     
        int l = 1, r = 1e9;
        while (l < r)
        { 
            int mid = l + r + 1 >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
     
        printf("%d\n", r);
        return 0;
    }

### 另外，牛客暑期NOIP真题班限时免费报名 ###

报名链接：[https://www.nowcoder.com/courses/cover/live/248][https_www.nowcoder.com_courses_cover_live_248]  
报名优惠券：DCYxdCJ

#### 参考链接：[https://blog.nowcoder.net/sylvie][https_blog.nowcoder.net_sylvie] ####

[https_ac.nowcoder.com_acm_contest_258_C]: https://ac.nowcoder.com/acm/contest/258/C
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70]: /images/20211122/e9c2e1bbf2f94803a9a0ec79ee37831d.png
[https_ac.nowcoder.com_acm_contest_259_B]: https://ac.nowcoder.com/acm/contest/259/B
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190726152729703.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA==,size_16,color_FFFFFF,t_70
[https_ac.nowcoder.com_acm_contest_260_B]: https://ac.nowcoder.com/acm/contest/260/B
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190726152858866.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA==,size_16,color_FFFFFF,t_70
[https_ac.nowcoder.com_acm_contest_263_A]: https://ac.nowcoder.com/acm/contest/263/A
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20190726153047108.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA==,size_16,color_FFFFFF,t_70
[https_www.nowcoder.com_courses_cover_live_248]: https://www.nowcoder.com/courses/cover/live/248
[https_blog.nowcoder.net_sylvie]: https://blog.nowcoder.net/sylvie