首页 > 其他分享 >多校A层冲刺NOIP2024模拟赛19

多校A层冲刺NOIP2024模拟赛19

时间：2024-11-07 17:42:19浏览次数：1  
标签：q1 q2 19 ll 多校 int ans NOIP2024 size

多校A层冲刺NOIP2024模拟赛19

\(T1\) A. 图书管理 (book) \(90pts/90pts\)

  • 部分分

    点击查看代码 
    int p[10010];
int main()
{
    freopen("book.in","r",stdin);
    freopen("book.out","w",stdout);
    int n,i,l,r;
    ll ans=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&p[i]);
    }
    for(l=1;l<=n;l++)
    {
        priority_queue<int,vector<int>,greater<int> >q1;
        priority_queue<int,vector<int>,less<int> >q2;
        for(r=l;r<=n;r+=2)
        {
            if(q2.empty()==0&&p[r]>q2.top())
            {
                q1.push(p[r]);
            }
            else
            {
                q2.push(p[r]);
            }
            if(abs((int)q1.size()-(int)q2.size())>=2)
            {
                if(q1.size()>q2.size())
                {
                    while(q1.size()-q2.size()>=2)
                    {
                        q2.push(q1.top());
                        q1.pop();
                    }
                }
                else
                {
                    while(q2.size()-q1.size()>=2)
                    {
                        q1.push(q2.top());
                        q2.pop();
                    }
                }
            }
            ans+=1ll*l*r*(q1.size()>q2.size()?q1.top():q2.top());
            if(r+2<=n)
            {
                if(q2.empty()==0&&p[r+1]>q2.top())
                {
                    q1.push(p[r+1]);
                }
                else
                {
                    q2.push(p[r+1]);
                }
                if(abs((int)q1.size()-(int)q2.size())>=2)
                {
                    if(q1.size()>q2.size())
                    {
                        while(q1.size()-q2.size()>=2)
                        {
                            q2.push(q1.top());
                            q1.pop();
                        }
                    }
                    else
                    {
                        while(q2.size()-q1.size()>=2)
                        {
                            q1.push(q2.top());
                            q2.pop();
                        }
                    }
                }
            }
        }
    }
    printf("%lld\n",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

  • 正解

    • 考虑枚举中位数 \(p_{i}\) ，计算区间个数。
    • 将 \([l,r]\) 内 \(>p_{i}\) 的数看做 \(1\) ， \(<p_{i}\) 的数看做 \(-1\) ，中位数的约束条件等价于 \([l,r]\) 内数的和等于 \(0\) ，开个桶一并维护左右端点即可。
    点击查看代码 
    ll p[10010],suml[20010],sumr[20010];
int main()
{
    freopen("book.in","r",stdin);
    freopen("book.out","w",stdout);
    ll n,num,ans=0,i,j;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>p[i];
    }
    for(i=1;i<=n;i++)
    {
        memset(suml,0,sizeof(suml));
        memset(sumr,0,sizeof(sumr));
        num=0;
        suml[n]=sumr[n]=i;
        for(j=i-1;j>=1;j--)
        {
            num+=(p[j]>p[i])?1:-1;
            suml[num+n]+=j;
        }
        num=0;
        for(j=i+1;j<=n;j++)
        {
            num+=(p[j]>p[i])?-1:1;
            sumr[num+n]+=j;
        }
        for(j=-n;j<=n;j++)
        {
            ans+=suml[j+n]*sumr[j+n]*p[i];
        }
    }
    cout<<ans<<endl;
    fclose(stdin);
    fclose(stdout);
    return 0;
}

\(T2\) B. 两棵树 (tree) \(30pts/30pts\)

  • 部分分

    • \(30pts\) ：爆搜出每种情况挨个计算。
    点击查看代码 
    const ll p=998244353;
