水题三章(2020初二创新班模拟赛(2020.12.19))

  • 时间:
  • 来源:互联网
  • 文章标签:

老久没上课了,于是LGJ出了三道水题。



第1题 云杉树

给出 n n n m m m 列的二维字符数组,每个元素是 ∗ * 或者 . . .
小马想着云杉树
1、云杉树所包含的元素必须都是 ‘ ∗ ’ ‘*’

2、假设云杉树的最高点格子是 ( x , y ) (x,y) (x,y)

3、那么对于所有的 1 ≤ i ≤ K 1 \le i \le K 1iK ,第 x + i − 1 x+i-1 x+i1 行的第 y − i + 1 y-i+1 yi+1 至第 y + i − 1 y+i-1 y+i1 列的所有格子都必须是 ‘ ∗ ’ ‘*’

下图中前 3 3 3 棵是云杉树,后两棵不是。
示例

你要统计二维数组里面有多少棵不同的云杉树。


输入格式

第一行,两个正整数 n n n m m m 1 ≤ n , m ≤ 2000 1 \le n,m \le 2000 1n,m2000
接下来是 n n n m m m 列的二维字符数组。
对于 80 % 80\% 80% 的数据, 1 ≤ n , m ≤ 50 1 \le n,m \le 50 1n,m50


输出格式

一个整数。


输入/输出样例1

输入:

4 5
.***.
*****
*****
.*.*.

输出:

23

样例解释


此题正解是 O ( m n ) O(mn) O(mn) 的时间复杂度,但是由于数据过水, O ( n 2 m 2 ) O(n^2m^2) O(n2m2) 也能过,这里就不讲了。看题目的同学都知道枚举云杉树的最高点,但是,这样子就没有办法形成一个递推关系,只能一个一个枚举。加上前缀和,时间复杂度 O ( n 2 m ) O(n^2m) O(n2m) 过不了。
我们可以换种方法想。我们可以枚举一棵云杉树的最右下方的节点。
假如我们枚举到了第 ( i , j ) (i,j) (i,j) 的位置,那么自己上一层的节点是 ( i − 1 , j − 1 ) (i-1,j-1) (i1,j1) 。如果当前节点前缀和大于等于上一层节点前缀和加一,那么以当前节点为树的一端能判定的云杉树个数是上一层个数加一(自己单独一个节点也算一棵)。
示例2
否则,可形成的云杉树只有前缀和的一半(向上取整)。
示例3
值得注意的是,前缀和必须是连续的,否则不计。为了方便判断,可以在两种情况间取 m i n min min 值。

Code:

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[2005][2005];
int q[2005][2005];
int f[2005][2005];
int ans;
int main()
{
	cin>>n>>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++)
	{
		int sum=0;
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]=='*') q[i][j]=++sum;
			else q[i][j]=sum=0;
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			f[i][j]=min(f[i-1][j-1]+1,q[i][j]/2+bool(q[i][j]%2)),ans+=f[i][j];
	cout<<ans;
	return 0;
}


第2题 排列实验

给出包含 n n n 个元素的数组 a [ 1.. n ] a[1..n] a[1..n] ,而且知道该数组保存的元素就是 n n n 的一个排列。例如: [ 2 , 3 , 1 , 5 , 4 ] [2,3,1,5,4] [2,3,1,5,4] 5 5 5 的一个排列。

[ 1 , 2 , 2 ] [1,2,2] [1,2,2] 不是排列,因为 2 2 2 出现了两次。 [ 1 , 3 , 4 ] [1,3,4] [1,3,4] 不是排列,因为数组有 3 3 3 个元素,但是数组里面出现了元素 4 4 4
小马看图
现在依次进行 m m m 次实验,第 i i i 次实验的格式是这样的:给出 R i R_i Ri P i P_i Pi ,表示对数组 a [ 1 ] a[1] a[1] a [ R i ] a[R_i] a[Ri] 这一段数进行实验,实验有 P i P_i Pi 的概率会成功,如果实验成功,那么数组 a [ 1 ] a[1] a[1] a [ R i ] a[R_i] a[Ri] 会从小到大排好序;如果实验失败,那么数组 a [ 1 ] a[1] a[1] a [ R i ] a[R_i] a[Ri] 不变。问依次进行完 m m m 次实验之后,数组 a a a 是升序数组的概率是多少。


输入格式

第一行,两个正整数 n n n m m m 1 ≤ n , m ≤ 100000 1 \le n,m \le 100000 1n,m100000
第二行, n n n 个整数,第 i i i 个整数是 a [ i ] a[i] a[i] 1 ≤ a [ i ] ≤ n 1 \le a[i] \le n 1a[i]n ,且所有 a [ i ] a[i] a[i] 互不相同。
接下来有 m m m 行,第 i i i 行是 R i R_i Ri P i P_i Pi 1 ≤ R i ≤ n , 0 ≤ P i ≤ 1 1 \le R_i \le n,0 \le P_i \le 1 1Rin,0Pi1


输出格式

一个实数,误差不超过 0.000001 0.000001 0.000001


输入/输出样例1

输入:

4 2
1 2 3 4
2 0.5
4 0.1

输出:

1.000000

输入/输出样例2

输入:

6 5
1 3 2 4 5 6
4 0.9
5 0.3
2 0.4
6 0.7
3 0.5

输出:

0.989500

输入/输出样例3

输入:

5 3
4 2 1 3 5
3 0.8
4 0.6
5 0.3

输出:

0.720000

样例解释

这一题相对来说更水,稍微动一下脚趾头,就知道实验的成功完全没有前效性和后效性。既然次次实验不会互相影响,那么实验如何成功呢?
就如说我这次实验可以排序 1 1 1 R i R_i Ri 的数字,如果可能成功,那么从 R i + 1 R_i+1 Ri+1 n n n 一定是有序的。反过来说,如果一开始数组区间 a [ q . . n ] a[q..n] a[q..n] 是有序的,那么能排序区间 a [ 1.. q − 1 ] a[1..q-1] a[1..q1] 的实验才可能成功。

