首页 > 其他分享 >2024暑假集训测试6

2024暑假集训测试6

时间：2024-07-20 12:11:04浏览次数：6  
标签：last val int void 2024 add 暑假 集训 define

前言

image

挂分挂的最多的一集。

T1 不知道摩尔投票，被 2M 内存限制卡死。

T2 赛时打了个很像正解的莫队，赛时出题人发现了之后现往里加 hack，还一个捆绑里加一个，直接爆零了，我真的谢了，求求以后不要一个捆绑放一个 hack 了，给条活路吧。

T3 一眼看出线段树优化建图，但是不会打。

出题人说这次比赛就是为了让我们涨涨见识，学一些板子和套路。

T1 活动投票

摩尔投票，若新的 \(a_i\) 与当前答案相同，则 \(sum+1\)，否则 \(sum-1\)，\(sum=0\) 时直接更新答案为当前 \(a_i\)，正确性显然。

T2 序列

  • 部分分 \(30pts\)：暴力没什么好说的。

  • 假做法：

    对于每个 \(a_i\) 有其 \(last_i\) 表示其上一次出现的位置，对于每个 \(last_i\ne 0\) 的 \(i\)，另 \(l=last_i,r=i\) 最为一组询问跑莫队，若该段询问区间里均存在只出现过一次的就合法，否则不合法。

    考虑做法的错误性，由于只考虑了 \(i\) 与 \(last_i\) 之间，进而没有考虑到一段子串中出现 \(3\) 次及以上的情况。

    提供一组 \(hack\)：1 2 1 2 1。

    考虑优化成 \(last_i\sim next_i\) 的，由于莫队复杂度擦边且存在一定常数，仍会 \(TLE\)，没有继续深入研究，这个算法最多只能骗 \(60pts\) 了。

  • 正解：

    正解有很多种，我只改了一种，也是很套路的一种。

    枚举右端点 \(r\)，\(f_i\) 表示区间 \([i,r]\) 存在只出现一次的数的个数，考虑当 \(r+1\) 时如何转移。

    若 \(a_{r+1}\) 之前没有出现过，则 \(f_1\sim f_{r+1}\) 均 \(+1\)。

    否则定义 \(last_{r+1}\) 表示 \(a_{r+1}\) 上一次出现的位置，\(f_{last_{r+1}+1}\sim f_{r+1}\) 均 \(+1\)，\(f_{last_{last_{r+1}}+1}\sim f_{last_{r+1}}\) 均 \(-1\)。

    合法的条件就是任意时刻 \(f_1\sim f_{r}\) 均 \(\ge 1\)。

    修改可以用线段树区间修改，查询可以线段树查询区间最小值。

    点击查看代码 
    #include<bits/stdc++.h>
#define int long long 
#define endl '\n'
#define sort stable_sort
#define f t[p]
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int N=2e5+10;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=true;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
void wt(int x){if(x>9)wt(x/10);putchar((x%10)+'0');}
void write(int x){if(x<0)putchar('-'),x=~x+1;wt(x);}
int T,n,a[N],b[N],last[N],old[N],now[N],cnt[N];
struct aa {int l,r,val,add;}t[N<<2];
void build(int p,int l,int r)
{
    f.l=l,f.r=r,f.val=f.add=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    f.val=min(t[ls].val,t[rs].val);
}
void spread(int p)
{
    if(f.add==0) return ;
    t[ls].val+=f.add,t[ls].add+=f.add;
    t[rs].val+=f.add,t[rs].add+=f.add;
    f.add=0;
}
void change(int p,int l,int r,int d)
{
    if(l>r) return ;
    if(l<=f.l&&r>=f.r) 
    {
        f.val+=d,f.add+=d;
        return ;
    }
    spread(p);
    int mid=(f.l+f.r)>>1;
    if(l<=mid) change(ls,l,r,d);
    if(r>mid) change(rs,l,r,d);
    f.val=min(t[ls].val,t[rs].val);
}
int ask(int p,int l,int r)
{
    if(l<=f.l&&r>=f.r) return f.val;
    spread(p);
    int mid=(f.l+f.r)>>1,ans=0x3f3f3f3f;
    if(l<=mid) ans=min(ans,ask(ls,l,r));
    if(r>mid) ans=min(ans,ask(rs,l,r));
    return ans;
}
signed main()
{
    read(T);
    while(T--)
    {
        read(n);
        for(int i=1;i<=n;i++) 
            read(a[i]),
            b[i]=a[i],
            cnt[i]=now[i]=last[i]=old[i]=0;
        sort(b+1,b+1+n);
        b[0]=unique(b+1,b+1+n)-(b+1);
        for(int i=1;i<=n;i++)
            a[i]=lower_bound(b+1,b+1+b[0],a[i])-b;
        for(int i=1;i<=n;i++) 
        {
            last[i]=now[a[i]];
            old[i]=last[last[i]];
            now[a[i]]=i;
        }
        build(1,1,n);
        bool flag=0;
        for(int i=1;i<=n;i++)
        {
            if(cnt[a[i]]==0)
            {
                change(1,1,i,1);
                if(ask(1,1,i)<=0)
                {
                    flag=1;
                    puts("boring");
                    break; 
                }
            }
            else 
            {
                change(1,last[i]+1,i,1);
                change(1,old[i]+1,last[i],-1);
                if(ask(1,1,i)<=0)
                {
                    flag=1;
                    puts("boring");
                    break; 
                }
            }
            cnt[a[i]]++;
        }
        if(!flag) puts("non-boring");
    }
}

