yl-9/probench huggingface dataset:
# Cidoai的听歌

## 题目描述

Cidoai 喜欢听歌。  
它拿到了一个长为 $n$ 的数列 $a_1,a_2,\cdots,a_n$。Cidoai 会循环进行以下两种操作，从操作 1 开始：  
1\. 选择数列中任意多个数+1;   


2\. 选择数列中任意多个数-1。 

单次操作中必须选择**不同位置** 的数。 

它都希望使用最少的**操作次数** 使得整个数列都相等，求最少的操作次数，以及整个数列最后等于的数  
可以证明，在最少操作次数的时候，整个数列最后等于的数唯一。  


## 输入描述:
    
    
    第一行一个正整数 $n$。  
    
    
    第二行 $n$ 个整数，分别表示 $a_1,a_2,\cdots,a_n$。
    
    $1 \le n \le 10^6,1 \le a_i \le 10^9$。  
    

## 输出描述:
    
    
    一行两个整数，分别表示最少的总操作次数和整个数列最后等于的数。

示例1 

## 输入
    
    
    8
    3 2 4 5 2 3 4 2

## 输出
    
    
    3 4

## 说明
    
    
    一开始的数列为 $[3,2,4,5,2,3,4,2]$。  
      
    Cidoai 选择 $a_2,a_5,a_8$ 操作第一次后可变为 $[3,3,4,5,3,3,4,3]$。  
      
    选择 $a_{4}$ 操作第二次后可变为 $[3,3,4,4,3,3,4,3]$。  
      
    选择 $a_1,a_2,a_5,a_6,a_8$ 操作第三次后可变为 $[4,4,4,4,4,4,4,4]$。  
      
    一共操作了 $3$ 次，最后得到的数为 $4$。

## 备注:
    
    
      
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# Cidoai的植物

## 题目描述

Cidoai 喜欢植物。  
Cidoai 有一个 $n$ 行 $m$ 列的花园，这个花园初始没有植物，它会对这个花园做 $k$ 次如下操作之一：  
1\. 选择第 $i$ 列，在这一列上**没有植物** 的位置上全部种下植物 $x$；  


2\. 选择第 $a$ 行第 $b$ 列，如果这个位置有植物，则铲除这株植物，否则不进行操作。 

现在它给了你 $n,m$ 以及它的操作序列，它想知道操作完后花园的状态。 

由于输入量过大，操作数列不会被直接输入，而是由参数生成，如下： 
    
    
    def rnd():
        p=(1<<32)
        ret=seed
        seed=(seed xor ((seed<<13) mod p)) mod p
        seed=(seed xor ((seed>>17) mod p)) mod p
        seed=(seed xor ((seed<<5) mod p)) mod p
        return ret
    for t=1 to k:
        op[t]=(rnd() mod 2) + 1
        if op[t]==1:
            i[t]=(rnd() mod m) + 1
            x[t]=(rnd() mod (n*m)) + 1
        if op[t]==2:
            a[t]=(rnd() mod n) + 1
            b[t]=(rnd() mod m) + 1

其中 $seed$ 由输入给定。$op[t]$ 表示第 $t$ 次操作对应的操作编号，为 1 或 2。若第 $t$ 次操作为 1 操作，$i[t],x[t]$ 表示对应的列数和植物编号。若第 $t$ 次操作为 2 操作，$a[t],b[t]$ 表示对应的行数和列数。 

rnd 函数的 C++ 代码如下： 
    
    
    unsigned seed;
    unsigned rnd(){
    	unsigned ret=seed;
    	seed^=seed<<13;
    	seed^=seed>>17;
    	seed^=seed<<5;
    	return ret;
    }

由于输出量过大，你不需要输出整个花园的状态，只需要输出如下值即可：$\bigoplus \limits_{i=1}^{n}\bigoplus \limits_{j=1}^{m} p_{i,j} \times ((i-1)\times m+j)$。其中 $p_{i,j}$ 表示花园中第 $i$ 行第 $j$ 列的植物编号，若该位置没有植物，则编号为 $0$。这个式子表示枚举所有 $i=1,2,\cdots,n,j=1,2,\cdots,m$，求得所有 $p_{i,j} \times ((i-1)\times m+j)$ 值后将其异或起来。 

## 输入描述:
    
    
    一行四个整数 $n,m,k,seed$。
    
      
    
    
    $1 \le n \le 2 \times 10^4,1 \le m \le 200,1 \le k \le 5\times 10^6,0 \le seed < 2^{32}$，操作 1 满足 $1 \le i \le m, 1 \leq x \leq nm$，操作 2 满足 $1 \le a \le n,1 \le b \le m$。  
    

## 输出描述:
    
    
    一行一个整数，表示答案。  
      
    注意输入和输出的**行列顺序** 。

示例1 

## 输入
    
    
    2 3 6 10

## 输出
    
    
    16

## 说明
    
    
    由参数生成的操作数列如下：
    
    1 1 1  
    2 1 1  
    2 2 1  
    1 2 5  
    1 3 1  
    2 2 3  
    花园的最后状态为：
    
    0 5 1  
    0 5 0  
    

示例2 

## 输入
    
    
    3 5 100 384312

## 输出
    
    
    167

## 说明
    
    
    花园的最后状态如下：
    
    4 9 12 3 8
    
    4 3 12 6 0  
    4 7 5 6 9  
    

示例3 

## 输入
    
    
    20000 200 4000000 1314520

