首页 > Grab the Seat!
开通博客写题解
头像 Double-Happy
发表于 2022-07-19 22:57:16
题目链接 Grab the Seat! Hint1：考虑每个学生会挡住的范围是什么 Hint2：对于每个学生挡住的范围我们都要考虑吗，哪些学生可以根本不用考虑。 以题中最左上的学生为例，学生遮住的范围可以见下图，可以发现细线范围内（包括边界）的所有点与红点连线都会与黑板有焦点，所以这个范围内的点都 展开全文
去ta的博客 赞 (11) 回复(0) 收起
头像 Zechariah
发表于 2022-07-19 23:26:29
C. Grab the Seat! 题解 观察数据范围发现qqq很小，O(n)O(n)O(n)的复杂度可以通过，考虑对每次询问分别独立地去求解。 观察出一个重要性质：一个被占的座位与屏幕两端连线所夹的区域以外都是会被挡住的点（动手画一画就能看出来）。 实际上，一个被占的座位所去掉的点可以被分成三个部 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 河南老乡唐可可
发表于 2022-07-21 11:17:06
题目大意 二维平面，屏幕是 (0,1)–(0,m)(0, 1)–(0, m)(0,1)–(0,m) 的线段,有nnn行mmm列座位在屏幕前面，是坐标范围 1≤x≤n,1≤y≤m1 ≤ x ≤ n, 1 ≤ y ≤ m 1≤x≤n,1≤y≤m的整点。有kkk个座位已经有人，求出到屏幕的视线不被任何人挡 展开全文
去ta的博客 赞 (2) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”