最近做的一点点CF上的题

1142A - The Beatles

环形数轴上有间隔为kknn个点,下标为 。首尾相接

你在数轴上走,设起点为ss,步长为LL,而现在只知道和ss距离最近的点的距离为aa,和(s+L)(s+L)距离最近的点的距离为bb。问从ss出发,第一次回到ss走的最多和最少的步数

n,k100000;a,bk2n, k\le 100000;a, b\le \frac{k}{2}

Solution

显然答案和ss没什么关系,只和LL有关系

考虑枚举所有可能的LL,先考虑L<kL < k的情况,然后不断再+k+k

L<kL < k时,通过画图发现只有四种情况:

  • L=k+abL = k + a - b
  • L=kabL = k - a - b
  • L=a+bL = a + b
  • L=k+baL = k + b - a

枚举出了LL之后,答案即为nkgcd(nk,L)\displaystyle \frac{n*k}{\gcd(n*k, L)}

1142B - Lynyrd Skynyrd

一个长度为nn排列aia_i,一个长度为mm序列bib_i,满足bi[1,n]b_i\in [1, n]

qq次询问[l,r][l, r],你需要回答是否能从序列bib_i的区间[l,r][l, r]中,选出一个长度为nn的子序列,满足它和排列aia_i循环同构

n,m,q2105n, m, q\le 2*10^5

Solution

题目可以转化为,把排列aia_i倍长之后,能否找到aa的一个长度为nn的子段,跟bb[l,r][l, r]范围内的一个子序列匹配上

也就是说,我们判断,把bb[l,r][l, r]范围内的子序列去跟aa匹配,看最长匹配长度是否n\ge n

因为aa是一个排列,因此对于bib_i而言,它肯定只会匹配对应aa中后面的那一个位置,这个关系在bb序列上构成了一棵树

问题转化为,我们只能选区间[l,r][l,r]内的点,问能否选出一条长度n\ge n的链

显然,每个点的n1n-1级祖先是固定的,能预处理出来。

ST表维护一下区间最小的那个n1n-1级祖先,看它是否属于[l,r][l, r]即可

1142C - U2

给你二维平面上的nn个点,对于任意两个xx坐标不同的点,连一条形如y=x2+bx+cy=x^2+bx+c的抛物线

问有多少条抛物线满足在它内部没有点

n105n\le 10^5

Solution

把每个点(x,y)(x, y)转化成(x,yx2)(x, y - x^2)之后求上凸壳即可

1144G - Two Merged Sequences

一个长度为nn的序列aia_i,问能否把它划分成一个严格上升子序列和一个严格下降子序列,并输出方案

n2105n\le 2*10^5

Solution

考虑当前这个数是分到上升序列还是下降序列

dp[i][0/1]dp[i][0/1]表示第ii个数作为下降/上升序列末尾时,上升/下降序列末尾的最小/最大值

顺便再记一下最小/最大值的位置,用pair实现