## 输出
    
    
    1569159159130

示例4 

## 输入
    
    
    20000 200 4990000 1206502205

## 输出
    
    
    10019837969254

## 备注:
    
    
    在 C++ 中，unsigned int 的运算会自动对 $2^{32}$ 取模。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# Cidoai的猫猫

## 题目描述

Cidoai 喜欢猫猫。  
它有一个长度 $n$ 的**仅由小写字符构成** 的字符串 $s$，每个字符代表一只猫猫的品种。它想要合并一些长为 $k$ 的子串，从而得到一个新的字符串 $t$。  
我们记 $t_{[i,j]}$ 表示由字符串 $t$ 中第 $i$ 位到第 $j$ 位的字符构成的子串。  
字符串 $s$ 一共有 $n-k+1$ 个长为 $k$ 的子串，按照左端点从左往右的顺序分别记为 $p_1,p_2,\cdots,p_{n-k+1}$。使得存在一个非负整数序列 $a$ 同时满足如下三个条件：  


  * $a_1=0$。 


  * $\forall i \in [1,n-k],0 \le a_{i+1}-a_i \le 1$； 


  * $\forall i \in [1,n-k+1],p_{i}=t_{[i-a_i,i+k-1-a_i]}$； 

设对于 $k$ 生成的 $t$ 的**最短长度** 为 $l_k$。  
举例而言：对于字符串 $s=\text{aabbbaaa}$ 以及 $k=2$ 的情况。$p_1=\text{aa},p_2=\text{ab},p_3=\text{bb},p_4=\text{bb},p_5=\text{ba},p_6=\text{aa},p_7=\text{aa}$。  
最短的满足条件的字符串 $t$ 为 $\text{aabbaa}$，对应的 $a=\\{0,0,0,1,1,1,2\\}$。  
由于 Cidoai 想要尝试不同的可能性，它想让你求出对于 $k=1,2,\cdots,n$ 的 $l_k$。为了避免输出量过大，它只需要你输出 $(1 \times l_1)\oplus(2 \times l_2) \oplus \cdots \oplus (n \times l_n)$。

## 输入描述:
    
    
    第一行一个正整数 $n$ 表示字符串长度。  
      
    第二行一个字符串 $s$。  
      
    $1 \le n \le 5 \times 10^6$。保证字符串仅由小写字母构成。

## 输出描述:
    
    
    一行一个整数表示答案。

示例1 

## 输入
    
    
    4
    baac

## 输出
    
    
    23

## 说明
    
    
    对于 $k=1$，令 $t=\text{bac}$，则 $a=\{0,0,1,1\}$ 满足条件，$l_1=3$。对于 $k=2,3,4$，只有 $t=\text{baac},a=\{0,0,0,0\}$ 满足条件，$l_2=l_3=l_4=4$。  
      
    因此 $(1 \times 3) \oplus (2\times 4) \oplus (3 \times 4) \oplus (4 \times 4)=23$。

示例2 

## 输入
    
    
    5
    ababc

## 输出
    
    
    13

## 说明
    
    
    对于 $k=1,2,3,4,5$，只有 $t=\text{ababc}$ 满足 $l_k=5$ 最小。

示例3 

## 输入
    
    
    15
    ababbbabaccaabb

## 输出
    
    
    247

示例4 

## 输入
    
    
    20
    ababcabbbbabaccaaabb

## 输出
    
    
    134

## 备注:
    
    
      
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# Cidoai的可乐

## 题目描述

Cidoai 喜欢可乐。  
它有 $n$ 个点，每个点都有点权 $a_i$ 和一个度数限制 $d_i$。它想将它们连成一棵树，其中一条边的边权为它的两个端点的点权较小值。它希望这棵树中，所有点的度数都不大于度数限制，且边权和最小。你需要输出这个边权和。

## 输入描述:
    
    
    第一行一个正整数 $n$ 表示点数。  
      
    第二行 $n$ 个数，依次表示 $a_1,a_2,\cdots,a_n$。  
      
    
    
    第三行 $n$ 个数，依次表示 $d_1,d_2,\cdots,d_n$。
    
      
    
    
    $1 \le n \le 10^5,1 \le a_i \le 10^9,1 \le d_i \le n-1$，保证 $\sum d_i \ge 2(n-1)$。  
    

## 输出描述:
    
    
    一行一个整数表示答案。

示例1 

## 输入
    
    
    5
    1 2 2 1 1
    3 4 2 1 3

## 输出
    
    
    4

示例2 

## 输入
    
    
    5
    1 2 3 4 5
    1 2 1 3 4

## 输出
    
    
    8


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# Cidoai的自恋

## 题目描述

Cidoai 喜欢小 C。  
它某天和小 C 在玩一个游戏。小 C 需要猜一个在 $[1,n]$ 之间的数，它会先给小 C 一个长度为 $k$ 的询问列表 $a_1,a_2,\cdots,a_k$，Cidoai 会根据答案 $x$ 对列表上的每个数给出**大于答案** 、**小于答案** 或是**等于答案** 的回答。  
小 C 认为一次无效询问是：如果存在一个 $i<j$ 满足 $a_i<x$ 且 $a_j \le a_i$ 或满足 $a_i>x$ 且 $a_j \ge a_i$，则询问 $a_j$ 是一次无效询问。  