因为只要一次试验成功就行了,所以实验成功概率就是 1 1 1 减去全部可能的实验失败的概率的乘积。
注意一下特判,如果数组本身就是有序的,就不用算了。

Code:

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100005];
double ansp=1.0;
int main()
{
	cin>>n>>m;
	int p=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]!=i) p=1; 
	} 
	if(p==0)
	{
		cout<<"1.000000"<<endl;
		return 0;
	}
	int pl;
	for(pl=n;pl>=1;pl--) if(a[pl]!=pl) break;
	pl++;
	for(int i=1;i<=m;i++)
	{
		int en;
		double p;
		cin>>en>>p;
		if(en>=pl-1) ansp=(1.0-p)*ansp*1.0;
	}
	printf("%.6f",1.0-ansp);
	return 0;
}


第3题 分裂数组

给出包含 n n n 个元素的数组 A [ 1... n ] A[1...n] A[1...n] 。你希望数组的所有元素加起来的结果等于 S S S 。因为 A A A 数组可能不满足这个要求,所以你可以尝试进行分裂数组来达到目标。分裂数组是这样定义的:

  1. M a x = m a x { A [ 1 ] , A [ 2 ] , . . . . . . A [ n ] } , M i n = m i n { A [ 1 ] , A [ 2 ] , . . . . . . A [ n ] } Max = max\{A[1],A[2],......A[n]\}, Min = min\{A[1],A[2],......A[n]\} Max=max{A[1],A[2],......A[n]},Min=min{A[1],A[2],......A[n]}

  2. m i d = ( M a x + M i n )   d i v   2 mid = (Max+Min)\ div\ 2 mid=(Max+Min) div 2,注意 d i v div div 是表示整除的意思;

  3. A A A 数组会分裂为两个数组: B B B C C C

  4. A A A 数组里面所有小于等于 m i d mid mid 的元素,都按照原来相对的次序,放入到 B B B 数组;

  5. A数组里面所有大于 m i d mid mid 的元素,都按照原来相对的次序,放入到 C C C 数组;

  6. 如果此时 B B B 数组所有元素的总和等于 S S S ,或者此时 C C C 数组所有元素的总和等于 S S S ,那么就完成目标了,结束;

  7. 如果第 6 步不成立,那么你面临二选一的抉择:要么只保留 B B B 数组,要么只保留 C C C 数组;

  8. 保留下来的那个数组,就变成了新的 A A A 数组,重复第 1 步,直到达到目标,或者不可能完成目标。

通过上面的分裂数组,假如每次你都能作出足够聪明的抉择,是否能完成目标?如果可以输出 Y e s {\rm} Yes Yes ,否则输出 N o {\rm} No No


输入格式

第一行,两个正整数 n n n Q Q Q 1 ≤ n , Q ≤ 100000 1 \le n,Q \le 100000 1n,Q100000 Q Q Q 表示有 Q Q Q个独立的询问,对每一个询问,你要输出答案。

第二行, n n n 个整数,第 i i i 个整数是 A [ i ] A[i] A[i] 1 ≤ A [ i ] ≤ 1 0 6 1 \le A[i] \le 10^6 1A[i]106

接下来有 Q Q Q 行,第 i i i 行一个整数 S i S_i Si ,表示能否通过分裂 A A A 数组得到 S i S_i Si 。注意:每一个询问都是独立的,每一个询问的一开始, A A A 数组都是输入数据读入的那个 A A A 数组。


输出格式

Q Q Q 行,每行一个字符串,“Yes” 或 “No” ,双引号不用输出。


#####输入/输出例子1
输入:

5 5
3 1 3 1 3
1
2
3
9
11

输出:

No
Yes
No
Yes
Yes

样例解释

很容易发现,无论数组的顺序怎么变,每一次分裂的 M i n Min Min 值和 M a x Max Max 值是不会变的,所以我们先把它排序,然后进行数组分裂,把所有可能的答案记录下来,直接离线。其中分裂和查找的时候要用二分。
注意输入输出用 scanf 和 printf ,不然会超时。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000005];
long long sum[1000005];
long long ans[2000005],e;
void split(int l,int r)
{
	if(l==r) {ans[++e]=a[l];return;}
	long long x=(a[l]+a[r])>>1;
	if(x>=a[r]) return;
	int pr=r,pl=l-1;
	while(pl+1<pr)
	{
		int mid=(pl+pr)>>1;
		if(a[mid]<=x) pl=mid;
		else pr=mid;
	}//二分,也可以提前标记
	ans[++e]=sum[pl]-sum[l-1];
	ans[++e]=sum[r]-sum[pl];
	split(l,pl);
	split(pr,r);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
	ans[++e]=sum[n];
	split(1,n);
	sort(ans+1,ans+e+1);
	for(int i=1,s;i<=m;i++)
	{
		scanf("%d",&s);
		int l=0,r=e;
		while(l+1<r)
		{
			int mid=(l+r)>>1;
			if(ans[mid]>=s) r=mid;
			else l=mid;
		}//再次二分
		if(ans[r]==s) printf("Yes\n");
		else printf("No\n");//输出用printf
	}
	return 0;
}


小结

是挺水的,迟了半小时考,280分,第一题 O ( n 2 m 2 ) O(n^2m^2) O(n2m2) 水过,第三题最后一个点超时。我果然还是太菜了。做题都最好打 scanf 和 printf 吧。
如果CHJ大佬来了肯定AK。

本文链接http://www.taodudu.cc/news/show-1944861.html