NIRVANA

Problem

我也不知道题目名字是什么

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

Description

给定一个序列$A[i]$，每次询问$l,r$，求$[l,r]$内最长子串，使得该子串为不上升子串或不下降子串

Input

第一行$n$，表示$A$数组有多少元素
接下来一行为$n$个整数$A[i]$
接下来一个整数$Q$，表示询问数量
接下来$Q$行，每行$2$个整数$l,\ r$

Output

对于每个询问，求$[l,r]$内最长子串，使得该子串为不上升子串或不下降子串

Problem

【NOIp2016】换教室

题目描述

对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。
在可以选择的课程中，有 $2n$ 节课程安排在 $n$ 个时间段上。在第 $i$（$1\le i\le n$）个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室 $c_i$ 上课，而另一节课程在教室 $d_i$ 进行。
在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的 $n$ 节安排好的课程。如果学生想更换第 $i$ 节课程的教室，则需要提出申请。若申请通过，学生就可以在第 $i$ 个时间段去教室 $d_i$ 上课，否则仍然在教室 $c_i$ 上课。
由于更换教室的需求太多，申请不一定能获得通过。通过计算，牛牛发现申请更换第 $i$ 节课程的教室时，申请被通过的概率是一个已知的实数 $k_i$ ，并且对于不同课程的申请，被通过的概率是互相独立的。
学校规定，所有的申请只能在学期开始前一次性提交，并且每个人只能选择至多 $m$ 节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室，而不能根据某些课程的申请结果来决定其他课程是否申请；牛牛可以申请自己最希望更换教室的 $m$ 门课程，也可以不用完这 $m$ 个申请的机会，甚至可以一门课程都不申请。
因为不同的课程可能会被安排在不同的教室进行，所以牛牛需要利用课间时间从一间教室赶到另一间教室。
牛牛所在的大学有 $v$ 个教室，有 $e$ 条道路。每条道路连接两间教室，并且是可以双向通行的。由于道路的长度和拥堵程度不同，通过不同的道路耗费的体力可能会有所不同。 当第 $i$（$1\le i\le n-1$）节课结束后，牛牛就会从这节课的教室出发，选择一条耗费体力最少的路径前往下一节课的教室。
现在牛牛想知道，申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小，请你帮他求出这个最小值。

输入输出格式

输入格式
第一行四个整数 $n,m,v,e$。$n$ 表示这个学期内的时间段的数量；$m$ 表示牛牛最多可以申请更换多少节课程的教室；$v$ 表示牛牛学校里教室的数量；$e$表示牛牛的学校里道路的数量。
第二行 $n$ 个正整数，第 $i（1\le i\le n）$个正整数表示 $c_i$ ，即第 $i$ 个时间段牛牛被安排上课的教室；保证 $1\le c_i \le v$。
第三行 $n$ 个正整数，第 $i（1\le i\le n）$个正整数表示 $d_i$ ，即第 $i$ 个时间段另一间上同样课程的教室；保证 $1\le d_i\le v$。
第四行 $n$ 个实数，第 $i（1\le i\le n）$个实数表示 $k_i$ ，即牛牛申请在第 $i$ 个时间段更换教室获得通过的概率。保证 $0\le k_i \le 1$。
接下来 $e$ 行，每行三个正整数 $a_j$, $b_j$,$w_j$，表示有一条双向道路连接教室 $a_j$, $b_j$，通过这条道路需要耗费的体力值是 $w_j$；保证 $1\le a_j, b_j \le v$，$1\le w_j\le 100$。
保证$1\le n\le 2000$，$0\le m\le 2000$，$1\le v\le 300$，$0\le e\le 90000$。
保证通过学校里的道路，从任何一间教室出发，都能到达其他所有的教室。
保证输入的实数最多包含 $3$ 位小数。
输出格式
输出一行，包含一个实数，四舍五入精确到小数点后恰好$2$位，表示答案。你的输出必须和标准输出完全一样才算正确。
测试数据保证四舍五入后的答案和准确答案的差的绝对值不大于$4\times 10^{-3}$。（如果你不知道什么是浮点误差，这段话可以理解为：对于大多数的算法，你可以正常地使用浮点数类型而不用对它进行特殊的处理）

Problem

【NOIp2016】蚯蚓

题目描述

