Problem

【SDOI2008】校门外的区间

Description

受校门外的树这道经典问题的启发，君根据基本的离散数学的知识，抽象出种运算维护集合(初始为空)并最终输出。现在，请你完成这道校门外的树之难度增强版——校门外的区间。
种运算如下：

基本集合运算如下：

Input

输入共行。
每行的格式为 ，用一个空格隔开，表示运算的种类，为一个区间(区间用表示)。

Output

共一行，即集合，每个区间后面带一个空格。若为空则输出 。

Problem

善意的投票

题目描述

幼儿园里有个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。
虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。
我们的问题就是，每位小朋友应该怎样投票，才能使冲突数最小？

输入输出格式

输入格式
文件的第一行只有两个整数，，保证有，。
其中代表总人数，代表好朋友的对数。文件第二行有个整数，第个整数代表第个小朋友的意愿，当它为时表示同意睡觉，当它为时表示反对睡觉。接下来文件还有行，每行有两个整数，。表示，是一对好朋友，我们保证任何两对，不会重复。
输出格式
只需要输出一个整数，即可能的最小冲突数。

Problem

切糕

Description

经历千辛万苦小得到了一块切糕，切糕的形状是长方体，小打算拦腰将切糕切成两半分给小。出于美观考虑，小希望切面能尽量光滑且和谐。于是她找到你，希望你能帮她找出最好的切割方案。
出于简便考虑，我们将切糕视作一个长，宽，高的长方体点阵。我们将位于第层中第行，第列上的点称为，它有一个非负的不和谐值。一个合法的切面满足以下两个条件：

1. 与每个纵轴有且仅有一个交点。即切面是一个函数，对于所有，，我们需指定一个切割点，且 。
2. 切面需要一定的光滑性要求，即相邻纵轴上的切割点不能相距太远。对于所有 和 ，若 ，则 , 其中是给定的一个非负整数。

能有许多切面满足上面的条件，小希望找出总的切割点上的不和谐值最小的那个，即最小。

Input

第一行是三个正整数，表示切糕的长、 宽、高。第二行有一个非负整数，表示光滑性要求。接下来是个行列的矩阵，第个矩阵的第行第列是。
的数据满足，，且给出的所有的不和谐值不超过。

Output

仅包含一个整数，表示在合法基础上最小的总不和谐值。

Problem

【JSOI2008】星球大战

题目描述

很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中
几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地
摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连
通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通快的个数。（如果两个星球可以通过现存的以太通道直接或间接地连通，
则这两个星球在同一个连通块中）。

输入输出格式

输入格式
输入文件第一行包含两个整数， 和，分别表示星球的数目和以太隧道的数目。星球用的整数编号。
接下来的行，每行包括两个整数，其中（且），表示星球和星球之间有以太隧道。注意所有的以太隧道都是双向的。
接下来一行是一个整数，表示帝国计划打击的星球个数。
接下来的行每行一个整数，满足，表示帝国计划打击的星球编号。帝国总是按输入的顺序依次摧毁星球的。
输出格式
输出文件的第一行是开始时星球的连通块个数。
接下来的行，每行一个整数，表示经过该次打击后现存星球的连通块个数。

Problem

【HNOI2008】越狱

Description

监狱有连续编号为的个房间，每个房间关押一个犯人，有种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

Input

输入两个整数， 。

Output

能越狱的状态数，答案模 。

Problem

【HNOI2007】紧急疏散evacuate

Description

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

Input

输入文件第一行是由空格隔开的一对正整数与，，，以下行列描述一个的矩阵。其中的元素可为字符’’, ‘’和’’，且字符间无空格。

Output

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

Problem

【SCOI2007】蜥蜴

Description

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

Input

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

Output

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

PRoblem

最优贸易

题目描述

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

输入输出格式

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

Problem

【HDU4348】To The Moon

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 integers . On these integers, you need to implement the following operations:

1. : Adding a constant d for every , and increase the time stamp by , this is the only operation that will cause the time stamp increase.
2. : Querying the current sum of .
3. : Querying a history sum of in time .
4. : Back to time . And once you decide return to a past, you can never be access to a forward edition anymore.

, , , . The system start from time , and the first modification is in time , , 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

食物链

Description

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

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

你的任务是根据给定的和句话，输出假话的总数。

Input

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

Output

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