题意
给 \(N(1\le N\le 1000)\) 辆在一条直线上跑的车,每辆车在区间 \([A_i,B_i](0\le A_i,B_i\le 10^9,A_i\ne B_i)\) 中行驶,可以把速度都看作一个单位速度。
然后给 \(M(1\le M\le 1000)\) 个询问,每个询问都有一组 \(X_i,Y_i,T_i(1\le X_i,Y_i,T_i\le 10^9)\) ,表示问在 \(T_i\) 时,区间 \([X_i,Y_i]\) 内有几辆车。
分析
我们注意到,题目里的 \(N\) 和 \(M\) 都不大,所以 \(O(NM)\) 的算法也可以过。
所以我们可以在每一组询问时,都直接暴力求解每辆车的位置,然后统计一遍就可以了。
经过观察,可以发现:因为车是来回往返的,时间为 \(T_j\) ,单次距离为 \(B_i-A_i\) ,所以当 \(T_j\bmod (B_i-A_i)\) 为偶数时,是从 \(A_i\) 往 \(B_i\),此时该车距离 \(A_i\) 点为 \(T_j\bmod (B_i-A_i)\) ;为奇数时,是从 \(B_i\) 往 \(A_i\) ,此时该车距离 \(A_i\) 点为 \(T_j-T_j\bmod (B_i-A_i)\) 。
我们此时求的距离是到 \(A_i\) 的,而不是真实的位置,所以还要再加上 \(A_i\) 。
Code
#include<bits/stdc++.h>
typedef long long ll;//个人习惯,没必要加long long
char buf[1<<21],*p1=buf,*p2=buf,obuf[1<<21],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
inline ll read(){ll x=0,f=1;char c=getchar();while(c<48||c>57){if(c==45)f=0;c=getchar();}while(c>47&&c<58)x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?x:-x;}
ll n,m,x,y,t,space[1005],ans;
struct car{
ll a,b;
}c[1005];//每辆车
signed main(){
n=read(),m=read();
for(int i=0;i<n;++i){
c[i].a=read(),c[i].b=read();
}//输入A,B
for(int j=0;j<m;++j){
x=read(),y=read(),t=read(),ans=0;
memset(space,0,sizeof space);
for(int i=0;i<n;++i){
if((t/(c[i].b-c[i].a))%2==1){
space[i]=(c[i].b-c[i].a)-t%(c[i].b-c[i].a);
}
else{
space[i]=t%(c[i].b-c[i].a);
}
space[i]+=c[i].a;//求车的位置,记住要在c[i].a的基础上加
if(space[i]>=x&&space[i]<=y)++ans;//统计
}
printf("%lld\n",ans);//输出
}
return 0;
}
标签:le,Knockout,bmod,long,距离,&&,NEERC2014,Racing
From: https://www.cnblogs.com/z10h09x11/p/17990751