本题中，我们将用符号$[c]$表示对$c$向下取整，例如：$[3.0] = [3.1] = [3.9] = 3$。
蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。
蛐蛐国里现在共有$n$只蚯蚓（$n$为正整数)。每只蚯蚓拥有长度，我们设第$i$只蚯蚓的长度为$a_i$$(i=1,2,\cdots,n)$，并保证所有的长度都是非负整数（即:可能存在长度为$0$的蚯蚓）。
每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数$p$(是满足$0<p<1$的有理数)决定，设这只蚯蚓长度为$x$，神刀手会将其切成两只长度分别为$[p\cdot x]$和$x-[p\cdot x]$的蚯蚓。特殊地，如果这两个数的其中一个等于$0$，则这个长度为$0$的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加$q$(是一个非负整常数)。
蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要$m$秒才能到来…($m$为非负整数）
蛐蛐国王希望知道这$m$秒内的战况。具体来说，他希望知道：

• $m$秒内，每一秒被切断的蚯蚓被切断前的长度（有$m$个数）
• $m$秒后，所有蚯蚓的长度（有$n+m$个数)。
  蛐蛐国王当然知道怎么做啦！但是他想考考你…

输入输出格式

输入格式
第一行包含六个整数$n,m,q,u,v,t$，其中：$n,m,q$的意义见【问题描述】；$u,v,t$均为正整数；你需要自己计算$p=\frac{u}{v}$(保证$0<u<v$)；$t$是输出参数，其含义将会在【输出格式】中解释。
第二行包含$n$个非负整数，为$a_1,a_2,\cdots a_n$，即初始时$n$只蚯蚓的长度。
同一行中相邻的两个数之间，恰好用一个空格隔开。
保证$1\le n\le 10^5$，$0<m\le 7\times10^6$，$0\le u<v\le 10^9$，$0\le q\le 200$，$1\le t\le 71$，$0<a_i\le 10^8$。
输出格式：
第一行输出$[\frac{m}{t}]$个整数，按时间顺序，依次输出第$t$秒，第$2t$秒，第$3t$秒……被切断蚯蚓（在被切断前）的长度。
第二行输出$[\frac{n+m}{t}]$个整数，输出$m$秒后蚯蚓的长度；需要按从大到小的顺序，依次输出排名第$t$，第$2t$，第$3t$……的长度。
同一行中相邻的两个数之间，恰好用一个空格隔开。即使某一行没有任何数需要 输出，你也应输出一个空行。
请阅读样例来更好地理解这个格式。

Problem

【SCOI2009】windy数

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

Description

$windy$定义了一种$windy$数。不含前导零且相邻两个数字之差至少为$2$的正整数被称为$windy$数。 $windy$想知道，在$A$和$B$之间，包括$A$和$B$，总共有多少个$windy$数？

Input

包含两个整数，$A,B$。

Output

一个整数

Problem

【ZJOI2010】count 数字计数

Time Limit: $3 Sec$
Memory Limit: $64 MB$

Description

给定两个正整数$a$和$b$，求在$[a,b]$中的所有整数中，每个数码$(digit)$各出现了多少次。

Input

输入文件中仅包含一行两个整数$a$、$b$，含义如上所述。

Output

输出文件中包含一行$10$个整数，分别表示$0\sim 9$在$[a,b]$中出现了多少次。

Problem

【ZJOI2006】Mahjong麻将

$\mathrm{Time\;Limit: \;1\;Sec}$
$\mathrm{Memory\;Limit:\;64\;MB}$

Description

很多人都知道玩麻将，当然也有人不知道，呵呵，不要紧，我在这里简要地介绍一下麻将规则：
普通麻将有砣、索、万三种类型的牌，每种牌有$1\sim 9$个数字，其中相同的牌每个有四张，例如$1砣\sim 9砣$，$1索\sim 9索$，$1万\sim 9万$各$4$张，所以共$36\times 3=108$张牌。胡牌时每人有$14$张牌，其中只要某人手里有若干句话（就是同种类型的牌连续三张或同种牌三张），另外再加上一对，即可胡牌。当然如果全是对，叫七小对，也可以胡牌。
要判断某人是否胡牌，显然一个弱智的算法就行了，某中学信息学小组超级麻将迷想了想，决定将普通麻将改造成超级麻将。
所谓超级麻将没有了砣、索、万的区分，每种牌上的数字可以是$1\sim 100$而每种数字的牌各有$100$张。另外特别自由的是，玩牌的人手里想拿多少张牌都可以，好刺激哦！
刺激归刺激，但是拿多了怎么胡牌呢？
超级麻将规定只要一个人手里拿的牌是若干句话（三个连续数字的牌各一张组成一句话，三张或四张同样数字的牌也算一句话），再加上一对相同的牌，就算胡了。
作为信息学竞赛选手的你，麻烦你给这位超级麻将迷编个程序，判断能否胡牌。

