fork()==0世界线变动

A. We Got Everything Covered!

B. A Balanced Problemset?

C. Did We Get Everything Covered?

D. Good Trip

E. Space Harbour

F. Fractal Origami

• 给定 $n$ ($1\le n\le 20$) 个城市和 $m$ ($1\le m\le 5\cdot {10}^4$)个点.

• 对于每个城市，给定所有点到该城市的距离与光在一秒内行走距离的比值 $d$ ($1\le d\le n+1$)（不一定满足三角不等式）.

• 从第零秒开始，每隔一秒可以点亮一个未被点亮的城市.

• 已知点亮城市的顺序随机，求第 n 秒的瞬间被照亮的点数的期望值,答案对 998244353 取模。

题目描述

给出一个在二维平面直角坐标系第一象限内的，单位长度为1的无限大网格，每条直线都代表道路。又给你一条直线ax+by+c=0，也代表一条道路。

现在给你两个格点A,B坐标(x1,y1)和(x2,y2)，让你求该两点间最短的道路距离。

输入

第一行a,b,c表示直线ax+by+c=0

第二行x1,y1,x2,y2表示A(x1,y1),B(x2,y2)的坐标

输出

求A,B间最短的道路距离（误差不超过10^−6）

一栋公寓有 $n$ 层，每层有 $m$ 个窗户，其中 $m$ 是 4 的倍数。

每层楼恰好有 ${\displaystyle \frac{m}{2}}$ 户是一居室，只有一个窗户；恰好有 ${\displaystyle \frac{m}{4}}$ 户是两居室，有相邻的两个窗户。你不知道每层楼哪些窗户是一居室、哪些连续窗户是两居室，且不同楼层的一居室和两居室的分布可能不同。

每个窗户有开灯和关灯两种状态。如果一居室的窗户开灯，或者两居室至少一个窗户开灯，则里面有人；否则没有人。请你计算整栋公寓至少和至多分别有多少户有人。

• 给你一个长度为 $n$ 的括号序列。

• 你从括号序列的左端出发，可以向右走或者向左走（不能向左走到起点的外面）。

• 有一个记录你走过括号的序列，即你每到达一个位置，上方的括号会被记录下来，加到这个记录你走过括号的序列的末尾。

• 当你走到括号序列的最右端时，你可以走出括号序列并终止流程，此时你需要判断记录你走过括号的序列是否括号匹配。

• 若存在一种走的方案，使得记录你走过括号的序列可以括号匹配，则称这个括号序列是“可行走的”。

• 你有多次询问，每次询问会修改某一个位置的状态（左括号变成右括号，右括号变成左括号），你需要判断修改过后这个括号序列是否是“可行走的”。

• 询问之间不互相独立，即每次询问会影响接下来的询问。

给予$n$个整数$m_{1,2,...,n}$，现在要将它们放进若干容器，要求：

• 在每个容器$p_j$中，对于每个数$i$（$1\le i\le k$），大于等于$i$的数不能超过$c_i$个。

求最小所需容器数以及安排方式，保证：

• $1\le n\le 2\cdot {10}^5$

• $1\le k\le 2\cdot {10}^5$

• $1\le m_i\le k$

• $n\ge c_1\ge c_2\ge ...\ge c_k\ge 1$

输入格式：

• 第一行两个整数$n,k$。

• 第二行$n$个整数$m_{1,2,...,n}$。

• 第三行$k$个整数$c_{1,2,...,k}$。

输出格式：

• 第一行输出最小容器数$ans$（$1\le ans\le n$）。

• 接下来输出$ans$行，第$i$行先输出一个整数$t$（$1\le t\le n$），接下来输出$t$个整数，表示第$i-1$个容器中的元素。

• $\sum t=n$。

• $m$中的每个数恰好在某个容器中出现一次。

• 输出任意一组最优解即可。

因为$c_k\ge 1$，所以一定存在一种合法分配方式。

您要设计一个只有一行的打字机，这一行的长度是无限大，一开始可以认为每个字符都是空。您的打字机有一个光标只指向一个字符，一开始指向最左侧的字符。

使用者有三种操作：

• L 将光标向左移一格（当光标已经在最左侧时，忽略这次操作）

• R 将光标向右移一格

• 一个小写字符或者'(',')' 将当前字符替换为给定字符

您需要在每次操作后，判断这一行是否是合法括号序列（例如 (ahakioi) 就是合法的，(ige))(tscore 就是非法的），不是输出 -1，否则输出最多嵌套数（例如 ()(())()() 的最多嵌套数是 2，(()(()())())(()) 的最多嵌套数是 3）。

第一行输入一个正整数 $n(1\le n\le {10}^6)$ 表示操作数

接下来一行一个长度为 $n$ 的字符串，只含 L,R,(,),小写字母，表示操作序列，第 $i$ 个字符表示第 $i$ 次操作。

输出 $n$ 个正整数表示每次操作后的结果。

```plain

1. (

2. (

3. (a

4. (a

5. (ab

6. (ab

7. (ab)

8. (ab)

9. (a))

10. (a))

11. (())

```