首页 > 其他分享 >【MX-S7】梦熊 NOIP 2024 模拟赛 3 & SMOI Round 2（同步赛）

【MX-S7】梦熊 NOIP 2024 模拟赛 3 & SMOI Round 2（同步赛）

时间：2024-11-24 20:46:05浏览次数：11  
标签：cnt NOIP int top S7 Round son 200010 ll

【MX-S7】梦熊 NOIP 2024 模拟赛 3 & SMOI Round 2（同步赛）

\(T1\) luogu P11323 【MX-S7-T1】「SMOI-R2」Happy Card \(20pts\)

  • 发现可以把「炸弹」也看做「三带一」。

  • 先使用「三带一」带走原用于出「单牌」的牌，若「三带一」还有剩余则尝试带走原用于出「对子」的牌，否则直接出「单牌」和「对子」。

    点击查看代码 
    ll a[300010],r[4];
int main()
{
// #define Isaac
#ifdef Isaac
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    ll t,n,ans,cnt,i,j;
    scanf("%lld",&t);
    for(j=1;j<=t;j++)
    {
        ans=cnt=0;
        memset(r,0,sizeof(r));
        scanf("%lld",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            r[a[i]%3]++;
            cnt+=a[i]/3;
        }
        if(cnt>=r[1])
        {
            cnt-=r[1];
            ans+=r[1];
            if(cnt>=2*r[2])
            {
                cnt-=2*r[2];
                ans+=2*r[2];
                ans+=cnt/4*3+((cnt%4==3)?3:(2*(cnt%4!=0)));
            }
            else
            {
                r[2]-=cnt/2;
                ans+=cnt;
                ans+=r[2];
            }
        }
        else
        {
            r[1]-=cnt;
            ans+=cnt+r[1]+r[2];
        }
        printf("%lld\n",ans);
    }
    return 0;
}

\(T2\) luogu P11324 【MX-S7-T2】「SMOI-R2」Speaker \(40pts\)

  • 部分分

    • \(40pts\)
      • 设 \(h_{i}\) 表示从 \(i\) 出发不经过 \(x \to y\) 路径上的其他点所能到达的点的最大贡献 \(c-2dis\) 。则等价于询问 \(c_{x}+c_{y}-dis_{x,y}+\max\limits_{z \in (x \to y)} \{ h_{z} \}\) 。
    点击查看代码 
    // #define Isaac