Input

第一行一个整数$N$（$N\le 100$），表示玩了$N$次超级麻将。 接下来$N$行，每行$100$个数$a_1,a_2,\cdots a_{100}$，描述每次玩牌手中各种牌的数量。$a_i$表示数字为$i$的牌有$a_i$张。（$0\le a_i\le 100$）

Output

输出$N$行，若胡了则输出$Yes$，否则输出$No$，注意区分$Yes$、$No$的大小写！

Problem

【ZJOI2008】杀蚂蚁

Description

最近，佳佳迷上了一款好玩的小游戏：$\mathrm{antbuster}$。
游戏规则非常简单：在一张地图上，左上角是蚂蚁窝，右下角是蛋糕，蚂蚁会源源不断地从窝里爬出来，试图把蛋糕搬回蚂蚁窝。而你的任务，就是用原始资金以及杀蚂蚁获得的奖金造防御塔，杀掉这些试图跟你抢蛋糕的蚂蚁~
下附一张游戏截图：

为了拿到尽可能高的分数，佳佳设计了很多种造塔的方案，但在尝试了其中的一小部分后，佳佳发现，这个游戏实在是太费时间了。为了节省时间，佳佳决定写个程序，对于每一种方案，模拟游戏进程，根据效果来判断方案的优劣。
根据自己在游戏中积累的一些经验，以及上网搜到的一些参数，佳佳猜了蚂蚁爬行的算法，并且假设游戏中的蚂蚁也是按这个规则选择路线：
1. 每一秒钟开始的时候，蚂蚁都在平面中的某个整点上。如果蚂蚁没有扛着蛋糕，它会在该点留下 2 单位的信息素，否则它会留下 5 单位的信息素。然后蚂蚁会在正北、正南、正东、正西四个方向中选择一个爬过去。
2. 选择方向的规则是：首先，爬完一个单位长度后到达的那个点上，不能有其他蚂蚁或是防御塔，并且那个点不能是蚂蚁上一秒所在的点（除非上一个时刻蚂蚁就被卡住，且这个时刻它仍无法动），当然，蚂蚁也不会爬出地图的边界（我们定义这些点为不可达点）。如果此时有多个选择，蚂蚁会选择信息素最多的那个点爬过去。
3. 如果此时仍有多种选择，蚂蚁先面向正东，如果正东不是可选择的某个方向，它会顺时针转90°，再次判断，如果还不是，再转 90°…直到找到可以去的方向。
4. 如果将每只蚂蚁在洞口出现的时间作为它的活动时间的第 1 秒，那么每当这只蚂蚁的活动时间秒数为 5 的倍数的时候，它先按规则 1~3 确定一个方向，面对该方向后逆时针转 90°，若它沿当前方向会走到一个不可达点，它会不停地每次逆时针转 90°，直到它面对着一个可达的点，这样定下的方向才是蚂蚁最终要爬去的方向。
5. 如果蚂蚁的四周都是不可达点，那么蚂蚁在这一秒内会选择停留在当前点。下一秒判断移动方向时，它上一秒所在点为其当前停留的点。
6. 你可以认为蚂蚁在选定方向后，瞬间移动到它的目标点，这一秒钟剩下的时间里，它就停留在目标点。
7. 蚂蚁按出生的顺序移动，出生得比较早的蚂蚁先移动。
然后，是一些有关地图的信息：
1. 每一秒，地图所有点上的信息素会损失 1 单位，如果那个点上有信息素的话。
2. 地图上某些地方是炮台。炮台的坐标在输入中给出。
3. 地图的长、宽在输入中给出，对于nm的地图，它的左上角坐标为(0,0)，右下角坐标为(n,m)。蚂蚁洞的位置为(0,0)，蛋糕的位置为(n,m)。
4. 你可以把蚂蚁看做一个直径为 1 单位的圆，圆心位于蚂蚁所在的整点。
5. 游戏开始时，地图上没有蚂蚁，每个点上的信息素含量均为 0。
一些有关炮塔的信息：
1. 炮塔被放置在地图上的整点处。
2. 为了简单一些，我们认为这些炮塔都是激光塔。激光塔的射速是 1 秒/次，它的攻击伤害为 d/次，攻击范围为 r。你可以认为每秒蚂蚁移动完毕后，塔才开始攻击。并且，只有当代表蚂蚁的圆的圆心与塔的直线距离不超过 r 时，塔才算打得到那只蚂蚁。
3. 如果一只蚂蚁扛着蛋糕，那么它会成为 target，也就是说，任何打得到它的塔的炮口都会对准它。如果蛋糕好好地呆在原位，那么每个塔都会挑离它最近的蚂蚁进行攻击，如果有多只蚂蚁，它会选出生较早的一只。
4. 激光塔有个比较奇怪的特性：它在选定了打击目标后，只要目标在其射程内，塔到目标蚂蚁圆心的连线上的所有蚂蚁（这里“被打到”的判定变成了表示激光的线段与表示蚂蚁的圆有公共点）都会被打到并损 d 格血，但激光不会穿透它的打击目标打到后面的蚂蚁。
5. 尽管在真实游戏中，塔是可以升级的，但在这里我们认为塔的布局和等级就此定了下来，不再变动。
再介绍一下蚂蚁窝：
1. 如果地图上的蚂蚁不足 6 只，并且洞口没有蚂蚁，那么窝中每秒会爬出一只蚂蚁，直到地图上的蚂蚁数为 6 只。
2. 刚出生的蚂蚁站在洞口。3. 每只蚂蚁有一个级别，级别决定了蚂蚁的血量，级别为 k 的蚂蚁的血量为[41.1^k]。每被塔打一次，蚂蚁的血减少 d。注意，血量为 0 的蚂蚁仍能精力充沛地四处乱爬，只有一只蚂蚁的血被打成负数时，它才算挂了。
3. 蚂蚁的级别是这样算的：前 6 只出生的蚂蚁是 1 级，第 7~12 只是 2 级，依此类推。
最后给出关于蛋糕的介绍：
1. 简单起见，你可以认为此时只剩最后一块蛋糕了。如果有蚂蚁走到蛋糕的位置，并且此时蛋糕没有被扛走，那么这只蚂蚁就扛上了蛋糕。蚂蚁被打死后蛋糕归位。
2. 如果一只扛着蛋糕的蚂蚁走到蚂蚁窝的位置，我们就认为蚂蚁成功抢到了蛋糕，游戏结束。
3. 蚂蚁扛上蛋糕时，血量会增加[该蚂蚁出生时血量/2]，但不会超过上限。
整理一下 1 秒钟内发生的事件：
1. 1 秒的最初，如果地图上蚂蚁数不足 6，一只蚂蚁就会在洞口出生。
2. 接着，蚂蚁们在自己所在点留下一些信息素后，考虑移动。先出生的蚂蚁先移动。
3. 移动完毕后，如果有蚂蚁在蛋糕的位置上并且蛋糕没被拿走，它把蛋糕扛上，血量增加，并在这时被所有塔设成 target。
4. 然后所有塔同时开始攻击。如果攻击结束后那只扛着蛋糕的蚂蚁挂了，蛋糕瞬间归位。
5. 攻击结束后，如果发现扛蛋糕的蚂蚁没死并在窝的位置，就认为蚂蚁抢到了蛋糕。游戏也在此时结束。
6. 最后，地图上所有点的信息素损失 1 单位。所有蚂蚁的年龄加 1。
7. 漫长的 1 秒到此结束。

