NIRVANA

Problem

【HNOI2007】紧急疏散evacuate

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

发生了火警，所有人员需要紧急疏散！假设每个房间是一个$N\times M$的矩形区域。每个格子如果是’$.$‘，那么表示这是一块空地；如果是’$X$’，那么表示这是一面墙，如果是’$D$’，那么表示这是一扇门，人们可以从这儿撤出房间。已知门一定在房间的边界上，并且边界上不会有空地。最初，每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格，当然他也可以站着不动。疏散开始后，每块空地上就没有人数限制了（也就是说每块空地可以同时站无数个人）。但是，由于门很窄，每一秒钟只能有一个人移动到门的位置，一旦移动到门的位置，就表示他已经安全撤离了。现在的问题是：如果希望所有的人安全撤离，最短需要多少时间？或者告知根本不可能。

Input

输入文件第一行是由空格隔开的一对正整数$N$与$M$，$3\le N\le 20$，$3\le M\le 20$，以下$N$行$M$列描述一个$N\times M$的矩阵。其中的元素可为字符’$.$', ‘$X$’和’$D$’，且字符间无空格。

Output

只有一个整数K，表示让所有人安全撤离的最短时间，如果不可能撤离，那么输出’$impossible$’（不包括引号）。

Problem

【SCOI2007】蜥蜴

Description

在一个$r$行$c$列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。 每行每列中相邻石柱的距离为$1$，蜥蜴的跳跃距离是$d$，即蜥蜴可以跳到平面距离不超过$d$的任何一个石柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减$1$（如果仍然落在地图内部，则到达的石柱高度不变），如果该石柱原来高度为$1$，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个石柱上。

Input

输入第一行为三个整数$r$，$c$，$d$，即地图的规模与最大跳跃距离。以下$r$行为石竹的初始状态，$0$表示没有石柱，$1\sim 3$表示石柱的初始高度。以下$r$行为蜥蜴位置，“$L$”表示蜥蜴，“$.$”表示没有蜥蜴。

Output

输出仅一行，包含一个整数，即无法逃离的蜥蜴总数的最小值。

Problem

【HDU4348】To The Moon

$\mathrm{Time\;Limit:\;4000/2000\;MS\;(Java/Others)}$
$\mathrm{Memory\;Limit:\;65536/65536\;KB\;(Java/Others)}$

Description

To The Moon is a independent game released in November 2011, it is a role-playing adventure game powered by RPG Maker.
The premise of To The Moon is based around a technology that allows us to permanently reconstruct the memory on dying man. In this problem, we’ll give you a chance, to implement the logic behind the scene.
You‘ve been given $N$ integers $A[1], A[2],..., A[N]$. On these integers, you need to implement the following operations:

1. $C$ $l$ $r$ $d$: Adding a constant d for every $\{A_i | l \le i \le r\}$, and increase the time stamp by $1$, this is the only operation that will cause the time stamp increase.
2. $Q$ $l$ $r$: Querying the current sum of $\{A_i | l \le i \le r\}$.
3. $H$ $l$ $r$ $t$: Querying a history sum of $\{A_i | l \le i \le r\}$ in time $t$.
4. $B$ $t$: Back to time $t$. And once you decide return to a past, you can never be access to a forward edition anymore.

$N, M \le 10^5$, $|A[i]|\le 10^9$, $1\le l\le r\le N$, $|d|\le 10^4$. The system start from time $0$, and the first modification is in time $1$, $t\ge 0$, and won’t introduce you to a future state.

Input

1
2
3

n m
A1 A2 ... An
... (here following the m operations. )

Output

1

... (for each query, simply print the result. )

PRoblem

最优贸易

题目描述

$C$ 国有 $n$ 个大城市和 $m$ 条道路，每条道路连接这 $n$ 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 $m$ 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 $1$ 条。$C$ 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。
商人阿龙来到 $C$ 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设 $C$ 国 $n$ 个城市的标号从 $1\sim n$，阿龙决定从 $1$ 号城市出发，并最终在 $n$ 号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有 $n$ 个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品――水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来 $C$ 国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。
现在给出 $n$ 个城市的水晶球价格，$m$ 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。

输入输出格式

