HZOI20190828模拟32题解

题面：https://www.cnblogs.com/Juve/articles/11428730.html

chinese：

考虑$\sum\limits_{i=0}^{n*m}i*f_i$的意义:所有方案中炼字的个数之和。

统计答案时可以考虑[1,k]每个字对答案的贡献,即每个字在多少种方案中成为炼字。

在方格的一个确定位置(x,y),字符i对答案的贡献((x,y)位置的数是i且i是炼字的方案数)是

$(i-1)^{n-1}*(i-1)^{m-1}*k^{n*m-n-m+1}$。

由于诗作中的所有位置都是等价的,那么最后的答案就是

$n*m*\sum\limits_{i=0}^{k}(i-1)^{n-1}*(i-1)^{m-1}*k^{n*m-n-m+1}$。

时间复杂度O(k)。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#define int long long

using namespace std;

const int mod=1e9+7;

int n,m,k,ans=0;

int q_pow(int a,int b,int p){

	int res=1;

	while(b){

		if(b&1) (res*=a)%=mod;

		(a*=a)%=mod;

		b>>=1;

	}

	return res%mod;

}

signed main(){

	scanf("%lld%lld%lld",&n,&m,&k);

	for(int i=1;i<=k;i++)

		(ans+=(q_pow(i-1,n-1,mod)*q_pow(i-1,m-1,mod)%mod*q_pow(k,n*m-n-m+1,mod)%mod))%=mod;

	(ans*=(n*m%mod))%=mod;

	printf("%lld\n",ans);

	return 0;

}

physics:

数据过水导致$O(qn^2log_2n)$过了

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#define MAXN 1005

#define re register

using namespace std;

int n,m,q,ans,l,r,mid,sum[MAXN][MAXN],ansi,ansj,x,y;

char ch[MAXN];

inline int read(){

	int a=0;

	char ch=getchar();

	while(ch<'0'||ch>'9') ch=getchar();

	while(ch>='0'&&ch<='9'){

		a=(a<<3)+(a<<1)+ch-'0';

		ch=getchar();

	}

	return a;

}

inline bool judge(re int k){

	for(re int i=1;i<=n-k+1;i++){

		for(re int j=1;j<=m-k+1;j++){

			re int res=sum[i+k-1][j+k-1]+sum[i-1][j-1]-sum[i+k-1][j-1]-sum[i-1][j+k-1];

			if(res==k*k){

				ansi=i,ansj=j;

				return 1;

			}

		}

	}

	return 0;

}

signed main(){

	//freopen("physics4.in","r",stdin);

	n=read(),m=read(),q=read();

	for(re int i=1;i<=n;i++){

		scanf("%s",ch+1);

		for(re int j=1;j<=m;j++){

			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];

			if(ch[j]=='-') continue;

			sum[i][j]++;

		}

	}

	ans=min(n,m),ansi=0,ansj=0;

	while(q--){

		x=read(),y=read();

		for(re int i=x;i<=n;i++){

			for(re int j=y;j<=m;j++)

				sum[i][j]--;

		}

		if(ans!=min(n,m)&&(x<ansi||x>ansi+ans-1||y<ansj||y>ansj+ans-1)){

			printf("%d\n",ans);

			continue;

		}

		l=0,r=ans,ans=0;

		while(l<=r){

			mid=(l+r)>>1;

			if(judge(mid)){

				ans=mid;

				l=mid+1;

			}

			else r=mid-1;

		}

		printf("%d\n",ans);

	}

	return 0;

}

正解：

典型的时光倒流,先将所有待修改的正电荷都修改为负电荷,然后倒序考虑所有修改操作。
考虑如何在较优复杂度内计算最后一次修改后的答案(经典问题):
up_i,j 表示 (i, j) 向上延伸的正电荷的最长长度。
down_i,j 表示 (i, j) 向下延伸的正电荷的最长长度。
可以通过单调栈求出 left_i,j 表示 (i, j) 左面第一个小于 up_i,j 的位
置, right_i,j 表示 (i, j) 右面第一个小于 up_i,j 的位置。
那么问题的答案就是max{min(up_i,j,right_i,j−left_i,j+1)} 。
时间复杂度 O(n²)

对于多次修改操作:
倒序考虑所有操作,如果答案增加,那么一定是由于当前(x, y) 位置负电荷变正电荷造成的。每次修改操作只会影响一列的 up, down ,可以暴力修改。考虑当前负电荷变正电荷后是否存在边长为 k 的正方形,那么问题就转化为是否存在min{up_{x,[i,i+k−1]}}+min{down_{x,[i,i+k−1]}}≥k 。求长度固定的区间的最小值,这就转化成单调队列的经典问题(滑动的窗口)。每次负电荷变正电荷后,可以二分求出由于此次修改造成的更优答案。

时间复杂度$O(n^2+qnlogn)$。

chemistry:

留坑

巴特西

HZOI20190828模拟32题解

最新文章

热门文章