ll ans=0;
ll qpow(ll a,ll b,ll p)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
        {
            ans=ans*a%p;
        }
        b>>=1;
        a=a*a%p;
    }
    return ans;
}
struct Graph
{
    struct node
    {
        ll nxt,to;
    }e[400010];
    ll head[200010],vis[200010],check[200010],cnt=0,tot=0;
    void add(ll u,ll v)
    {
        cnt++;
        e[cnt].nxt=head[u];
        e[cnt].to=v;
        head[u]=cnt;
    }
    void dfs(ll x)
    {
        vis[x]=tot;
        for(ll i=head[x];i!=0;i=e[i].nxt)
        {
            if(vis[e[i].to]!=tot&&check[e[i].to]==0)
            {
                dfs(e[i].to);
            }
        }
    }
    ll ask(ll n)
    {
        tot++;
        ll ans=0;
        for(ll i=1;i<=n;i++)
        {
            if(vis[i]!=tot&&check[i]==0)
            {
                dfs(i);
                ans++;
            }
        }
        return ans;
    }
}T,U;
void dfs(ll pos,ll n)
{
    if(pos==n+1)
    {
        ans=(ans+T.ask(n)*U.ask(n))%p;
    }
    else
    {
        T.check[pos]=1;
        U.check[pos]=0;
        dfs(pos+1,n);
        T.check[pos]=0;
        U.check[pos]=1;
        dfs(pos+1,n);
    }
}
int main()
{
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    ll n,u,v,i;
    cin>>n;
    for(i=1;i<=n-1;i++)
    {
        cin>>u>>v;
        T.add(u,v);
        T.add(v,u);
    }
    for(i=1;i<=n-1;i++)
    {
        cin>>u>>v;
        U.add(u,v);
        U.add(v,u);
    }
    dfs(1,n);
    cout<<ans*qpow(qpow(2,n,p),p-2,p)%p<<endl;
    fclose(stdin);
    fclose(stdout);
    return 0;
}

  • 正解

    • 对于一个森林，连通块数（树数）等于点数 \(V\) 减边数 \(E\) 。此时等价于求 \((V_{T}-E_{T}) \times (V_{U}-E_{U})=V_{T}V_{U}-E_{T}V_{U}-V_{T}E_{U}+E_{T}E_{U}\) 的期望值，考虑分别统计这几项的贡献。
    • \(V_{T}V_{U}\)
      • 暴力推式子，有 \(\begin{aligned} &E(V_{T}V_{U}) \\ &=\frac{1}{2^{n}} \times \sum\limits_{i=0}^{n}\dbinom{n}{i}(n-i)i \\ &=\frac{1}{2^{n}} \times \sum\limits_{i=1}^{n}\frac{n!}{(i-1)!(n-i-1)!} \\ &=\frac{1}{2^{n}} \times \sum\limits_{i=0}^{n-2}\dbinom{n-2}{i}(n-1)n \\ &=\frac{n(n-1)}{4} \end{aligned}\) 。
      • 考虑组合意义，对于 \(x \in T,y \in U\) ，当 \(x \ne y\) 时均被保留的概率为 \(\frac{1}{4}\) ，否则均被保留的概率为 \(0\) ，总期望为 \(\frac{n(n-1)}{2}\) 。
    • \(E_{T}V_{U}\)
      • 考虑组合意义，对于 \((x,y) \in T,u \in U\) ，当 \(x,y,u\) 互不相同时均被保留的概率为 \(\frac{1}{8}\) ，否则均被保留的概率为 \(0\) ，总期望为 \(\frac{(n-1)(n-2)}{8}\) 。
    • \(V_{T}E_{U}\)
      • 同 \(E_{T}V_{U}\) ，总期望为 \(\frac{(n-1)(n-2)}{8}\) 。
    • \(E_{T}E_{U}\)
      • 考虑组合意义，对于 \((x,y) \in T,(u,v) \in U\) ，当 \(x,y,u,v\) 互不相同时均被保留的概率为 \(\frac{1}{16}\) ，否则均被保留的概率为 \(0\) 。
      • 枚举 \((x,y) \in T\) ，那么 \((u,v) \in U\) 满足 \(x,y,u,v\) 互不相同的数量等于 \(n-1-du_{U,x}-du_{U,y}+[(x,y) \in U]\) 。
      • 总期望为 \(\sum\limits_{(x,y) \in T}\frac{n-1-du_{U,x}-du_{U,y}+[(x,y) \in U]}{16}\) 。
    • 最终，有 \(\frac{n-1}{2}+\sum\limits_{(x,y) \in T}\frac{n-1-du_{U,x}-du_{U,y}+[(x,y) \in U]}{16}\) 即为所求。
    点击查看代码 
    const ll p=998244353;