Input

输入的第一行是 $2$ 个用空格隔开的整数， $n$、$m$，分别表示了地图的长和宽。
第二行是 $3$ 个用空格隔开的整数， $s$、 $d$、 $r$，依次表示炮塔的个数、单次攻击伤害以及攻击范围。接下来 $s$ 行，每行是 $2$ 个用空格隔开的整数 $x$、 $y$，描述了一个炮塔的位置。当然，蚂蚁窝的洞口以及蛋糕所在的位置上一定没有炮塔。
最后一行是一个正整数 $t$，表示我们模拟游戏的前 $t$ 秒钟。

Output

如果在第 $t$ 秒或之前蚂蚁抢到了蛋糕，输出一行“$\mathrm{Game\;over\;after\;}x\mathrm{\;seconds}$”，其中$x$为游戏结束的时间，否则输出“$\mathrm{The\;game\;is\;going\;on}$”。
如果游戏在 $t​$ 秒或之前结束，输出游戏结束时所有蚂蚁的信息，否则输出 $t​$ 秒后所有蚂蚁的信息。
格式如下：第一行是 $1$ 个整数 $s$，表示此时活着的蚂蚁的总数。接下来 $s$ 行，每行 $5$ 个整数，依次表示一只蚂蚁的年龄（单位为秒）、等级、当前血量，以及在地图上的位置$(a,b)$。输出按蚂蚁的年龄递减排序。

