2020牛客暑期多校第五场

Author Avatar
MorphLing 8月 02, 2020

D.Drop-Voicing

算法标签：LIS

经过一些观察之后把问题转换成：“最少移动多少个数使得环有序”，也就是要找出原环的最长递增子序列（LIS）。打的时候因为n比较小直接$O(n^3)$过了，但是通过二分或者树状数组其实是可以压到$O(n^2logn)$的

参考：最长上升子序列(LIS)的三种求法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1000+5,INF=0x3f3f3f3f;

int T,n,m,A[N],dp[N],ans;

int check(int l,int r)
{
    for (int i=l;i<r;i++)
    {
        int j=lower_bound(dp,dp+n,A[i])-dp;
        dp[j]=A[i];
    }
    return n-(lower_bound(dp,dp+n,INF)-dp);
}
int main()
{
    cin>>n;
    for (int i=0;i<n;i++)
    {
        scanf("%d",&A[i]);
        A[n+i]=A[i];
    }
    ans=INF;
    for (int k=0;k<n;k++)
    {
        memset(dp,INF,sizeof(dp));
        ans=min(ans,check(k,k+n));
    }
    cout<<ans;
    return 0;
}

B.Graph

算法标签：字典树、异或最小生成树、Boruvka算法

同样先观察到无论如何操作，树上任意两点连边的权值是固定的。于是可以任意选取一个结点作为根（比如0结点），通过dfs求出每个点到根节点路径的异或和，将其作为点的权值，那么任意两点连边的权值就等同于这两点权值的异或。

此时问题就变成求异或最小生成树了。

解决方法是通过字典树和Boruvka算法的思想。

先读了读代码了解一下Boruvka算法是个啥。Boruvka算法介绍

但其实更多的还是借用了它的思想，即对于某个联通块（一开始每个节点各自属于独立的联通块），我们可以贪心地找到所有从该联通块指向其他联通块的权值最小的边，并直接将它加入最小生成树中。

把这个思想运用到字典树中，其实就变成了子树合并的问题。把一个结点的左右子树分别看作两个联通块，对于这两个联通块，当前权值最小的边一定同时连接了这两个联通块。那么借助字典树，尽可能在往下走走一样的方向，就可以找到这条边的权值了。

对于权值重复的点，肯定会在第一步就互相连边，由于这些边权值一定是0，可以忽略，所以只需要直接去重就可以了。

因为这里字典树只有0和1，所以直接用l和r存左右儿子了。通用的字典树写法之后再补。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int INF=0x3f3f3f3f;

int l[N<<5],r[N<<5];

struct Edge{
    int t,w;
};

int root,num;

vector<Edge>G[N];

vector<int>P;

int u,v,w,n;

ll tot;

void dfs(int x,int fa,int now)
{
    P.push_back(now);
    for (auto to:G[x])
    {
        if (to.t!=fa)
            dfs(to.t,x,now^to.w);
    }
}
void MakeTrie(int subroot,int check,int x)
{
    if (check==0) return;
    if ((x&check)==0)
    {
        if (l[subroot]==0) l[subroot]=++num;
        MakeTrie(l[subroot],check>>1,x);
    }
    else
    {
        if (r[subroot]==0) r[subroot]=++num;
        MakeTrie(r[subroot],check>>1,x);
    }
}
ll dfs3(int a,int b,int check)
{
    if (!a || !b) return INF;
    if (check==0) return 0;
    ll t1,t2;
    t1=min(dfs3(l[a],l[b],check>>1),dfs3(r[a],r[b],check>>1));
    if (t1==INF)
        t2=check+min(dfs3(l[a],r[b],check>>1),dfs3(r[a],l[b],check>>1));
    else t2=INF;
    return min(t1,t2);
}
ll dfs2(int subroot,int check)
{
    ll ret=0;
    if (l[subroot]) ret+=dfs2(l[subroot],check>>1);
    if (r[subroot]) ret+=dfs2(r[subroot],check>>1);
    if (l[subroot] && r[subroot])
    {
        int t1=l[subroot],t2=r[subroot];
        ret+=check+dfs3(t1,t2,check>>1);
    }
    return ret;
}

int main()
{
    cin>>n;
    for (int i=1;i<=n-1;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        G[u].push_back({v,w});
        G[v].push_back({u,w});
    }
    dfs(0,-1,0);
    sort(P.begin(),P.end());
    P.erase(unique(P.begin(),P.end()),P.end());
    for (auto x:P)
    {
        MakeTrie(0,1<<30,x);
    }
    printf("%lld\n",dfs2(0,1<<30));
    return 0;
}

A.Portal

思考点：传送时一定会在脚下先丢一个传送门，然后传送到另一个门，所以只有一个门是有效的

于是dp时只需要记录一个门的情况

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " : " << x << endl

using namespace std;
typedef long long LL;

const int N = 6e2 + 5;
const LL INF = 0x3f3f3f3f3f3f3f3f;

LL dp[N][N];

LL dis[N][N];

int n, m, k, u, v, w, des[N];

int main() {
    scanf("%d %d %d", &n, &m, &k);
    memset(dis, INF, sizeof(dis));
    for (int i=1; i<=n; i++) dis[i][i]=0;
    for (int i=1; i<=m; i++) {
        scanf("%d %d %d", &u, &v, &w);
        if (w<dis[u][v]) dis[u][v] = dis[v][u] = w;
    }
    for (int k=1; k<=n; k++) {
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++)
                if (dis[i][k]+dis[k][j]<dis[i][j]) dis[i][j] = dis[i][k]+dis[k][j];
        }
    }
    for (int i=1; i<=k; i++) {
        scanf("%d %d", &u, &v);
        des[i*2-1]=u, des[i*2]=v;
    }
    memset(dp, INF, sizeof(dp));
    dp[1][0]=dis[1][des[1]];
    for (int i=1; i<=n; i++) {
        dp[1][i]=dis[1][i]+dis[i][des[1]];
    }
    for (int i=2; i<=2*k; i++) {
        for (int j=0; j<=n; j++) { //dp[i][j]
            for (int l=0; l<=n; l++) { //dp[i-1][l]
                if (j==l) dp[i][j]=min(dp[i][j], dp[i-1][l]+dis[des[i-1]][des[i]]);
                LL tmp=dp[i-1][l] + min(dis[des[i-1]][j], dis[l][j]) + min(dis[j][des[i]], dis[l][des[i]]);
                //LL tmp2=dis[des[i-1]
                dp[i][j]=min(dp[i][j], tmp);
            }
        }
    }
    LL ans = INF;
    for (int i=0; i<=n; i++) ans=min(ans, dp[2*k][i]);
    printf("%lld\n", ans);
    return 0;
}