T3 Legacy

线段树优化建图板子。

  • 建树：

    建两棵树，一颗出树一颗入树。

    对于入树，若该节点被连接则其子节点一定被连接，所以每个点向子节点连权值为 \(0\) 的边。

    对于出树，若该节点可向外连接则其父节点也一定能向外连接，故每个点向其父节点连权值为 \(0\) 的边。

    进了该点后就要出点，于是入树上每个节点向出树上对应节点连权值为 \(0\) 的边。

  • 连边：

    只考虑区间连区间这种更一般的情况，点就是长度为 \(1\) 的区间。

    对于区间 \([a,b]\) 连 \([c,d]\)，定义一个新的虚点 \(x\)，在出树上另 \([a,b]\) 连 \(x\)，再另 \(x\) 连入树上 \([c,d]\)，考虑权值不可重复计算，两次操作中仅让一个带权值，另一个权值为 \(0\)。

点击查看代码 
#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
#define sort stable_sort
#define f t[p]
#define ls (p<<1)
#define rs (p<<1|1)
using namespace std;
const int N=2e6+10;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=true;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
void wt(int x){if(x>9)wt(x/10);putchar((x%10)+'0');}
void write(int x){if(x<0)putchar('-'),x=~x+1;wt(x);}
int n,m,cnt,s,pos[N],dis[N];
bool vis[N];
int tot,head[N],to[N],nxt[N],w[N];
struct aa {int l,r;}t[N];
void add(int x,int y,int z)
{
    nxt[++tot]=head[x];
    to[tot]=y;
    w[tot]=z;
    head[x]=tot;
}
void build(int p,int l,int r)
{
    f.l=l,f.r=r;
    add(p+4*n,p,0);
    if(l==r) {pos[l]=p; return ;}
    add(ls,p,0),add(rs,p,0);
    add(p+4*n,ls+4*n,0),add(p+4*n,rs+4*n,0);
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
}
void change(int p,int x,int l,int r,int z,bool d)
{
    if(l<=f.l&&r>=f.r)
    {
        if(d==0) add(p,x+8*n,0);
        else add(x+8*n,p+4*n,z);
        return ;
    }
    int mid=(f.l+f.r)>>1;
    if(l<=mid) change(ls,x,l,r,z,d);
    if(r>mid) change(rs,x,l,r,z,d);
} 
void add(int a,int b,int c,int d,int z)
{
    cnt++;
    change(1,cnt,a,b,z,0);
    change(1,cnt,c,d,z,1);
}
void dij(int s)
{
    memset(dis,0x3f,sizeof(dis));
    priority_queue<pair<int,int>>q;
    dis[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        int x=q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=nxt[i])
        {
            int y=to[i],z=w[i];
            if(dis[y]>dis[x]+z)
            {
                dis[y]=dis[x]+z;
                q.push(make_pair(-dis[y],y));
            }
        }
    }
}
signed main()
{
    read(n),read(m),read(s);
    build(1,1,n);
    for(int i=1,op,z,a,b,c,d;i<=m;i++)
    {
        read(op);
        if(op==1)
            read(a),read(c),read(z),
            b=a,d=c;
        if(op==2)
            read(a),read(c),read(d),read(z),
            b=a;
        if(op==3)
            read(c),read(a),read(b),read(z),
            d=c;
        add(a,b,c,d,z);
    }
    dij(pos[s]);
    for(int i=1;i<=n;i++)
        if(i==s) write(0),putchar(' ');
        else write(dis[pos[i]+n*4]==0x3f3f3f3f3f3f3f3f?-1:dis[pos[i]+n*4]),putchar(' ');
}

