P6641 [CCO 2020] A Game with Grundy
题目描述
本题的所有讨论均在平面直角坐标系上进行。
有N NN个人，每个人有一个视野，同时每个人在( x i , 0 ) (x_i,0)(xi,0)的位置上。
视野可抽象为一个角。
注意，组成角的两条射线未在视野内。
现在，您可以站在( a , Y ) (a,Y)(a,Y)上，其中L ≤ a ≤ R L\le a\le RL≤a≤R。
请求出，对于每个i ( 0 ≤ i ≤ N ) i(0\le i\le N)i(0≤i≤N)，您可以站在多少个位置，使得您至多在i ii个人的视野内。
输入格式
第一行为一个整数N NN。
第二行为三个整数L , R , Y L,R,YL,R,Y。
接下来N NN行，每行三个整数，分别为x i , v i , h i x_i,v_i,h_ixi,vi,hi，其中v i v_ivi和h i h_ihi表示，组成角的两条射线的斜率分别为v i h i , − v i h i \frac{v_i}{h_i},\frac{-v_i}{h_i}hivi,hi−vi，一端的端点为( x i , 0 ) (x_i,0)(xi,0)。
输出格式
共N + 1 N+1N+1行，每行一个整数，第i ii行的数表示您可以站在的位置个数，使得您至多在i − 1 i-1i−1个人的视野内。
输入输出样例 #1
输入 #1
3 -7 7 3 0 2 3 -4 2 1 3 3 1输出 #1
5 12 15 15说明/提示
样例解释
子任务
本题采用捆绑测试。
- Subtask 1（60 6060分）：保证− 10 6 ≤ L ≤ R ≤ 10 6 -10^6\le L\le R\le 10^6−106≤L≤R≤106。
- Subtask 2（40 4040分）：无特殊限制。
对于100 % 100\%100%的数据，保证1 ≤ N ≤ 10 5 1\le N\le 10^51≤N≤105，− 10 9 ≤ L ≤ R ≤ 10 9 -10^9\le L \le R\le 10^9−109≤L≤R≤109，1 ≤ Y ≤ 10 6 1\le Y\le 10^61≤Y≤106，1 ≤ x i ≤ R 1\le x_i\le R1≤xi≤R，1 ≤ v i , h i ≤ 100 1\le v_i,h_i\le 1001≤vi,hi≤100。
说明
本题译自 Canadian Computing Olympiad 2020 Day 1 T1 A Game with Grundy。
C++实现
#include<iostream>#include<cstdio>#include<algorithm>#include<utility>usingnamespacestd;constintN=1e5+5;intn;intl,r,y;pair<int,int>pr[N*2];intbuc[N];intmain(){scanf("%d",&n);scanf("%d%d%d",&l,&r,&y);intx,v,h;for(inti=1;i<=n;i++){scanf("%d%d%d",&x,&v,&h);intal,ar;intyh=y*h;intxl=x-((yh%v==0)?(yh/v-1):(yh/v));intxr=x+((yh%v==0)?(yh/v):(yh/v+1));pr[i*2-1]=(pair<int,int>){xl,-1};pr[i*2]=(pair<int,int>){xr,1};}sort(pr+1,pr+n*2+1);for(inti=1;i<=2*n;i++)pr[i].first=min(max(pr[i].first,l),r+1);intnow=0;pr[2*n+1].first=r+1;buc[0]+=pr[1].first-l;for(inti=1;i<=2*n;i++){now+=-pr[i].second;buc[now]+=pr[i+1].first-pr[i].first;}for(inti=0;i<=n;i++)printf("%d\n",buc[i]),buc[i+1]+=buc[i];return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