Problem

斗地主

Time Limit: $30 Sec$
Memory Limit: $1024 MB$

Description

牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的$A$到$K$加上大小王的共$54$张牌来进行的扑克牌游戏。在斗地主中，牌的大小关系根据牌的数码表示如下：$3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王$，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由$n$张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。现在，牛牛只想知道，对于自己的若干组手牌，分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。需要注意的是，本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下：

Input

第一行包含用空格隔开的$2$个正整数$T,N$，表示手牌的组数以及每组手牌的张数。
接下来$T$组数据，每组数据$N$行，每行一个非负整数对$A_i,B_i$，表示一张牌，其中$A_i$表示牌的数码，$B_i$表示牌的花色，中间用空格隔开。特别的，我们用1来表示数码A，$11$表示数码$J$，$12$表示数码$Q$，$13$表示数码$K$；黑桃、红心、梅花、方片分别用$1\sim 4$来表示；小王的表示方法为$01$，大王的表示方法为$02$。

Output

共$T$行，每行一个整数，表示打光第$T$组手牌的最少次数。

Problem

【JSOI2010】Group 部落划分

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

Description

聪聪研究发现，荒岛野人总是过着群居的生活，但是，并不是整个荒岛上的所有野人都属于同一个部落，野人们总是拉帮结派形成属于自己的部落，不同的部落之间则经常发生争斗。只是，这一切都成为谜团了——聪聪根本就不知道部落究竟是如何分布的。 不过好消息是，聪聪得到了一份荒岛的地图。地图上标注了$N$个野人居住的地点（可以看作是平面上的坐标）。我们知道，同一个部落的野人总是生活在附近。我们把两个部落的距离，定义为部落中距离最近的那两个居住点的距离。聪聪还获得了一个有意义的信息——这些野人总共被分为了$K$个部落！这真是个好消息。聪聪希望从这些信息里挖掘出所有部落的详细信息。他正在尝试这样一种算法： 对于任意一种部落划分的方法，都能够求出两个部落之间的距离，聪聪希望求出一种部落划分的方法，使靠得最近的两个部落尽可能远离。 例如，下面的左图表示了一个好的划分，而右图则不是。请你编程帮助聪聪解决这个难题。

Input

第一行包含两个整数$N$和$K$($1\le N\le 1000$,$1< K\le N$)，分别代表了野人居住点的数量和部落的数量。
接下来$N$行，每行包含两个正整数$x,y$，描述了一个居住点的坐标($0\le x, y\le10000$)

Output

输出一行，为最优划分时，最近的两个部落的距离，精确到小数点后两位。

Problem

【SDOI2015】星际战争

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

Description

$3333$年，在银河系的某星球上，$X$军团和$Y$军团正在激烈地作战。在战斗的某一阶段，$Y$军团一共派遣了$N$个巨型机器人进攻$X$军团的阵地，其中第$i$个巨型机器人的装甲值为$A_i$。当一个巨型机器人的装甲值减少到$0$或者以下时，这个巨型机器人就被摧毁了。$X$军团有$M$个激光武器，其中第i个激光武器每秒可以削减一个巨型机器人$B_i$的装甲值。激光武器的攻击是连续的。这种激光武器非常奇怪，一个激光武器只能攻击一些特定的敌人。$Y$军团看到自己的巨型机器人被$X$军团一个一个消灭，他们急需下达更多的指令。为了这个目标，$Y$军团需要知道$X$军团最少需要用多长时间才能将$Y$军团的所有巨型机器人摧毁。但是他们不会计算这个问题，因此向你求助。

Input

第一行，两个整数，$N$、$M$。
第二行，$N$个整数，$A_1$、$A_2$ $\cdots$ $A_N$。
第三行，$M$个整数，$B_1$、$B_2$ $\cdots$ $B_M$。
接下来的$M$行，每行$N$个整数，这些整数均为$0$或者$1$。这部分中的第$i$行的第$j$个整数为$0$表示第$i$个激光武器不可以攻击第$j$个巨型机器人，为$1$表示第$i$个激光武器可以攻击第$j$个巨型机器人。

Output

一行，一个实数，表示$X$军团要摧毁$Y$军团的所有巨型机器人最少需要的时间。输出结果与标准答案的绝对误差不超过$10^{-3}$即视为正确。