CF1672E notepad.exe 做题记录

这是一道交互题。

在文本编辑器里有 nn 个单词,其中第 ii 个单词的长度为 lil_i (1li20001 \le l_i \le 2000)。ll 仅对测评机可见。

文本编辑器一行一行展示文本,以空格分开相邻的两个单词,但是行末不一定有空格,即单词可以直接作为某一行的末尾。定义文本的高度 hh 为文本展示需要的行数。对于给定的屏幕宽度,编辑器会以高度最小的方式显示。

更正式地,设文本编辑器的宽度为 ww 。设 aa 是一个长度为 k+1k + 1 的序列,其中 1=a1<a2<...<ak+1=n+11 = a_1 < a_2 < ... < a_{k+1} = n + 1. {an}\{a_n\} 是一个合法的序列当且仅当,1ik,lai+1+lai+1+1++1+lai+11w\forall 1 \le i \le k, l_{a_i} + 1 + l_{a_{i + 1}} + 1 + \dots + 1 + l_{a_{i+1} - 1} \le w。 那么,hh 就是所有合法的 {an}\{a_n\} 中最小的 kk.。

注意,如果 wmax(li)w \le \max(l_i),那么文本编辑器将不能显示所有的文字并且崩溃,此时 h=0h = 0

你可以做 n+30n + 30 次询问。每次询问中,输出宽度 ww . 测评机将返回 hwh_w ,即当宽度为 ww 的最小高度。

请找到文本编辑器的最小面积,即求 min(w×hw1wn)min(w\times h_w | 1 \le w \le n)

阅读全文 »

CF1679E Typical Party in Dorm 做题记录

给定一个长度为 n(1n1000)n(1\le n\le 1000) ,仅由前 1717 个英文小写字母和问号组成的字符串 ss

多次询问,每次给出一个由前 1717 个英文小写字母组成的字符集 AA ,你可以将 ss 中的问号任意替换成 AA 中的字母,求你能得到多少个不同的回文子串

答案对 998144353998144353 取模。

阅读全文 »

ABC232H King's Tour 做题记录

棋盘大小为 h×wh \times w,有一个王在 (1,1)(1,1)。每一步可以走到八连通的格子之一。构造一种方案,使得王经过所有格子,并停在 (a,b)(a,b)

1h,w1001 \le h,w \le100

阅读全文 »

CF1697E Coloring 做题记录

给定平面上的 nn 个点的坐标 (xi,yi)(x_i,y_i)其中没有两点有相同的坐标 。定义点 i,ji,j 间的距离为 d(i,j)=xixj+yiyjd(i,j)=|x_i-x_j|+|y_i-y_j|

现用 nn 种颜色对这些点进行染色,求满足以下条件的方案数:

  • 每种相同颜色的点两两间距离相等

  • 每个点到具有不同颜色的点的距离总 大于 与其颜色相同的其他点(若存在)的距离。

答案取模 998244353998244353

2n100,0xi,yi1082\le n\le 100,0\le x_i,y_i\le 10^8

阅读全文 »

ABC229G Longest Y 做题记录

给你一个字符串 SS,由 Y. 构成。

现在你可以最多进行 kk 次操作,每次可以交换两个相邻的字符。

请你求出最多 kk 次操作后,最长连续字符 Y 的长度。

  • 2S2×1052 \leq |S| \leq 2 \times 10^5
  • 0K10120 \leq K \leq 10^{12}
阅读全文 »

CF1416D Graph and Queries 做题记录

给定一个 nn 个点 mm 条边的无向图,第 ii 个点的点权初始值为 pip_i,所有 pip_i 互不相同。

接下来进行 qq 次操作,分为两类:

  • 1 v\tt 1\ v 查询与 vv 连通的点中, pup_u 最大的点 uu 并输出 pup_u,然后让 pu=0p_u=0
  • 2 i\tt 2\ i 将第 ii 条边删掉。

1n21051 \le n \le 2 \cdot 10^51m31051 \le m \le 3 \cdot 10^51q51051 \le q \le 5 \cdot 10^5

阅读全文 »

CF1580B Mathematics Curriculum 做题记录

求满足以下条件的排列个数:

  • 长度为 nn
  • 恰有 kk 个数满足:所有包含这个数的区间中,不同的最大值的个数恰有 mm 个。

答案对 pp 取模。

1n100,1mn,1kn,1p1091 \le n \le 100, 1 \le m \le n, 1 \le k \le n, 1 \le p \le 10^9

阅读全文 »

ABC234G Divide a Sequence 做题记录

给定长度为 NN 的序列 AA,我们定义一种将 AA 划分为若干段的方案的价值为每一段的最大值减去最小值的差的乘积,你需要求出所有划分方案的价值的总和,答案对 998244353998244353 取模。

  • 1N3×1051 \leq N \leq 3 \times 10^5
  • 1Ai1091 \leq A_i \leq 10^9
阅读全文 »