Codeforces 975D Ghosts 【math】-白红宇

Codeforces 975D Ghosts 【math】

阅读量：5101 次

发布时间：2019-06-13

本文共 941 字，大约阅读时间需要 3 分钟。

打了两次cf里的比赛，发现cf比较喜欢考数学题。一开始看到这道题没有思路，因为总想dp，图论，贪心这些东西。如果下次再没有思路，可以从数学的角度入手。

题解说的比较清楚：

===2018.9.4===又看了遍这题，在看题解前虽然知道是数学题，但仍然一点思路都没有

关键在于不知道怎么建模。

题解里的突破口在于想到两个鬼相遇指的是x坐标和y左边一样，然后想到让x坐标相等的时间=y坐标相等的时间，

然后再化简到等号一边只有一个鬼的参数的形式。

（注意：一个鬼的移动轨迹（一条直线）与另一个鬼的移动轨迹有【相交】不代表他们能吓到彼此，因为他们到达那个相交的点的时间可能是不同的。）

1 #include
     
       2 #include
       3 #define ll long long 4 #define MAXN 200000 5 using namespace std; 6  7 ll n,a,b,ans,parallel; 8 map
       
         m; 9 map< pair
        
         ,int> p;10 int main(){11     cin>>n>>a>>b;12     for(int i=1;i<=n;i++){13         int x,Vx,Vy; scanf("%d%d%d",&x,&Vx,&Vy);14         //每个维护出来a*Vx-Vy15         ll key = a*Vx-Vy;16         ans+=m[key];//相同key的能collide 17         m[a*Vx-Vy]++;18         parallel+=p[ make_pair(Vx,Vy) ];19         p[  make_pair(Vx,Vy)  ]++;20     }21     cout<<(ans-parallel)*2;22     23     return 0; 24 }

转载于:https://www.cnblogs.com/ZhenghangHu/p/8982277.html

你可能感兴趣的文章