Cidoai 想要捉弄一下小 C，因此它会根据询问列表确定答案 $x$，满足它不在小 C 的询问列表中且**无效的询问次数** 最多，如果有多个满足条件的数，输出最小的那个。 

Cidoai 保证，对于题目所给的所有数据，**不存在** 无解的情况。 

由于输入量过大，$a$ 数列不会被直接输入，而是由参数生成，伪代码如下： 
    
    
    def rnd():
        p=(1<<32)
        ret=seed
        seed=(seed xor ((seed<<13) mod p)) mod p
        seed=(seed xor ((seed>>17) mod p)) mod p
        seed=(seed xor ((seed<<5) mod p)) mod p
        return ret
    for i=1 to k: 
        a[i]=(rnd() mod n) + 1

其中 $seed$ 由输入给定。 

rnd 函数的 C++ 代码如下： 
    
    
    unsigned seed;
    unsigned rnd(){
    	unsigned ret=seed;
    	seed^=seed<<13;
    	seed^=seed>>17;
    	seed^=seed<<5;
    	return ret;
    }

## 输入描述:
    
    
    一行三个整数 $n,k,seed$。其中 $seed$ 用来生成 $a$ 数列。
    
    $1 \le n,k \le 5 \times 10^6,0 \le seed < 2^{32}$。

## 输出描述:
    
    
    一行一个整数表示答案。

示例1 

## 输入
    
    
    6 3 5

## 输出
    
    
    5

## 说明
    
    
    根据参数生成的 $a=[6,4,2]$。  
      
    若答案 $x=1$，则询问都有效。  
      
    若答案 $x=3$，则询问都有效。  
      
    若答案 $x=5$，则询问 $a_3$ 无效。  
      
    若答案 $x=2,4,6$，则在小 C 的询问列表中。  
      
    因此 $x=5$ 是使得无效询问次数最多的最小答案。  
    

示例2 

## 输入
    
    
    6 2 5

## 输出
    
    
    1

## 说明
    
    
    生成的 $a=[6,4]$。  
    答案 $x=1,2,3,5$ 时，询问都有效。  
    因此 $x=1$ 是最小的满足条件的答案。  
    

示例3 

## 输入
    
    
    14 6 4

## 输出
    
    
    4

示例4 

## 输入
    
    
    32 6 25

## 输出
    
    
    28

示例5 

## 输入
    
    
    52052 1206 13149999

## 输出
    
    
    11800

## 备注:
    
    
    在 C++ 中，unsigned int 的运算会自动对 $2^{32}$ 取模。  
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 最后DISCO

## 题目描述

___你迷离的 身影 散逸 宛如 烟霾_  
_我痴醉中 追寻 寻回忆 的灿烂_  
_顺着律动 摇摆 摆到 曲终人散_  


_再去重播 让整个 世界 都狂欢_

_——阿良良木健《最后DISCO》_

  


给你 $4$ 个整数 $a,b,c,d$，你需要回答 $(a^b)\times c+d$ 是奇数还是偶数。  


## 输入描述:
    
    
    一行 $4$ 个数，$a,b,c,d$。$(1 \le a \le 10^9,0 \le b,c,d \le 10^9 )$  
    

## 输出描述:
    
    
    一行一个字符串。如果是奇数，输出 YES，否则输出 NO。  
    

示例1 

## 输入
    
    
    3 4 5 6

## 输出
    
    
    YES

示例2 

## 输入
    
    
    1 0 2 4

## 输出
    
    
    NO

## 备注:
    
    
      
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 末日DISCO

## 题目描述

_明白 你那份跳动的爱_  
_别再 装作着无所谓的姿态_  
_现在 就跟着节奏摇摆_  


_将所有的伪装抛开_

_——阿良良木健《末日DISCO》_  


  


给定一个正整数 $n$，你需要构造 $n$ 个集合 $S_1,S_2,\dots, S_n$，每个集合均含有 $n$ 个元素，且满足：  
1\. 在每个集合中，每个数最多出现 $1$ 次。  
2\. 任意两个集合 $S_i,S_j$ 满足 $i \neq j$，都有 $|S_i \cap S_j|=1$，即 $S_i$ 和 $S_j$ 的交集的大小均为 $1$。  
3\. 对于所有在 $S_1,S_2,\dots S_n$ 中出现过的元素 $x$，$x$ 在所有集合的出现次数之和必须小于等于 $2$。  
4\. 集合中的元素 $x$ 必须满足 $1 \le x \le10^6$。 

## 输入描述:
    
    
    一行一个正整数 $n$。$( 1 \le n \le 500)$

## 输出描述:
    
    
    $n$ 行，每行 $n$ 个正整数，表示答案。

示例1 

## 输入
    
    
    3

## 输出
    
    
    1 2 3
    3 4 5
    1 5 6

## 备注:
    
    
      
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld
# 明日DISCO

## 题目描述

_燃烧的梦想是最初的歌_  


_相信自己其实你眼光仍清澈_

_就在你许下 愿望的那刻_

_让那天空铺上绚丽的颜色_

_——阿良良木健《明日DISCO》_

  


你有一个 $n+2$ 行，$n+2$ 列的正方形棋盘，行和列的编号都是 $0,1,\dots, n+1$。  
  
这个棋盘上的每个格子都有一个数。棋盘的第 $0$ 行、第 $0$ 列、第 $n+1$ 行、第 $n+1$ 列的所有数都是 $0$。记坐标为 $(x,y)$ 个格子上的数为 $a_{x,y}$。  
  
