首页 > 其他分享 >2024初三年前集训测试1

2024初三年前集训测试1

时间：2024-01-31 16:55:19浏览次数：18  
标签：int register 差分 2024 define 初三 集训 sim getchar

前言

  • 总分： \(210\)

    \(T1\) : \(40\) ，挂了 \(60\) ，没考虑到他最后可能没有 “句号”

    \(T2\) ： \(100\) ，\(Hash\) 套 \(map\) 最劣解 \(A\) 掉了，直接用 \(map\) 实际上也能过。

    \(T3\) ： \(70\) ，忘记判断无解挂了 \(20\) 。跑的最短路，发现会被 \(Hack\) 调了好久，到最后自己造的 \(Hack\) 也没有过，交上去只 \(Hack\) 掉一个，还可以。

    \(T4\) ： \(0\) ，读错题了，也是因为时间不够了，调 \(T3\) 时间用太长了，也没有想到用差分。

  • 比赛链接

题解

学说话

  • 题目链接

  • 题面：

    给出一句话，求其中最长一个单词的长度，每个单词用 \(\_\) 连接。

    \(eg: I\_am\_Charlie\) ，最长长度为 \(7\) 。

  • 解法：

    签到题，非常简单，但是挂分了，还是考虑不全面。

    注意他最后一个单词后可能没有 \(\_\) ，所以循环结束后还需要刷新答案，显然最后一个单词最长的都挂了。

  • 代码如下：

#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
using namespace std;
const int N=1e6+10,P=1e9+7;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=1;
    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);
}
string s;
int n,ans,sum;
signed main()
{
    // #ifndef ONLINE_JUDGE
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // #endif
    freopen("word.in","r",stdin);
    freopen("word.out","w",stdout);
    cin>>s;
    n=s.size();
    for(int i=0;i<n;i++)
    {
        if(s[i]!='_') sum++;
        else 
            ans=max(ans,sum),
            sum=0;
    }
    ans=max(ans,sum);//这里不要忘了！qwq
    cout<<ans;
}

膜拜大佬

  • 题目链接

  • 题面：

    给出几个大佬的名字，判断接下来给出的几个名字是否是大佬。

  • 解法：

    纯 \(Hash\) 一道，但数据足够水，直接 \(map\) 也能过。

    怕 \(Hash\) 被卡掉，可能会想到字典树，但这玩意太容易 \(MLE\) 了开小了又会 \(RE\) ，所以尽可能别用吧。

    也可以再使用 \(map\) 存一下 \(Hash\) 值，但这样我为什么不直接用 \(map\) 呢？

  • \(Hash\) 代码：

#include<bits/stdc++.h>
#define int unsigned long long 
#define endl '\n'
using namespace std;
const int N=5010,P=1e9+7;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=1;
    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);
}
string s,s1,s2;
int n,big,h,b[N],m;
map<int,bool>v;
void Base(int n)
{
    b[1]=233;
    for(int i=2;i<=n;i++)
        b[i]=b[i-1]*b[1];
}
int get_hash(string s)
{
    int l=s.size(),res=0;
    for(int i=0;i<l;i++)
        res=res*b[1]+s[i];
    return res;
}
signed main()
{
    // #ifndef ONLINE_JUDGE
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // #endif
    freopen("dalao.in","r",stdin);
    freopen("dalao.out","w",stdout);
    Base(N-1);
    read(n);
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        big=get_hash(s);
        v[big]=1;
    }
    read(m);
    for(int i=1;i<=m;i++)
    {
        cin>>s1>>s2>>s;
        h=get_hash(s);
        if(v[h]) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}