输入格式：
第一行包含 $2$ 个正整数 $n$ 和 $m$，中间用一个空格隔开，分别表示城市的数目和道路的数目。
第二行 $n$ 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 $n$ 个城市的商品价格。
接下来 $m$ 行，每行有 $3$ 个正整数，$x$，$y$，$z$，每两个整数之间用一个空格隔开。如果 $z=1$，表示这条道路是城市 $x$ 到城市 $y$ 之间的单向道路；如果 $z=2$，表示这条道路为城市 $x$ 和城市 $y$ 之间的双向道路。
输出格式：
输出文件 $trade.out$ 共 $1$ 行，包含 $1$ 个整数，表示最多能赚取的旅费。如果没有进行贸易，则输出 $0$。

Problem

K大数查询

Description

有$N$个位置，$M$个操作。操作有两种，每次操作如果是$1\ a\ b\ c$的形式表示在第$a$个位置到第$b$个位置，每个位置加入一个数$c$；如果是$2\ a\ b\ c$形式，表示询问从第$a$个位置到第$b$个位置，第$c$大的数是多少。

Input

第一行$N$，$M$
接下来$M$行，每行形如$1\ a\ b\ c$或$2\ a\ b\ c$

Output

输出每个询问的结果

Problem

食物链

Description

动物王国中有三类动物$A,B,C$，这三类动物的食物链构成了有趣的环形。$A$吃$B$，$B$吃$C$，$C$吃$A$。
有$N$个动物，以$1\sim N$编号。每个动物都是$A,B,C$中的一种，但是我们并不知道它到底是哪一种。
人用两种说法对这$N$个动物所构成的食物链关系进行描述：
一种说法是$1\;X\;Y$，表示$X$和$Y$是同类。
二种说法是$2\;X\;Y$，表示$X$吃$Y$。
人对$N$个动物，用上述两种说法，一句接一句地说出$K$句话，这$K$句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

• 当前的话与前面的某些真的话冲突，就是假话；
• 当前的话中$X$或$Y$比$N$大，就是假话；
• 当前的话表示$X$吃$X$，就是假话。

你的任务是根据给定的$N（1 \le N \le 50000）$和$K$句话$（0 \le K \le 100000）$，输出假话的总数。

Input

第一行是两个整数$N$和$K$，以一个空格分隔。
以下$K$行每行是三个正整数 $D$，$X$，$Y$，两数之间用一个空格隔开，其中$D$表示说法的种类。
若$D=1$，则表示$X$和$Y$是同类。
若$D=2$，则表示$X$吃$Y$。

Output

只有一个整数，表示假话的数目。

Problem

Shopping Offers

Description

In a shop each kind of product has a price. For example, the price of a flower is $2$ ICU (Informatics Currency Units) and the price of a vase is $5$ ICU. In order to attract more customers, the shop introduces some special offers.
A special offer consists of one or more product items for a reduced price. Examples: three flowers for $5$ ICU instead of $6$, or two vases together with one flower for $10$ ICU instead of $12$.
Write a program that calculates the price a customer has to pay for certain items, making optimal use of the special offers. That is, the price should be as low as possible. You are not allowed to add items, even if that would lower the price.
For the prices and offers given above, the (lowest) price for three flowers and two vases is $14$ ICU: two vases and one flower for the reduced price of $10$ ICU and two flowers for the regular price of $4$ ICU.

Input

Your program is to read from standard input. The first line contains the number $b$ of different kinds of products in the basket $(0 \le b \le 5)$. Each of the next b lines contains three values $c$, $k$, and $p$. The value $c$ is the (unique) product code $(1 \le c \le 999)$. The value $k$ indicates how many items of this product are in the basket $(1 \le k \le 5)$. The value p is the regular price per item $(1 \le p \le 999)$. Notice that all together at most $5\times 5=25$ items can be in the basket. The $b+2^{nd}$ line contains the number $s$ of special offers $(0 \le s \le 99)$. Each of the next $s$ lines describes one offer by giving its structure and its reduced price. The first number n on such a line is the number of different kinds of products that are part of the offer $(1 \le n \le 5)$. The next n pairs of numbers $(c,k)$ indicate that $k$ items $(1 \le k \le 5)$ with product code $c$ $(1 \le c \le 999)$ are involved in the offer. The last number $p$ on the line stands for the reduced price $(1 \le p \le 9999)$. The reduced price of an offer is less than the sum of the regular prices.

