Codeforces Round #600 (Div. 2)

D题

每次给你一条边，，然后问你最少添加多少条边使得这些边可以变成和谐图（和谐图：图上任两连接个点l，r，那么l必须可以和l+1，l+2，l+3。。。r，这些点联通）

直接边排序+并查集

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+7;
const ll mod = 998244353;
#define afdafafafdafaf y1;
int ar[maxn], n, m;
 
pair<int,int> p[maxn];
int f[maxn];
int findx(int x){
    return f[x] == x ? x : f[x] = findx(f[x]);
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++)f[i] = i;
    for(int i=1;i<=m;i++){
        int a,b;scanf("%d%d", &a, &b);
        if(a > b)swap(a, b);
        p[i].first = a;
        p[i].second = b;
        a = findx(a);
        b = findx(b);
        f[a] = b;
    }
    sort(p + 1, p + m + 1);
    int pa = 0, pb = 0;
    p[m+1].first = int(1e9);
    //cout<<p[m+1].first<<'
';
    int ans=0;
    for(int i=1;i<=m+1;i++){
        //cout<<"i = " << i << ' ' << p[i].first<<" "<<p[i].second<<"
";
        if(p[i].first > pb){
            int x = pa;
            //cout<<pa<<" "<<pb<<"
";
            for(int j=pa+1;j<=pb;j++){
                x = findx(x);
                int y = j;
                y = findx(y);
                if(x != y){
                    f[x] = y;
                    ans++;
                }
            }
            pa = p[i].first;
            pb = p[i].second;
        }
        else{
            pb = max(pb, p[i].second);
        }
    }
    printf("%d
", ans);
    return 0;
}

　　C

给你n棵糖，再给你k，每天限制吃最多k课糖，一颗糖的甜度是ai，很恐怖的是这颗糖会随着天数的增加导致甜度+=ai，例如一颗糖第一天的时候是3，第二天就会变成6，第三天变成9；问你求吃第n课糖时候最小甜度是多少，吃过的肯定没有的了，不能第二天还选；

首先！！！先当然的是第一天吃甜度高点的，甜度低点的在第二天吃这样的贪心，所以我们先给甜度排个序；

例如我们给个例子 k=2，n颗糖 2 3 4 5 6 7 8

第一颗：dp1=2 ;dp2=2+3,dp3=dp1+2+3+4,dp4=dp2+2+3+4+5;规律就出来了，dp走起：dp[i]=dp[i-k]+sum[i](sum[i]表示排序后的前i颗糖甜度）