Let's play paintingball!

CoronaQL · 2021-06-12 20:32:33 · 题解

题目大意

我们有一把枪，然后要保证击中所有奶牛，题目详细看这儿题目传送门

蒟蒻思路

蒟蒻首先是无脑的打了一遍大模拟，然后就TLE！这证明我们不能直接模拟。

于是蒟蒻换了一种思路枚举，再来一次，于是就A了A了。 蒟蒻主要降低了时间复杂度，不然肯定超时。

AC代码

#include<bits/stdc++.h>
using namespace std;
int arr[110][110];
int n,k,ans=0;
void run(int x,int y)//测位函数
{
    int m=x-1,c=y-1,t=y+1;
    while(m>0)
    {
        arr[m][y]++;
        if(c>0) 
        arr[m][c]++;
        if(t>0&&t<=n) 
        arr[m][t]++;
                m--;
        c--;
        t++;
    }
    for(int j=1;j<=n;j++) 
    arr[x][j]++;
        m=x+1;
    c=y+1;
    t=y-1;
    while(m<=n)
    {
        arr[m][y]++;
        if(c>0&&c<=n) 
        arr[m][c]++;
        if(t>0) 
        arr[m][t]++;
                m++;
        c++;
        t--;
    }
}
int main()
{
    scanf("%d %d",&n,&k);
    for(int i=1,x,y;i<=k;i++)
    {
        scanf("%d %d",&x,&y);
        run(x,y);//从图x,y开始
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(arr[i][j]>=k) 
            {
                ans++;//打擂台，比大小不过那就多一个答案
            }
        }  
    }    
    printf("%d",ans);//输出的是ANS
}