Misaka16172's Blog

Day -INF J组初赛前一天。 看了看锣鼓上的模拟卷，觉得自己应该能考上50分，于是摆烂睡觉。讲个笑话，本蒟蒻的第一次CSP-J竟然是在高一，CSP-S甚至怕水平不够没敢报，实在是太菜了。 Day -INF+1 初赛是在bsz考的，主场作战，场上rp大爆发，蒙对了四道选择，估分80pts。 可是出分之后不知道哪挂了2.5pts，最后77.5进了复赛，突然感觉自己又行了。 Day -1 J组复赛前一天。 上锣鼓写了几道往年J组的t1 t2，把之前一直没写过的直播获奖a掉了。很难想象这个时候在一个小时内切掉橙题就能让我觉得自己很牛批。 可是写着写着被CSP-J 2019的公交换乘卡住了，交了两发都零分，大大挫伤了自己的信心，为明天的逆天表现埋下了伏笔。 Day 0 J组复赛去了ssf，看见身边都是比我小还比我强的小朋友倍感难受。谁让我耽误了最珍贵的青春呢。 上机之后发现键盘是机械键盘，好评，但是旁边小朋友打字真的很吵。 先看t1，甚至一开始真的开了个1e9的bool数组，险些爆零，发现暴力时间复杂读太烂 （其实真实原因是我当时码力太烂连暴力 ...

学oi这么多月了第一次场切黄题（尽管不会哈希做法用的是侥幸没被出题人卡掉的umap），所以打算写篇题解，顺带着测试一下自己blog的可用性（反正也没有人看）（连LaTeX都不支持可用个鬼啊） 根据题面，假设两个点在第ttt秒相遇，则编号为iii的AAA类点在第ttt秒时的坐标为(i,ai⋅t)(i,a_i\cdot t)(i,ai​⋅t)，编号为jjj的BBB类点在第ttt秒时的坐标则为(bj⋅t,j)(b_j\cdot t,j)(bj​⋅t,j)。显然，当同时满足i=bj⋅ti=b_j\cdot ti=bj​⋅t且j=ai⋅tj=a_i\cdot tj=ai​⋅t时，两点能在第ttt秒相遇。可以把上式变形为t=ibj=jait=\frac {i} {b_j}=\frac {j} {a_i}t=bj​i​=ai​j​。 到这里就是第一个坑点了，t不一定是一个整数，所以不能直接计算ibj\frac {i} {b_j}bj​i​和jai\frac {j} {a_i}ai​j​的值，c++中除法的自动取整会把两个互不相等的ttt取成同一个整数。于是可以想到把等式两边同时乘以bj⋅aib_j ...