Atcoder352(D-E)题解

D - Permutation Subsequence

题意

给你一个到的排列，找到一个长为的子序列，满足子序列中元素重排后构成公差为的等差数列，求子序列的最小跨度。

解题思路

首先我们可以开一个pos数组记录中每一个数的位置，由此问题转换求

• 解决方案一：式子中关键部分：求出一个区间值，这可以用来快速解决此题，时间复杂度为
• 解决方案二：由于区间长度是固定的，我们可以用动态维护一个长度为的集合，然后达到快速求出值，时间复杂度为

解题代码

解题代码一：

#include <bits/stdc++.h>
using namespace std;
const int N=200010;
const int INF=1e8;
int n,k,x,pos[N],lg[N];
int mx[N][20],mn[N][20];
int ans=1e8;

void init()
{
  memset(mx,-INF,sizeof mx);
  memset(mn,INF,sizeof mn);
  lg[1]=0;
  for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
  for(int i=1;i<=n;i++) mx[i][0]=mn[i][0]=pos[i];
  for(int j=1;j<=lg[n];j++){
    for(int i=1;i+(1<<j)-1<=n;i++){
      mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
      mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
    }
  }
}

int mx_query(int l,int r)
{
  int len=lg[r-l+1];
  return max(mx[l][len],mx[r-(1<<len)+1][len]);
}

int mn_query(int l,int r)
{
  int len=lg[r-l+1];
  return min(mn[l][len],mn[r-(1<<len)+1][len]);
}

int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n>>k;
  for(int i=1;i<=n;i++) cin>>x,pos[x]=i;
  init();
  for(int l=1,r=k;r<=n;l++,r=l+k-1){
    ans=min(ans,mx_query(l,r)-mn_query(l,r));
  }
  cout<<ans;
  return 0;
}

解题代码二：

#include <bits/stdc++.h>
using namespace std;
const int N=200010;
int n,k,a[N],x;
set<int> s;
int ans=1e8;

int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n>>k;
  for(int i=1;i<=n;i++) cin>>x,a[x]=i;
  for(int i=1;i<=n;i++){
    s.insert(a[i]);
    if(i>=k){
      ans=min(ans,*prev(s.end())-*s.begin());
      s.erase(a[i-k+1]);
    }
  } 
  cout<<ans;
  return 0;
}

E - Clique Connect

题意

给你一个有 个顶点的加权无向图 ，顶点编号为 到 。最初， 没有边。

您将执行 次操作为 添加边。 th操作 如下：

• 给你一个由 个顶点组成的顶点子集 。对于每一对 ，即 和 ，在顶点 和 之间添加一条边，权重为 。

执行 次操作后，确定 是否相连。如果是，求 最小生成树中各条边的总重。

解题思路

如果将所有的边均枚举一遍，必然会，考虑到顶点集中的所有点必然属于同一个连通块，而最小生成树要求的是总权值最小，所以我们顶点集的相邻节点连接即可，然后再跑一遍判断是否相连或求出最小生成树

解题代码

#include <bits/stdc++.h>
using namespace std;
const int N=200010;
typedef long long ll;
int n,m,c,k,q;
int a[N];
struct edge{
    int u,v,w;
    bool operator<(const edge &t)const {
        return w<t.w;
    }
}e[4*N];

int fa[N];
ll res,cnt;

inline int find(int x)
{
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}

inline ll kruskal()
{
    sort(e,e+m);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=0;i<m;i++){
        int x=find(e[i].u);
        int y=find(e[i].v);
        if(x!=y){
            fa[x]=y;
            res+=e[i].w;
            cnt++;
            if(cnt==n-1) return res;
        }
    }
    return -1;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    while(q--){
        cin>>k>>c;
        for(int i=1;i<=k;i++){
            cin>>a[i];
            if(i>=2) e[m++]={a[i-1],a[i],c};
        }
    }
    cout<<kruskal();
    return 0;
}