NIRVANA

Problem

Bounce 弹飞绵羊

Description

某天，$\mathrm{Lostmonkey}$发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，$\mathrm{Lostmonkey}$在地上沿着一条直线摆上$n$个装置，每个装置设定初始弹力系数$k_i$，当绵羊达到第$i$个装置时，它会往后弹$k_i$步，达到第$i+k_i$个装置，若不存在第$i+k_i$个装置，则绵羊被弹飞。绵羊想知道当它从第$i$个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，$\mathrm{Lostmonkey}$可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

Input

第一行包含一个整数$n$，表示地上有$n$个装置，装置的编号从$0$到$n-1$,接下来一行有$n$个正整数，依次为那$n$个装置的初始弹力系数。第三行有一个正整数$m$，接下来$m$行每行至少有两个数$i$、$j$，若$i=1$，你要输出从$j$出发被弹几次后被弹飞，若$i=2$则还会再输入一个正整数$k$，表示第$j$个弹力装置的系数被修改成$k$。

Output

对于每个$i=1$的情况，你都要输出一个需要的步数，占一行。

Problem

阿狸的打字机

Description

阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有$28$个按键，分别印有$26$个小写英文字母和$B$、$P$两个字母。
经阿狸研究发现，这个打字机是这样工作的：

• 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
• 按一下印有$B$的按键，打字机凹槽中最后一个字母会消失。
• 按一下印有$P$的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。

例如，阿狸输入$aPaPBbP$，纸上被打印的字符如下：
$a$
$aa$
$ab$
我们把纸上打印出来的字符串从$1$开始顺序编号，一直到$n$。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数$(x,y)$（其中$1\le x,y\le n$），打字机会显示第$x$个打印的字符串在第$y$个打印的字符串中出现了多少次。
阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？

Input

输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。
第二行包含一个整数$m$，表示询问个数。
接下来$m$行描述所有由小键盘输入的询问。其中第$i$行包含两个整数$x$, $y$，表示第$i$个询问为$(x, y)$。

Output

输出$m$行，其中第$i$行包含一个整数，表示第$i$个询问的答案。

Problem

Count on a tree

Description

给定一棵$N$个节点的树，每个点有一个权值，对于$M$个询问$(u,v,k)$，你需要回答$u\ \ xor\ \ lastans$和$v$这两个节点间第$K$小的点权。其中$lastans$是上一个询问的答案，初始为$0$，即第一个询问的$u$是明文。

Input

第一行两个整数$N,M$。
第二行有$N$个整数，其中第$i$个整数表示点$i$的权值。
后面$N-1$行每行$2$个整数$(x,y)$，表示点$x$到点$y$有一条边。
最后$M$行每行$3$个整数$(u,v,k)$，表示一组询问。

Output

$M$行，表示每个询问的答案。最后一个询问不输出换行符

Problem

可持久化并查集 by zky

Description

$n$个集合 $m$个操作
操作：
$1\;a\;b$ 合并$a,b$所在集合
$2\;k$ 回到第$k$次操作之后的状态(查询算作操作)
$3\;a\;b$ 询问$a,b$是否属于同一集合，是则输出$1$否则输出$0$

Input

第一行两个整数$n,m$
以后$m$行，每行三个或两个整数$opt\;a\;b$或$opt\;k$，意义如上所述

Ouput

对于每个$3$操作，输出$1/0$

Problem

Three Palindromes

Description

Can we divided a given string $S$ into three nonempty palindromes?

Input

First line contains a single integer $T\le 20$ which denotes the number of test cases.
For each test case , there is an single line contains a string $S$ which only consist of lowercase English letters.$1\le |s|\le 20000$

Output

For each case, output the Yes or No​ in a single line.

Problem

Matrix

Time Limit: $3000MS$
Memory Limit: $65536K$

Description

Given an $N\times N$ matrix $A$, whose elements are either $0$ or $1$. $A[i, j]$ means the number in the $i^{th}$ row and $j^{th}$ column. Initially we have $A[i, j] = 0 (1 \le i, j\le< N)$.
We can change the matrix in the following way. Given a rectangle whose upper-left corner is $(x_1, y_1)$ and lower-right corner is $(x_2, y_2)$, we change all the elements in the rectangle by using “not” operation (if it is a ‘$0$’ then change it into ‘$1$’ otherwise change it into ‘$0$’). To maintain the information of the matrix, you are asked to write a program to receive and execute two kinds of instructions.

1. $C$ $x_1$ $y_1$ $x_2$ $y_2$ ($1\le x_1\le x_2\le n, 1\le y_1\le y_2\le n$) changes the matrix by using the rectangle whose upper-left corner is $(x_1, y_1)$ and lower-right corner is $(x_2, y_2)$.
2. $Q$ $x$ $y$ ($1\le x, y\le n$) querys $A[x, y]$.

Input

The first line of the input is an integer $X (X \le 10) $representing the number of test cases. The following X blocks each represents a test case.
The first line of each block contains two numbers $N$ and $T$ ($2 \le N \le 1000$, $1 \le T \le 50000$) representing the size of the matrix and the number of the instructions. The following $T$ lines each represents an instruction having the format “$Q$ $x$ $y$” or “$C$ $x_1$ $y_1$ $x_2$ $y_2$”, which has been described above.

Output

For each querying output one line, which has an integer representing $A[x, y]$.
There is a blank line between every two continuous test cases.

Problem

Intervals

Description

You are given $n$ closed, integer intervals $[a_i, b_i]$ and $n$ integers $c_1\sim c_n$.
Write a program that:
reads the number of intervals, their end points and integers $c_1\sim c_n$ from the standard input, computes the minimal size of a set $Z$ of integers which has at least $c_i$ common elements with interval $[a_i, b_i]$, for each $i=1,2,\cdots ,n$, writes the answer to the standard output.

Input

The first line of the input contains an integer $n$ ($1\le n\le 5\times 10^4$) – the number of intervals. The following n lines describe the intervals. The $(i+1)^{th}$ line of the input contains three integers $a_i$, $b_i$ and $c_i$ separated by single spaces and such that $0\le a_i\le b_i\le 5\times 10^4$ and $1\le c_i\le b_i - a_i+1$.

Output

The output contains exactly one integer equal to the minimal size of set $Z$ sharing at least $c_i$ elements with interval $[a_i, b_i]$, for each $i=1,2,\cdots ,n$.

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment