HGOI20191114 CSP模拟赛反思

Problem A 宇宙魔方

　　　有一个$N \times N \times N$的魔方，每一次操作可以整体转动该魔方，也可以对于一层整体+X。

　　　给出最后魔方的最终状态，其中有一个位置为-1。利用其它位置的信息输出这个-1具体表示的值。

　　　对于$100\%$的数据满足$1 \leq n\leq 100$

Self-correction：

　　考场看错题，最后炸题，导致期望得分为0。

　　不能把问题看的太简单，该思考的时候还是得多思考。

Solution1：

　　标程给的解答是，将x层y行z列的点染色成$(x+y+z)\% n$，

　　此时容易证明，同一个层上每行每列都是一个$[0,n-1]$的轮换。

　　若将魔方转置，容易看出，同行，每列，每层都是一个$[0,n-1]$的轮换；同列，每行，每层都是一个$[0,n-1]$的轮换。

　　这样一来，如果我们对于一次+X的操作，虽然不同位置的值会发生改变，但是同一颜色的点的和仍然保持不变。

　　最后，由于-1只占一个颜色，我们计算其他任意一种颜色位置上的权值和，直接减去-1那种颜色的权值和就是答案。

　　时间复杂度为$O(n^3)$

Solution2 :

　　一种比较美妙的做法是，可以将同一层上的+x，转化为若干次同一列或者同一行的操作。（转置同理）

　　这样，如果我们对于$(x,y,z)$是$-1$的位置，只需要利用容斥原理，利用同层、同列、同行构造的矩形就可以求解了。

　　每个位置，同层、同列、同行，必然能构造出一个宽度为$1$的正方形，所以这样构造可以通过所有测试点。

　　时间复杂度为$O(n^3)$

Code : 这个题目方法比较多我就不贴了....

Problem B 战争

　　有$n$个点的图，点的标号为$[0,n-1]$，有$m$条边，求出图上严格单增最长路的长度。

　　对于$100\%$的数据满足$1 \leq n,m\leq 5\times 10^4$　

Self-correction：

　　考场需要仔细，虽然这个题，看成了[1,n]还有$96$的好成绩。

　　但是不排除毒瘤出题人，给你卡到0分。还是要多加注意....

Solution ：

　　考虑$f[i]$表示到第$i$点的最长连读单增最长路长度。

　　那么按照边权排序之后，直接$dp$就没有后效性了。

　　注意到，由于是严格单增，那么需要相同边权所连的点同时转移。

　　复杂度是$O(n+m)$

# include <bits/stdc++.h>

using namespace std;

const int N=1e5+;

int n,m,tot;

int t[N],f[N];

struct Edge { int u,v,w;}e[N];

bool cmp(Edge a,Edge b) { return a.w < b.w;}

int main() {

    scanf("%d%d",&n,&m);

    for (int i=;i<=m;i++) {

        int u,v,w; scanf("%d%d%d",&u,&v,&w);

        e[++tot].u=u; e[tot].v=v; e[tot].w=w;

    }

    sort(e+,e++m,cmp);

    int last = ;

    for (int i=;i<=m;i++) if (i==m || e[i].w < e[i+].w) {

        for (int j=last+;j<=i;j++) t[e[j].u]=f[e[j].u],t[e[j].v]=f[e[j].v];

        for (int j=last+;j<=i;j++) {

            f[e[j].u]=max(f[e[j].u],t[e[j].v]+);

            f[e[j].v]=max(f[e[j].v],t[e[j].u]+);

        }

        last = i;

    }

    int ans = ;

    for (int i=;i<n;i++) ans=max(ans,f[i]);

    printf("%d\n",ans);

    return ;

}

war.cpp

Problem C 和平

　　考虑$n$个点的树，每条边有边权，处理$q$个询问。

　　从$u$走到$v$的最短路径，如果不经过边权小于$w$的边，最远能走到那个节点。

　　对于$100\%$的数据，满足$1 \leq n ,q \leq 10^5$