T4 DP搬运工1

预设性 \(DP\)，计数 \(DP\)。

定义 \(f_{i,j,k}\) 表示当前填的数为 \(i\)，存在 \(j+1\) 个段，其和为 \(k\) 有多少情况，另其强制从小到大填数，初始值 \(f_{1,0,0}=1\)。

对于新填一个数对于 \(k\) 的贡献，有：

  • \(i\) 与左右两边均不相邻，其后面填的数一定 \(>i\)，故不产生贡献。

  • \(i\) 与左右两边中的一个相邻，\(i\) 一定 \(>\) 之前填的数，其后面填的数一定 \(>i\)，故贡献为 \(i\)。

  • \(i\) 与左右两边均相邻，\(i\) 一定 \(>\) 之前填的数，故贡献为 \(2\times i\)。

因此有转移：

  • 若填在原序列两端：

    • 若与原序列不相邻：

      会产生一个新的段，同时不产生贡献，两端有两种可能，有 \(f_{i,j+1,k}+=f_{i-1,j,k}\times 2\)。

    • 若与原序列相邻：

      不会产生新的段，产生 \(i\) 的贡献，两端有两种可能，有 \(f_{i,j,k+i}+=f_{i-1,j,k}\times 2\)。

  • 若填在原序列之间：

    • 与原序列不存在相邻：

      会产生一个新的段，对答案不产生贡献，\(j+1\) 个段有 \(j\) 个空，有 \(f_{i,j+1,k}+=f_{i-1,j,k}\times j\)。

    • 与原序列一端相邻：

      不会产生新的段，对答案产生 \(i\) 的贡献，\(j+1\) 个段有 \(j\) 个空，与其任意一端相邻有两种情况，有 \(f_{i,j,k+i}+=f_{i-1,j,k}\times j\times 2\)。

    • 与原序列两端均相邻：

      将两端接壤，故减少一个段，对答案产生 \(2\times i\) 的贡献，\(j+1\) 个段有 \(j\) 个空，有 \(f_{i,j-1,k+2\times i}+=f_{i-1,j,k}\times j\)。

最后答案 \(ans=\sum\limits_{i=0}^mf_{n,0,i}\)。

点击查看代码 
#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=55,P=998244353;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=true;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
void wt(int x){if(x>9)wt(x/10);putchar((x%10)+'0');}
void write(int x){if(x<0)putchar('-'),x=~x+1;wt(x);}
int n,m,ans,f[N][N][N*N];
signed main()
{
    read(n),read(m);
    f[1][0][0]=1;
    for(int i=2;i<=n;i++)
        for(int j=0;j<=n-i+1;j++)
            for(int k=0;k<=m;k++)
            {
                (f[i][j+1][k]+=f[i-1][j][k]*2)%=P;
                (f[i][j][k+i]+=f[i-1][j][k]*2)%=P;
                if(j!=0)
                    (f[i][j+1][k]+=f[i-1][j][k]*j)%=P,
                    (f[i][j][k+i]+=f[i-1][j][k]*j*2)%=P,
                    (f[i][j-1][k+i*2]+=f[i-1][j][k]*j)%=P;
            }
    for(int i=0;i<=m;i++) (ans+=f[n][0][i])%=P;
    write(ans);
}

总结

像 T1 这样怎么想都过不去的就不要抱有侥幸心理，而是去想新做法。

想到做法时先想想会不会被 hack。

多积累一些板子和套路，类似数颜色类型的区间特点统计的题考虑类似 T2 的套路。

标签：last,val,int,void,2024,add,暑假,集训,define
From： https://www.cnblogs.com/Charlieljk/p/18312926

