题解：CF2157B Expansion Plan 2

Hog_Dawa_IOI · 2025-11-24 19:54:14 · 题解

题目大意

一个无限大的网格，一开始只有 (0,0) 是黑色的，其它都是白色的。给一个长度为 n 的字符串，按顺序进行操作：

• 如果该字符串第 i 位是 4，那么与黑方块四连通的方块都会变为黑色。
• 否则，与黑方块八连通的方块都会变为黑色。

“四连通”指的是上下左右，“八连通”则不仅有上下左右，还有左上角、左下角、右上角、右下角四个角。
最后问你坐标 (X,Y) 的颜色。

解法

画图手玩样例后可发现，最后形成的图是一个正方形，且四个角被挖去了。
正方形的“半径”就是 n，所以如果不在这个“正方形”内的一定是白色。
我们研究四个角有什么性质。它有点像一个“阶梯”，而高度（和宽度）为数字 4 出现的次数。
为什么？一个数字 8 相当于把原图形的外面都套了一大圈，而一个数字 4 相当于会在四个边角留下一些空缺。
于是判断 (X,Y) 是否在四个空缺中即可。判断的方法也很简单，找到正方形的四个顶点，到它的曼哈顿距离 < cnt，其中 cnt 是数字 4 的个数。

#include<stdio.h>
int t,n,x,y,cnt;char s[200005];
int abs(int x){return x>0?x:-x;}
int main()
{
    scanf("%d",&t);while(t--)
    {
        scanf("%d%d%d%s",&n,&x,&y,s+1),cnt=0;
        for(int i=1;i<=n;i++) cnt+=(s[i]=='4');
        if(abs(x)>n||abs(y)>n)
        {printf("NO\n");continue;}
        int xx=-n,yy=-n;
        if(x-xx+y-yy<cnt) 
        {printf("NO\n");continue;}
        xx=n,yy=-n;
        if(xx-x+y-yy<cnt) 
        {printf("NO\n");continue;}
        xx=-n,yy=n;
        if(x-xx+yy-y<cnt) 
        {printf("NO\n");continue;}
        xx=n,yy=n;
        if(xx-x+yy-y<cnt) 
        {printf("NO\n");continue;}
        printf("YES\n");
    }
}