走迷宫

  • 题目链接

  • 题面：

    迷宫起点 \(@\) 终点 \(=\) ，\(\#\) 表示墙，字母 \(A\sim Z\) 为传送门，成对出现，到达其中一传送门 立马 传到相同字母的另一装置上，传送过程不花费时间，剩下的是 \(\huge{.}\) ；从起点开始，可以上下左右走，每走一步为 \(1\) 秒。

    求最短多久可以到达终点。

  • 解法：

    赛时打了半天，相当麻烦，还 \(Hack\) 一个点，主要在于他到达传送门后立刻到达对应点，不可继续往前走，这对于我的代码就需要判断是进传送门还是出传送门，十分麻烦，而且不完全正确。

    听完同学的讲解后恍然大悟。

    终点在于建图，他到达这个传送点后立即传送。当前点 \(x\) 上下左右存在传送门，不放直接把 \(x\) 和传送终点连上，不连这个起点。

    如图：

    image

    image

    边权都是 \(1\) 。

    然后正常 \(spfa\) 最短路即可（当然 \(dijsktra\) 也可以）。

    至于建图时我用了一个比较巧妙的方法，用了一下 \(Hash\) 思想，存二维的 \(i,j\) 显然麻烦，将 \(i,j\) 放在一起转化成一个进制数，再来存图，就会方便很多。

    当然进制要选择要个大于 \(i,j\) 的质数，我选的 \(773\) ，最大搞出来才 \(2e5\) 左右，不用模数，就更没有误差。

    即 \(h=i\times 773+j\) ，用 \(h\) 来存。

  • 代码如下：

#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
using namespace std;
const int N=5e5+10,P=1e9+7,b=773;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=1;
    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);
}
char a[510][510];
int n,m,sta,d[N],en,from[N],too[N];
bool v[N];
int head[N],to[N],w[N],nxt[N],tot;
queue<int>q;
int c[4]={1,-1,0,0},e[4]={0,0,1,-1};
void add(int x,int y,int z)
{
    nxt[++tot]=head[x];
    to[tot]=y;
    w[tot]=z;
    head[x]=tot;
}
void spfa(int x)
{
    memset(d,0x3f,sizeof(d));
    d[x]=0;
    v[x]=1;
    q.push(x);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        v[x]=0;
        for(int i=head[x];i;i=nxt[i])
        {
            int y=to[i],z=w[i];
            if(d[y]>d[x]+z)
            {
                d[y]=d[x]+z;
                if(!v[y])
                {
                    v[y]=1;
                    q.push(y);
                }
            }
        }
    }
}
signed main()
{
    // #ifndef ONLINE_JUDGE
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // #endif
    freopen("maze.in","r",stdin);
    freopen("maze.out","w",stdout);
    read(n),read(m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            int h=i*b+j;
            if(a[i][j]=='@') sta=h;
            else if(a[i][j]=='=') en=h;
            else if(a[i][j]>='A'&&a[i][j]<='Z')
            {
                if(!from[a[i][j]-'A'+1])
                    from[a[i][j]-'A'+1]=h;
                else too[a[i][j]-'A'+1]=h;
            }
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int h=i*b+j;
            if(a[i][j]!='#')
                for(int k=0;k<4;k++)
                {
                    int x=i+c[k],y=j+e[k];
                    int hh=x*b+y;
                    if(x>=1&&x<=n&&y<=m&&y>=1)
                    {
                        if(a[x][y]>='A'&&a[x][y]<='Z')
                        {
                            if(from[a[x][y]-'A'+1]!=hh)
                                add(h,from[a[x][y]-'A'+1],1);
                                
                            else add(h,too[a[x][y]-'A'+1],1);
                        }
                        else if(a[x][y]!='#')
                            add(h,hh,1);
                    }
                }
            
        }
    spfa(sta);
    if(d[en]>999999) cout<<-1;//记得判无解！！！qwq
    else cout<<d[en];
}

  • 附录：

    • 没用了的的 \(Hack\) 数据呈上（自造）：

      \([email protected]=\) 和 \([email protected]=\)

    • 关于测试点数据：

      37 70
######################################################################
#....#TCP#...........................................................#
#....#####.....#......#..............................................#
#.............#.#....#.#.............................................#
#..............######W#..............................................#
#.............#........#..##############################.............#
#............#..V....V..#..#............................#..#...#.....#
#.............#........#....#............................#..#.#.#....#
#.............#..X##X..#..#...............W...............#..#...#...#
#............#...N##N...#..#.............................#...........#
#........MOO..#..@.....#....#.#.#.#...................#.#............#
#..............########.....#.#.#.##############.#.#..#.#............#
#...........................#.#.#.#.............#.#.#.#.#............#
#.......#########...........#.#.#.#.................#.#.#............#
#......#.........#..........#.#.#.#.................#.#.#............#
#..#.#.#G#R#A#S#S#.#.#......#.#.#.#.................#.#I#............#
#..###################......#T#C#P#.................#I#G#............#
#............................#.#.#...................#.#.............#
#....................................................................#
#....................................................................#
#......########........########.......#...........#...........#......#
#.....#...............#R......A#.......#.........#.#.........#.......#
#.....#...............#........#........#.......#...#.......#........#
#.....#...............#........#.........#.....#.....#.....#.........#
#.....#...............#........#..........#...#.......#...#..........#
#.....#...............#..M.....#...........#.#.........#.#...........#
#......########........########.............#...........#............#
#....................................................................#
#....................................................................#
#....................................................................#
####################################################################.#
#....................................................................#
##.###################################################################
#..#F#ZD#.#Y#.#JL#.#...#QJ#.#.#.#.#EK#....#.L#.............#BQ#......#
#.##Z####.#U#.####.#.#.####.#.#.#.####.#..####.............####.####.#
#....#DE#.###.#UH#...#.#HK#.#.#.#.#F...#........................#BY#.#
####################################################################=#

