题解与反思

这次的题目比较正常吧，就是感觉做题太少了，思路打不开，有些不是很难的题目想不到。

D - Permutation Subsequence

滑动窗口的经典题目。
首先要弄明白，怎样才能选出来好索引序列。只要对应的元素集合是sort（）之后是一个公差为1等差数列即可，我们可以考虑对原来的数组进行排序，然后选取k长度的序列对应的索引序列，这个索引必然是好索引序列。
我们如何快速求解索引序列的最大值，最小值呢？我们可以用set来存储，一个按greatr, 一个按less , 这时候极差等于两个set.begin() 的差值。
我们要做的就是维护一个长度为k的序列，每次删掉第一个元素，然后加上下一个元素。由于set.insert()和set.erase() 复杂度都是 $log(N)$ ，总的复杂度为 $O(Nlog(N)$ 。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
using namespace std;

typedef long long LL;
const int N = 2e5 + 10;
struct node
{
    int x, id;
    bool operator < (const node t) const
    {
        return x < t.x;
    }
}s[N];
int a[N];
set<int, greater<int>> b1;//从大到小排序
set<int, less<int>> b2;//从小到大排序
int main()
{
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i ++)
    {
        int x;
        cin >> x;
        s[i].x = x;
        s[i].id = i;
    }
    sort(s + 1, s + 1 + n);
    int res = 1e9;
    for(int i = 1; i <= k; i ++)
    {
        b1.insert(s[i].id);
        b2.insert(s[i].id);
    }
    res = min(res, *b1.begin() - *b2.begin());
    for(int i = k + 1; i <= n; i ++)
    {
        b1.erase(s[i - k].id);
        b2.erase(s[i - k].id);
        b1.insert(s[i].id);
        b2.insert(s[i].id);
        res = min(res, *b1.begin() - *b2.begin());
    }
    cout << res << endl;
    return 0;
}

E - Clique Connect

图论，并查集的应用

由于每次对一个集合中建的边权都是相同的，那么不需要记录所有的边，只要保证这个集合中的点连通即可，这里选择将每个点与集合中前一个点建边。
然后就是经典的Kruscal算法，将所有边按边权排序，然后按边权从小到大遍历边，并使用并查集进行维护，当两个点不在同一个集合中时，就在这两个点之间建边，并记录费用以及连的边数。
结束操作后，如果没有连上条边，就说明不存在最小生成树，输出-1。否则，输出记录的费用。
有一点疑问，为啥每个集合不用存储所有的边?
解答：我们保证每个集合联通，就相当于这个集合的最小生成树，也就是新的边集E’

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
using namespace std;

typedef long long LL;
const int N = 4e5 + 10;
struct node
{
    LL u, v, w;
    bool operator < (const node& t) const
    {
        return w < t.w;
    }
}edge[N];
int fa[N];
LL n, m, cnt, res, sum;
int find(int x)
{
    if(x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}
void Union(node t)
{
    int fu = find(t.u);
    int fv = find(t.v);
    if(fu != fv)
    {
        
        fa[fu] = fv;
        sum ++;
        res += t.w;
    }
}
int main()
{

    cin >> n >> m;
    while(m --)
    {
        int k, c, pre = -1;
        cin >> k >> c;
        for(int i = 1; i <= k; i ++)
        {
            int x;
            cin >> x;
            if(i > 1) edge[cnt++] = {pre, x, c};
            pre = x;
        }
    }
    sort(edge, edge + cnt);
    for(int i = 1; i <= n; i ++) fa[i] = i;
    for(int i = 0; i < cnt; i ++)
    {
        Union(edge[i]);
    }
    if(sum != n - 1) cout << -1 << endl;
    else cout << res << endl;
    return 0;
}

AtCoder Beginner Contest 352

题解与反思

D - Permutation Subsequence

E - Clique Connect