Output

Your program is to write to standard output. Output one line with the lowest possible price to be paid.

Problem

最大数

题目描述

现在请求你维护一个数列，要求提供以下两种操作：

1. 查询操作。
   语法：$Q\ \ L$
   功能：查询当前数列中末尾$L$个数中的最大的数，并输出这个数的值。
   限制：$L$不超过当前数列的长度。
2. 插入操作。
   语法：$A\ \ n$
   功能：将$n$加上$t$，其中$t$是最近一次查询操作的答案（如果还未执行过查询操作，则$t=0$），并将所得结果对一个固定的常数$D$取模，将所得答案插入到数列的末尾。
   限制：$n$是整数（可能为负数）并且在长整范围内。

注意：初始时数列是空的，没有一个数。

输入输出格式

输入格式
第一行两个整数，$M$和$D$，其中$M$表示操作的个数$(M\le 2\times 10^5)$，$D$如上文中所述，满足$(0<D<2\times 10^9)$
接下来的$M$行，每行一个字符串，描述一个具体的操作。语法如上文所述。
输出格式
对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。

Problem

【APIO2009】ATM

$\mathrm{Time\;Limit:\;15\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

$\mathrm{Siruseri}$城中的道路都是单向的。不同的道路由路口连接。按照法律规定，在每个路口都设立了一个$\mathrm{Siruseri}$银行的$\mathrm{ATM}$取款机。令人奇怪的是，$\mathrm{Siruseri}$的酒吧都设在路口，虽然并不是每个路口都设有酒吧。
$\mathrm{Banditiji}$计划实施$\mathrm{Siruseri}$有史以来最惊天动地的$\mathrm{ATM}$抢劫。他将从市中心出发，沿着单向道路行驶，抢劫所有他途径的$\mathrm{ATM}$机，最终他将在一个酒吧庆祝他的胜利。
使用高超的黑客技术，他获知了每个$\mathrm{ATM}$机中可以掠取的现金数额。他希望你帮助他计算从市中心出发最后到达某酒吧时最多能抢劫的现金数额。他希望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可以经过同一路口或道路任意多次。但只要他抢劫某个$\mathrm{ATM}$机后，该$\mathrm{ATM}$机就不会再有钱了。

Input

第一行包含两个整数$N$、$M$。$N$表示路口的个数，$M$表示道路条数。接下来$M$行，每行两个整数，这两个整数都在$1$到$N$之间，第$i+1$行的两个整数表示第i条道路的起点和终点的路口编号。接下来$N$行，每行一个整数，按顺序表示每个路口处的$\mathrm{ATM}$机中的钱数。接下来一行包含两个整数$S$、$P$，$S$表示市中心的编号，也就是出发的路口。$P$表示酒吧数目。接下来的一行中有$P$个整数，表示$P$个有酒吧的路口的编号。

Output

输出一个整数，表示$\mathrm{Banditji}$从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。

Problem

维护序列

题目描述

老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为$N$的数列，不妨设为$a_1,a_2,\cdots ,a_N$。有如下三种操作形式： $(1)$把数列中的一段数全部乘一个值; $(2)$把数列中的一段数全部加一个值; $(3)$询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模$P$的值。

输入输出格式

输入格式
第一行两个整数$N$和$P$($1\le P\le 10^9$）。第二行含有N个非负整数,从左到右依次为$a_1,a_2,\cdots ,a_N$, ($0\le a_i\le 10^9,1\le i\le N$)。第三行有一个整数$M$，表示操作总数。从第四行开始每行描述一个操作，输入的操作有以下三种形式： 操作$1$：“$1$ $t$ $g$ $c$”(不含双引号)。表示把所有满足$t\le i\le g$的$a_i$改为$a_i\times c$$ (1\le t\le g\le N,0\le c\le 10^9)$。 操作$2$：“$2$ $t$ $g$ $c$”(不含双引号)。表示把所有满足$t\le i\le g$的$a_i$改为$a_i+c$$ (1\le t\le g\le N,0\le c\le 10^9)$。 操作$3$：“$3$ $t$ $g$”(不含双引号)。询问所有满足$t\le i\le g$的$a_i$的和模$P$的值 $(1\le t\le g\le N)$。 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。
输出格式
对每个操作$3$，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。