初中信息奥赛模拟测试

T1 ZEW 玩扫雷

\(n\) 和 \(m\) 都是小的，枚举即可。

#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
using namespace std;
const int N=1010;
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);
}
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,sum[N][N];
char a[N][N];
signed main()
{
	#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    read(n),read(m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j]=='.')
            {
                if(i-1>0&&j-1>0&&a[i-1][j-1]=='*') sum[i][j]++;
                if(i-1>0&&j>0&&a[i-1][j]=='*') sum[i][j]++;
                if(i-1>0&&j+1<=m&&a[i-1][j+1]=='*') sum[i][j]++;
                if(i>0&&j-1>0&&a[i][j-1]=='*') sum[i][j]++;
                if(i>0&&j+1<=m&&a[i][j+1]=='*') sum[i][j]++;
                if(i+1<=n&&j-1>0&&a[i+1][j-1]=='*') sum[i][j]++;
                if(i+1<=n&&j+1<=m&&a[i+1][j+1]=='*') sum[i][j]++;
                if(i+1<=n&&j>0&&a[i+1][j]=='*') sum[i][j]++;
            }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            if(a[i][j]=='.') cout<<sum[i][j];
            else cout<<a[i][j];
        cout<<endl;
    }
}

• 注意 当 \(a_{i,j}\) 是 \("."\) 时，他周围可能一个地雷也没有，那么此时 \(sum_{i,j}\) 就是 \(0\)。
  所以最后输出时，一定不能是

  if(sum[i][j]!=0) cout<<sum[i][j];
  

  不然所有的 \(0\) 都会输出成 \("."\)，像这样：

所以这道题爆零了 \(qwq\)

T2 ZEW 的游戏

显然所有平行的直线中只能要一个。

那么我们可以通过 \(\dfrac{y_i-y_j}{x_i-x_j}\) 求出斜率 \(k\)，所以就是求能求出的 \(k\) 的个数。

所以可以先把所有的直线的 \(k\) 都求出来，之后可以排序再去重，也可以用 \(map\)。

建 \(map\) 时 \(<>\) 内第一个是下标（ \(key\) ），第二个是返回值（ \(value\) ）。

#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
using namespace std;
const int N=1010;
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);
}
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,ans,tot;
double c[N*N];
struct aa
{
    int x,y;
}e[N];
map<double,bool>q;
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(e[i].x),read(e[i].y);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            if(e[i].x!=e[j].x) c[++tot]=(double)(e[i].y-e[j].y)/(e[i].x-e[j].x);
            else c[++tot]=0x7f7f7f;
            if(!q[c[tot]]) ans++;
            q[c[tot]]=1; 
        }
    cout<<ans;
}

\(k\) 一定要是 \(double\)，所以代码中第 \(35\) 行括号里的 \(double\) 一定要加，\(\times 1.0\) 不好使 \(qwq\)

所以也爆零了

T3 ZEW 学分块

可以用双指针，定义 \(l,r\)。

枚举第二个分割点 \(r\)，由此将 \(r\) 固定住，再去搞前两个分块。

而当前两个块差值最小的时候，也就是他们两个中最大值最小的时候，那么去找到第一个左块大于右块的 \(l\) 和最后一个左块小于右块的 \(l\)，选择他们之中最优的那一个，去更新 \(ans\)。

通过赛时打出的暴力，我们知道每种情况的 \(ans\) 呈一个不规则的二次函数形状，所以出现第一个当前 \(ans\) 大于等于已经推出的 \(ans\) 时，就可以 \(break\) 了。

#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
using namespace std;
const int N=5e7+10;
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);
}
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,a[N],sum[N],l,r,ans=0x7f7f7f7f;
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]),
        sum[i]=sum[i-1]+a[i];
    l=1,r=2;
    while(r<n)
    {
        while(sum[l]<sum[r]-sum[l]&&l<r) l++;
        if(min({max({sum[l],sum[r]-sum[l],sum[n]-sum[r]}),max({sum[l-1],sum[r]-sum[l-1],sum[n]-sum[r]})})>=ans) break;
        ans=min({ans,max({sum[l],sum[r]-sum[l],sum[n]-sum[r]}),max({sum[l-1],sum[r]-sum[l-1],sum[n]-sum[r]})});
        r++;
    }
    cout<<ans;
}

• 直接暴力的话超时 \(40\) 分，虽然根据他呈不规则二次函数而加了 \(n\) 个 \(break\) 。( \(n\) 是虚数)
• 至于数据范围中给了一个 \(1\le a_i\le 233\)，所以隔壁 @\(minecraft666\) 直接暴力枚举 \(233^2\)，然后 \(A\) 掉了，就很离谱 。
• 当然这道题正解应是二分答案，但 \(m=3\)，所以双指针也是可以的。

T4 ZEW 玩 thd

\(\Huge 不会\)