[关闭]
@fuheimao 2014-11-21T21:20:22.000000Z 字数 939 阅读 703

NOIP2014题解

NOIP2014 题解


Day2 T1

无需判断是否越界的一种方法,就当是学习 C++ vector 和 map 的一个小栗子吧。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<vector>
  4. #include<map>
  5. using namespace std;
  6. struct cross{
  7. int x,y,num;
  8. };
  9. vector<cross> road;
  10. map<int,int> ans;
  11. int main(){
  12. freopen("wireless.in","r",stdin);
  13. freopen("wireless.out","w",stdout);
  14. ios::sync_with_stdio(false);
  15. int d,n,x,y,k;
  16. cin>>d>>n;
  17. for (int i=1;i<=n;i++){
  18. cin>>x>>y>>k;
  19. road.push_back((cross){x,y,k});//读入有公共场所的路口
  20. }
  21. for (int i=0;i<=128;++i){
  22. for (int j=0;j<=128;++j){//枚举网格上每一个点
  23. int temp=0;
  24. //枚举每一个存在公共场所的路口是否在覆盖范围内,这样最多 129*129*20=332 820 次循环就能求出。
  25. for (vector<cross>::iterator m=road.begin();m!=road.end();++m){
  26. if (m->x<=i+d&&m->x>=i-d&&m->y<=j+d&&m->y>=j-d){
  27. temp+=m->num;
  28. }
  29. }
  30. if (temp){
  31. ans[temp]++;
  32. }
  33. }
  34. }
  35. map<int,int>:: iterator q=ans.end();
  36. q--;//由于 map 中的数据是排好序(默认从小到大)的,所以最后 map 中的最后一个就是最大的
  37. cout<<q->second<<" "<<q->first<<endl;
  38. return 0;
  39. }

Day2 T2

由于代码还没写,所以就先写思路吧。

路径上的所有点的出边所指向的点都直接或间接与终点连通。

从终点反向BFS即可得到与终点连通的点。
再遍历一次就可以得到该点是否可以出现在答案路径上(即该点的所有出边所指向的点都直接或间接与终点连通)。
然后求最短路就可以了。

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注