\(\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;
}