首页 > 其他分享 >4.【初中信息奥赛模拟测试】

4.【初中信息奥赛模拟测试】

时间：2024-01-14 18:12:18浏览次数：29  
标签：int long read 奥赛 ans 初中 inline 模拟 define

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

初中信息奥赛模拟测试

T1 ZEW 玩扫雷

\(100pts\)

  • 定义 \(\large ans_i{_,}{_j}\) 为如果 \((i,j)\) 这个地块不是雷，旁边有多少个雷，枚举每一个点周围八个地块，如果是空地则不变，如果是雷就加一。
  • 时间复杂度为 \(O(n*m)\)
include<bits/stdc++.h>
#define N (10000010)
#define int long long
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<<21,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;
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;}
int e[N],siz[N];
long long qpow(long long x,int b,int P)
{
    long long ans=1;
    for(;b;b>>=1){if(b&1)ans=(ans*x)%P;x=(x*x)%P;}
    return ans;
}
char c[1010][1010];
int a[1010][1010],n,m;
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    //n=read(),m=read();
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i(1);i<=n;++i)
        for(int j(1);j<=m;++j)
            cin>>c[i][j];
    for(int i(1);i<=n;++i)
        for(int j(1);j<=m;++j)
        {
            if(c[i][j]=='.')
            {
                if(c[i][j-1]=='*')++a[i][j];
                if(c[i][j+1]=='*')++a[i][j];
                if(c[i+1][j]=='*')++a[i][j];
                if(c[i-1][j]=='*')++a[i][j];
                if(c[i+1][j-1]=='*')++a[i][j];
                if(c[i+1][j+1]=='*')++a[i][j];
                if(c[i-1][j-1]=='*')++a[i][j];
                if(c[i-1][j+1]=='*')++a[i][j];
            }
        }
    for(int i(1);i<=n;++i)
    {
        for(int j(1);j<=m;++j)
            if(c[i][j]=='*')cout<<'*';
            else cout<<a[i][j];
        cout<<'\n';
    }
    return 0;
}

T2ZEW 的游戏

\(0pts→(100pts)\) （交错题了）

  • 两条直线不平行，意味着两条直线斜率不相等。斜率 \(\large k=\dfrac{y1-y2}{x1-x2}\) 。特别地，当 \(x1=x2\) 时，需要进行特判。最后枚举每两个点连线可能出现的斜率，再去重即可。
  • \(O(n^2)\)
#include<bits/stdc++.h>
#define sort stable_sort
#define endl '\n'
#define N (1000001)
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<<21,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;
int n,m,a[210][4],len,ans,zero;
long double g[1000010],ls;//直线斜率
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
	n=read();
    for(int i(1);i<=n;++i)
        a[i][1]=read(),a[i][2]=read();
    for(int i(1);i<=n;++i)
        for(int j(i+1);j<=n;++j)
        {
            if(a[j][1]!=a[i][1])
                g[++len]=(double(a[j][2]-a[i][2]))/(a[j][1]-a[i][1]);
            else zero=1,g[++len]=0x7f7f7f;
            //防止x1-x2=0爆掉。
            //防止double炸精度
        }
    sort(g+1,g+1+len);
    ++ans,ls=g[1];
    for(int i(2);i<=len;++i)
        if(g[i]!=ls&&g[i]!=0x7f7f7f)ls=g[i],++ans;//去重
    if(zero)++ans;
    write(ans,' ');
    flush();
    return 0;
}

T3ZEW 学分块

\(10pts→(80pts)→(100pts)\)

  • 错的很抽象，本来暴力能过，结果改成了二分（打错了），改回去之后又发现少打一个 \(min\) 然后超时了……
  • 首先 \(1\leq n\leq 5\times10^6\) ， \(1\leq a_i\leq 233\) 。
  • 首先看出复杂度至少是 \(O(n\log(n))\) 。 因为要分成三段，求出三段中的最大值的最小值，所以想出应该接近于平均分的状态。
  • 所以想到求出两个三等分点，之后再枚举。这时候 \(1\leq a_i\leq 233\) 就有用了。
  • 因为所有的值小于等于 \(233\) ，所以即使三等分点附近都是 \(1\) ，其他地方都是 \(233\) ，那么左右也最多只需要枚举 \(233\) 个点，就能够不漏掉最优解。