相关文章

  • 2024牛客暑期多校训练营1
    A:ABitCommon题目大意：建立一个长度为n且每个数严格小于\(2^m\)的非空序列A使其存在一个非空子序列B，B中所有元素的与运算结果为1，输出合法A序列的个数。思路：存在子序列合法即该序列合法，其他元素无要求。即可以枚举合法子序列的长度，其他元素均为必定非合法整数。又因为需要结果为......
  • 小欧吃苹果-OPPO 2024届校招正式批笔试题-数据开发（C卷）
    在处理这个问题前，先看一个经典的贪心算法题目。信息学奥赛一本通（C++版）在线评测系统http://ybt.ssoier.cn:8088/problem_show.php?pid=1320注意移动纸牌的贪心策略并不是题目中给出的移动次序：第1堆纸牌9<10，因为是最左侧，它只能从第2堆移动过来一张，这个动作是必须做的（没有别的......
  • 「模拟赛」暑期集训CSP提高模拟2（7.19）
    学长组题+预告：题会有点难雀氏。。。题目列表A.活动投票B.序列C.LegacyD.DP搬运工1A.活动投票题意：衡中活动很多，人也很多，一次活动有$n$个学生参与投票，现已知一名参赛选手票数超过半数，求其参赛号$ai$​（参赛号随机，$0≤ai≤21474836470≤ai​≤2147483647)$。很......
  • [lnsyoj110/luoguP2024]食物链
    题意原题链接三类元素\(a,b,c\)满足\(a\tob\)，\(b\toc\)，\(c\toa\)。现在共有\(n\)个元素，给出\(m\)条关系\(x\toy\)或\(x\)与\(y\)种类相同，输出非法或与前面所属关系相矛盾的关系数量sol并查集可以处理“朋友的朋友是朋友”这样的传递关系，却不能处理“敌人......
  • 大一升大二暑假 NJU暑期课程 Linux系统基础（1） 20240720
    一.操作系统操作系统OperatingSystem简称OS，是软件的一部分，它是硬件基础上的第一层软件，是硬件和其它软件沟通的桥梁。操作系统会控制其他程序运行，管理系统资源，提供最基本的计算功能，如管理及配置内存、决定系统资源供需的优先次序等，同时还提供一些基本的服务程序。Q1:什么是文件......
  • 2024/07/19（暑假学习hadoop第二周总结）
    本周的学习任务主要是完成Hadoop中有关的组件的配置。有关于此配置的过程严格按照黑马程序员大数据入门到实战教程，大数据开发必会的Hadoop、Hive，云平台实战项目全套一网打尽_哔哩哔哩_bilibili来进行配置。首先就是HDFS的配置，这是Hadoop分布式文件系统，用于在多个服务器上构建存储......
  • 河南萌新联赛2024第（一）场
    先给出比赛链接：https://ac.nowcoder.com/acm/contest/86639A造数题目问多少次操作可以把0转为n操作共有三种\(+1\)\(+2\)\(\times2\)能够发现操作的数字最大是2，那么这题就可以考虑二进制。三种操作就能这么理解：\(末位+1\)\(倒数第二位+1\)\(左移1位\)那么我们就......
  • 干货 | 2024应用安全防护之云原生安全实践方案（免费下载）
    诚挚邀请您扫码加入以下信息安全精品资料知识星球，获取上万份安全PPT解决方案！！！感谢支持！！！......
  • 航电多校 2024 笔记
    01写点赛时不会的。难绷场，可能因为是01所以比较水，就只有最后一个能放省选模拟T1，以及一堆原神题。T5hdu7434博弈小马给出了一个可重小写字符集合 \(S\)。Alice初始时有空串 \(A\)，Bob初始时有空串 \(B\)。两人轮流等概率取出集合 \(S\) 中的一个字符 \(c\)，将它拼接......
  • 初级java每日一道面试题-2024年7月19日
    在Java中，重载（Overloading）和重写（Overriding）是面向对象编程中多态性的两个重要概念。1.重载（Overloading）定义：重载是指在同一个类中，允许存在一个以上的同名方法，只要它们的参数列表不同即可。也就是说，这些方法的名称相同，但参数的个数、类型或顺序至少有一个不同。目的：重载......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99