鸭子游戏

  • 题目链接

  • 关于原题：IncDec Sequence

  • 题面（原题）：

    给定一个长度为 \(n\) 的数列 \(a_1\sim a_n\) ，每次可以选定一个区间 \([l,r]\) ，使这个区间内每个数都 \(+1\) 或 \(-1\) 。

    先给定这个数列，求最少操作多少次能使其所有书都一样，在最少操作次数前提下，最终得到的数列会有多少中可能情况。

  • 解法：

    差分

    这是第二次模拟赛有差分不会了，看来我需要系统搞一下差分了。

    到最后数列内所有数都相同，也就是说，将其转化为差分数组 \(c_1\sim c_n\) ,那么除 \(c_1=a_1\) 外，\(c_2\sim c_n\) 军为 \(0\) 。

    线将原来的数组转化为差分数组。线选择一个区间 \([l,r]+1\) ，在差分数组中表示出来就是 \(c_l+1,c_{r+1}-1\) ，反之同理，运用差分的基本维护方法。那么现在在原数组中任意选择区间 \([l,r]\) ，转化在差分数组中就是任选两个数 \(+1\) 或 \(-1\) 。

    我们当然要将差分数组中对应负值 \(+1\) ，对应 正值 \(-1\) ，那么每次修改就是选一出一组正负值，分别 \(-1,+1\) 。

    但同时也要考虑边界，我们的目标是将 \(c_2\sim c_n\) 都变为 \(0\) ，所以变 \(c_1\) 是没用的，同样的，变 \(c_{n+1}\) 也是没用的，所以尽可能的在 \(c_2\sim c_n\) 中选出一组正负值，直到最后只剩正值或负值，再去和 \(c_1,c_{n+1}\) 进行修改。

    那么按照上面的思路，用 \(q\) 表示 \(c_2\sim c_n\) 的正值的和，同理 \(p\) 表示负值的和，每次选出一组来就是进行 \(min(p,q)\) 步，到了最后只剩 \(p\) 或只剩 \(q\) 了，再将其和 \(c_1||c_{n+1}\) 进行组合，就再进行了 \(|p-q|\) 步。加在一起，也就是 \(max(p,q)\) 步，步数就这么解决了。

    那么继续考虑最后有多少种可能，最后 \(a_1\sim a_n\) 数组所有值都是一样的，而 \(c_1=a_1\) ，就是求到最后 \(c_1\) 有多少中可能情况。

    我们发现在前面的操作中和 \(c_1,c_{n+1}\) 都没有关系，直到最后 \(|p-q|\) 步，这几步可以任意选择和 \(c_1\) 或 \(c_{n+1}\) 组合，那么从全部和 \(c_{n+1}\) 组合到全部和 \(c_1\) 组合，一共有 \(|p-q|+1\) 种情况，即最后的答案。

  • 代码如下：

#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
using namespace std;
const int N=2e6+10,P=1e9+7;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=1;
    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);
}
int n,a[N],b[N],ans1,ans2;
signed main()
{
	#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif    
    read(n);
    for(int i=1;i<=n;i++)
    {
        read(a[i]);
        b[i]=a[i]-a[i-1];
        if(i>1)
        {
            if(b[i]>0) ans1+=b[i];
            else ans2-=b[i];
        }
    }
    cout<<max(ans1,ans2)<<endl<<abs(ans1-ans2)+1;
}

总结：

教练说这次题相对比较简单，下次考就难了，还有下次？

总体下来确实难度不大，但不妨碍我分数不高。

也是有一定收获的，入门晚，快速赶进度的局限性显然使我必定会有很多地方不扎实，经验也较少，每一次比赛的挂分其实都是依次教训，都是为今后不再犯这样的错误作为一次教训。每次比赛发现有不扎实的地方就回去复习，收货不小。

同时还有对考试时间的掌控要分配合理。

集训时间好短啊，再过几天就走了，但短短几天收获非常的大，光是这种教训就吃了好多次，都是为了以后的真正比赛不出这种低级错误做准备。

所以我有必要去好好搞一下差分了。