#include<bits/stdc++.h>
#define N (5000010)
#define int long long
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<<21,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;
int n,m,t,P;
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 qpow(long long x,int b,int P=P)
{
    long long ans=1;
    for(;b;b>>=1){if(b&1)ans=(ans*x)%P;x=(x*x)%P;}
    return ans;
}
int a[N],sum[N],ti,tj,ans=0x3f3f3f3f3f3f3f;
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    n=read();
    for(int i(1);i<=n;++i)a[i]=read(),sum[i]=a[i]+sum[i-1];
    //都是正整数。三个尽量差不多大
    for(int i(1);i<=n;++i)
        if(sum[i]>=sum[n]/3)
        {
            ti=i;
            break;
        }
    for(int i(n);i;--i)
        if(sum[i]<=(sum[n]<<1)/3)
        {
            tj=i;
            break;
        }
    for(int i(max(1ll,ti-233));i<=min(ti+233,n);++i)
        for(int j(max(1ll,tj-233));j<=min(tj+233,n);++j)
            ans=min(ans,max({sum[i],sum[j]-sum[i],sum[n]-sum[j]}));
    //枚举找一下答案
    write(ans,' ');
    flush();
    return 0;
}
  • 时间复杂度为 \(O(n)\) ，常数为 \(217156\) ，事实上可以过。
  • 不过还能优化一下（但是意义不大）。
  • 求两个三等分点时可以二分。
  • 可以用双指针优化，假设三个区间的值分别为 \((1,i)\) 、 \((i+1,j)\) 、 \((j+1,n)\) 。 当 \((i+1,j)>(j+1,n)\) 且 \((i+1,j+1)>(j+2,n)\) 时， 第二个区间一定不是最优解。
  • 优化后复杂度为 \(O(n+\log(n))\) ，常数为 \(466\) 。
#include<bits/stdc++.h>
#define N (5000010)
#define int long long
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<<21,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;
int n,m,t,P;
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 qpow(long long x,int b,int P=P)
{
    long long ans=1;
    for(;b;b>>=1){if(b&1)ans=(ans*x)%P;x=(x*x)%P;}
    return ans;
}
int a[N],sum[N],ti,tj,ans=0x3f3f3f3f3f3f3f;
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    n=read();
    for(int i(1);i<=n;++i)a[i]=read(),sum[i]=a[i]+sum[i-1];
    int l(1),r(n);
    for(;l<=r;)
    {
        int mid=l+r>>1;
        if(sum[mid]>=sum[n]/3)r=mid-1,ti=mid;
        else l=mid+1;
    }
    l=1,r=n;
    for(;l<=r;)
    {
        int mid=l+r>>1;
        if(sum[mid]<=(sum[n]<<1)/3)l=mid+1,tj=mid;
        else r=mid-1;
    }
    for(int i(max(1ll,ti-233)),j(max(1ll,tj-233));i<=min(ti+233,n)&&j<=min(tj+233,n);++i,--j)
        while(sum[j]-sum[i]<sum[n]-sum[j]&&j<=min(tj+233,n))
            ans=min(ans,max({sum[i],sum[++j]-sum[i],sum[n]-sum[j]}));
    write(ans,' ');
    flush();
    return 0;
}
  • 这个题还有一个 \(O(\large n\log_2(\sum\limits_{i=1}^na_i))\) 的解法（通用解法），也就是二分答案，具体可以看 \(Shadow\) 的博客。

T4ZEW 玩 thd

