当前位置：首页 > news >正文

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

news 2026/6/5 20:51:28

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;}