hgoi#20191112

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

T1- 牛皮酥

你有一块 $n*m$ 的饼 每次可以吃某一块饼的一行或一列 问最多可以吃几次

解法

可以发现,每次吃出两个形似 $1*x$ 的饼最优 然后打表找一下式子

ac 代码

#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007ll
#define inv_2 500000004ll
using namespace std;
ll n,m;
int main()
{
    freopen("crisp.in","r",stdin);
    freopen("crisp.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    if((n&1)||(m&1))
        n%=mod,m%=mod,printf("%lldn",(1llnm%mod+n+m-1)*inv_2%mod);
    else n%=mod,m%=mod,printf("%lldn",(1llnm%mod+n+m-2)*inv_2%mod);
    return 0;
}

T2- 传送技术

有一棵有边权的树,现在要构造一个传送系统 每个节点有一个范围 $[l_i,r_i]$ ,节点可以任取一个范围内的数作为参数 $a_i$ 两个节点之间的传送代价为 $|a_i-a_j|$ 要求两个节点之间的传送代价均小于直接走的代价 问你能否构造一个这样的系统 如果不能,求最小的 $x$ 使所有的范围变为 $[l_i-x,r_i+x]$ 后能构造该系统

解法

容易想到,我们只需要检查相邻的点是否符合要求即可 所以对于每一个点,都能从它的儿子处传上来一个范围 如果这些范围全部有解,就可以构造出一个系统 如果不行,我们思考,对于两个区间的交集,如果两个区间全部左右扩大 $x$ 那么它们的交集也会左右扩大 $x$ ,所以我们找出最不合法的区间,再算出 $x$ 即可

ac 代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define l first
#define r second
using namespace std;
namespace fast_IO
{
    const int IN_LEN = 10000000, OUT_LEN = 10000000;
    char ibuf[IN_LEN], obuf[OUT_LEN], ih = ibuf + IN_LEN, oh = obuf, lastin = ibuf + IN_LEN, lastout = obuf + OUT_LEN - 1;
    inline char getchar_(){return (ih == lastin) && (lastin = (ih = ibuf) + fread(ibuf, 1, IN_LEN, stdin), ih == lastin) ? EOF : *ih++;}
    inline void putchar_(const char x){if(oh == lastout) fwrite(obuf, 1, oh - obuf, stdout), oh = obuf; *oh ++= x;}
    inline void flush(){fwrite(obuf, 1, oh - obuf, stdout);}
    inline void read(int&x)
    {
        int fh=1;x=0;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 write(int x){if(x>9)write(x/10);putchar_(x%10+'0');}
    inline void writeln(int x){write(x),putchar_('n');}
};
using namespace fast_IO;
vector<int>e[1000010],w[1000010];
int T,opt,n,x,y,z,ans;
pii a[1000010];
pii f(pii x,int y){return mp(x.l-y,x.r+y);}
pii solve(pii x,pii y){return mp(max(x.l,y.l),min(x.r,y.r));}
void check(pii x){ans=max(ans,x.l-x.r);}
pii dfs(int u,int fa)
{
    pii tmp=a[u];
    int sz=e[u].size();
    for(int i=0;i<sz;i++)if(eu!=fa)
        check(tmp=solve(tmp,f(dfs(eu,u),wu)));
    return tmp;
}
signed main()
{
  freopen("transport.in","r",stdin);
  freopen("transport.out","w",stdout);
    read(T),read(opt);
    while(T--)
    {
        read(n);
        for(int i=1;i<=n;i++)
            e[i].clear(),w[i].clear();
        for(int i=1;i<=n;i++)read(a[i].l);
        for(int i=1;i<=n;i++)read(a[i].r);
        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);
        ans=0,dfs(1,0),ans=(ans+1)/2;
        printf("%lldn",opt?ans:(bool)ans);
    }
    return 0;
}

T3- 故乡的老树

对于一棵树,求每个节点的子树中,到其他点距离之和最小的点

解法

一棵树中到其他点距离之和最小的点就是树的重心,所以题目转化为求一棵树所有子树的重心
有几个结论 (我都不会证 QWQ)
一棵树的重心最多有两个,且一定相邻
一棵树的重心一定在它重儿子的重心到根节点的这条链上
对于 $f_x=max(maxp[x],sz[rt]-sz[x])$ 即重心的定义式
在这条链上一定是一个谷函数,即先减少后增加
然后,我们根据这几条性质直接暴搜就好了 QWQ
复杂度是 $O(n)$ ,我还是不会证 嘤嘤嘤

ac 代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
namespace fast_IO
{
    const int IN_LEN = 10000000, OUT_LEN = 10000000;
    char ibuf[IN_LEN], obuf[OUT_LEN], ih = ibuf + IN_LEN, oh = obuf, lastin = ibuf + IN_LEN, lastout = obuf + OUT_LEN - 1;
    inline char getchar_(){return (ih == lastin) && (lastin = (ih = ibuf) + fread(ibuf, 1, IN_LEN, stdin), ih == lastin) ? EOF : *ih++;}
    inline void putchar_(const char x){if(oh == lastout) fwrite(obuf, 1, oh - obuf, stdout), oh = obuf; *oh ++= x;}
    inline void flush(){fwrite(obuf, 1, oh - obuf, stdout);}
    inline void read(int&x)
    {
        x=0;char c=getchar_();
        for(;!isdigit(c);c=getchar_());
        for(;isdigit(c);c=getchar_())x=x*10+c-'0';
    }
    inline void write(int x){if(x>9)write(x/10);putchar_(x%10+'0');}
    inline void writeln(int x){write(x),putchar_('n');}
};
using namespace fast_IO;
vector<int>e[1000010],ans[1000010];
int n,x,y,f[1000010],sz[1000010],ct[1000010],maxp[1000010];
void dfs1(int u,int fa)
{
    sz[u]=1,f[u]=fa;
    for(auto v:e[u])if(v!=fa)
        dfs1(v,u),sz[u]+=sz[v],
        maxp[u]=max(maxp[u],sz[v]);
    for(auto v:e[u])if(v!=fa)
        if(sz[v]==maxp[u])ct[u]++;
}
void dfs2(int u,int fa)
{
    int nub;
    for(auto v:e[u])if(v!=fa)
    {
        dfs2(v,u);
        if(sz[v]==maxp[u])nub=v;
    }
    if(ct[u]!=1)ans[u].pb(u);
    else
    {
        int nw=fans[nub],lst=ansnub;
        while(nw!=f[u])
        {
            int tmp1=max(sz[u]-sz[nw],maxp[nw]);
            int tmp2=max(sz[u]-sz[lst],maxp[lst]);
            if(tmp1==tmp2){ans[u].pb(lst),ans[u].pb(nw);break;}
            else if(tmp1>tmp2){ans[u].pb(lst);break;}
            lst=nw,nw=f[nw];
        }
        if(!ans[u].size())ans[u].pb(u);
    }
}
int main()
{
    freopen("extree.in","r",stdin);
    freopen("extree.out","w",stdout);
    read(n);
    for(int i=1;i<n;i++)
        read(x),read(y),e[x].pb(y),e[y].pb(x);
    dfs1(1,0),dfs2(1,0);
    for(int i=1;i<=n;i++)
    {
        sort(ans[i].begin(),ans[i].end());
        if(ans[i].size()==1)writeln(ansi);
        else write(ansi),putchar_(' '),writeln(ansi);
    }
    flush();return 0;
}