Difference between revisions of "Sun Yat-sen University Programming Contest"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) (Created page with "== Problem A == Solved by Kilo_5723. 03:48:17 (-1) == Problem B == Solved by Kilo_5723. 00:17:23 (-2) == Problem C == Unsolved. == Problem D == Solved by Xiejiadong. 01...") |
Xiejiadong (talk | contribs) |
||
| Line 19: | Line 19: | ||
题解：二维平面差分。对于矩形\((a,b,c,d)\)，在位置\((a,b)\; +1\)、\((a,d+1)\; -1\)、\((c+1,b)\; -1\)、\((c+1,d+1)\; +1\)，进行一起前缀和，就能得到所有矩阵位置被覆盖的次数。 | 题解：二维平面差分。对于矩形\((a,b,c,d)\)，在位置\((a,b)\; +1\)、\((a,d+1)\; -1\)、\((c+1,b)\; -1\)、\((c+1,d+1)\; +1\)，进行一起前缀和，就能得到所有矩阵位置被覆盖的次数。 | ||
| − | 对于所有满足\(\ge 1\)的位置，即已经被覆盖的位置，改成\(1\)，其余为\(0\) | + | 对于所有满足\(\ge 1\)的位置，即已经被覆盖的位置，改成\(1\)，其余为\(0\)，再进行一次前缀和即可支持子矩阵和查询。 |
| + | |||
| + | 对于每一个询问，只需要询问矩阵面积和子矩阵的面积相等即可。 | ||
== Problem E == | == Problem E == | ||
Revision as of 10:35, 21 April 2019
Problem A
Solved by Kilo_5723. 03:48:17 (-1)
Problem B
Solved by Kilo_5723. 00:17:23 (-2)
Problem C
Unsolved.
Problem D
Solved by Xiejiadong. 01:49:36 (-5)
题意：给出一些矩形覆盖平面，询问一个矩形区域，问是否已经被覆盖。
题解：二维平面差分。对于矩形\((a,b,c,d)\)，在位置\((a,b)\; +1\)、\((a,d+1)\; -1\)、\((c+1,b)\; -1\)、\((c+1,d+1)\; +1\)，进行一起前缀和，就能得到所有矩阵位置被覆盖的次数。
对于所有满足\(\ge 1\)的位置，即已经被覆盖的位置，改成\(1\)，其余为\(0\)，再进行一次前缀和即可支持子矩阵和查询。
对于每一个询问，只需要询问矩阵面积和子矩阵的面积相等即可。
Problem E
Unsolved.
Problem F
Unsolved.
Problem G
Unsolved.
Problem H
Unsolved.
Problem I
Unsolved.
Problem J
Unsolved.
Problem K
Unsolved.