赛后——2.14 寒假模拟10

\(\text{T1}\) 正方形

题意

小 \(S\) 有一个二维平面,上面有 \(n\) 个点。

现在,小 \(S\) 想用一个长和宽都平行于坐标轴的正方形去覆盖所有点,求正方形的最小面积。

思路

\(S=(\max(x_{\max}-x_{\min},y_{\max}-y_{\min}))^2\)

代码

点击查看代码
int main(){
	n=read();
	maxx=maxy=-1,minx=miny=2000;
	for(int i=1;i<=n;i++){
		int x=read(),y=read();
		maxx=max(maxx,x),minx=min(minx,x);
		maxy=max(maxy,y),miny=min(miny,y);
	}
	int ans=max(maxx-minx,maxy-miny);
	printf("%d\n",ans*ans);
	return 0;
}

\(\text{T2}\) 玩蛇

题意

小 \(S\) 画了一个高度为 \(n\) 的三角形,从上到下第 \(i\) 层的宽度为 \(i\)。

接着小 \(S\) 将一个字符串 \(T\) 蛇形的循环填入三角形,例如 \(n=6,T=\text{JANJETINA}\) 时,三角形为:

\(\text{J}\)
\(\text{NA}\)
\(\text{JET}\)
\(\text{JANI}\)
\(\text{ANJET}\)
\(\text{NAJANI}\)

现在有 \(Q\) 次询问,每次询问要去第 \(k\) 行字符 \(c\) 出现了多少次?

思路

赛时瞎搞用分块优化疯狂挂分。

首先我们发现这东西可以取模然后把左右的零散串暴力算出来,发现 \(|S|\le 10^6\),因此需要前缀和。

做完了,赛时真是智障。

代码

点击查看代码
int main(){
	n=read();
	scanf("%s",s+1);
	len=strlen(s+1);
	for(int i=1;i<=len;i++){
		for(int j=1;j<=26;j++){
			sum[i][j]=sum[i-1][j];
		}
		sum[i][s[i]-'A'+1]++;
	}
	q=read();
	while(q--){
		ll k=read(),ans=0;
		char c;
		cin>>c;
		ll l,r;
		if(k&1) l=(((k-1)/2%len)*(k%len)+1)%len;
		else l=(((k/2)%len)*((k-1)%len)+1)%len;
		r=(l+k-1)%len;
		if(!l) l=len;
		if(!r) r=len;
		if(l<r&&k<=len) ans=sum[r][c-'A'+1]-sum[l-1][c-'A'+1];
		else{
			ll num=k-(len-l+1)-r;
			ans=(num/len)*sum[len][c-'A'+1];
			ans+=sum[r][c-'A'+1]+sum[len][c-'A'+1]-sum[l-1][c-'A'+1];
		}
		printf("%lld\n",ans);
	}
	return 0;
}

\(\text{T3}\) 嗷呜

题意

思路

代码

\(\text{T4}\) 开车

题意

思路

代码

上一篇:H 指数


下一篇:【一起来学java数据结构】——排序