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

6.【2024初三年前集训测试1】

时间：2024-01-31 16:12:45浏览次数：41  
标签：int 31 long 2024 freopen inline 初三 集训 define

\(\Huge打了一场模拟赛，又垫底了。qwq\)

2024初三年前集训测试1

T1学说话

\(100pts\)

  • 水题，秒了。
  • 单词被下划线分隔开，对于每个单词来说，只要记录最长的单词长度，用 \(tot\) 临时记录，遇到下划线就清零， \(ans\) 记录最大值，最后输出即可。

代码

#include<bits/stdc++.h>
#define int long long
#define N (1000010)
#define sort stable_sort
using namespace std;
namespace IO
{
    #define ll long long
    const int MAX=1<<25;
    char buf[MAX],*p1=buf,*p2=buf;
    char obuf[MAX],*o=obuf;
    #define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<25,stdin),p1==p2)?EOF:*p1++)
    //template<typename T>
    //inline T read()
    inline int read()
    {
        int x=0;bool f=1;
        char c=gc();
        for(;c<48||c>57;c=gc())if(c=='-')f=0;
        for(;c>=48&&c<=57;c=gc())x=(x<<3)+(x<<1)+(c^48);
        return f?x:~x+1;
    }
    void print(ll x){if(x>9)print(x/10);*o++=(x%10)+'0';}
    void pit(ll x){if(x<0)*o++='-',x=~x+1;print(x);}
    void write(ll x,char end){pit(x);*o++=end;}
    void flush(){fwrite(obuf,o-obuf,1,stdout);}
    #undef ll
}
using IO::read;using IO::write;using IO::flush;using std::complex;
inline int min(int x,int y){return y&((y-x)>>31)|x&(~(y-x)>>31);}
inline int max(int x,int y){return x&((y-x)>>31)|y&(~(y-x)>>31);}
inline void swap(int &x,int &y){int tmp=x;x=y;y=tmp;}
long long n,m;
void init_set()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    #ifdef ONLINE_JUDGE
    freopen("word.in","r",stdin);
    freopen("word.out","w",stdout);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
}
int l,r,xx,yy,zz,lss;
string s;
int tot,ans;
signed main()
{
    init_set();
    cin>>s;
    int len(s.size());
    for(int i(0);i<len;++i)
    {
        tot=0;
        while(s[i]!='_'&&i<len)++tot,++i;
        ans=max(ans,tot);
    }
    write(ans,' ');
    flush();
    return 0;
}

T2膜拜大佬

\(0pts→100pts\)

  • 哈希水题，把每位大佬的哈希值存起来，时间复杂度 \(\large O(\sum\limits|L|)\) ，约为 \(\large O(n^2)\) 。当询问时，前两个字符串显然无用，对最后一个字符串求哈希值，如果有一个哈希可以匹配到，看做两个字符串相同 输出 \(Yes\) 后跳出查找，否则输出 \(No\) 。时间复杂度为 \(O(n^2)\) 。
    \(\Huge一定要看好写的是~i~还是~j~，蒟蒻因为这个一分没得qwq\)

代码

