CTT ✘

CTDST ✔

先回忆一波题目。

D1T1 lxl

给定 $n,k$，构造大小为 $n+1$ 的方阵 $a$ 满足：

• $\mathrm{\forall }i,a_{i,i}=1$
• $\mathrm{\forall }i,a_{i,i+1}=1$
• $\mathrm{\forall }i,j(i>j),a_{i,j}=0$
• $\mathrm{\forall }i,j(j\ge i+2,a_{i,j}=1),\mathrm{\exists }k\in (i,j),a_{i,k}=a_{k,j}=1$
• $\mathrm{\forall }i,j(i\le j),(A^k{)}_{i,j}=1$

令 $m=\sum _{i,j(j\ge i+2)}[a_{i,j}=1]$， 则你的分数为 ，你需要保证 $m\le nf(k)$，其中 $f(k)$ 是给定的评分参数。

数据范围（分值可能不准确，但大致是 $\frac{1}{k}$）：

$1900\le n\le 2000$

D1T2 bruteforce

定义怪兽为属性序对 $(a,b,c,x,y)$ 。

假设你当前血量为 $w$，那么如果你要大一个属性为 $(a,b,c,x,y)$ 的怪兽，你需要保证 $w\ge x$，打完后你的血量会变为 $w-x+y$。

你有一个怪兽笼子，初始为空。

给出 $q$ 次操作，一次操作有三种类型：

• 操作一：往笼子中加入属性为 $(a,b,c,d,x,y)$ 的怪兽。

• 操作二：将第 $i$ 个被加入的怪兽移除笼子，保证这个怪兽此时在笼子中。

• 操作三：给定 $(A,B,C)$，询问如果要打败笼子中所有满足 $a\le A,b\le B,c\le C$ 的怪兽，初始血量至少为多少。

$q\le 150,000$，每种操作次数最多为 $50,000$。

D1T3 gedit

给定 $n,l,r$ 和长度为 $n$ 的序列 $a$，求长度最小的区间 $(i,j)$，满足 $i<l\le r<j$ 且不存在 $i^{\prime }\le j^{\prime }$ 满足 $a_i=a_{i^{\prime }},a_j=a_{j^{\prime }}$。

输出长度最小的区间的长度，若不存在，输出 $-1$

D2T1 ezds

给定 $n$ 和长度为 $n$ 的序列 $a$，你要进行三种操作：

• 给定 $x$, $\mathrm{\forall }i,a_i\leftarrow min(a_i,x)$

• $\mathrm{\forall }i,a_i\leftarrow a_i+i$

• 给定 $l,r$，求 $\sum _{l\le i\le r}{a}_i$

$n,q\le {10}^5$

要求 polylog

D2T2 datalab

D2T3 graph

给定 $n$ 个点的有向图，初始有一下两种边：

• $\mathrm{\forall }i\in [1,n],i\to i$

• $\mathrm{\forall }i\in [1,n),i\to (i+1)$

你可以加入 $m$ 条边，使得在这张图上随机游走时 $1\to n$ 的期望距离最大。

输出期望的最大值，对 $p$ 取模。

$n,m,p\le {10}^9,n<p,m<p$

D3T1 tree

给定一棵以 1 为根的有根树和一个 $2\sim n$ 的排列，初始所有结点的颜色都是白的，按照排列的顺序把结点染黑。

定义一个时刻是美丽的，当且仅当所有黑点的子树中都是黑点。

求所有美丽的时刻，黑点构成联通块个数之和。

这个问题太简单了，因此给出 $q$ 次操作，每次操作删除一条边再加入一条边，每次操作完后求出以上问题的答案。

$n,q\le {10}^5$

D3T2 rand

给定 $n$ 和长度为 $n$ 的序列 $a$，保证 $a_i$ 在 $[-1000,1001]$ 中随机生成。

$q$ 次询问，每次询问给出 $l,r$，求 $l\le i\le j\le r$ 使得 $f(i,j)={\displaystyle \frac{(\sum _{i\le k\le j}{a}_k{)}^2}{r-l+1}}$ 最大，以分数形式输出最大的 $f(i,j)$。

数据有两部分：$n\le {10}^5,q\le 3\times {10}^5$ 以及 $n\le 5\times {10}^5,q=1$。

D3T3 string

牛逼串串题，场上没人过。

给定字符串 $s$，$q$ 次询问，每次询问给出 $s$ 的一个子串 $t$，求有多少本质不同的 $s$ 的子串，满足它循环无限次以后，字典序小于 $t$ 循环无限次。

$n,q\le 5\times {10}^5$，时限 6s。

D4T1 math

没想到吧我连求阶都不会。

转换过后的题意是：给定 $p,T$，$T$ 次询问，每次询问给出 $b$，求最小的正整数 $k$ 满足 $b^{k-1}\equiv -1(\mathrm{mod}p)$。

D4T2 tree

给定一棵树，每个结点 $u$ 有一个布尔变量 $a_u$，定义 ${\mathrm{dis}}_r(u)$ 表示以 $r$ 为根时结点 $u$ 所在子树的高度（其实是 SG 值）。

定义

$q$ 次操作，每次操作为翻转某个 $a_u$ 或者求 $u$ 周围点 $v$ 的 $f(v)$ 之和。

D4T3

万欧题，成功的区分了 djq 和其他人。