Solution :

　　全场最可做题，二分+倍增的暴力人人都会。

　　复杂度为$O(n {log_2}^2 n)$

Code :

# pragma GCC optimize()

# include<bits/stdc++.h>

# define inf (2e9)

using namespace std;

const int N=2e5+;

struct rec{ int pre,to,w; }a[N];

int n,m,tot;

int head[N],g[N][],d[N][],dep[N];

void adde(int u,int v,int w) {

    a[++tot].pre=head[u];

    a[tot].to=v;

    a[tot].w=w;

    head[u]=tot;

}

void dfs(int u,int fa) {

    g[u][]=fa; dep[u]=dep[fa]+;

    for (int i=head[u];i;i=a[i].pre) {

        int v=a[i].to; if (v==fa) continue;

        d[v][]=a[i].w; dfs(v,u);

    }

}

int lca(int u,int v) {

    if (dep[u]<dep[v]) swap(u,v);

    for (int i=;i>=;i--)

        if (dep[g[u][i]]>=dep[v]) u=g[u][i];

    if (u==v) return u;

    for (int i=;i>=;i--)

        if (g[u][i]!=g[v][i]) u=g[u][i],v=g[v][i];

    return g[u][];

}

int dist(int u,int v) {

    int ret=inf;

    if (dep[u]<dep[v]) swap(u,v);

    for (int i=;i>=;i--)

        if (dep[g[u][i]]>=dep[v]) ret=min(ret,d[u][i]),u=g[u][i];

    if (u==v) return ret;

    for (int i=;i>=;i--)

        if (g[u][i]!=g[v][i]) {

            ret=min(ret,d[u][i]);

            ret=min(ret,d[v][i]);

            u=g[u][i],v=g[v][i];

        }

    return ret;

}

int Get(int u,int d) {

    for (int i=;i>=;i--) if (d>=(<<i)) {

        u=g[u][i]; d-=(<<i);

    }

    return u;

}

int work1(int u,int v,int w) {

    int l=,r=dep[v]-dep[u],ans;

    while (l<=r) {

        int mid = (l+r)>>;

        int to = Get(v,mid);

        if (dist(to,u)>=w) ans=mid,r=mid-;

        else l=mid+;

    }

    return Get(v,ans);

}

int work2(int u,int v,int w) {

    int l=,r=dep[u]-dep[v],ans;

    while (l<=r) {

        int mid = (l+r)>>;

        int to = Get(u,mid);

        if (dist(to,u)>=w) ans=mid,l=mid+;

        else r=mid-;

    }

    return Get(u,ans);

}

int work3(int u,int v,int w,int l) {

    int ret1=work2(u,l,w); if (ret1!=l) return ret1;

    int ret2=work1(l,v,w); return ret2;

}

int main() {

//  freopen("peace.in","r",stdin);

//  freopen("peace.out","w",stdout);

    scanf("%d%d",&n,&m);

    for (int i=;i<=n;i++) {

        int u,v,w; scanf("%d%d%d",&u,&v,&w);

        adde(u,v,w); adde(v,u,w);

    }

    memset(d,0x3f,sizeof(d));

    dfs(,);

    for (int i=;i<=;i++)

        for (int j=;j<=n;j++) {

            g[j][i]=g[g[j][i-]][i-];

            d[j][i]=min(d[j][i-],d[g[j][i-]][i-]);

        }

    while (m--) {

        int u,v,w; scanf("%d%d%d",&u,&v,&w);

        int l = lca(u,v);

        if (l == u) printf("%d\n",work1(u,v,w));

        else if (l == v) printf("%d\n",work2(u,v,w));

        else printf("%d\n",work3(u,v,w,l));

    }

    return ;

 }

peace.cpp

巴特西

HGOI20191114 CSP模拟赛反思

最新文章

热门文章

巴特西

HGOI20191114 CSP模拟赛 反思

最新文章

热门文章

HGOI20191114 CSP模拟赛反思