#include<bits/stdc++.h>
#define int long long
#define N (1000010)
#define sort stable_sort
using namespace std;
namespace IO
{
    #define ll long long
    const int MAX=1<<25;
    char buf[MAX],*p1=buf,*p2=buf;
    char obuf[MAX],*o=obuf;
    #define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<25,stdin),p1==p2)?EOF:*p1++)
    //template<typename T>
    //inline T read()
    inline int read()
    {
        int x=0;bool f=1;
        char c=gc();
        for(;c<48||c>57;c=gc())if(c=='-')f=0;
        for(;c>=48&&c<=57;c=gc())x=(x<<3)+(x<<1)+(c^48);
        return f?x:~x+1;
    }
    void print(ll x){if(x>9)print(x/10);*o++=(x%10)+'0';}
    void pit(ll x){if(x<0)*o++='-',x=~x+1;print(x);}
    void write(ll x,char end){pit(x);*o++=end;}
    void flush(){fwrite(obuf,o-obuf,1,stdout);}
    #undef ll
}
using IO::read;using IO::write;using IO::flush;using std::complex;
inline int min(int x,int y){return y&((y-x)>>31)|x&(~(y-x)>>31);}
inline int max(int x,int y){return x&((y-x)>>31)|y&(~(y-x)>>31);}
inline void swap(int &x,int &y){int tmp=x;x=y;y=tmp;}
long long n,m;
void init_set()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    #ifdef ONLINE_JUDGE
    freopen("dalao.in","r",stdin);
    freopen("dalao.out","w",stdout);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
}
int l,r,xx,yy,zz,lss;
string s;
int tot,ans;
unsigned __int128 has[100010],p[100010],qhs;
bool flag=0;
signed main()
{
    init_set();
    cin>>n;
    p[0]=1,p[1]=131;
    for(int i(2);i<=10000;++i)p[i]=p[i-1]*p[1];
    for(int i(1);i<=n;++i)
    {
        cin>>s;
        int len(s.size());
        for(int j(0);j<len;++j)
            has[i]=has[i]*p[1]+s[j];
    }
    cin>>m;
    for(int i(1);i<=m;++i)
    {
        cin>>s>>s>>s;
        flag=0;
        int len(s.size());
        qhs=0;
        for(int j(0);j<len;++j)qhs=qhs*p[1]+s[j];
        for(int j(1);j<=n;++j)
            if(qhs==has[j]){flag=true,puts("Yes");break;}
        if(!flag)puts("No");
    }
    flush();
    return 0;
}

T3走迷宫

\(80pts→100pts\)

  • 假如当时没有把无解情况注释掉，就是 \(100pts\) 了。
  • 很容易看出来这道题是个搜索，但是也有人用 \(\text SPFA\) \(AC\) 了。
  • 如果用搜索，显然需要用 \(BFS\) 而不是 \(DFS\) ，因为要求最优路线， \(BFS\) 第一个搜到的解一定是最优解，而 \(DFS\) 就做不到。
  • 但是蒟蒻一开始把 \(BFS\) 打成了 \(DFS\) 也就浪费了半个小时 \(qwq\dots\) 。
  • 由于可以有传送门，先记录上每个传送门匹配的位置。之后就能快速传送。
  • \(BFS\) 要用队列，而 \(DFS\) 一般是用函数递归。用结构体存坐标和步数，在第一个队列中放入起始点，初始步数为 \(0\) 。之后 \(while(h\leq t)\) ，每次从队头取值，加入四周有可以达到的点或未走过的点，就进行 \(BFS\) ，将新的点加入队尾。如果最终也没有搜到答案，可以在一开始将答案赋为极大值，找到答案就更新，未找到答案就输出 \(-1\) 。
  • 对于传送门（字母）来说，可以进行特判，走到字母上直接传送到另一个字母上。
