hgoi#20190512

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

T1-Memory and De-Evolution

Memory 对物体,尤其是三角形的变化感兴趣。 他有一个边长为 x 的等边三角形,他希望通过一些操作获得一个边长为 y 的等边三角形。 他一次可以修改当前三角形一边的长度,修改后也应为合法的三角形。每次修改后,每一边的长度都应该是整数。 Memory 要获得边长 y 的等边三角形,所需的最小修改次数是多少?

解法

大模拟,发现从大的往小的模拟很难找最优策略,就从小的往大的模拟,每次将最小的变成最大的

ac 代码

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,c,ans=0,sum,minn;
int main()
{
    scanf("%d%d",&n,&m),a=b=c=m;
    while(a!=n||b!=n||c!=n)
    {
        sum=a+b+c,minn=min(min(a,b),c),ans++;
        if(minn==a)a=min(sum-a-1,n);
        else if(minn==b)b=min(sum-b-1,n);
        else if(minn==c)c=min(sum-c-1,n);
    }
    printf("%dn",ans);
    return 0;
}

T2-Memory and Scores

AB 两人玩一个游戏,两人玩 t 轮 每人每次随机且等概率从 [-k,k] 中取一个数字加到总得分中 得分高者赢 已知 A B 初始分别有 a b 分,问 A 取得胜利的概率是多少 为了避免小数精度问题答案 *(2k+1)^t mod 1000000007

解法

因为 [-k,k] 是对称的,所以可以看做初始分数为 a -b,玩 2t 轮,每轮从 [-k,k] 中选一个数字加到分数中,求分数为正的概率 这样就可以 dp 了,dp[i]=dp[j]的和(i-k<=j<=i+k) 发现复杂度很大,k 方 t 方的样子,反正过不了 每次转移用前缀和来优化,就可以 kt 方了,刚好能过

ac 代码

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int a,b,k,t,lim,ans=0,dp[410000],f[410000];
int main()
{
    scanf("%d%d%d%d",&a,&b,&k,&t),lim=kt2,dp[lim]=1;
    for(int i=1;i<=t*2;i++)
    {
        f[0]=dp[0];
        for(int j=1;j<=lim*2+k;j++)f[j]=(f[j-1]+dp[j])%mod;
        for(int j=0;j<=k;j++)dp[j]=f[j+k];
        for(int j=k+1;j<=lim*2;j++)dp[j]=(f[j+k]-f[j-k-1]+mod)%mod;
    }
    for(int i=lim-a+b+1;i<=lim*2;i++)ans=(ans+dp[i])%mod;
    printf("%dn",ans);
    return 0;
}

T3-Strange Radiation

你有一个炸弹,速度比人快。炸弹气流从爆炸位置以速度 s 向左右两边飞。 一维坐标。给你 n 个人的坐标 x、走向 dir、速度 v。 当炸弹和人重叠且同向的时候,人的速度变为 v +s,不考虑逆气流的影响。 让你在 [0, 1e6] 的范围内放置炸弹,花最少的时间使得至少有一个走到位置 0,还有一个人走到位置 1e6。求最少时间。

解法

