题解 P2038 【无线网络发射器选址】

Snowflake_Pink

2019-01-31 23:56:29

Solution

## [题面](https://www.luogu.org/problemnew/show/P2038) * 分析:洛谷上已经标了这是一道橙题,所以我就以非常不屑的心态做了这道题,然后就$WA \times 3$了~~(嘤嘤嘤)~~。这道题最大的坑点是**你可以把信号放在地图之外**!!我刚开始也想到这一点,但是你把信号放在地图之外肯定不能保证题中所要求的的最优解,所以我就直接忽略这种情况了。这种想法是错误的,我用一张图告诉你为什么: ![捕获.PNG](https://i.loli.net/2019/01/31/5c5316e8d9c98.png) **所以这就是大多数人70分的原因!!!**(好骄傲啊~~) * Code: ```cpp #include <iostream> #include <cstdio> #define INF 999999999 using namespace std; inline int in(){//这是读入优化,我比较强迫症,所以就加了,在这个数据范围是快读没什么大的影响。 int X=0,w=0; char ch=0; while(!isdigit(ch)) {w|=ch=='-';ch=getchar();} while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } int data[200][200],d,n,sum,Max=-INF; int main(){ d=in(); n=in(); for (int i=1;i<=n;i++){ int x,y; x=in();//题解里面有位dalao说这里的x和y要换一下(你看一下题目就知道了) y=in();//但是没必要,因为整张图是正方形,换不换对答案没影响 data[x+20][y+20]=in();//这里因为懒得判断是否越界,所以就直接+20了,20不是随便加的,去看d的取值范围 } for (int i=0;i<=128;i++) for (int j=0;j<=128;j++){ int t=0; for (int k=i-d+20;k<=i+d+20;k++) for (int l=j-d+20;l<=j+d+20;l++){ t+=data[k][l]; } if (t>Max){ Max=t; sum=1; } else if (t==Max) sum++; } printf("%d %d\n",sum,Max); return 0; } ``` * 记住!!在$OI$的任何一道题中,都不要以不屑的态度去做每一道题,不然就不是你$AK$题目,是题目$AK$你。 $PS$:如果题解有问题请私信我哦~~