打卡信奥刷题（3046）用C++实现信奥题 P6641 [CCO 2020] A Game with Grundy

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}hi​vi​​,hi​−vi​​一端的端点为( x i , 0 ) (x_i,0)(xi​,0)。输出格式共N 1 N1N1行每行一个整数第i ii行的数表示您可以站在的位置个数使得您至多在i − 1 i-1i−1个人的视野内。输入输出样例 #1输入 #13 -7 7 3 0 2 3 -4 2 1 3 3 1输出 #15 12 15 15说明/提示样例解释子任务本题采用捆绑测试。Subtask 160 6060分保证− 10 6 ≤ L ≤ R ≤ 10 6 -10^6\le L\le R\le 10^6−106≤L≤R≤106。Subtask 240 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≤1091 ≤ Y ≤ 10 6 1\le Y\le 10^61≤Y≤1061 ≤ x i ≤ R 1\le x_i\le R1≤xi​≤R1 ≤ 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实现#includeiostream#includecstdio#includealgorithm#includeutilityusingnamespacestd;constintN1e55;intn;intl,r,y;pairint,intpr[N*2];intbuc[N];intmain(){scanf(%d,n);scanf(%d%d%d,l,r,y);intx,v,h;for(inti1;in;i){scanf(%d%d%d,x,v,h);intal,ar;intyhy*h;intxlx-((yh%v0)?(yh/v-1):(yh/v));intxrx((yh%v0)?(yh/v):(yh/v1));pr[i*2-1](pairint,int){xl,-1};pr[i*2](pairint,int){xr,1};}sort(pr1,prn*21);for(inti1;i2*n;i)pr[i].firstmin(max(pr[i].first,l),r1);intnow0;pr[2*n1].firstr1;buc[0]pr[1].first-l;for(inti1;i2*n;i){now-pr[i].second;buc[now]pr[i1].first-pr[i].first;}for(inti0;in;i)printf(%d\n,buc[i]),buc[i1]buc[i];return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容