将时间二分,check 的时候对于每个点考虑炸弹可以放置的区间,求并集,最后左右区间如果有交集就是可行解,需要用到前缀和去维护 需要推一个计算每个点是否可行的公式,下面给出三个关于向左走是否可行的式子,请自行求解 QAQ 设人离左边界距离为 dis1,气流赶上人时人走了 dis2,炸弹离左边界距离为 x 人的速度 v,气流速度 s,二分出的时间 t dis2/v+(dis1-dis2)/(v+s)<=t x>=dis1 x=(dis1-dis2)+dis2·x/v 至于向右走是否可行的式子,同理可自行推导,其实是我懒得写(大雾

ac 代码

#include<bits/stdc++.h>
#define ll long long
#define eps (1e-8)
using namespace std;
struct node{int x,v,w;}a[1000010];
int n,s,suml[1000010],sumr[1000010];
double l=0,r=1000010;
bool judge(double t)
{
    memset(suml,0,sizeof(suml)),memset(sumr,0,sizeof(sumr));
    for(int i=1;i<=n;i++)if(a[i].w==1)
    {
        double d=a[i].x;
        if(d<t(1.0a[i].v)+eps){suml[0]++;continue;}
        ll dis=floor((t(1.0(a[i].v+s))-d)(1.0(s-a[i].v))/(1.0s)+1.0a[i].x);
        if(dis>=a[i].x)dis=min(dis,1000000ll),suml[a[i].x]++,suml[dis+1]--;
    }
    else
    {
        double d=1000000-a[i].x;
        if(d<t(1.0a[i].v)+eps){sumr[0]++;continue;}
        ll dis=ceil(1.0a[i].x-(t(1.0(a[i].v+s))-d)(1.0(s-a[i].v))/(1.0s));
        if(dis<=a[i].x)dis=max(dis, 0ll),sumr[dis]++,sumr[a[i].x+1]--;
    }
    for(int i=1;i<=1000000;i++)
        {suml[i]+=suml[i-1],sumr[i]+=sumr[i-1];if(suml[i]&&sumr[i])return 1;}
    return suml[0]&&sumr[0];
}
int main()
{
    scanf("%d%d",&n,&s);
    for(int i=1;i<=n;i++)scanf("%d%d%d",&a[i].x,&a[i].v,&a[i].w);
    while(r-l>eps){double mid=(l+r)/2;if(judge(mid))r=mid;else l=mid;}
    printf("%.6fn",l);
}

T4-Misha, Grisha and Underground

有一棵 n 个节点的树,一共 q 次询问 每次询问给定 3 个点,求两条起点终点在这三个点上且不完全重合的路径的最多公共节点数

解法

lca 板子题,求出三个点的 lca 之后,枚举每一个点作为公共点的可能性,推一下式子,公共节点有两种情况:(公共点为 a,其他两点为 b、c,i=lca(a,b),j=lca(a,c),k=lca(b,c)) 1、min(a->i,a->j) 产生一段贡献 2、如果 i =j,k->i 产生一段贡献 至于贡献的算法,就是深度的差

ac 代码

#include<bits/stdc++.h>
using namespace std;
struct p{int to,next;}a[200010];
struct point{int dep,fa[20];}po[100010];
int n,m,head[100010],x,y,z,l=0,lg[100010];
void add(int i,int j){a[++l].to=j,a[l].next=head[i],head[i]=l;}
void dfs(int u,int f)
{
    po[u].fa[0]=f,po[u].dep=po[f].dep+1;
    for(int i=1;(1<<i)<po[u].dep;i++)po[u].fa[i]=po[po[u].fa[i-1]].fa[i-1];
    for(int i=head[u];i!=-1;i=a[i].next)if(a[i].to!=f)dfs(a[i].to,u);
}
int f(int xx,int yy)
{
    if(po[xx].dep<po[yy].dep)swap(xx,yy);
    while(po[xx].dep!=po[yy].dep)xx=po[xx].fa[lg[po[xx].dep-po[yy].dep]];
    for(int i=lg[po[xx].dep-1];i>=0;i--)if(po[xx].fa[i]!=po[yy].fa[i])xx=po[xx].fa[i],yy=po[yy].fa[i];
    return xx==yy?xx:po[xx].fa[0];
}
int calc()
{
    int i=f(x,y),j=f(x,z),k=f(y,z),ans=0;
    ans=max(ans,po[z].dep-max(po[j].dep,po[k].dep)+(j==k?po[i].dep-po[j].dep:0));
    ans=max(ans,po[y].dep-max(po[i].dep,po[k].dep)+(i==k?po[j].dep-po[i].dep:0));
    ans=max(ans,po[x].dep-max(po[j].dep,po[i].dep)+(j==i?po[k].dep-po[j].dep:0));
    return ans+1;
}
int main()
{
    memset(head,-1,sizeof(head)),scanf("%d%d",&n,&m);
    for(int i=2;i<=n;i++)scanf("%d",&x),add(x,i),add(i,x),lg[i]=log2(i);
    lg[1]=log2(1),po[0].dep=0,dfs(1,0);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),printf("%dn",calc());
}