也是有一些巧妙的做法，自己想出来的有用 \(Hash\) 将二维变为一个值方便储存；别人讲解的，尤其是那个建图，非常的巧妙，当然也是自己画了个图方便理解；差分的做法一直那么巧妙。

标签：int,register,差分,2024,define,初三,集训,sim,getchar
From： https://www.cnblogs.com/Charlieljk/p/17999601

相关文章

  • 2024最新Melodyne下载最新直装版
    MelodyneStudio是一款专业音频编辑软件，由德国公司Celemony开发。它的独特之处在于能够以无与伦比的准确性和自然性编辑音频的音高和时长。用户可以轻松调整音符，修复音频缺陷，甚至改变乐器的音调。MelodyneStudio版本是其最高级别，提供多轨编辑、全频谱编辑等高级功能，适用于专业音......
  • 6.【2024初三年前集训测试1】
    \(\Huge打了一场模拟赛，又垫底了。qwq\)2024初三年前集训测试1T1学说话\(100pts\)水题，秒了。单词被下划线分隔开，对于每个单词来说，只要记录最长的单词长度，用\(tot\)临时记录，遇到下划线就清零，\(ans\)记录最大值，最后输出即可。代码#include<bits/stdc++.h>#defineintl......
  • 2024年小年是哪一天？小年习俗记到手机便签
    随着春节的临近，我们即将迎来一个重要的传统节日——“小年”。那么2024年小年是哪一天呢？关于2024年小年的具体日期，地域不同，节日时间有所不同。在北方，小年通常是在腊月二十三，即2月2日；而在南方，小年则一般定在腊月二十四，即2月3日。小年作为一个重要的传统节日，有着丰富的习俗。家长们......
  • 杂题20240131
    CF1753C思路点拨考虑一共有\(s\)个\(0\)，\(n-s\)个\(1\)。最终序列的形态就是\(s\)个\(0\)在最前面，后面全部都是\(1\)。考虑在前\(s\)个位置中有\(k\)个\(1\)，那么只需要将这\(k\)个\(1\)移动到后面就可以了。考虑第一次有效操作的概率，有\(\dfrac{n(n-1)......
  • USACO2024JAN 三组连打
    假的，只连打了两组。Ag没时间了。日后再补吧。无意中存了题面，但代码大部分因为系统还原消失了，只有文字题解，将就着看吧。Cu-A省流：任意区间内，若某元素出现个数严格大于区间长度一半，则可将整个区间推平为该值。问最终可以使整个序列被推平为哪些值。注意到当任意长度\(\ge2......
  • 算法模板 v1.6.1.20240131
    算法模板v1.1.1.20240115：之前的历史版本已经不可寻，创建了第一份算法模板。v1.2.1.20240116：删除“编译”-“手动开栈”与“编译”-“手动开O优化”；将“编译”-“CF模板”中的第20行代码cin>>T;注释；删除“读写”及其目录下的内容；删除“图论”-“欧拉图”-“混合图”；删除“图论”-......
  • 2024初三年前集训测试1
    2024初三年前集训测试1\(T1\)学说话\(100pts\)找到下划线后将计数器归零。点击查看代码strings;intmain(){freopen("word.in","r",stdin);freopen("word.out","w",stdout);intans=0,num=0,len,i;cin>>s;len=s.si......
  • 2024初三年前集训测试1
    2024初三年前集训测试1我TM以后比赛不造数据对拍就TM是大傻逼打了2hours，觉得挺简单的，于是交了就润了。所以我是傻逼。T1:显然题，但scanf("%c",&a)\(\to\)scanf("%c",&a)，\(100pts\to30pts\)wkh2008精通科技，可是我不会。科技#include<bits/stdc++.h>using......
  • 2024年上半年NPDP产品经理认证【报名到这】
    产品经理国际资格认证NPDP是新产品开发方面的认证，集理论、方法与实践为一体的全方位的知识体系，为公司组织层级进行规划、决策、执行提供良好的方法体系支撑。 【认证机构】 产品开发与管理协会（PDMA）成立于1979年，是全球范围内产品开发与管理专业人士最杰出的倡导者，协助个人、企业或......
  • 2024年上半年软考高级信息系统项目管理师【报名来这】
    信息系统项目管理师是全国计算机技术与软件专业技术资格（水平）考试（简称软考）项目之一，是由国家人力资源和社会保障部、工业和信息化部共同组织的国家级考试，既属于国家职业资格考试，又是职称资格考试。信息系统项目管理师，属于软考三个级别中的“高级”。 【报考要求】 不设学历与资历条......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99