\(20pts\)

  • 首先贪心，争取让塔多输出，剩下的时间就能留给打别人。
  • 设 \(t_i\) 为第 \(i\) 个小兵被打到残血（ \(1\le t_i\le q\) ，死了是不算残血的）塔需要打的秒数，所以 \(\large t_i=\lfloor(\dfrac{h_i}{q}+1)\rfloor\) 。再求出 \(z_i\) 为 \(ZEW\) 打残血小兵需要的秒数。所以 \(\large z_i=\lceil \dfrac{h_i\mod q}{p} \rceil\) 当然，如果 \(q|h_i\) ， \(\large z_i=\lceil\dfrac{q}{p}\rceil\) 。
  • 然后就有两种可能，一种打不死，一种打死了，得到钱（废话）。
  • 所以设 \(\large f_i{_,}{_j}\) 为打到第 \(i\) 个小兵，第 \(j\) 秒时，得到的钱。第一种 \(\Large f_i{_,}{_{j+t_i+1}}=\max(f_i{_,}{_{j+t_i+1}},f_{i-1}{_,}{_{j}})\) 。 \(j+t_i+1\) 就是 \(i-1\) 死了之后， \(i\) 存活的秒数。第二种首先要判断是否能打死，即 \(j-(z_i-t_i)\geq0\) 后再求 \(\Large f_i{_,}{_{j-z_i+t_i}}=\max(f_i{_,}{_{j-z_i+t_i}},f_{i-1}{_,}{_j}+g_i)\) 也就是比较杀掉 \(i\) 赚钱还是不杀 \(i\) 杀别人更赚钱。
  • 最后输出最大值即可。
  • 当然可以滚动数组优化，因为求 \(i\) 只需要从 \(i-1\) 的状态推过去。
  • \(\Large O(\sum\limits_{i=1}^n(t_i+1))\)
#include<bits/stdc++.h>
#define N (100010)
#define sort stable_sort
#define int long long
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<<21,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;
int n,m,p,q;
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 qpow(long long x,int b,int P)
{
    long long ans=1;
    for(;b;b>>=1){if(b&1)ans=(ans*x)%P;x=(x*x)%P;}
    return ans;
}
int maxx,sum[N],gun;
int f[3][20010];
struct aa
{
    int a,b,t,z,rk;
}e[N];
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    p=read(),q=read(),n=read();
    for(int i(1);i<=n;++i)
        e[i].a=read(),e[i].b=read(),
        e[i].t=(e[i].a%q)?(e[i].a/q):(e[i].a/q-1),
        e[i].z=(e[i].a%q)?ceil(1.0*(e[i].a%q)/p):ceil(1.0*q/p),
        sum[i]=sum[i-1]+e[i].t;
        //a[i]=read(),b[i]=read(),t[i]=q/a[i],z[i]=(a[i]%q)/p;
    //t[i]表示让塔打到残血需要多久，z[i]表示打残血ZEW需要打多久。
    //注：残血不算0，即从1到q是残血。
    //那么t[i]是可以节省下来的时间，可以留着时间给钱多的。
    //sum[i]是t[i]的前缀和。
    //其实是背包DP
    memset(f,-0x3f,sizeof(f));
    f[0][1]=0;
    for(int i(1);i<=n;++i)//第i个兵
    {
        gun^=1;
        for(int j(0);j<=sum[n]+n;++j)//过了多少秒
        {
            f[gun][j+e[i].t+1]=max(f[gun][j+e[i].t+1],f[gun^1][j]);//不屑于打死他，直接转移。
            if(j-(e[i].z-e[i].t)>=0)//有时间把他噶了拿钱
                f[gun][j-e[i].z+e[i].t]=max(f[gun][j-e[i].z+e[i].t],f[gun^1][j]+e[i].b);
        }
    }
    for(int i(0);i<=sum[n]+n;++i)
        maxx=max(maxx,f[gun][i]);
    write(maxx,' ');
    flush();
    return 0;
}

标签：int,long,read,奥赛,ans,初中,inline,模拟,define
From： https://www.cnblogs.com/minecraft666/p/17963700

