总结

T1 统计方形

方法1：四层循环找起点和终点，来判断是正方形还是长方形。

时间复杂度：O(n×n×m×m)

方法2：从一个顶点，这个点可能是矩形的左上、右上、左下、右下之一。

时间复杂度：O(n×n)

方法3：既然可以枚举四个顶点，那么可以只枚举一个顶点，这样可以保证每e个方形只被枚举一次，假设枚举右下角顶点。

时间复杂度：O(n×n)

方法4：通过枚举边长继续观察可以发现，每个矩形不是正方形就是长方形，一个矩形由它4条边所在的直线确定，由枚举两条横线和竖线可以确定矩形的总数量。求出正方形后，长方形=总数-正方形数。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	freopen("rect.in","r",stdin);
        freopen("rect.out","w",stdout);
	long long n,m,cut1=0,cut2=0;
	cin>>n>>m;
	for(int i=1;i<=min(m,n);i++)
	{
		cut1=cut1+(n-i+1)*(m-i+1);
	}
	cut2=(n+1)*(m+1)*m*n/4-cut1;
	cout<<cut1<<' '<<cut2; 
return 0;
}

时间复杂度：O(n)

方法5：直接用数学公式算。

时间复杂度：O(1)

T2 说谎者的数量

枚举说谎者的数量，从一开始到人数结束

#include<bits/stdc++.h>
using namespace std;
const int c=1e5+10;
int a[c];
int main()
{
int t,n,ans=0;
cin>>t;
int f=1;
while(t--)
{
f=1;
cin>>n;
for(int j=1;j<=n;j++)
{
cin>>a[j];
}
for(int i=0;i<=n;i++)
{
ans=0;
for(int j=1;j<=n;j++)
{
if(a[j]>i)
{
ans++;
}
}
if(ans==i)
{
cout<<i<<endl;
f=0;
break;
}
}
if(f==1)
{
cout<<"-1"<<endl;
}
}
return 0;
}

T3 珠心算测验

三重循环枚举所有可能：如果a[i]=a[j]+a[c]；那么ans++；最后输出ans即可。

#include<bits/stdc++.h>
using namespace std;
const int N=100+10;
int  a[N];
int b[N];
int main()
{
	freopen("count.in","r",stdin);
        freopen("count.out","w",stdout);
	int n,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=0;
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<i;j++) 
		{
			for(int z=1;z<j;z++)
			{
				if(a[i]==a[j]+a[z]&&z!=j&&j!=i&&b[i]==0)
				{
					ans++;
					b[i]++;
				}
			}
		}
	}
	cout<<ans;
return 0;
}

T4 比例简化

根据L的范围，枚举所有可能的比例组合，判断它们的差是否小于最小值。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	freopen("reduce.in","r",stdin);
        freopen("reduce.out","w",stdout);
	double a,b,l,ap,bp;
	double minn=1e9;
	cin>>a>>b>>l;
	for(double i=1;i<=l;i++)
	{
		for(double j=1;j<=l;j++)
		{
			if(i/j-a/b<minn&&i/j-a/b>=0)
			{
				minn=i/j-a/b;
				ap=i;
				bp=j;
			}
		}
	}
	cout<<ap<<' '<<bp;
	return 0;
}

T5 扫雷游戏

枚举所有数据，如果是'*'。那么直接输出。 如果不是那么输出八个方向上的雷。

#include<bits/stdc++.h>
using namespace std;
const int N=100+10;
char  a[N][N];
int y=0;
int main()
{
	freopen("boom.in","r",stdin);freopen("boom.out","w",stdout);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			sum=0;
			if(a[i][j]=='*')
			{
				cout<<'*';
			}
			else if(a[i][j]=='?')
			{
				if(a[i+1][j]=='*')
				{
					sum++;
				}
				if(a[i-1][j]=='*')
				{
					sum++;
				}
				if(a[i][j+1]=='*')
				{
					sum++;
				}
				if(a[i][j-1]=='*')
				{
					sum++;
				}
				if(a[i-1][j-1]=='*')
				{
					sum++;
				}
				if(a[i+1][j-1]=='*')
				{
					sum++;
				}
				if(a[i-1][j+1]=='*')
				{
					sum++;
				}
				if(a[i+1][j+1]=='*')
				{
					sum++;
				}
				cout<<sum;
			}
		}
		cout<<endl;
	}
return 0;
}