初中信息奥赛模拟测试

\(T1\) ZEW 玩扫雷 \(100pts\)

原题：luogu P2670 [NOIP2015 普及组] 扫雷游戏
- 本题修改：本题的非地雷地区为 . 。

代码

char a[1010][1010];
int main()
{
	//freopen("mine.in","r",stdin);
	//freopen("mine.out","w",stdout);
	int n,m,i,j,sum;
	cin>>n>>m;
	for(j=0;j<=m+1;j++)
	{
		a[0][j]=a[n+1][j]='.';
	}
	for(i=1;i<=n;i++)
	{
		a[i][0]='.';
		for(j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
		a[i][m+1]='.';
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(a[i][j]=='*')
			{
				cout<<"*";
			}
			else
			{
				sum=(a[i-1][j-1]=='*')+(a[i-1][j]=='*')+(a[i-1][j+1]=='*')+(a[i][j-1]=='*')+(a[i][j+1]=='*')+(a[i+1][j-1]=='*')+(a[i+1][j]=='*')+(a[i+1][j+1]=='*');
				cout<<sum;
			}
		}
		cout<<endl;
	}
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

\(T2\) ZEW 的游戏 \(100pts\)

原题：luogu P2665 [USACO08FEB] Game of Lines S

正解

因为一个点可以引多条直线，求互不平行直线个数等价于求不同斜率的个数。
另外的一些细节：求出斜率后不用 double 去存，而是存其对应的最简分式的分子和分母；注意要处理平行于坐标轴的情况；题目中没说是否有重合的点，建议特判，然而并没有构造重点的数据。

bitset<500>vis[500];
map<int,map<int,int> >a;
int x[500],y[500];
int main()
{
	//freopen("game.in","r",stdin);
	//freopen("game.out","w",stdout);
	int n,i,j,d,ans=0,p,q,pd,pd1=0,pd2=0;//pd1存是否有平行于y轴，pd2存是否有平行于x轴
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>x[i]>>y[i];
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(i!=j&&vis[i][j]==0)
			{
				if(x[i]==x[j]&&y[i]==y[j])//题目没有说是否存在重点
				{
					continue;
				}
				vis[i][j]=1;
				p=y[i]-y[j];
				q=x[i]-x[j];
				pd=(p<0)*(q<0);
				if(pd==1)//同时消去分子、分母的负号
				{
					p=-p;
					q=-q;
				}
				else
				{
					if(q<0)//如果斜率为负数，规定分子为负数，分母为正数
					{
						p=-p;
						q=-q;
					}
				}
				if(q==0)
				{
					ans+=(pd1==0);
					pd1=1;
				}
				else
				{
					if(p==0)
					{
						ans+=(pd2==0);
						pd2=1;
					}
					else
					{
						d=__gcd(abs(p),abs(q));//先取abs再求gcd不再多说
						ans+=(a[p/d][q/d]==0);
						a[p/d][q/d]=1;
					}
				}
			}
		}
	}
	cout<<ans<<endl;
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

\(T3\) ZEW 学分块 \(40pts\)

强化版：luogu P1182 数列分段 Section II | luogu P2884 [USACO07MAR] Monthly Expense S
- 本题修改：本题规定 \(m=3\) 。
部分分
- \(40pts\) ：枚举左右端点，没什么好说的。
- \(80pts\) ： @hly_shen 的一个假了的贪心做法，具体做法自己去问吧。

正解

二分答案。

ll a[5000010];
bool check(ll mid,ll n)
{
	ll num=0,ans=0,i;
	for(i=1;i<=n;i++)
	{
		if(num+a[i]<=mid)
		{
			num+=a[i];
		}
		else
		{
			num=a[i];
			ans++;
		}
	}
	return (ans>=3);
}
int main()
{
	//freopen("divide.in","r",stdin);
	//freopen("divide.out","w",stdout);
	ll n,i,l=0,r=0,mid;
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		l=max(l,a[i]);
		r+=a[i];
	}
	while(l<=r)
	{
		mid=(l+r)/2;
		if(check(mid,n)==true)
		{
			l=mid+1;
		}
		else
		{
			r=mid-1;
		}
	}
	printf("%lld\n",l);
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

因本题规定 \(m=3\) ，故也可使用双指针做法，但是我不会双指针，想了解算法的可以去找 @wang54321 问。
- 注：赛时 \(AC\) 的只有 @wang54321 使用了该做法。

\(T4\) ZEW 玩 thd \(10pts\)

部分分
- \(10pts\) ：输出 0 。
- \(20pts\) ：输出 \(\sum\limits_{i=1}^{n}g_i\) 。
正解
- 背包 \(DP\) 。

总结

没有挂分，挺好的。

\(20:40\) 之后基本就在罚坐了，头脑一片空白。

犯了和普及模拟1 T1 Past 一样的问题，没有意识到是原题。之所以出现这个问题，是因为对题目本质的认识不清楚，或者说是没有一个相对模块化的思想。

后记

题目没有 \(\LaTeX\) ，差评。

比赛的时候机房人比平常人多了不少。从奥赛宣讲后，已经过了多半年了，甚至还有人没学文件读写来打 \(OI\) 赛制比赛，难评。\(feifei\) 因有人没学文件读写，而把文件读写删了，导致删后没有重交（误以为 \(OI\) 赛制只能提交一次）的人爆零了，虽然赛后的确安排了重测，但这属实不应该出现在校内考试中。