CF1142

做不来,做不来

A

有nk个城市排成一个环形,其中第$kx+1(0\le k \lt n)$个城市有家快餐店。

B

题意

给定一个序列$a_i$,一个排列$b_i$,$q$次询问$a_{l\dots r}$存不存在一个子序列和$b$循环同构。

认为$a_1,a_2,\dots,a_n$和$a_{i},a_{i+1},\dots,a_n,a_1,a_2,\dots a_{i-1}$循环同构。

C

题意

有$n$个点,对于任意$x$不同的两个点连一条形如$y=x^2+bx+c$的抛物线,求有多少条抛物线上方没点。

D

题意

定义一个正整数数x是好数,当且仅当$x\lt 10$或者:

  1. $\lfloor\frac{x}{10}\rfloor$是好数
  2. 设$\lfloor\frac{x}{10}\rfloor$是第$i$小的好数,$x\bmod 10 \lt i \bmod 11$

给定一个数字串$S$,求$S$有多少个子串是好数。

题解

设$a_i$表示第$i$小的好数。
令$10a_i+j=a_k$。统计有多少个好数$\lt a_k$,那么$k=9+\sum_{l=1}^{i-1}(l\bmod 11)+j+1$。

看这个$-1$感觉特别不爽,所以把编号整体$-1$,那么$k=9+\sum_{l=1}^{i}(l\bmod 11)+j\equiv 9+\sum_{l=1}^{i\bmod 11}(l\bmod 11)+j\pmod {11}$。

显然$k\bmod 11$只和$i\bmod 11$和$j$有关。

记$f_{r,i}$表示右端点为$r$,s[l:r]是好数且(s[l:r]在好数中编号-1 )$\bmod 11$为$i$的$l$个数。
那么就可以快速从$f_{r-1,0\dots 10}$推到$f_{r,0\dots 10}$

E

题意

有一个竞赛图,其中有$m$条边是粉色边,其它边是绿色边。
粉色边的的方向已经给出来了,但是绿色边的方向没有给。
你可以做不超过2n次查询任意一条绿色边的方向,请输出一个点能走单色路径到其它所有点。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×