A Add Odd or Subtract Even


题意:给定两个数\(a\),\(b\),你的任务是把\(a\)变成\(b\),存在两种变化方式,你可以把\(a\)加上一个奇数或者减掉一个偶数,问你最少需要多少步可以将\(a\)变成\(b\)


解答:考虑三种不同的情况,\(a\)大于\(b\),\(a\)等于\(b\),\(a\)小于\(b\),如果\(a\)大于\(b\),差是奇数就是一步,偶数就是加上两个奇数咯;如果\(a\)大于\(b\),差是偶数就是一步,奇数就是先减掉一个偶数,减成\(a\)小于\(b\)的状态;相等的时候为0。对应状态输出即可



B WeirdSort


题意:给你一个数组\(a\),和\(m\)个可以交换的位置,表示\(a[p[i]]\)和\(a[p[i+1]]\)可以交换,现在问你能否通过交换使得数组递增排列


解答:使用插入排序的思想,每交换一次,观察这种情况是否出现过,如果出现过就是NO,都没有出现过就是YES



C Perform the Combo


题意:给一个长度为\(n\)字符串和\(m\)个数字,\(p[i]\)代表从这个位置断掉从头开始,问最后26个字母各按了多少次


解答:前缀和维护到每一个位置前面26个字母出现多少次,然后加上\(p[i]\)这个位置的前缀和即可



D Three Integers


题意:给定三个数字,让你把这三个数字变成\(a\)整除\(b\),\(b\)整除\(c\)


解答:预处理出所有的情况,注意放出一点范围防止WA,因为数据可能超过10000这里采用了11000的数据(10000被Hack了)



F Moving Points


题意:给定\(n\)个质点,位置为\(x[i]\),在数轴上面做匀速直线运动,速度为\(v[i]\),问每两个质点的最短距离之和是多少


解答:如果两个质点可以相交,那么答案就是0,不相交的话就是现在的位置之差,不相交的条件就是位置之差和速度之差反向,由于这里的速度仅仅需要大小关系,考虑按照\(x\)从小到大sort,将v离散化后维护两个和速度有关的树状数组即可,一个维护前面每个位置的个数(\(bit2\)),一个维护前面每个位置的坐标之和(\(bit1\)),那么第\(i\)个位置,x比它小的且满足题意的总共有\(\Sigma_{j=1}^{i-1}c[i].first-c[j].first  (c[j].second<=c[i].second)\)用树状数组维护过后式子就等价于\(getsum(bit2,1,c[i].second)*c[i].first-getsum(bit1,1,c[i].second)\)对每一个处理过后再edit一下即可


 


0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注