YZOJ P4578 [CSP-S 2019 四校联训 Round 1]树上排列

YZOJ P4578 [CSP-S 2019 四校联训 Round 1]树上排列

时间限制:4000MS      内存限制:524288KB

难度:\(7.0\)

  • 题目描述

给定一颗 \(n\) 个点的树。每个点都一个正整数点权 \(A_i\),你需要支持以下两种操作:

1、询问点 \(x\) 和点 \(y\) 之间的路径上的所有点(包括点 \(x\) 和点 \(y\) )的点权是否构成一个从 \(1\) 开始的排列。

2、将 \(A_x\) 修改为 \(y\)。

  • 输入格式

第一行一个正整数 \(T\) 表示数据组数。

接下来一行输入两个正整数 \(n,q\) 表示数的点数和询问个数。

接下来一行 \(n\) 个正整数,第 \(i\) 个正整数表示 \(A_i\) 的初值。

接下来 \(n-1\) 行每行两个正整数 \(u,v\) 表示树上的一条边 \((u,v)\) 。

接下来 \(n\) 行每行三个正整数 \(tp,x,y\) 表示一个操作,其中 \(tp\) 表示操作种类。

  • 输出格式

对于每一个操作 \(1\) 如果符合条件,输出 Yes ,否则输出 No

  • 样例输入


Read the rest

YZOJ T1860-P2 Find

Find

时间限制:1000MS 内存限制:65536KB

  • 题目描述

我们定义两种操作

操作1的格式 :I 字符串 \(S\),加入 1 个字符串 \(S\)。

操作2的格式 :F 字符串\(S\),查找字符串\(S\)是否在当前寻找前已经出现过

注释:同一个字符串可能多次被插入和查找,字符串长度\(\left|S\right|≤20\),字符集为小写英文字母。

  • 输入格式

第一行,指令个数\(N\)。

接下来\(N\)行,每行一个指令。

  • 输出格式

对于每次查找,找到输出 ‘YES’,没找到输出 ‘NO’ 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(40\%\) 的数据 \(N≤5000\)

对于 \(100\%\) 的数据 \(N≤150000\)