Skip to content

Latest commit

 

History

History
142 lines (113 loc) · 5.65 KB

contest.x1.md

File metadata and controls

142 lines (113 loc) · 5.65 KB
Raw

CSP-S 2024 复赛冲刺卷 1 - SatNov2 2024

信友队供题，原题面不公开。

理论：$100+100+80+10=290$；实际：$85+60+60+0=205$

math

有一个长度为 $n$ 的序列 ${a}$。$q$ 次询问 $(l,r)$。对于每一个问题，输出 $$#{[x,y]\subseteq[l,r]|a_{l,l+1,\cdots,r}\ 中既有奇数，又有偶数}$$

art

一个 $n\times m$ 的矩形，B 黑色，W 白色。每次可以让一整行黑色的变成白色，白色的变成黑色。可以重复任意多次。

进行任意多次行取反操作后，最大的正方形色块的大小是多少（一块连续的颜色相同的区域）。该正方形的边界必须与画纸平行。

note

单调队列维护最小

bio

$n$ 种植物。它们排列成从左到右的一条直线。它们的高度相互不同。

一只蚂蚁一直在做往返的运动，蚂蚁会朝着它当前所面对的方向，移动到第一个比它当前所在植物更高的植物上，之后，蚂蚁会改变运动的方向。

如果蚂蚁在运动前/面朝左边，那么到达新的植物后，它将面朝右边，反之亦然。蚂蚁会一直运动，直到它面朝的方向上没有比当前植物更高的植物为止。

涛涛记录了所有植物的生长情况和每一次蚂蚁做往返运动开始的植物编号和初始方向，他希望每一次你都能告诉他，蚂蚁会在哪里停下来。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示植物的数量和记录的数量。植物从左向右编号依次为 $1，2，3,\cdots, n$

第二行包含 $n$ 个不同的整数 $H_1, H_2, \cdots, H_n$，其中 $H_i$ 是第 $i$ 棵植物的初始高度。

接下来的 $m$ 行按时间顺序描述涛涛的记录，每行对应一个记录。

如果表示某棵植物的生长，该行包含大写字母 U，后跟两个整数 $\mathrm{id}$ 和 $H$ ，表示植物 $\mathrm{id}$ 的新高度是 $H$；新高度 $H$ 大于植物 $\mathrm{id}$ 的旧高度，并且与其他植物的当前高度不同。

如果某条记录表示蚂蚁的运动，该行包含大写字母 L 或 R，后跟一个整数 $j (1 ≤ j ≤ n)$，表示蚂蚁从植物 $j$ 开始运动；如果字母是 L，则蚂蚁开始时面朝左边；如果字母是 R，则蚂蚁开始时面朝右边。

n m
h1 h2 ... hn
U i h'
L/R j

输出格式

对于每次蚂蚁的运动，输出一行，包含一个整数，表示蚂蚁停止运动的植物编号。

数据范围

  • 对于 20% 的数据，$n，m ≤ 300$
  • 对于 40% 的数据，$n，m ≤ 5000$
  • 有额外 20% 的数据，满足没有出现 U，即植物没有生长

对于 100% 的数据，$n，m ≤ 200000$

保证在任何时候都满足 $0 ≤ H_i ≤ 10^9$, 并且数据完全随机.

eng

一个字符串 $s$，初始状态下 $s=s_0$。有 $n$ 个字符串，为 $t_1 ,t_2 , ..., t_n$。任意时刻，仅有一个 $t$ 处于激活状态，称为激活串。初始状态下，$t_{x_0}$ 激活。在任意时刻 $s$ 是激活串的某个子串。

假设现在笔记本上的字符串为 $s$，处于激活状态的字符串为 $t_x$，3 种操作：

  1. 激活串不变，花费 $a(x, c)$ 的代价，在 $s$ 的两端加上一个相同的字符 $c$（修改后仍须满足 $s$ 与 $t_x$ 的某个子串相等）
  2. 激活串不变，花费 $b(x, c)$ 的代价，在 $s$ 的两端去除一个相同的字符 $c$（修改后仍须满足 $s$ 与 $t_x$ 的某个子串相等）
  3. 将激活串从 $t_x$ 变成 $t_y$ ，这需要花费 $| x - y |$ 的代价。需要注意的是，要满足条件 $| x - y | ≤ k$。（须满足 $s$ 与 $t_y$ 的某个子串相等）

把 $s$ 变成 $s_1$，并且激活串是 $s_{y_0}$ 的最小的累计代价是多少？如果无法实现则输出 $-1$。

本题所述字符串仅包含小写字母。

输入格式

第一行两个整数 $n$ 和 $k$

接下来 $3n$ 行，每三行的组成如下：

  1. 第一行是一个字符串，表示 $s_i$
  2. 第二行是 26 个整数，对应规则 1 对应的代价 $a(i, c)$
  3. 第二行是 26 个整数，对应规则 2 对应的代价 $b(i, c)$

然后是一行一个整数和一个字符串，表示 $x_0$​ 和 $s_0$​。

最后是一行一个整数和一个字符串，表示 $y_0$ 和 $s_1$。

n k
st1
a1a a1b ... a1z
b1a b1b ... b1z
st2
a2a a2b ... a2z
b2a b2b ... b2z
...
stn
ana anb ... anz
bna bnb ... bnz
x s y t

样例

Input 1

2 1
ababa
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
ababa
1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 a
2 bab

Output 1

2

Input 2

4 4
aaabaaaabbbbaabbaaaabbaaaaabbabababaababaaaba
769 365 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
26 582 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
abbabbbaabbbbbbabbaabaaaabbaaaabbabbaaabaabaa
867 224 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
679 367 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
baaabaabaababbbababaaaababbbabbbabbbaabbaaaba
86 237 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
894 888 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
aaaababbbaaabbababbabbaaaabbaaaabaaabaaaabaab
813 672 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
757 323 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 abaaaaba
1 aabbaaaabbaa

Output 2

2523

数据范围

  • 对于 10% 的数据，n = 1，每个单词的长度 ≤ 500，字母仅有 a 和 b
  • 对于 30% 的数据，n ≤ 10，每个单词的长度 ≤ 2000，字母仅有 a 和 b
  • 有额外 15% 的数据，K = 1
  • 有额外 20% 的数据，字母最多只有三种

k ≤ n ≤ 1e5; 单词总长度 ≤ 1e6; a,b≤2000

note

对哦为什么不骗点分呢？