#include<bits/stdc++.h>
#define int long long
#define N (1000010)
#define sort stable_sort
using namespace std;
namespace IO
{
    #define ll long long
    const int MAX=1<<25;
    char buf[MAX],*p1=buf,*p2=buf;
    char obuf[MAX],*o=obuf;
    #define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<25,stdin),p1==p2)?EOF:*p1++)
    //template<typename T>
    //inline T read()
    inline int read()
    {
        int x=0;bool f=1;
        char c=gc();
        for(;c<48||c>57;c=gc())if(c=='-')f=0;
        for(;c>=48&&c<=57;c=gc())x=(x<<3)+(x<<1)+(c^48);
        return f?x:~x+1;
    }
    void print(ll x){if(x>9)print(x/10);*o++=(x%10)+'0';}
    void pit(ll x){if(x<0)*o++='-',x=~x+1;print(x);}
    void write(ll x,char end){pit(x);*o++=end;}
    void flush(){fwrite(obuf,o-obuf,1,stdout);}
    #undef ll
}
using IO::read;using IO::write;using IO::flush;using std::complex;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline void swap(int &x,int &y){int tmp=x;x=y;y=tmp;}
long long n,m;
void init_set()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    #ifdef ONLINE_JUDGE
    freopen("maze.in","r",stdin);
    freopen("maze.out","w",stdout);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
}
int l,r,x,y,xx,yy,zz,lss,begx,begy,ans(0x7f7f7f7f);
struct aa{int x,y;}e[100][5];
struct bb{int x,y,stp;}q[5000010];
bool pd[510][510];
char cap[510][510],c[510][510];
signed main()
{
    init_set();
    cin>>n>>m;
    for(int i(1);i<=n;++i)
        for(int j(1);j<=m;++j)
        {
            cin>>c[i][j];
            if(c[i][j]!='#')pd[i][j]=1;
            if(c[i][j]>='A'&&c[i][j]<='Z')
            {
                if(e[c[i][j]-'A'][0].x!=0)
                    e[c[i][j]-'A'][1]={i,j};
                else e[c[i][j]-'A'][0]={i,j};
            }
            if(c[i][j]=='@')begx=i,begy=j;
        }
    int t(0),h(0),stp(0);
    q[0]={begx,begy,0};
    for(;h<=t;)
    {
        x=q[h].x,y=q[h].y;stp=q[h].stp;++h;
        if(!pd[x][y]||x<1||x>n||y<1||y>m)continue;
        pd[x][y]=0;
        if(c[x][y]=='='){ans=stp,cout<<stp<<'\n';break;}
        if(c[x+1][y]>='A'&&c[x+1][y]<='Z')
        {
            if(e[c[x+1][y]-'A'][0].x==x+1&&e[c[x+1][y]-'A'][0].y==y)
                q[++t]=(bb){e[c[x+1][y]-'A'][1].x,e[c[x+1][y]-'A'][1].y,stp+1};
            else
                q[++t]=(bb){e[c[x+1][y]-'A'][0].x,e[c[x+1][y]-'A'][0].y,stp+1};
        }
        else q[++t]=(bb){x+1,y,stp+1};
        if(c[x-1][y]>='A'&&c[x-1][y]<='Z')
        {
            if(e[c[x-1][y]-'A'][0].x==x-1&&e[c[x-1][y]-'A'][0].y==y)
                q[++t]=(bb){e[c[x-1][y]-'A'][1].x,e[c[x-1][y]-'A'][1].y,stp+1};
            else
                q[++t]=(bb){e[c[x-1][y]-'A'][0].x,e[c[x-1][y]-'A'][0].y,stp+1};
        }
        else q[++t]=(bb){x-1,y,stp+1};
        if(c[x][y-1]>='A'&&c[x][y-1]<='Z')
        {
            if(e[c[x][y-1]-'A'][0].x==x&&e[c[x][y-1]-'A'][0].y==y-1)
                q[++t]=(bb){e[c[x][y-1]-'A'][1].x,e[c[x][y-1]-'A'][1].y,stp+1};
            else
                q[++t]=(bb){e[c[x][y-1]-'A'][0].x,e[c[x][y-1]-'A'][0].y,stp+1};
        }
        else q[++t]=(bb){x,y-1,stp+1};
        if(c[x][y+1]>='A'&&c[x][y+1]<='Z')
        {
            if(e[c[x][y+1]-'A'][0].x==x&&e[c[x][y+1]-'A'][0].y==y+1)
                q[++t]=(bb){e[c[x][y+1]-'A'][1].x,e[c[x][y+1]-'A'][1].y,stp+1};
            else
                q[++t]=(bb){e[c[x][y+1]-'A'][0].x,e[c[x][y+1]-'A'][0].y,stp+1};
        }
        else q[++t]=(bb){x,y+1,stp+1};
    }
    if(ans==0x7f7f7f7f)puts("-1"),exit(0);
    flush();
    return 0;
}

T4鸭子游戏

\(20pts\)

  • 本来感觉有思路，但是还是假了……如果想到差分就很好做了。
  • 一开始以为可以设定一个高度，之后暴力判断使所有高度都为这个高度需要多少步。然后又觉得可以三分，但是最后没打出来。
  • 正解：差分。
  • 首先看这样一组数据 \(1\) \(3\) \(5\) \(3\) \(1\) 差分数组为 \(0\) \(2\) \(2\) \(-2\) \(-2\) ，用人脑模拟得出，第一步将 \(2-4\) 的高度 \(-2\) ，之后把 \(3\) 的高度 \(-2\)

原数组：

