NOIP2014题解

NOIP2014 题解

Day2 T1

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

#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
struct cross{
       int x,y,num;
};
vector<cross> road;
map<int,int> ans;
int main(){
    freopen("wireless.in","r",stdin);
    freopen("wireless.out","w",stdout);
    ios::sync_with_stdio(false);
    int d,n,x,y,k;
    cin>>d>>n;
    for (int i=1;i<=n;i++){
        cin>>x>>y>>k;
        road.push_back((cross){x,y,k});//读入有公共场所的路口
    }
    for (int i=0;i<=128;++i){
        for (int j=0;j<=128;++j){//枚举网格上每一个点
            int temp=0;
            //枚举每一个存在公共场所的路口是否在覆盖范围内，这样最多 129*129*20=332 820 次循环就能求出。
            for (vector<cross>::iterator m=road.begin();m!=road.end();++m){
                if (m->x<=i+d&&m->x>=i-d&&m->y<=j+d&&m->y>=j-d){
                   temp+=m->num;
                }
            }
            if (temp){
               ans[temp]++;
            }
        }
    }
    map<int,int>:: iterator q=ans.end();
    q--;//由于 map 中的数据是排好序（默认从小到大）的，所以最后 map 中的最后一个就是最大的
    cout<<q->second<<" "<<q->first<<endl;
    return 0;    
}

Day2 T2

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

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

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