hgoi#20191114

muronglin
muronglin 2019年11月14日
  • 在其它设备中阅读本文章

T1- 宇宙魔方

有一个 $n^3$ 的立方体,每次会给这个立方体的一层都加上 $X$ 或整体转动这个立方体 现在给你若干次操作后的立方体,有一个格子上的值不知道,请你求出

解法

直接模拟回溯所有的操作 具体是每次找到一层的最小值 全部减去即可

ac 代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
inline void read(int&x)
{
    x=0;int fh=1;char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')fh=-1;
    for(;isdigit(c);c=getchar())x=x*10+c-'0';
    x*=fh;
}
inline void print(int x)
{
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
int n,minn,a110[110];
int main()
{
    freopen("cube.in","r",stdin);
    freopen("cube.out","w",stdout);
    read(n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                read(ai[k]);
    for(int i=1;i<=n;i++)
    {
        minn=inf;
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                if(ai[k]>=0)
                    minn=min(minn,ai[k]);
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                ai[k]-=minn;
        minn=inf;
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                if(aj[k]>=0)
                    minn=min(minn,aj[k]);
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                aj[k]-=minn;
        minn=inf;
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                if(aj[i]>=0)
                    minn=min(minn,aj[i]);
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                aj[i]-=minn;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                if(ai[k]<0)
                    print(-ai[k]-1);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

T2- 战争

给你一个带权无向图,要求你每次走的边权都要严格递增 求最远能走的距离

解法

这个根本不用建图 令 $f_{i,j}$ 表示 $i$ 号点作为终点,上一个走的权值为 $j$ 的最远距离 我们发现一条边只会更新两个点,所以把第二维压掉 具体见代码

ac 代码

#include<bits/stdc++.h>
using namespace std;
inline void read(int&x)
{
    x=0;int fh=1;char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')fh=-1;
    for(;isdigit(c);c=getchar())x=x*10+c-'0';
    x*=fh;
}
inline void print(int x)
{
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
struct node
{
    int x,y,s;
    void init(){read(x),read(y),read(s);}
    bool operator<(const node&a)const{return s<a.s;}
}e[50010];
queue<int>q;
int n,m,ans,f[50010],g[50010];
int main()
{
    freopen("war.in","r",stdin);
    freopen("war.out","w",stdout);
    read(n),read(m);
    for(int i=1;i<=m;i++)e[i].init();
    sort(e+1,e+m+1);
    int nw=1,ed=1;
    while(nw<=m)
    {
        while(ed<m&&e[ed].s==e[ed+1].s)ed++;
        while(nw<=ed)
        {
            g[e[nw].x]=max(g[e[nw].x],max(f[e[nw].x],f[e[nw].y]+1));
            g[e[nw].y]=max(g[e[nw].y],max(f[e[nw].y],f[e[nw].x]+1));
            q.push(e[nw].x),q.push(e[nw].y),nw++;
        }ed++;
        while(!q.empty())f[q.front()]=g[q.front()],q.pop();
    }
    for(int i=0;i<n;i++)ans=max(ans,f[i]);print(ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

T3- 和平

给你一棵带边权的树,若干次询问 每次询问 $A、B、c$ 表示从 A 出发,走到 B,只能通过边权大于等于 $c$ 的点 求最多能走到哪里

解法

先拆成两部分,先从 $A$ 走到 $LCA$ ,再从 $LCA$ 走到 $B$ 如果停下的地方在第一部分,用倍增非常好做 但是如果停下的地方在第二部分怎么办呢 我们可以二分求这条路径的断点,然后求出一段的最小值,看是否符合要求 具体实现见代码

ac 代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define mid (l+r>>1)
#define pb push_back
#define N 100010
#define K 18
using namespace std;
inline void read(int&x)
{
    x=0;int fh=1;char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')fh=-1;
    for(;isdigit(c);c=getchar())x=x*10+c-'0';
    x*=fh;
}
inline void print(int x)
{
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
vector<int>e[N],w[N];
int n,m,x,y,z,d[N],fN,vN;
void dfs(int u,int fa)
{
    int sz=e[u].size();
    for(int i=0;i<sz;++i)if(eu!=fa)
        fe[u][0]=u,ve[u][0]=wu,
        de[u]=d[u]+1,dfs(eu,u);
}
inline int lca(int x,int y)
{
    if(d[x]<d[y])swap(x,y);
    if(d[x]>d[y])
    {
        int g=d[x]-d[y];
        for(int i=0;i<K;++i)
            if(g&(1<<i))
                x=fx;
    }
    if(x==y)return x;
    for(int i=K-1;i>=0;--i)
        if(fx!=fy)
            x=fx,y=fy;
    return fx;
}
inline int get(int u,int g)
{
    int ans=inf;
    for(int i=0;i<K;++i)
        if(g&(1<<i))
            ans=min(ans,vu),
            u=fu;
    return ans;
}
//得到u向上g条边的最小值
inline int find(int u,int g)
{
    for(int i=0;i<K;++i)
        if(g&(1<<i))
            u=fu;
    return u;
}
//寻找u向上g条边的点
inline int query(int st,int ed,int G)
{
    int LCA=lca(st,ed),da=d[st]-d[LCA],db=d[ed]-d[LCA];
    int l=0,r=da+db,ans,D=get(st,da);
    while(l<=r)
        if((mid<=da?get(st,mid):min(D,get(find(ed,da+db-mid),mid-da)))<G)r=mid-1;else ans=mid,l=mid+1;
    //二分这个断点,如果在第一部分,那么路径只有一段
    //如果在第二部分,分成整个第一部分和第二部分断点上方的位置求解
    if(ans>da)return find(ed,da+db-ans);else return find(st,ans);
}
int main()
{
    freopen("peace.in","r",stdin);
    freopen("peace.out","w",stdout);
    read(n),read(m);
    for(int i=1;i<n;i++)
        read(x),read(y),read(z),
        e[x].pb(y),w[x].pb(z),
        e[y].pb(x),w[y].pb(z);
    dfs(1,0);
    for(int j=1;j<K;++j)
        for(int i=1;i<=n;++i)
            fi=ff[i][j-1],
            vi=min(vi,vf[i][j-1]);
    for(int i=1;i<=m;++i)
        read(x),read(y),read(z),
        print(query(x,y,z)),putchar('n');
    fclose(stdin);
    fclose(stdout);
    return 0;
}