1 2 3 4 5
1 3 5 3 1
1 1 3 1 1
1 1 1 1 1

差分数组：

1 2 3 4 5
0 2 2 -2 -2
0 0 2 -2 0
0 0 0 0 0
  • 看出规律了吗？肯定看出来了。 每次修改就是将差分数组正负匹配。如对 \(2-4\) 的修改，事实上就是在将 \(2\) 与 \(5\) 的差分数组正负匹配，对 \(3\) 的修改，就是对 \(3\) \(4\) 的差分数组正负匹配，之后变成 \(0\) 。
  • 所有最后也就只需要去记录正的差分和负的差分的和，之后输出其中最大的即可。

代码

#include<bits/stdc++.h>
#define int long long
#define N (1000010)
#define sort stable_sort
using namespace std;
namespace IO
{
    #define ll long long
    const int MAX=1<<25;
    char buf[MAX],*p1=buf,*p2=buf;
    char obuf[MAX],*o=obuf;
    #define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<25,stdin),p1==p2)?EOF:*p1++)
    //template<typename T>
    //inline T read()
    inline int read()
    {
        int x=0;bool f=1;
        char c=gc();    
        for(;c<48||c>57;c=gc())if(c=='-')f=0;
        for(;c>=48&&c<=57;c=gc())x=(x<<3)+(x<<1)+(c^48);
        return f?x:~x+1;
    }
    void print(ll x){if(x>9)print(x/10);*o++=(x%10)+'0';}
    void pit(ll x){if(x<0)*o++='-',x=~x+1;print(x);}
    void write(ll x,char end){pit(x);*o++=end;}
    void flush(){fwrite(obuf,o-obuf,1,stdout);}
    #undef ll
}
using IO::read;using IO::write;using IO::flush;using std::complex;
inline int min(int x,int y){return y&((y-x)>>31)|x&(~(y-x)>>31);}
inline int max(int x,int y){return x&((y-x)>>31)|y&(~(y-x)>>31);}
inline void swap(int &x,int &y){int tmp=x;x=y;y=tmp;}
long long n,m;
void init_set()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    #ifdef ONLINE_JUDGE
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
}
int l,r,x,y,xx,yy,zz,lss,las,ans,res,kop;
int a[2000010];
int cf[2000010];
signed main()
{
    init_set();
    n=read();
    las=read();
    for(int i(2);i<=n;++i)
    {
        lss=read();
        kop=lss-las;
        if(kop>0)ans+=kop;
        else res-=kop;
        las=lss;
    }
    write(max(ans,res),' ');
    flush();
    return 0;
}

\(\Huge但是打了一场模拟赛，又垫底了。qwq\)

标签：int,31,long,2024,freopen,inline,初三,集训,define
From： https://www.cnblogs.com/minecraft666/p/17999257

相关文章

  • 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年上半年软考高级信息系统项目管理师【报名来这】
    信息系统项目管理师是全国计算机技术与软件专业技术资格（水平）考试（简称软考）项目之一，是由国家人力资源和社会保障部、工业和信息化部共同组织的国家级考试，既属于国家职业资格考试，又是职称资格考试。信息系统项目管理师，属于软考三个级别中的“高级”。 【报考要求】 不设学历与资历条......
  • 2024年深圳/东莞CPDA数据分析师认证【这里靠谱】
    CPDA数据分析师认证是大数据方面的认证，助力数据分析人员打下扎实的数据分析基础知识功底，为入门数据分析保驾护航。帮助数据分析人员掌握系统化的数据分析思维和方法论，提升工作效率和决策能力，遇到问题能够举一反三，为大部分决策难题提供解决方案。帮助数据分析人员掌握几种通用的数据......
  • 2024年西安/厦门/杭州/深圳DAMA-CDGA/CDGP数据治理认证【招生】
    DAMA认证为数据管理专业人士提供职业目标晋升规划，彰显了职业发展里程碑及发展阶梯定义，帮助数据管理从业人士获得企业数字化转型战略下的必备职业能力，促进开展工作实践应用及实际问题解决，形成企业所需的新数字经济下的核心职业竞争能力。DAMA是数据管理方面的认证，帮助数据从业者提升......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99