首页 > 其他分享 >NOIP2024加赛2

NOIP2024加赛2

时间：2024-11-06 16:19:41浏览次数：2  
标签：cnt int ll pos dfs 加赛 NOIP2024 jc

NOIP2024加赛2

题目来源： 2023NOIP A层联测18

\(T1\) HZTG5733. 新的阶乘 \(100pts\)

  • 预处理素数后直接对 \(1 \sim n\) 进行质因数分解因为有太多冗余枚举导致无法通过。

  • 考虑枚举最终形式。具体地，从质因数的角度入手，设当前枚举的质数为 \(p\) ，暴力求出 \(ip\) 中 \(p\) 的指数即可。

  • 时间复杂度为 \(1 \sim n\) 中每个数质因数分解后的各指数之和 \(=O(n \log n)\) ，在 \(1s\) 内仅能处理 \(3 \times 10^{7}\) 以内的数据。

    • 时间复杂度在于暴力求 \(ip\) 中 \(p\) 的指数。
    点击查看代码 
    ll prime[700010],c[700010],len=0;
bool vis[10000010];
void isprime(ll n)
{
    memset(vis,0,sizeof(vis));
    for(ll i=2;i<=n;i++)
    {
        if(vis[i]==0)
        {
            len++;
            prime[len]=i;
        }
        for(ll j=1;j<=len&&i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                break;
            }
        }
    }
}
ll ask(ll n,ll p)
{
    ll ans=0;
    while(n%p==0)
    {
        ans++;
        n/=p;
    }
    return ans;
}
int main()
{
    freopen("factorial.in","r",stdin);
    freopen("factorial.out","w",stdout);
    ll n,cnt,mul,i,j;
    scanf("%lld",&n);
    isprime(n);
    for(i=1;i<=len;i++)
    {
        for(j=1;prime[i]*j<=n;j++)
        {
            c[i]+=(ask(j,prime[i])+1)*(n-prime[i]*j+1);
        }
    }
    printf("f(%lld)=",n);
    for(i=1;i<=len;i++)
    {
        printf("%lld",prime[i]);
        if(c[i]!=1)
        {
            printf("^%lld",c[i]);
        }
        if(i!=len)
        {
            printf("*");
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

  • 官方题解中省去了暴力求指数的一步。

\(T2\) HZTG5734. 博弈树 \(80pts\)

  • 部分分

    • \(80pts\) ：暴力建出博弈的搜索树，因为状态数规模为 \(O(n^{2})\) ，加个记忆化即可，可能需要 \(O(1)\) 的求 \(\operatorname{LCA}\) （？）。
    点击查看代码 
    struct node
{
    int nxt,to;
}e[200010];
int head[100010],dfn[100010],dep[100010],cnt=0,tot=0;
unordered_map<int,bool>f[100010];
void add(int u,int v)
{
    cnt++;
    e[cnt].nxt=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
int sx_min(int x,int y)
{
    return dfn[x]<dfn[y]?x:y;
}
struct ST
{
    int fminn[100010][20];
    void init(int n)
    {
        for(int j=1;j<=log2(n);j++)
        {
            for(int i=1;i+(1<<j)-1<=n;i++)
            {
                fminn[i][j]=sx_min(fminn[i][j-1],fminn[i+(1<<(j-1))][j-1]);
            }
        }
    }
    int query(int l,int r)
    {
        int t=log2(r-l+1);
        return sx_min(fminn[l][t],fminn[r-(1<<t)+1][t]);
    }
}T;
void get_dep(int x,int fa)
{
    tot++;
    dfn[x]=tot;
    dep[x]=dep[fa]+1;
    T.fminn[tot][0]=fa;
    for(int i=head[x];i!=0;i=e[i].nxt)
    {
        if(e[i].to!=fa)
        {
            get_dep(e[i].to,x);
        }
    }
}
int lca(int u,int v)
{
    if(dfn[u]>dfn[v])
    {
        swap(u,v);
    }
    return (dfn[u]==dfn[v])?u:T.query(dfn[u]+1,dfn[v]);
}
int get_dis(int u,int v)
{
    return dep[u]+dep[v]-2*dep[lca(u,v)];
}
bool dfs(int x,int last,int n)
{
    if(f[x].find(last)!=f[x].end())
    {
        return f[x][last];
    }
    for(int i=1;i<=n;i++)
    {
        int d=get_dis(x,i);
        if(d>last&&dfs(i,d,n)==false)
        {
            return f[x][last]=true;
        }
    }
    return f[x][last]=false;
}
int main()
{
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    int n,m,u,v,i;
    cin>>n>>m;
    for(i=1;i<=n-1;i++)
    {
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    get_dep(1,0);
    T.init(n);
    for(i=1;i<=m;i++)
    {
        cin>>u;
        if(dfs(u,0,n)==true)
        {
            cout<<"Alice"<<endl;
        }
        else
        {
            cout<<"Bob"<<endl;
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

  • 正解

    • 若节点 \(x\) 是直径的端点，那么直接判定 Alice 必胜。否则谁先移动到直径的端点谁就输。
    • 考虑删去所有直径的端点（一定是叶子节点），若节点 \(x\) 是删完后的树的直径端点，那么 Alice 也是必胜的。因为 Alice 可以将点移动到删完后的树的另一个直径端点，而 Bob 就只能移到原树的直径端点上，从而得到 Alice 必胜。
    • 考虑模拟删叶子的过程，若删到最后只剩一个点说明在这个点时 Bob 是必胜的，否则 Alice 一定可以通过不断将点移动到下一层的直径端点取得胜利（对于 Bob 的干扰， Alice 可以通过利用直径的最长性进行反制）。
    • 而最后剩下的这个点一定是直径的中点（直径长度为奇数时），预处理即可。
    点击查看代码 
    struct node
{
    int nxt,to;
}e[200010];
int head[200010],dep[200010],fa[200010],cnt=0;
vector<int>d;
void add(int u,int v)
{
    cnt++;
    e[cnt].nxt=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
void dfs(int x,int father)
{
    fa[x]=father;
    dep[x]=dep[father]+1;
    for(int i=head[x];i!=0;i=e[i].nxt)
    {
        if(e[i].to!=father)
        {
            dfs(e[i].to,x);
        }
    }
}
int main()
{
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    int n,m,u,v,rt1=0,rt2=0,i;
    cin>>n>>m;
    for(i=1;i<=n-1;i++)
    {
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    for(i=1;i<=n;i++)
    {
        rt1=(dep[i]>dep[rt1])?i:rt1;
    }
    dfs(rt1,0);
    for(i=1;i<=n;i++)
    {
        rt2=(dep[i]>dep[rt2])?i:rt2;
    }
    while(rt2!=0)
    {
        d.push_back(rt2);
        rt2=fa[rt2];
    }
    for(i=1;i<=m;i++)
    {
        cin>>u;
        if(d.size()%2==0||d[d.size()/2]!=u)
        {
            cout<<"Alice"<<endl;
        }
        else
        {
            cout<<"Bob"<<endl;
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

\(T3\) HZTG5735. 划分 \(9pts\)

  • 部分分

    • 测试点 \(1 \sim 2\) ：爆搜。
    • 测试点 \(9 \sim 12\)
      • 设第一个 \(1\) 出现的位置为 \(pos\) 。那么最大值一定为 \(s_{pos \sim n}\) ，因为 \([pos,n]\) 中任意断开就会导致最大值变小。方案数仅会由前面的 \(0\) 决定，即 \(\sum\limits_{i=k}^{pos}\dbinom{pos-1}{i-1}\) 。
      • 若不存在 \(1\) ，则最大值为 \(0\) ，方案数为 \(\sum\limits_{i=k}^{n}\dbinom{n-1}{i-1}\) 。
    点击查看代码 
    const ll p=998244353;
ll inv[2000010],jc[2000010],jc_inv[2000010],ans=0,cnt=0;
char s[2000010];
ll ask(ll l,ll r)
{
    ll ans=0;
    for(ll i=l;i<=r;i++)
    {
        ans=(ans*2+s[i]-'0');
    }
    return ans;
}
ll work(ll l,ll r)
{
    ll ans=0;
    for(ll i=l;i<=r;i++)
    {
        ans=(ans*2%p+s[i]-'0')%p;
    }
    return ans;
}
void dfs(ll pos,ll n,ll k,ll sum,ll num,ll last)
{
    if(pos==n)
    {
        num++;
        sum+=ask(last+1,n);
        if(num>=k)
        {
            if(sum>ans)
            {
                ans=sum;
                cnt=1;
            }
            else
            {
                if(sum==ans)
                {	
                    cnt++;
                }
            }
        }
    }
    else
    {
        dfs(pos+1,n,k,sum,num,last);
        dfs(pos+1,n,k,sum+ask(last+1,pos),num+1,pos);
    }
}
ll C(ll n,ll m,ll p)
{
    return (n>=m&&n>=0&&m>=0)?(jc[n]*jc_inv[n-m]%p)*jc_inv[m]%p:0;
}
int main()
{
    freopen("divide.in","r",stdin);
    freopen("divide.out","w",stdout);
    ll n,k,pos=0,sum=0,i;
    cin>>n>>k;
    for(i=1;i<=n;i++)
    {
        cin>>s[i];
        pos=(pos==0&&s[i]=='1')?i:pos;
    }
    if(pos>k||pos==0)
    {	
        inv[1]=1;
        jc[0]=jc_inv[0]=jc[1]=jc_inv[1]=1;
        for(i=2;i<=n;i++)
        {
            inv[i]=(p-p/i)*inv[p%i]%p;
            jc[i]=jc[i-1]*i%p;
            jc_inv[i]=jc_inv[i-1]*inv[i]%p;
        }
        if(pos==0)
        {
            for(i=k;i<=n;i++)
            {
                sum=(sum+C(n-1,i-1,p))%p;
            }
            cout<<0<<" "<<sum<<endl;
        }
        else
        {
            for(i=k;i<=pos;i++)
            {
                sum=(sum+C(pos-1,i-1,p))%p;
            }
            cout<<work(pos,n)<<" "<<sum<<endl;
        }
    }
    else
    {
        dfs(1,n,k,0,0,0);
        cout<<ans%p<<" "<<cnt%p<<endl;
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

  • 正解

    • 考虑不保证 \(\forall i \in [1,k],s_{i}=0\) 时怎么做。
    • 最优解的划分方案一定形如选出一段 \(n-k'+1(k' \ge k-1)\) 单独作为一段，剩下的每个数单独作为一段。
    • 因为 \(1\) 的数量是一定的，所以所有的构造方案对应的 \(n-k'+1(k' \ge k-1)\) 这段数的前 \(n-k\) 位一定相同（若长度不够 \(n-k+1\) 则先在前面补 \(0\) 补成长度为 \(n-k+1\) 的段，可以证明这并不影响结果）。
    • 考虑二分哈希找到最大的划分点，然后哈希判断有多少个其他划分点的前 \(n-k\) 位与其相等。
    • 需要特判 \(n=k\) 时方案数为 \(1\) 。
    点击查看代码

\(T4\) HZTG5736. 灯笼 \(0pts\)

总结

  • \(T3\) 没有想 \(\forall i \in [1,k],s_{i}=0\) 的 \(15pts\) 部分分。

标签：cnt,int,ll,pos,dfs,加赛,NOIP2024,jc
From： https://www.cnblogs.com/The-Shadow-Dragon/p/18530496

相关文章

  • CSP2024 前集训：NOIP2024加赛 1
    前言赛时本来rk3，赛后自己加hack卡自己于是成rk4了。因为这场是假做法大战，T1假贪心有\(92pts\)；T2\(O(n^2m)\)能过（是因为数据里\(m\le10\)）；T3相当抽象，赛时我打的爆搜只加了一个剪枝能得\(70pts\)，赛后发现无解的时候会跑满，于是提前判掉无解就过了甚至最优解\(30ms\)......
  • 多校A层冲刺NOIP2024模拟赛18
    多校A层冲刺NOIP2024模拟赛18\(T1\)A.选彩笔（rgb）\(100pts/100pts\)观察到\(0\ler,g,b\le255\)且答案具有单调性，故考虑二分答案。将\(r,g,b\)分别抽象成三维坐标下的\(x,y,z\)。设当前二分出的答案为\(mid\)，由调整法分析可知若存在一个边长为\(mid\)的......
  • [61] (多校联训) A层冲刺NOIP2024模拟赛18
    无论从什么意义上都能称得上挂75分的一场A.选彩笔好题答案显然可以二分突然发现我好像专长二分答案钦定最大差值\(dx\)，将所有物品以\((r,g,b)\)看成三维空间坐标内的点，原问题可以转化成问空间里一个边长为\(dx\)的立方体内是否有至少\(k\)个点考虑到值域不大，可......
  • [赛记] 多校A层冲刺NOIP2024模拟赛16 && 17
    四舍五入100pts对于一个数$x$，可以发现它的答案可以分成两部分，一部分在$[2x+1,n]$范围内，一部分在小于它的数的范围内，前者$\Theta(1)$算，对于后者，我们发现满足这个要求的数$y$一定有$x\mody<w(x,y)$（$w(x,y)$定义为如果$x\mody=0$，则$w(a,......
  • NOIP2024模拟赛21
    省流：没过T1，玩了1h俄罗斯，不好评价。还好T3一个小时写完了平方暴力，还没菜到离谱，感觉这才是一个正常的分数。但是好像正解要不到1h？T2的dp优化是我弱项，做不出正常，spdarkle是真逆天。怎么一眼的怎么一眼的怎么一眼的怎么一眼的怎么一眼的怎么一眼的怎么一眼的。发现后面又......
  • 多校A层冲刺NOIP2024模拟赛17
    多校A层冲刺NOIP2024模拟赛17T1、网格首先看上去很麻烦，但是最终所有的式子都可以写成几个数的积相加的形式，那么我们只要处理数（拼接起来）、数的积以及积的和。那么我们维护三个变量，第一个是$x$，表示最后一个积前面所有的数和，第二个是$y$，表示目前的积，第三个是z，表......
  • 多校 A 层冲刺 NOIP2024 模拟赛 17
    多校A层冲刺NOIP2024模拟赛17T1网格签到题注意到\(+\)与\(\times\)由于优先级其实是分开的，所以可以考虑每到达一个\(+\)计算一次贡献（乘上一个组合数），然后将前置贡献重新赋值为方案数，DP只需考虑连续\(\times\)段即可。时间复杂度\(O(nm)\)。T2矩形根号分治发现不......
  • 【考试题解】多校A层冲刺NOIP2024模拟赛17
    A.网格(grid)题目内容给你一个\(n\timesm\)的字符网格\(s\)，\(s_{i,j}\in[1,9]\cup\{+,*\}\)，从\((1,1)\)开始，仅向下或向右走并最终到达\((n,m)\)的路径被称为合法路径，求所有合法路径对应的表达式的运算结果之和，答案对\(998244353\)取模。部分分44pts爆搜，枚举路径，......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛17
    Rank一般A.网络签不上的签到题。首先考虑枚举路径的做法，如果先枚举再计算的话复杂度会是\(\mathcal{O(\binom{n+m-2}{n-1}(n+m))}\)的，稍微优化一点的过程中可以去掉后面的\((n+m)\)。考虑此时我们要记什么，首先遇到加号其前面的值\(z\)就确定了，若上个符号为乘号那么......
  • NOIP2024 模拟赛 #12
    学长出的模拟赛，风格挺好。赛时8:00T1会了一个\(O(n^2\logn)\)的做法，先写一下，看看能不能过样例。8:20过了小样例，大样例跑得慢但是是对的。8:40发现一个好的做法，可以枚举\(c_i\)最小的那一天选了哪个，再枚举\(k\)天，这样纯枚举复杂度是\(O(k)\)的。但是有些细节不太......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99