相关文章

  • 初中信息奥赛模拟测试
    初中信息奥赛模拟测试T1ZEW玩扫雷\(n\)和\(m\)都是小的，枚举即可。#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;constintN=1010;template<typenameTp>inlinevoidread(Tp&x){x=0;registerboolz=1......
  • 模拟 - CF1196C Robot Breakout
    RobotBreakout(CF1196C)思路这道题因为平面极大，暴力枚举每个点肯定会超时。所以，我们不妨从机器人出发。我们可以枚举每个机器人可以执行的操作：位置从\((X_i,Y_i)\)变为\((X_i-1,Y_i)\)，即向左走。位置从\((X_i,Y_i)\)变为\((X_i,Y_i+1)\)，即向上走。位置从\((X_......
  • 初中信息奥赛模拟测试
    初中信息奥赛模拟测试\(T1\)ZEW玩扫雷\(100pts\)原题：luoguP2670[NOIP2015普及组]扫雷游戏本题修改：本题的非地雷地区为.。正解chara[1010][1010];intmain(){ //freopen("mine.in","r",stdin); //freopen("mine.out","w",stdout); intn,m,i,j......
  • 初中英语优秀范文100篇-057My Favourite Story-我最喜欢的故事
    初中英语优秀范文100篇-057MyFavouriteStory-我最喜欢的故事PDF格式公众号回复关键字:SHCZFW057记忆树1MyfavoritestoryisTheNightoftheHorse.翻译我最喜欢的故事是《马之夜》简化记忆故事句子结构主语：Myfavoritestory主语是一个名词短语，由形容词"fav......
  • Ubuntu下运行LVGL模拟器
    目录一、前言二、下载并安装VSCode(方法很多，总之装好VSCode就行了)三、获取源码3.2方法一：从Github拉取源码（有梯子）3.3方法二：从Gitee码云拉取源码（无梯子）四、安装LinuxSDL2驱动五、编译源码一、前言​ LVGL是一个可高度可裁剪、低资源占用、界面美观且易用的C语言嵌入式系统......
  • NES 模拟器中音画同步问题
    背景模拟器是与游戏和播放器都有相似之处的系统。模拟器与游戏的相似之处，在于都需要一个采集输入--执行逻辑--然后按一定帧率（通常是60FPS）把画面显示出来的循环。但是模拟器又需要模拟音频设备，播放音频设备产生的声音样本，这点与播放器相似。与播放器一样，模拟器也要处理音、视频......
  • 初中英语优秀范文100篇-056I have the courage to accept the challenge-我有勇气接受
    PDF格式公众号回复关键字:SHCZFW056记忆树1Everyyearthereisasingingcompetitioninourschool.翻译每一年，我们学校都会举行一场歌唱比赛。简化记忆比赛句子结构主语("Everyyear")：表示时间状语的短语，意思是“每年”。谓语("thereis")：这是一个therebe句......
  • 1.11模拟赛 T1题解
    简要题意\(n\le10^3,\sumK_i\le3\times10^5\)思路首先容易想到一个暴力DP，\(f_{l,r,x}\)表示区间中最大值为\(x\)的最大值稍微想亿下可以发现如果这个位置选的不是区间最大值的话，答案一定不优所以我们可以直接\(f_{l,r}\)DP转移，但复杂度还是没变，我们把柿子列出来\(......
  • [ 20230308 CQYC省选模拟赛 T2 ] 塑料内存条
    题意给定\(n\)个不可重集，初始每个集合\(i\)有元素\(c_i\)。请你以下\(3\)种操作：1xy在集合\(x\)插入\(y\)。2xy将\(y\)集合所有数插入\(x\)，并删除\(y\)集合（不影响别的集合的下标）3xy求\(x\)集合与\(y\)集合的交之和。Sol可塑性记忆。注意到前......
  • 1.11模拟赛 T2题解
    简要题意每个点有一定概率向前面的点连边，求两点之间距离的期望思路推柿子code#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineN1000005intn,m,u,v;constintmod=1e9+7;inta[N],sum[N],c[N],dep[N],s[N],f[N],g[N],h[N];intksm(intx......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99