0%

CF1245E

题意:给一个棋盘,有10行10列。格子上可能有梯子,能通过梯子爬到上方的某个格子。但不能连续爬,即通过梯子到达一个格子后不能爬这个格子上的梯子。有一个均匀的6面骰子,求到终点的最小期望投骰子次数。(我概括的不好,有些细节没有提到,建议还是自己读题)

Read more »

NOIOL2 题解

比上次办的好多了至少有LaTeX了

注:提高组的题,如果在acwing上提交,请手动O2,否则可能会被卡常(我放的代码在洛谷等OJ上是不用O2也可以A的)

提高组

Read more »

CF1202E

题意:给一个串$T$和$n$个串$s_i$.定义$f(T,s)$表示$s$在$T$中的出现次数。

求$\sum_{i=1}^n\sum_{j=1}^nf(T,s_i+s_j)$. 数据范围:$|T|,\sum_{i=1}|s_i|\le 2\times 10^5$

Read more »

CF1336C

题意:给一个初始串$s$和目标串$t$,每次可以取出(并删除)$s$的第一个字符加入另一个串$A$的开头或末尾(初始为空),求$t$是$A$的前缀的方案数(任意一步操作不同即不同,$s$不必删完)

$|t|\le |s|\le 3000$

Read more »

浅谈线段树分治

众所周知区间加,区间乘等操作可以利用线段树在单次操作$\mathcal O(\log n)$时间复杂度内完成。
对于更复杂的对区间的操作,同样可以利用线段树每次访问$\mathcal O(\log n)$个节点的性质,把标记打在这$\mathcal O(\log n)$个节点上,最后从根开始dfs,将信息下推至叶子节点,以此更快速的解决。

在此介绍两个例题:

CF 981E

题意:

给一个长度为$n$ 的序列(初始全为0)和$q$条操作(以$(l,r,x)$表示将$[l,r]$中的每个数都加上$x$.
对于$1\le k\le n$,求哪些$k$满足选出若干条操作后序列最大值为$k$.(对于一个$k$,每条操作至多用一次)

$1\le n,q\le 10^4$

Read more »

题意:给一个$n$个点的无向图(无重边、自环),要找出包含不少于$\lceil \sqrt n\rceil $个点的简单环或独立集。

$n\le 10^5,m\le 2\times 10^5$

Read more »

题意:给一个长为$n$的正整数序列,每个数至多有$7$个约数,要你选出一个乘积为完全平方数的最短子序列,输出长度即可

$n\le 10^5,a_i\le 10^6$

Read more »

NOI Online sol

好像都是sb题,但我没AK啊,可能我是sb吧

提高组

游记都是流水账,懒得写了.

T1

简化题意:给序列$A,B(|A|=|B|=n)$和$m$种操作,1操作可以让$u_i,v_i$都+1或-1,2操作可以让$u_i+1,v_i-1$或$u_i-1,v_i+1$,问能否让$A=B$

$n,m\le 10^5$

Read more »