你可以执行任意次操作。操作有两种类型：  
  
1\. 选择一个格子 $(x,y)$ 满足 $1\le x,y\le n$ 且 $a_{x,y}$ 均大于它上下左右的 $4$ 个数，将 $a_{x,y}$ 减去 $1$。  
  
2\. 选择一个格子 $(x,y)$ 满足 $1\le x,y\le n$ 且 $a_{x,y}$ 均小于它上下左右的 $4$ 个数，将 $a_{x,y}$ 加上 $1$。  
  
问你最后能否使得这个棋盘上的所有数均相等。  


## 输入描述:
    
    
    第一行一个数 $n$。  
      
    
    
    接下来 $n$ 行，每行 $n$ 个数。第 $i$ 行的第 $j$ 个数表示 $a_{i,j}$。
    
      
    
    
    $( 1 \le n \le 500,-10^9 \le a_{i,j} \le 10^9)$  
    

## 输出描述:
    
    
    如果可以，请输出一行一个字符串 YES，否则输出 NO。

示例1 

## 输入
    
    
    1
    1

## 输出
    
    
    YES

示例2 

## 输入
    
    
    2
    0 0
    1 1

## 输出
    
    
    NO

示例3 

## 输入
    
    
    2
    0 0
    -1 0

## 输出
    
    
    YES

## 备注:
    
    
      
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 太阳系DISCO

## 题目描述

_あの一等星のさんざめく光で_  
_那颗一等星正在放着喧嚣的光芒_  
_あなたとダンスを踊ろうか_  
_我们一起来跳舞怎么样_  
_我が太陽系の法則に誘われ_  
_我被太阳系的引力所捕获_  
_交わった感度で綺羅めいて、星ッ！_  


_相互照耀，闪耀起光芒！_

_——ナユタン星人《太陽系デスコ》_  


  


平行世界的太阳系中，星球可以被抽象为一个长度为 $n$ 的环，它们分别编号为 $1,2,\dots n$ （按照顺时针排列），相邻两个星球之间的距离均相等（将这个环 $n$ 等分）。保证 $n$ 是偶数。  
  
初始你在 $a$ 号星球，你想要达到 $b$ 号星球。每次你可以花费 $1$ 的时间，顺时针移动 $x$ 个星球的距离，或者逆时针移动 $y$ 个星球的距离。  
  
你也可以发动 $k$ 次技能。发动技能会花费 $1$ 的时间，让你顺时针移动 $\frac{n}{2}$ 个星球，即太阳系中你对面的那个星球。  
  
问你最少花费多少时间。  


## 输入描述:
    
    
    一行 $6$ 个数，依次为 $n,k,a,b,x,y$。
    
      
    
    
    $(2 \le n \le 2\times 10^5, 1 \le a,b,x,y \le n,0 \le k \le 2\times 10^5 )$  
    

## 输出描述:
    
    
    一行一个数，最小花费的时间。如果永远不能到达，输出 -1。

示例1 

## 输入
    
    
    4 0 1 2 2 1

## 输出
    
    
    2

示例2 

## 输入
    
    
    4 114514 1 3 1 1

## 输出
    
    
    1

示例3 

## 输入
    
    
    4 114514 1 2 2 2

## 输出
    
    
    -1

## 备注:
    
    
      
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 普通DISCO-1

## 题目描述

_普通的 disco我们普通的摇_  
_旁边普通的路人在普通的瞧_  
_我普通的灵魂在普通地出窍_  


_在普通的动次打次中普通地燃烧_

_——ilem《普通DISCO》_

  


**请注意，本题和F题****普通DISCO-2 的区别在于，本题要求使得深度最大化。**

  


给你一棵 $n$ 个节点的树，树根为 $1$ 号节点。  
你可以最多执行**一次** 以下操作（它们是一个整体）：  


  * 选择两个不同的节点 $u,v$ 满足 $u,v$ 均不是树根且 $u,v$ 互相不呈祖先关系。 
  * 记 $u$ 的父亲为 $p$，$v$ 的父亲为 $q$。 
  * 断掉 $u$ 与 $p$，$v$ 与 $q$ 之间的边。 
  * 连接 $u$ 与 $q$，$v$ 与 $p$。 

你需要使得最终这棵树的深度**最大化** 。请输出这个深度。  


## 输入描述:
    
    
    第一行一个正整数 $n$，表示节点个数。  
      
    
    
    接下来 $n-1$ 行，每行 $2$ 个数 $u,v$，表示 $u$ 与 $v$ 之间有一条边。
    
      
    
    
    $( 3 \le n \le 5\times 10^5 )$  
    

## 输出描述:
    
    
    一行一个数，最大可能达到的深度。

示例1 

## 输入
    
    
    6
    1 2
    2 3
    2 4
    4 5
    3 6

## 输出
    
    
    5