namespace IO{
    #ifdef Isaac
    FILE*Fin(fopen("in.in","r")),*Fout(fopen("out.out","w"));
    #else
    FILE*Fin(stdin),*Fout(stdout);
    #endif
    class qistream{static const size_t SIZE=1<<16,BLOCK=64;FILE*fp;char buf[SIZE];int p;public:qistream(FILE*_fp=stdin):fp(_fp),p(0){fread(buf+p,1,SIZE-p,fp);}void flush(){memmove(buf,buf+p,SIZE-p),fread(buf+SIZE-p,1,p,fp),p=0;}qistream&operator>>(char&x){x=getch();while(isspace(x))x=getch();return*this;}template<class T>qistream&operator>>(T&x){x=0;p+BLOCK>=SIZE?flush():void();bool flag=false;for(;!isdigit(buf[p]);++p)flag=buf[p]=='-';for(;isdigit(buf[p]);++p)x=x*10+buf[p]-'0';x=flag?-x:x;return*this;}char getch(){p+BLOCK>=SIZE?flush():void();return buf[p++];}qistream&operator>>(char*str){char ch=getch();while(ch<=' ')ch=getch();int i=0;for(;ch>' ';++i,ch=getch())str[i]=ch;str[i]='\0';return*this;}}qcin(Fin);
    class qostream{static const size_t SIZE=1<<16,BLOCK=64;FILE*fp;char buf[SIZE];int p;public:qostream(FILE*_fp=stdout):fp(_fp),p(0){}~qostream(){fwrite(buf,1,p,fp);}void flush(){fwrite(buf,1,p,fp),p=0;}template<class T>qostream&operator<<(T x){int len=0;p+BLOCK>=SIZE?flush():void();x<0?(x=-x,buf[p++]='-'):0;do buf[p+len]=x%10+'0',x/=10,++len;while(x);for(int i=0,j=len-1;i<j;++i,--j)std::swap(buf[p+i],buf[p+j]);p+=len;return*this;}qostream&operator<<(char x){putch(x);return*this;}void putch(char ch){p+BLOCK>=SIZE?flush():void();buf[p++]=ch;}qostream&operator<<(char*str){for(int i=0;str[i];++i)putch(str[i]);return*this;}qostream&operator<<(const char*s){for(int i=0;s[i];++i)putch(s[i]);return*this;}}qcout(Fout);
}
#define cin IO::qcin
#define cout IO::qcout
struct node
{
    int nxt,to,w;
}e[400010];
int head[400010],fa[400010],siz[400010],dep[400010],son[400010],top[400010],cnt=0;
ll dis[400010],c[400010],maxx;
bool vis[400010];
queue<int>q;
void add(int u,int v,int w)
{
    cnt++;
    e[cnt].nxt=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    head[u]=cnt;
}
void dfs1(int x,int father)
{
    siz[x]=1;
    fa[x]=father;
    dep[x]=dep[father]+1;
    for(int i=head[x];i!=0;i=e[i].nxt)
    {
        if(e[i].to!=father)
        {
            dis[e[i].to]=dis[x]+e[i].w;
            dfs1(e[i].to,x);
            siz[x]+=siz[e[i].to];
            son[x]=(siz[e[i].to]>siz[son[x]])?e[i].to:son[x];
        }
    }
}
void dfs2(int x,int id)
{
    top[x]=id;
    if(son[x]!=0)
    {
        dfs2(son[x],id);
        for(int i=head[x];i!=0;i=e[i].nxt)
        {
            if(e[i].to!=fa[x]&&e[i].to!=son[x])
            {
                dfs2(e[i].to,e[i].to);
            }
        }
    }
}
int lca(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]>dep[top[v]])
        {
            u=fa[top[u]];
        }
        else
        {
            v=fa[top[v]];
        }
    }
    return dep[u]<dep[v]?u:v;
}
void dfs(int x,int fa,ll dis)
{
    maxx=max(maxx,-2*dis+c[x]);
    for(int i=head[x];i!=0;i=e[i].nxt)
    {
        if(e[i].to!=fa&&vis[e[i].to]==0)
        {
            dfs(e[i].to,x,dis+e[i].w);
        }
    }
}
ll query(int u,int v,int n)
{
    int rt=lca(u,v);
    ll ans=c[u]+c[v]-(dis[u]+dis[v]-2*dis[rt]);
    for(int i=1;i<=n;i++)
    {
        vis[i]=0;
    }
    maxx=0;
    vis[rt]=1;
    q.push(rt);
    for(;u!=rt;u=fa[u])
    {
        vis[u]=1;
        q.push(u);
    }
    for(;v!=rt;v=fa[v])
    {
        vis[v]=1;
        q.push(v);
    }
    while(q.empty()==0)
    {
        dfs(q.front(),0,0);
        q.pop();
    }
    return ans+maxx;
}
int main()
{
    int n,m,u,v,w,i;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        cin>>c[i];
    }
    for(i=1;i<=n-1;i++)
    {
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    dfs1(1,0);
    dfs2(1,1);
    for(i=1;i<=m;i++)
    {
        cin>>u>>v;
        cout<<query(u,v,n)<<endl;
    }
    return 0;
}

  • 正解

    • 发现“不经过 \(x \to y\) 路径上的其他点”这个限制没什么用，去掉后并不会对答案产生影响，推导过程同 luogu P2491 [SDOI2011] 消防 | luogu P1099 [NOIP2007 提高组] 树网的核 。
    • 现在需要快捷地求出 \(h_{i}\) 表示从 \(i\) 出发所能到达的点的最大贡献 \(c-2dis\) ，赛时以为会和 luogu P6419 [COCI2014-2015#1] Kamp 一样换根分讨最长链、次长链的多种更新情况遂没写，但实际上因为当固定一些东西后，只有距离这一个变量（其实是距离的差值）所以还算比较好写。
    • 设 \(f_{x}\) 表示从 \(x\) 出发到达以 \(x\) 为根的子树内的节点的最大贡献，状态转移方程为 \(f_{x}=\max(c_{x},\max\limits_{y \in Son(x)}\{ f_{y}-2w_{x \to y} \})\) ，边界为 \(g_{1}=f_{1}\) 。
    • 然后进行换根，设 \(g_{x}\) 表示从 \(x\) 出发所能到达的点的最大贡献。状态转移方程为 \(g_{y}=\max(f_{y},g_{x}-2w_{x \to y}),y \in Son(x)\) 。
    • 树剖加 \(ST\) 表或倍增暴力跳即可。
    点击查看代码 
    struct node
{
    ll nxt,to,w;
}e[400010];
ll head[200010],c[200010],dis[200010],dep[200010],siz[200010],fa[200010],top[200010],son[200010],pos[200010],dfn[200010],f[200010],g[200010],cnt=0,tot=0;
void add(ll u,ll v,ll w)
{
    cnt++;
    e[cnt].nxt=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    head[u]=cnt;
}
void dfs1(ll x,ll father)
{
    f[x]=c[x];
    siz[x]=1;
    fa[x]=father;
    dep[x]=dep[father]+1;	
    for(ll i=head[x];i!=0;i=e[i].nxt)
    {
        if(e[i].to!=father)
        {
            dis[e[i].to]=dis[x]+e[i].w;
            dfs1(e[i].to,x);
            f[x]=max(f[x],f[e[i].to]-2*e[i].w);
            siz[x]+=siz[e[i].to];
            son[x]=(siz[e[i].to]>siz[son[x]])?e[i].to:son[x];
        }
    }
}
void reroot(ll x)
{
    for(ll i=head[x];i!=0;i=e[i].nxt)
    {
        if(e[i].to!=fa[x])
        {
            g[e[i].to]=max(f[e[i].to],g[x]-2*e[i].w);
            reroot(e[i].to);
        }
    }
}
void dfs2(ll x,ll id)
{
    top[x]=id;
    tot++;
    dfn[x]=tot;
    pos[tot]=x;
    if(son[x]!=0)
    {
        dfs2(son[x],id);
        for(ll i=head[x];i!=0;i=e[i].nxt)
        {
            if(e[i].to!=fa[x]&&e[i].to!=son[x])
            {
                dfs2(e[i].to,e[i].to);
            }
        }
    }
}
struct ST
{
    ll fmaxx[200010][25];
    void init(ll n)
    {
        memset(fmaxx,-0x3f,sizeof(fmaxx));
        for(ll i=1;i<=n;i++)
        {
            fmaxx[i][0]=g[pos[i]];
        }
        for(ll j=1;j<=log2(n);j++)
        {
            for(ll i=1;i+(1<<j)-1<=n;i++)
            {
                fmaxx[i][j]=max(fmaxx[i][j-1],fmaxx[i+(1<<(j-1))][j-1]);
            }
        }
    }
    ll query(ll l,ll r)
    {
        ll t=log2(r-l+1);
        return max(fmaxx[l][t],fmaxx[r-(1<<t)+1][t]);
    }
}T;
ll query(ll u,ll v)
{
    ll ans=c[u]+c[v]-dis[u]-dis[v],maxx=-0x3f3f3f3f;
    while(top[u]!=top[v])
    {
        if(dep[top[u]]>dep[top[v]])
        {
            maxx=max(maxx,T.query(dfn[top[u]],dfn[u]));
            u=fa[top[u]];
        }
        else
        {
            maxx=max(maxx,T.query(dfn[top[v]],dfn[v]));
            v=fa[top[v]];
        }
    }
    if(dep[u]<dep[v])
    {
        maxx=max(maxx,T.query(dfn[u],dfn[v]));
        return ans+2*dis[u]+maxx;
    }
    else
    {
        maxx=max(maxx,T.query(dfn[v],dfn[u]));
        return ans+2*dis[v]+maxx;
    }
}
int main()
{
// #define Isaac
#ifdef Isaac
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    ll n,m,u,v,w,i;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        cin>>c[i];
    }
    for(i=1;i<=n-1;i++)
    {
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    dfs1(1,0);
    g[1]=f[1];
    reroot(1);
    dfs2(1,1);
    T.init(n);
    for(i=1;i<=m;i++)
    {
        cin>>u>>v;
        cout<<query(u,v)<<endl;
    }
    return 0;
}

\(T3\) luogu P11325 【MX-S7-T3】「SMOI-R2」Monotonic Queue \(0pts\)

  • 正在理解题意。

\(T4\) luogu P11326 【MX-S7-T4】「SMOI-R2」XA-Game \(0pts\)

总结

  • 整场都在瞪 \(T1\) ，\(T3\) 基本没有进行转化题意。
  • 写 \(T2\) 的过程中死了两次机，以为 \(O(nq)\) 可以直接冲 \(60pts\) ，然后发现自己写的常数太大了。

标签：cnt,NOIP,int,top,S7,Round,son,200010,ll
From： https://www.cnblogs.com/The-Shadow-Dragon/p/18566323

相关文章

  • CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)（A - D) (C2 还在补)
    CodeTONRound9(Div.1+Div.2,Rated,Prizes!)4/11(ABC1D)A.ShohagLovesMod题目大意Shohag有一个整数nn。请帮助他找到一个递增的整数序列1≤a1<a2<…<an≤1001≤a1<a2<…<an≤100，使得对于所有的1≤i<j≤n1≤i<j≤n，都满足aimodi≠ajmodjaimodi≠ajmodj∗∗......
  • [CSS] Houdini CSS to animate linear gradient background
    https://developer.mozilla.org/en-US/docs/Web/API/Houdini_APIs<!doctypehtml><htmllang="en"><head><metacharset="utf-8"/><title>Houdini</title><linkrel="stylesheet"......
  • 『模拟赛』【MX-S7】梦熊NOIP2024模拟赛3
    Rank因为提前知道打不完就没打暴力A.【MX-S7-T1】「SMOI-R2」HappyCardlink。签。比较好想到炸弹等价于三带一，因此本质只有三种出牌类型。并且三带一一次能出掉四张牌，显然优先打三带一是很优的。所以我们处理出三带的个数以及剩下零牌中对子的个数，然后分讨。如果三带......
  • P1125 [NOIP2008 提高组] 笨小猴 C语言
    先说思路：创建了一个函数来判断是否是质数，然后将字符串输入，因为题干中说长度小于100,再加上\0，所以要把长度定义为101，之后对每一个字母用双层循环进行遍历，外层用count来计数，若超过maxn则赋新值，minn同样，之后再对maxn-minn得到的数进行判断即可，之后根据题意用if-else语句即可完成......
  • P11323 【MX-S7-T1】「SMOI-R2」Happy Card
    P11323【MX-S7-T1】「SMOI-R2」HappyCard-洛谷|计算机科学教育新生态(luogu.com.cn)这题不复杂，本质就是一个贪心，可以发现，三带一和炸弹可以合并为三个相同的带任意一张牌。那我们尽量都选三张相同的，这样每种牌最后只剩\(0,1,2\)张牌，我们先用三张带走尽量带走只剩1张的......
  • P11324 【MX-S7-T2】「SMOI-R2」Speaker
    P11324【MX-S7-T2】「SMOI-R2」Speaker-洛谷|计算机科学教育新生态(luogu.com.cn)就是，复杂的分类讨论。最核心的就是树上倍增求链的最大值。不写多了。#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<cmath>usingnamespace......
  • 【CodeForces训练记录】CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
    训练情况赛后反思发现自己越来越能猜结论了，连续两题结论猜对了，一把rating上青了。A题构造一个数组使得模数互不相同，考虑构造一个模数为\([0,1,2,3,4,5]\)的数列，所以一个全是奇数的数列\([1,3,5,7,9]\)符合条件，直接输出\(1\simn\)的奇数即可。#include<bits/stdc++.......
  • NOIP2024 前集训：多校A层冲刺NOIP2024模拟赛25
    前言music《浮游》天已经微亮我睁开双眼长夜漫漫总有散来到故事终点如果有人问此生不悔碰触着你的地方刻下纠缠印痕说再见不是离别何必追赶着句点思念在一瞬间倾倒地平线荒野在歌唱大地在缄默光粒穿透海尘埃中花开游蜉望着天誓言追光影灵魂在......
  • [赛记] NOIP2024加赛7
    镜的绮想(mirror)100pts考虑$\Theta(nm)$的做法，发现我们可以对于每一对实点和虚点求它们的“镜面”，然后得到$\Theta(nm)$个“镜面”，发现这些直线只可能是形如$y=0.5x,x\inZ$的直线，所以我们直接乘$2$，然后开个桶统计一下即可；时间复杂度：$\Theta(nm)$；点击......
  • P1055 [NOIP2008 普及组] ISBN 号码
    题目描述每一本正式出版的图书都有一个ISBN号码与之对应，ISBN码包括 99 位数字、11 位识别码和 33 位分隔符，其规定格式如 x-xxx-xxxxx-x，其中符号 - 就是分隔符（键盘上的减号），最后一位是识别码，例如 0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99