題目思路

這道題是一道非常典型的CCF-CSP認證前兩題的題目，主要考察對二維坐標的標記和對標記的查詢。

把輸入的點全部利用數組存儲起來，然后對所有的點進行位置標記。接著，我們去按順序訪問所有有垃圾的點(x,y)，對于每個點，我們都有以下操作：

• 根據該點判斷該點是否適合作為垃圾點。如果合適就進行下個操作；否則，訪問下一個點。
• 根據四個對角位置存在多少處垃圾對該回收站點進行評分，接著該分數的站點數加一。

對于坐標點的存儲，可以定義 $Point$ 結構體，也可以直接用C++ STL提供的 $pair<int,int>$ 進行存儲。下面代碼中對于兩種方法都有涉及，其實只用一種就夠了，但是如果只用定義 $Point$ 結構體的方法的話，需要重載==運算符；

對于點的標記，可以考慮用C++ STL提供 $set$ 或者 $map$，也可直接用數組順序存儲標記，但是每次查找都需要用 $O(n)$ 的時間復雜度去遍歷。

坑點：

• 雖然點的個數不多，但是單個點的坐標可以到 $10^9$，所以不能直接開二維數組來進行地圖標記。

代碼如下

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int maxn = 1e3 + 10; struct Point {int x, y; } p[maxn]; set<pair<int, int> > vis;int n, score[10];/*** 判斷點(x, y)是否適合作為回收站* 如果適合，就返回1；否則返回0*/ int isSuit(int x, int y) {if (!vis.count(pair<int , int>(x + 1, y))) return 0; if (!vis.count(pair<int , int>(x - 1, y))) return 0;if (!vis.count(pair<int , int>(x, y + 1))) return 0;if (!vis.count(pair<int , int>(x, y - 1))) return 0;return 1; } /*** 計算點(x, y)作為回收站可以得到的評分* 返回評分*/ int getScore(int x, int y) {int res = 0;if (vis.count(pair<int , int>(x + 1, y + 1))) res++;if (vis.count(pair<int , int>(x + 1, y - 1))) res++;if (vis.count(pair<int , int>(x - 1, y + 1))) res++;if (vis.count(pair<int , int>(x - 1, y - 1))) res++;return res; }int main() {//freopen("2.txt", "r", stdin);scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d %d", &p[i].x, &p[i].y);vis.insert(pair<int, int>(p[i].x, p[i].y));}for (int i = 1; i <= n; i++) {if (isSuit(p[i].x, p[i].y)) {score[getScore(p[i].x, p[i].y)]++;}}for (int i = 0; i <= 4; i++) printf("%d\n", score[i]);return 0; }

總結

以上是生活随笔為你收集整理的ccf-csp #201912-2 回收站选址的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。