## 备注:
    
    
    ![](https://uploadfiles.nowcoder.com/images/20241202/0_1733069500685/08217126369C4811D6DBBA82D3286F10)![](https://uploadfiles.nowcoder.com/images/20241202/0_1733069512536/EBF7F47AA7898619F360D8EF859B542F)


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 普通DISCO-2

## 题目描述

_普通的 disco我们普通的摇  
我普通的心在扑通扑通的跳  
有普通的热情在普通的尖叫  
_

_在普通的动次打次之中冲上云霄_

_——ilem《普通DISCO》_

**  
**

**请注意，本题和E题****普通DISCO-1 的区别在于，本题要求使得深度最小化。**

  


给你一棵 $n$ 个节点的树，树根为 $1$ 号节点。  
你可以最多执行**一次** 以下操作（它们是一个整体）：  


  * 选择两个不同的节点 $u,v$ 满足 $u,v$ 均不是树根且 $u,v$ 互相不呈祖先关系。 
  * 记 $u$ 的父亲为 $p$，$v$ 的父亲为 $q$。 
  * 断掉 $u$ 与 $p$，$v$ 与 $q$ 之间的边。 
  * 连接 $u$ 与 $q$，$v$ 与 $p$。 

你需要使得最终这棵树的深度**最小化** 。请输出这个深度。 

## 输入描述:
    
    
    第一行一个正整数 $n$，表示节点个数。  
      
    
    
    接下来 $n-1$ 行，每行 $2$ 个数 $u,v$，表示 $u$ 与 $v$ 之间有一条边。
    
      
    
    
    $(3 \le n \le 5\times 10^5)$  
    

## 输出描述:
    
    
    一行一个数，最小可能达到的深度。

示例1 

## 输入
    
    
    6
    1 2
    2 3
    2 6
    3 4
    4 5

## 输出
    
    
    4

## 备注:
    
    
    ![](https://uploadfiles.nowcoder.com/images/20241202/0_1733069561722/F10C57B2C52364F3BF4E2852B5FA2695)![](https://uploadfiles.nowcoder.com/images/20241202/0_1733069568145/CC9D1CD6C0B285BD2FE1C710D153B4FD)  
    


## 时空限制

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# lz的吃饭问题

## 题目描述

$lz$和$gzy$每天吃饭不知道吃什么，他俩就摇俩个骰子，他们去比较两个骰子乘积的大小，谁的小就谁决定，如果相等由$gzy$决定。（骰子是$n$面的）。

## 输入描述:
    
    
    第一行两个整数$a1,b1$表示$lz$的两个骰子的点数
    
    第二行两个整数$a2,b2$表示$gzy$的两个骰子的点数  
    

## 输出描述:
    
    
    如果由$lz$决定这顿饭吃什么就输出$lz$，反之亦然

示例1 

## 输入
    
    
    3 4
    4 5

## 输出
    
    
    lz

## 说明
    
    
    $3 * 4 < 4 *5$故输出$lz$

## 备注:
    
    
    $1\leq n \leq 100$


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# lz的数字问题

## 题目描述

lz得到了两个**正实数** $a,b$，他想知道这两个数是否相等，但由于数字太长，他自己不会判断了，想请你帮助他。 

**定义两个实数相等的条件是整数部分完全相同且小数部分最高的****6****位****完全相同，不考虑小数部分第7位的进位问题。**

保证数字长度不超过$2e5$，且不包含前导$0$ 

## 输入描述:
    
    
    一行，两个正实数$a,b$

## 输出描述:
    
    
    如果相同输出$YES$，否则输出$NO$

示例1 

## 输入
    
    
    10 10.0000001

## 输出
    
    
    YES

示例2 

## 输入
    
    
    10 10.000001

## 输出
    
    
    NO


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# lz的蛋挞问题

## 题目描述

lz买了一些奶贝和蛋挞，恰好可以放满一个两行$n$列的盒子。 

假定在上下左右四个方向相邻的蛋挞之间有一条路径。定义蛋挞连通块为一组蛋挞，这组蛋挞中任意两个蛋挞都连通。 

如下图，白色代表蛋挞，黑色方格代表奶贝。 

![](https://uploadfiles.nowcoder.com/images/20241117/0_1731853609024/74DBAA0CA35EEDD4A74EE3212500D034)

现在lz只允许你吃掉一个蛋挞，并在其原来的位置上放一个奶贝，并要求**蛋挞的连通块的数量发生变化** 。 

例如上述情况，我们吃掉第一行的第一个蛋挞，则蛋挞的连通块的数量**由3变为4。**

现在lz想知道有多少个蛋挞被吃掉后可以改变蛋挞的联通块的数量  


## 输入描述:
    
    
    第一行输入一个整数$n(1≤n≤2⋅10^5)$表示列数  
    接下来**2** 行，每行**n** 个字符，每个字符是 **.** （表示蛋挞）或 **x** （表示奶贝）  
      
    

## 输出描述:
    
    
    一个整数，表示答案。

示例1 

## 输入
    
    
    8
    ..x....x
    .x.xx...

## 输出
    
    
    5


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# lz的染色问题

## 题目描述

在$lz$的花园里有$n$朵花，每朵花都有自己的颜色$c_i$，在以后的$m$天里，他每天都会观察两朵花$i$和$j$，但他有强迫症，如果两朵花的颜色不同，他会生气。 

你需要挑选最少数量的花，依次将他们重新染色，使得$lz$不会生气。输出最少的需要重新染色的花的数量。 

## 输入描述:
    
    
    第一行包括两个整数$n$，$m$($2 \leq n \leq 2 *10^{5}, 1 \leq m \leq 2 *10^{5}$)表示花的总数和天数   
    第二行包括n个整数$c_i$($1 \leq c_i  \leq n$)，表示每朵花的颜色    
    后面$m$行，每行包括两个不同的整数$i,j$($1 \leq i,j \leq n$)，表示$lz$每天要观察的花的序号  
      
    

## 输出描述:
    
    
    输出一个整数表示最小染色次数

示例1 

## 输入
    
    
    4 2
    1 2 3 4
    1 2
    3 4

## 输出
    
    
    2


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# lz的括号问题

## 题目描述

给定一个由$n$对括号组成的字符串，按每个$($出现的先后顺序给每对括号编号，比如$((()))(())$，编号后为$1233214554$。 

每两个相同的数字代表的是原字符串中匹配的括号，每对匹配上的括号会直接删除（括号匹配的定义为：你可以从给定字符串中任意选择一个长度为$2$且为$()$的连续子序列删除，并将删除位置后面的所有下标减$2$）。 

按顺序输出每对括号删除之前**至多** 可以删除多少对括号，如果不能匹配上所有括号则输出$-1$。 

## 输入描述:
    
    
    第一行一个整数$n(1 \leq n \leq 10^5)$
    
    第二行一个字符串$s$，仅由$()$组成长度为$2*n$

## 输出描述:
    
    
    一行$n$个整数，表示第$i$对括号在删除前最多删除多少对括号

示例1 

## 输入
    
    
    5
    ((()))(())

## 输出
    
    
    4 3 2 4 3

## 说明
    
    
    编号为$1$的括号可以在其他所有括号删除之后删除，答案为$4$  
    编号为$2$的括号不能在编号为$1$的括号之前删除，答案为$3$  
    编号为$3$的括号不能在编号为$1,2$的括号之前删除，答案为$2$

示例2 

## 输入
    
    
    3
    (()))(

## 输出
    
    
    -1

## 说明
    
    
    所有的括号无法匹配


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# lz的序列问题

## 题目描述

定义一段区间$[l,r]$的美丽值为$(a_{l} + a_{l} * a_{l +1} +a_{l} * a_{l +1} * a_{l + 2} +......+a_{l}*...*a_{r})$。  


已知一段序列有 $n$ 个数，第 $i$ 个数为$a_{i}( 1 \leq a_{i} \leq 10^{9})$。你需要对序列进行 $q$ 次操作。 

每次可进行以下两种操作中的一种： 

1、将区间 $[l,r]$ 内每一个数都改为 $x$ 。 

2、输出区间 $[l,r]$ 的美丽值。 

## 输入描述:
    
    
    第一行两个整数$n ( 1 \leq n \leq 10 ^ {5})$，$q( 1 \leq q \leq 10^{5})$。
    
    第二行 $n$ 个整数表示数组$a$，其中$1 \leq a_{i} \leq 10^{9}$。
    
    接下来 $q$ 行，每行首先输入一个整数 $op$ 表示操作类型。
    
    若$op == 1$，同一行输入$3$个整数$l，r，x (1 \leq l\leq r \leq n, 1 \leq x \leq 10^{9})$。  
    
    
    若$op==2$同一行输入$2$个整数
    
    $l，r (1 \leq l\leq r \leq n)$。  
    
    
      
    

## 输出描述:
    
    
    输出若干行整数，即为所有操作 $2$ 的结果。
    
    答案可能很大, 输出对 $1000000007$ 取模的结果.

示例1 

## 输入
    
    
    5 5
    1 2 3 4 5
    2 1 3
    2 2 5
    1 1 3 2
    1 2 4 3
    2 1 5

## 输出
    
    
    9
    152
    350


## 时空限制

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 小红购买装备

## 题目描述

小红准备去打地下城，在进入地下城之前首先需要购买合适的装备。  
已知商店共有$n$件装备，每种装备提供$a_i$的攻击和$b_i$的防御，价格为$c_i$，小红身上已有的装备攻击为$x$，防御为$y$，该装备卖给商店可以回收$z$金币。另外小红拥有的金币数量为$T$。  
小红的战斗力计算为攻击+防御。现在小红想知道自己最终从装备处可以获得的战斗力最大值是多少？  
注：小红最多只能生效一件装备！

## 输入描述:
    
    
    第一行输入五个正整数$n,x,y,z,T$，分别代表商店的装备数量、小红身上的装备攻击、防御、回收价格，以及小红携带的金币。  
    接下来的$n$行，每行输入三个正整数，代表商店每件装备的攻击、防御和金币数量。  
    $1\leq n\leq 10^5$  
    $1\leq x,y,z,a_i,b_i,c_i,T \leq 10^9$

## 输出描述:
    
    
    一个正整数，代表小红从装备处获得的最高战斗力。

示例1 

## 输入
    
    
    2 100 30 50 100
    120 50 120
    200 100 1000

## 输出
    
    
    170

## 说明
    
    
    小红卖掉身上的装备，购买第一件装备即可。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 小红招募英雄

## 题目描述

小红将装备整备完毕，准备招募共同冒险的英雄。  
已知英雄共有5种稀有度：N、R、SR、SSR、UR。小红每次招募将优先选择稀有度为SSR和UR的英雄。小红一共需要2名队友，现在给出每次招募出每个稀有度的概率，请你帮小红计算单次十连抽（等同于抽取10次）即可凑齐队友（即不小于2名SSR以上稀有度英雄）的概率。

## 输入描述:
    
    
    五个小数$p_1,p_2,p_3,p_4,p_5$，分别代表单次抽取时，N、R、SR、SSR、UR被抽到的概率。  
    $0\leq p_1,p_2,p_3,p_4,p_5 \leq 1$  
    $p_1+p_2+p_3+p_4+p_5=1$

## 输出描述:
    
    
    一个小数，代表小红单次十连抽即可凑齐两名队友的概率。如果相对误差或绝对误差不超过 $10^{-6}$ ，您的答案将被接受。具体来说，设您的答案为 $a$ ，裁判的答案为 $b$ ，当且仅当 $\frac{|a-b|}{\max(1,|b|)}\le 10^{-6}$ 时，您的答案将被接受。  
    

示例1 

## 输入
    
    
    0.2 0.2 0.2 0.2 0.2

## 输出
    
    
    0.9536425984


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld
# 小红打怪

## 题目描述

有$n$个怪物排成一排，小红和队友们准备进攻这些怪物。  
小红的技能是全体打击，对所有怪物造成1点伤害。  
队友1的技能是单体打击，对单体怪物造成1点伤害。  
队友2的技能是范围攻击，对相邻的两只怪物分别造成1点伤害（可以对死去的怪物尸体释放该技能）。  
  
每回合每个人均可释放1次技能。小红想知道，击杀全部怪物最少需要多少回合？

## 输入描述:
    
    
    第一行输入一个正整数$n$，代表怪物的总数。  
    第二行输入$n$个正整数$a_i$，代表每个怪物的血量。  
    $2\leq n \leq 10^5$  
    $1\leq a_i \leq 10^9$

## 输出描述:
    
    
    一个整数，代表击杀全部怪物的最少回合数。

示例1 

## 输入
    
    
    5
    1 2 3 4 5

## 输出
    
    
    2

## 说明
    
    
    第一回合，小红攻击全体怪物，队友1攻击5号怪物，队友2攻击4号和5号怪物，剩余每只怪物血量为[0,1,2,2,2]。  
    第二回合，小红攻击全体怪物，队友1攻击5号怪物，队友2攻击3号和4号怪物，即可击杀所有怪物。  
    
    
      
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 小红开锁

## 题目描述

小红来到了地下城的门口，发现门口有一个密码锁。  
这个锁一共有$n$层，每层为一个正方形的图案。小红每次操作一次可以选择一层使其每个位置的元素按顺时针移动一个格子。  
该图演示一个3层的锁，小红操作第二层时的变化。  
![](https://uploadfiles.nowcoder.com/images/20241106/0_1730886143007/964EE62FEED27780FA70B8F08B971546)  
该锁以中心为原点建立平面直角坐标系后，每个象限为一个区域，共分为4个区域，当且仅当某个区域内全部为'X'图案、且其余三个区域全部为'O'图案时，锁被解开。  
小红想知道，这个锁需要操作最少多少次可以解开？

## 输入描述:
    
    
    第一行输入一个正整数$n$，代表锁的层数。  
    接下来输入$2n$行，每行输入一个长度为$2n$的字符串，用来表示锁的初始图案。  
    $1\leq n \leq 100$  
    保证存在一个合法的开锁方式。

## 输出描述:
    
    
    一个整数，代表小红需要操作的最少次数。

示例1 

## 输入
    
    
    2
    OXXX
    OOOO
    OXOO
    OOOO

## 输出
    
    
    3

## 说明
    
    
    对内层操作2次，对外层操作1次即可开锁。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 小红开宝箱

## 题目描述

小红来到了一个宝箱面前，但这个宝箱上锁了，开这个宝箱需要进行解密。  
  
解密的方式是：给出了$n$根柱子，小红必须按照规定的次序依次击打这$n$根柱子。  
  
现在小红通过贿赂地下城的设计者小紫，得出了每次应击打的柱子的可能性。小红想让你帮忙设计一个击打顺序，使得该顺序和小紫给出的信息不冲突。

## 输入描述:
    
    
    第一行输入一个正整数$n$，代表柱子的数量。  
    接下来的$n$行，每行首先输入一个正整数$k_i$，代表对于第$i$次击打小紫给出的信息（柱子的可能性）数量。紧接着是$k_i$个正整数$p_{ij}$，代表该次击打有可能是哪一个柱子。  
    $1\leq n \leq 10^5$  
    $1\leq k_i \leq 2$  
    $1\leq p_{ij} \leq n$

## 输出描述:
    
    
    如果不存在一个合法解，代表小紫欺骗了小红，请输出"kou is angry"。否则输出一个长度为$n$的排列，代表一个合法的击打序列。有多解时输出任意即可。  
    

示例1 

## 输入
    
    
    3
    1 2
    2 1 3
    2 1 3

## 输出
    
    
    2 1 3

## 说明
    
    
    输出2 3 1也是可以的。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld
# 小红闯地下城

## 题目描述

已知地下城是树形结构，一共有$n$个房间，$n-1$条双向通路。入口和出口都在1号房间，每个房间有1只怪物，小红进入房间后必须先击杀怪物。  
每个房间有一个通往其他房间的单向传送阵。小红可以使用最多1次传送。  
当小红通过道路或者传送阵移动到其他房间时，将消耗1点体力。击杀1只怪物同样也需要1点体力。  
小红初始有$x$点体力。她想知道，最多可以击杀多少只怪物？  
请注意，小红最终必须回到1号房间离开地下城。击杀的怪物不能复生。

## 输入描述:
    
    
    第一行输入两个正整数$n,x$，用空格隔开，分别代表房间的数量和小红的初始体力。  
    第二行输入$n$个正整数$a_i$，代表每个房间的传送阵通向的房间编号。  
    接下来的$n-1$行，每行输入两个正整数$u,v$，代表房间$u$和房间$v$有一条通路。  
    $1\leq n \leq 200000$  
    $1\leq a_i,u,v \leq n$  
    $1 \leq x \leq 1000000$

## 输出描述:
    
    
    一个整数，代表小红可以击杀的怪物最大数量。

示例1 

## 输入
    
    
    3 2
    2 3 1
    1 2
    2 3

## 输出
    
    
    1

## 说明
    
    
    小红只有2点体力，她首先击杀1号房间的怪物，消耗1点体力，然后就什么都做不了了（如果离开1号房间就回不来了）。  
    
    
      
    

示例2 

## 输入
    
    
    3 6
    1 3 1
    1 2
    1 3

## 输出
    
    
    3

## 说明
    
    
    小红安排体力的流程如下：  
    击杀1号房间怪物，消耗1体力。  
    移动到2号房间，消耗1体力。  
    击杀2号房间怪物，消耗1体力。  
    传送到3号房间，消耗1体力。  
    击杀3号房间怪物，消耗1体力。  
    移动到1号房间，消耗1体力。  
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 冰冰的正多边形

## 题目描述

fresh_boy 给你 $n$ 根木棍，求用这 $n$ 根木棍中的任意根能拼成的正多边形中周长最小的正多边形周长是多少？要求拼成的正多边形的每条边仅能由一根木棍构成。若不能拼成任何正多边形，请输出 no。 

  


正多边形是指二维平面内各边相等，各角也相等的多边形，也叫正多角形。

  


正三角形（正三边形），正方形（正四边形），正五边形，正六边形如下：  


  


![](https://uploadfiles.nowcoder.com/images/20241017/0_1729177918326/4A47A0DB6E60853DEDFCFDF08A5CA249)  


  


## 输入描述:
    
    
    多组测试数据。  
      
    第一行一个正整数 $t(1\leq t\leq 10^3)$ 表示数据组数。  
      
    接下来 $t$ 组数据，每组数据两行：  
      
    第一行一个正整数 $n(1\leq n\leq 10)$ 表示木棍数目。  
      
    接下来一行 $n$ 个正整数 $a_i(1\leq a_i\leq 100)$ 表示第 $i$ 根木棍的长度。

## 输出描述:
    
    
    输出共 $t$ 组，每组第一行 "no"（不含引号） 表示无解，或 "yes"（不含引号） 表示可以拼成至少一个正多边形。若可以拼成至少一个正多边形，则第二行输出一个正整数表示能拼成的正多边形中周长最小的正多边形周长，
    
      
    
    
    可以以任何大小写(大写或小写)输出 "yes" 和 "no"。例如，字符串“yEs”、“yes”、“Yes” 和 “YES” 将被判定为正确。  
    

示例1 

## 输入
    
    
    3
    1
    1
    3
    3 3 3
    4
    1 1 2 2

## 输出
    
    
    no
    yes
    9
    no

## 说明
    
    
    对于第一组数据，一根木棍无法构成任何正多边形。  
    
    
    对于第二组数据，只能构成一个边长为 $3$ 的正三角形，其周长为 $9$。
    
    对于第三组数据，因为拼成的正多边形每条边仅能由一根木棍构成，所以无法使用 $1,1,2,2$ 组成任何正多边形。  
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

Difficulty: 700
# 冰冰的电子邮箱

## 题目描述

给定一个字符串，验证是否是电子邮箱。  
  
fresh_boy 为了简化问题，发明了一个新的电子邮箱命名规范。（注意此处的电子邮箱格式与常规的电子邮箱格式要求的区别）  
  
fresh 电子邮件地址格式如下：  
  
local-part@domain  
  
其中：  
  
\- `local-part` 本地部分，是电子邮件地址的用户名称。  
\- `domain` 域名部分，是电子邮件地址所属的域名。  
\- 中间用一个 `@` 连接。  
  
local-part（本地部分）  
  
1\. 字符范围：  
\- 可以包含字母（a-z, A-Z）、数字（0-9）。  
\- 可以包含点 .，但不能出现在开头或结尾。  
  
2\. 长度限制：  
\- 最长 $64$ 个字符，最短 $1$ 个字符。  
  
domain（域名部分）  
  
1\. 字符范围：  
\- 可以包含字母（a-z, A-Z）、数字（0-9）。  
\- 可以包含点 .，但不能出现在开头或结尾。  
\- 可以包含分隔符 -，但不能出现在开头或结尾。  
  
2\. 长度限制：  
\- 最长 $255$ 个字符，最短 $1$ 个字符。

## 输入描述:
    
    
    多组测试数据，第一行一个正整数 $t(1\leq t\leq 10^2)$ 表示数据组数。  
      
    接下来 $t$ 行，每行一个字符串 $s(1\leq |s|\leq 350)$，保证输入字符为 ASCII 码值在 $[32,126]$ 之间的可显示字符，且不含空格。

## 输出描述:
    
    
    共 $t$ 行，每行一个字符串 `Yes` 表示电子邮箱格式正确，`No` 表示电子邮箱格式不正确。

示例1 

## 输入
    
    
    8
    example@example.com
    user.nametagsorting@example.com
    user-name@sub.domain.com
    plainaddress
    @example.com
    user@.com
    user@com
    user@-example.com

## 输出
    
    
    Yes
    Yes
    No
    No
    No
    No
    Yes
    No


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Difficulty: 900