map<pair<ll,ll>,ll>e;
ll du[200010],u[400010],v[400010];
ll qpow(ll a,ll b,ll p)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
        {
            ans=ans*a%p;
        }
        b>>=1;
        a=a*a%p;
    }
    return ans;
}
int main()
{
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    ll n,ans,inv=qpow(16,p-2,p),i;
    cin>>n;
    ans=(n-1)*qpow(2,p-2,p)%p;
    for(i=1;i<=n-1;i++)
    {
        cin>>u[i]>>v[i];
        if(u[i]>v[i])
        {
            swap(u[i],v[i]);
        }
    }
    for(i=1;i<=n-1;i++)
    {
        cin>>u[i+n]>>v[i+n];
        du[u[i+n]]++;
        du[v[i+n]]++;
        if(u[i+n]>v[i+n])
        {
            swap(u[i+n],v[i+n]);
        }
        e[make_pair(u[i+n],v[i+n])]=1;
    }
    for(i=1;i<=n-1;i++)
    {
        ans=(ans+(n-1-du[u[i]]-du[v[i]]+(e.find(make_pair(u[i],v[i]))!=e.end()))*inv%p)%p;
    }
    cout<<ans<<endl;
    fclose(stdin);
    fclose(stdout);
    return 0;
}

\(T3\) C. 函数（fun） \(60pts/60pts\)

  • 部分分

    • \(30 \%\) ：模拟。

      点击查看代码 
      ll x[1000010];
