Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"OOOVOOO","updateTime":1562385839000,"title":"虔诚的守墓人","dislikeCnt":0,"content":"# 虔诚的~~掘墓人~~墓主人#\n*[传送门](https://www.lydsy.com/JudgeOnline/problem.php?id\u003d1227)*\n\n-----\n题目描述:\n小W 是一片新造公墓的管理人。公墓可以看成一块N×M 的矩形,矩形的每个格点,要么种着一棵常青树,要么是一块还没有归属的墓地。当地的居民都是非常虔诚的基督徒,他们愿意提前为自己找一块合适墓地。为了体现自己对主的真诚,他们希望自己的墓地拥有着较高的虔诚度。一块墓地的虔诚度是指以这块墓地为中心的十字架的数目。一个十字架可以看成中间是墓地,墓地的正上、正下、正左、正右都有恰好k 棵常青树。小W 希望知道他所管理的这片公墓中所有墓地的虔诚度总和是多少\n\n-----\n输入格式:\n第一行包含两个用空格分隔的正整数N 和M,表示公墓的宽和长,因此这个矩形公墓共有(N+1) ×(M+1)个格点,左下角的坐标为(0, 0),右上角的坐标为(N, M)。第二行包含一个正整数W,表示公墓中常青树的个数。第三行起共W 行,每行包含两个用空格分隔的非负整数xi和yi,表示一棵常青树的坐标。输入保证没有两棵常青树拥有相同的坐标。最后一行包含一个正整数k,意义如题目所示。\n\n-----\n输出格式:\n包含一个非负整数,表示这片公墓中所有墓地的虔诚度总和。为了方便起见,答案对2,147,483,648 取模。\n\n-----\n样例输入:\n5 6\n13\n0 2\n0 3\n1 2\n1 3\n2 0\n2 1\n2 4\n2 5\n2 6\n3 2\n3 3\n4 3\n5 2\n2\n\n-----\n样例输出:\n6\n\n-----\n数据范围与提示:\n图中(图被我吃了),以墓地(2, 2)和(2, 3)为中心的十字架各有3个,即它们的虔诚度均为3。其他墓地的虔诚度为0。\n所有数据满足\n1 ≤ N, M ≤ 1,000,000,000,\n0 ≤ xi ≤ N,\n0 ≤ yi ≤ M,\n1 ≤ W ≤ 100,000,\n1 ≤ k ≤ 10。\n存在50%的数据,满足1 ≤ k ≤ 2\n存在25%的数据,满足1 ≤ W ≤ 10000。 \n注意:”恰好有k颗树“,这里的恰好不是有且只有,而是从\u003e\u003dk的树中恰好选k棵。\n\n-----\n题解:\n\t\t\t\t\t先看一眼数据范围。。。\n\t\t\t\t\t也太不友善了吧,一点都不符合社会主义核心价值观;\n\t\t\t\t\t\u003cfont color\u003d\u0027purple\u0027 size \u003d 3\u003e1 ≤ N, M ≤ 1,000,000,000\u003c/font\u003e,\u003ch6\u003eO(n)都要T飞好不好,所以最终的时间复杂度里一定不能有\u003c/h6\u003e\u003ci class\u003d\"fa fa-spin\"\u003em或n\u003c/i\u003e\n\t\t\t\t\t`mn\u003d1000000000000000000`真的是伤不起,但是却只有`w\u003d100000`棵树。~~这墓地真的是空旷,~~所以要考虑离散化,最后有w行w列。\n\t\t\t\t\t同时我们会发现`wlogw\u003d1660964.047443681`貌似还是可行的。\n\t\t\t\t\t那么就要凑这个时间复杂度。\n\t\t\t\t\t于是问题来了:\n\t\t\t\t\t一共有`w`行,每行`logw`处理,你逗我笑呢?\n\t\t\t\t\t~~于是本人mb了很久很久久很久久久~~~~~~\n\t\t\t\t\t我们考虑一下样例:\n\t\t\t\t\t对于同一行的两棵树\n\t\t\t\t\tans+\u003d...\n\t\t\t\t\t∑敲不上去,我佛了。\n\t\n-----\n\n\n\t\t\t\t\n\t\t\t\t","likeCnt":0,"createTime":1562385839000,"isWorkbook":false,"viewCnt":1177,"openness":1,"fav":false,"id":1270,"trustable":false}