int main()
{
    freopen("fun.in","r",stdin);
    freopen("fun.out","w",stdout);
    ll n,q,a,b,ans,i,j;
    scanf("%lld%lld",&n,&q);
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&x[i]);
    }
    for(j=1;j<=q;j++)
    {
        scanf("%lld%lld",&a,&b);
        ans=-1;
        for(i=1;i<=n-1;i++)
        {
            if(((x[i]^a)-b)*((x[i+1]^a)-b)<=0)
            {
                ans=i;
                break;
            }
        }
        cout<<ans<<endl;
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

  • 正解

    • 考虑手动建出 \(f(x)\) 的函数图象，设左右端点分别为 \(l,r\) ，使用 \(01Trie\) 可以轻松维护。
    • 若 \(f(l)f(r)>0\) 则一定无解，否则一定存在 \(f(l)f(mid) \le 0 \lor f(mid)f(r) \le 0\) ，其中 \(mid=\frac{l+r}{2}\) 。二分处理即可。
      • 正确性由二分法求函数零点可知。
    • 把二分改成递归在 accoders NOI 上大数据平均快了 \(300ms\) 左右，但在学校 \(OJ\) 上变慢了，不是很理解为啥。
    点击查看代码 
    int x[1000010];
struct Trie
{
    int son[32000010][2],ed[32000010],rt_sum=0;
    void insert(int s,int id)
    {
        int x=0;
        for(int i=30;i>=0;i--)
        {
            if(son[x][(s>>i)&1]==0)
            {
                rt_sum++;
                son[x][(s>>i)&1]=rt_sum;
            }
            x=son[x][(s>>i)&1];
        }
        ed[x]=id;
    }
    int query_min(int s)
    {
        int x=0;
        for(int i=30;i>=0;i--)
        {
            if(son[x][(s>>i)&1]!=0)
            {
                x=son[x][(s>>i)&1];
            }
            else
            {
                x=son[x][((s>>i)&1)^1];
            }
        }
        return ed[x];
    }
    int query_max(int s)
    {
        int x=0;
        for(int i=30;i>=0;i--)
        {
            if(son[x][((s>>i)&1)^1]!=0)
            {
                x=son[x][((s>>i)&1)^1];
            }
            else
            {
                x=son[x][(s>>i)&1];
            }
        }
        return ed[x];
    }
}T;
int f(int x,int a,int b)
{
    return (x^a)-b;
}
int main()
{
    freopen("fun.in","r",stdin);
    freopen("fun.out","w",stdout);
    int n,q,a,b,l,r,ans,mid,i;
    scanf("%d%d",&n,&q);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x[i]);
        T.insert(x[i],i);
    }
    for(i=1;i<=q;i++)
    {
        scanf("%d%d",&a,&b);
        l=T.query_min(a);
        r=T.query_max(a);
        if(l>r)
        {
            swap(l,r);
        }
        ans=-1;
        if(1ll*f(x[l],a,b)*f(x[r],a,b)<=0)
        {
            while(r-l>1)
            {
                mid=(l+r)/2;
                if(1ll*f(x[l],a,b)*f(x[mid],a,b)<=0)
                {
                    r=mid;
                }
                else
                {
                    l=mid;
                }
            }
            ans=l;
        }
        printf("%d\n",ans);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

\(T4\) D. 编辑（edit） \(60pts/60pts\)

  • 弱化版： luogu P5479 [BJOI2015] 隐身术

  • 部分分

    • \(30pts\) ：枚举左右端点，然后 \(O(|S||T|)\) 计算编辑距离，同 luogu P2758 编辑距离 ，时间复杂度为 \(O(k|S||T|^{2})\) 。
    • \(60pts\) ：考虑固定一个端点，然后让另一个端点单调，时间复杂度为 \(O(|S||T|^{2})\) 。
    点击查看代码 
    ll ans[50],f[2][50010];
char s[50010],t[50010];
int main()
{
    freopen("edit.in","r",stdin);
    freopen("edit.out","w",stdout);
    ll k,lens,lent,l,r,i;
    cin>>k>>(s+1)>>(t+1);
    lens=strlen(s+1);
    lent=strlen(t+1);
    for(l=1;l<=lent;l++)
    {
        for(i=0;i<=lens;i++)
        {
            f[(l-1)&1][i]=i;
        }
        for(r=l;r<=lent;r++)
        {
            f[r&1][0]=r-l+1;
            for(i=1;i<=lens;i++)
            {
                f[r&1][i]=min(f[(r-1)&1][i-1]+(s[i]!=t[r]),min(f[r&1][i-1]+1,f[(r-1)&1][i]+1));
            }
            if(f[r&1][lens]<=k)
            {
                ans[f[r&1][lens]]++;
            }
        }
    }
    for(i=0;i<=k;i++)
    {
        cout<<ans[i]<<endl;
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

  • 正解

    枚举每个后缀，\(f_{i,j}\) 表示最大的 \(x\)，使得 \(S[1:x]\) 和 \(T[1:x+j]\) 可以在 \(i\) 次编辑内得到，显然若 \(x\) 可以，所有\(x_0 \leq x\)， \(S[1:x_0]\) 和 \(T[1:x_0+j]\) 都可以在 \(i\) 次编辑内得到。

    考虑如何转移，先考虑做完第 \(j\) 次编辑操作后往外延申，可以延申的即为 \(S\) 的一个后缀和 \(T\) 的一个后缀的最长公共前缀，即\(f_{i,j} = f_{i,j} + \text{LCP}(S[f_{i,j + 1}:|S|],T [f_{i,j} + j + 1 . .: |T|])\)，随后我们可以通过对\(f_{i+1,j-1},f_{i+1,j},f_{i+1,j+1}\) 三项进行转移，即考虑下一次的编辑的具体操作是删除添加还是修改。

    每次要算的两个后缀的前缀下标不会差超过 \(k\)，因此一共至多求 \(O(nk)\) 次 LCP，可以利用二分+ hash 的方式解决。

    记录每个后缀中 \(f_{i,j}=|S|\) 的那些状态，即可计算出最终答案，时间复杂度为 \(O(nk^2+nk \log n)\)。

总结

  • \(T1\) 直接对着 \(2s\) 的时限冲了个 \(O(n^{2} \log n)\) 的做法，大样例在本地跑了 \(1.4s \sim 1.6s\) ，遂直接交了。
  • \(T2\) 的 \(Trick\) 好像在之前见过，但想不起来是哪道题了。
  • \(T4\) 想了一个小时的怎么求编辑距离，属于去年初赛白考了。

后记

  • \(T1\)

    • 下发的 \(PDF,markdown\) 题面都给了 \(2s\) 的时限，且在一段时间内题目界面也给了 \(2s\) 的时限，但在比赛结束时发现改成了 \(1s\) 。
    • 第一次下发的大样例假了，暴力都跑不过去。

  • \(T2\) 临结束时在学校 \(OJ\) 补充了额外的大样例。

  • \(T3\) 中途更换了大样例，并下发了 testlib 和 checker.cpp ，但默认我们已经会使用 checker.cpp 了， \(huge\) 还让我们别卡 checker.cpp 。

    点击查看代码 
    #include"testlib.h"
#include<bits/stdc++.h>
const int N=1e6+7;
int f[N];
int main(int argc,char *argv[]){
    registerTestlibCmd(argc,argv);
    int n=inf.readInt(),q=inf.readInt();
    for(int i=1;i<=n;i++) f[i]=inf.readInt(); 
    while(q--){
        int x=inf.readInt(),y=inf.readInt();
        int a=ouf.readInt(),b=ans.readInt();
        if((a==-1)^(b==-1)) quitf(_wa,"Wrong Answer.");
        if(a==-1) continue;
        if(1ll*((f[a]^x)-y)*((f[a+1]^x)-y)>0) quitf(_wa,"Wrong Answer.");
        std::swap(a,b);
        if(1ll*((f[a]^x)-y)*((f[a+1]^x)-y)>0) quitf(_wa,"Wrong Answer.");
    }
    quitf(_ok,"Correct. Participant found a valid solution.");
    return 0;
}

  • \(T4\) 中途更换了大样例。

  • \(T3,T4\) 因为时间复杂度较大，考虑到各学校 \(OJ\) 评测机，所以 后两题没有时间，设置题目的时候用标程跑一下就行了 。

标签：q1,q2,19,ll,多校,int,ans,NOIP2024,size
From： https://www.cnblogs.com/The-Shadow-Dragon/p/18533667

相关文章

  • Oracle 19c Rac环境部署
    Oracle19cRac环境部署前言搭建Oracle19cRac环境部署，使用dns进行解析。一、软件包linuxx64_193000_grid_home.ziplinuxx64_193000_db_home.zip二、配置信息1.IP地址规划编辑/etc/hosts#publicip10.1.50.213kezcc1kezcc1.zcc.com10.1.50.214kezcc......
  • BTTPS|cas：1341215-19-7
    BTTPS是一种化学物质，以下是对其的详细介绍：一、基本信息CAS号：1341215-19-7分子式：C20H34N10O4S分子量：510.62外观：淡灰白色固体溶解度：可溶于水、DMSO、DMF、甲醇等存储条件：避光，在-20摄氏度下保存保存时间：三年结构式：二、化学性质与用途性质：BTTPS是一种铜盐催化的“叠氮-炔基”......
  • 【题解】CF1944
    CF1944A简要题意给定完全图删k条边使得从一号点开始的可达点最少Solution注意到最多需要删n-1条边就可以使得任意一个其他点都到达不了又注意到只要删的边少于n-1就可以从一号点走出去，主要走出去就可以走到任何点所以这题答案只有两种如果k≤n-1答案为n否则答案为1......
  • NOIP2024集训Day71 贪心
    NOIP2024集训Day71贪心B.[CCO2015]饥饿的狐狸显然的，要求出最大美味值，应该先交错吃温度最大的和最小的饼干。所以我们给所有饼干按照温度排序，交替选择左右端点吃，如果喝水能够达到更大那就先喝水再吃，反正水管够。分两种情况，即左右端点谁先开始，再取个\(\operatorname{max}\)。......
  • 3193. 统计逆序对的数目
    3193.统计逆序对的数目题目链接：3193.统计逆序对的数目代码如下：classSolution{public: intnumberOfPermutations(intn,vector<vector<int>>&requirements) { vector<int>req(n,-1); req[0]=0; for(auto&p:requirements) { req[p[0]]=......
  • LOJ6119 「2017 山东二轮集训 Day7」国王
    题意给定一颗树，每个点有权值\(1\)和\(-1\)，称一条路径是好的当且仅当路径上所有点的权值和为\(0\)。求连续编号区间\([l,r]\)使得两个点都在\([l,r]\)的好路径比两个点都不在\([l,r]\)的好路径数严格多的方案数。\(n\le10^5\)。Sol两个端点都在区间内不好做，......
  • 多校A层冲刺NOIP2024模拟赛18
    多校A层冲刺NOIP2024模拟赛18T1选彩笔（rgb）签到题，但是没签上。。。没想到三维前缀和，直接上了个bitset。就是直接二分答案，然后枚举这三维每维的区间的起点，前缀和查数量是否大于等于$K$即可，也可以把二分答案改为第一维的双指针，少一个$log$。T2兵蚁排序（sort）比T1还签......
  • CSP2024 前集训：NOIP2024加赛 2
    前言T2开太晚了，没打完，别的没怎么挂。哦对，T1以为埃筛复杂度是\(nlog^2\)，实际上是\(n\ln(\ln(n))\)，结果以为复杂度是错的，然后本地不开O2都飞快，我甚至还在惊叹本地竟然能跑\(5e9\)……还有我之前不知道树的直径的中点时唯一的……T1新的阶乘直接埃筛做完了。点击查......
  • NOIP2024 模拟赛 #15 总结
    Larunatrecy：信心赛。赛时T1求中位数，想起前两天做过的[ABC203D]Pond，考虑了二分答案。看出二分答案后不会做了，罚坐\(20\)min。然后发现我傻逼了，选出一个区间翻转，可以通过钦定右端点，找到最优的左端点得到，神仙Heldivis就出过一道这样的题。写完后调了下二分边界过了大样......
  • CSP2024 前集训：多校A层冲刺NOIP2024模拟赛18
    前言不知道咋回事儿？脑子里一直放歌。然后T3空间给了256，开了256.23死了。T1选彩笔显然可以二分答案，所以现在有了\(O(nv^3\logv)\)的做法，去重后可以拿到\(80pts\)，发现直接三维前缀和就可以做到\(O(v^3\logv)\)。点击查看代码#include<bits/stdc++.h>#definell......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99