Problem

【SCOI2005】互不侵犯King

Description

在的棋盘里面放个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共个格子。

Input

只有一行，包含两个数, (, )

Output

方案数。

Problem

【HAOI2007】上升序列

Description

对于一个给定的,若有,满足()且()。那么就称为的一个上升序列。如果有多个满足条件，那么我们想求字典序最小的那个。任务给出序列，给出若干询问。对于第个询问，求出长度为的上升序列，如有多个，求出字典序最小的那个（即首先最小，如果不唯一，再看最小……），如果不存在长度为的上升序列，则输出.

Input

第一行一个，表示序列一共有个元素第二行个数，为 第三行一个，表示询问次数。下面接行每行一个数，表示要询问长度为的上升序列。，

Output

对于每个询问，如果对应的序列存在，则输出，否则输出.

Problem

【NOIp2016】蚯蚓

题目描述

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

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

  输入输出格式

  输入格式
  第一行包含六个整数，其中：的意义见【问题描述】；均为正整数；你需要自己计算(保证)；是输出参数，其含义将会在【输出格式】中解释。
  第二行包含个非负整数，为，即初始时只蚯蚓的长度。
  同一行中相邻的两个数之间，恰好用一个空格隔开。
  保证，，，，，。
  输出格式：
  第一行输出个整数，按时间顺序，依次输出第秒，第秒，第秒……被切断蚯蚓（在被切断前）的长度。
  第二行输出个整数，输出秒后蚯蚓的长度；需要按从大到小的顺序，依次输出排名第，第，第……的长度。
  同一行中相邻的两个数之间，恰好用一个空格隔开。即使某一行没有任何数需要 输出，你也应输出一个空行。
  请阅读样例来更好地理解这个格式。
  阅读全文 »

Problem

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

Description

给定一个序列，每次询问，求内最长子串，使得该子串为不上升子串或不下降子串

Input

第一行，表示数组有多少元素
接下来一行为个整数
接下来一个整数，表示询问数量
接下来行，每行个整数

Output

对于每个询问，求内最长子串，使得该子串为不上升子串或不下降子串

Problem

【NOIp2016】换教室

题目描述

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

输入输出格式

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

Problem

【HAOI2015】树上操作

Description

有一棵点数为 的树，以点 为根，且树点有边权。然后有 个
操作，分为三种：
操作 ：把某个节点 的点权增加 。
操作 ：把某个节点 为根的子树中所有点的点权都增加 。
操作 ：询问某个节点 到根的路径中所有点的点权和。

Input

第一行包含两个整数 。表示点数和操作数。接下来一行 个整数，表示树中节点的初始权值。接下来 行每行三个正整数 ， 表示该树中存在一条边 。再接下来 行，每行分别表示一次操作。其中第一个数表示该操作的种类 ，之后接这个操作的参数 。

Output

对于每个询问操作，输出该询问的答案。答案之间用换行隔开。

Problem

【ZJOI2006】Mahjong麻将

Description

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

Input

第一行一个整数（），表示玩了次超级麻将。 接下来行，每行个数，描述每次玩牌手中各种牌的数量。表示数字为的牌有张。（）

Output

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

Problem

【ZJOI2010】count 数字计数

Time Limit:
Memory Limit:

Description

给定两个正整数和，求在中的所有整数中，每个数码各出现了多少次。

Input

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

Output

输出文件中包含一行个整数，分别表示在中出现了多少次。

Problem

【SCOI2009】windy数

Description

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

Input

包含两个整数，。

Output

一个整数

Problem

【ZJOI2008】杀蚂蚁

Description

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

为了拿到尽可能高的分数，佳佳设计了很多种造塔的方案，但在尝试了其中的一小部分后，佳佳发现，这个游戏实在是太费时间了。为了节省时间，佳佳决定写个程序，对于每一种方案，模拟游戏进程，根据效果来判断方案的优劣。
根据自己在游戏中积累的一些经验，以及上网搜到的一些参数，佳佳猜了蚂蚁爬行的算法，并且假设游戏中的蚂蚁也是按这个规则选择路线：

1. 每一秒钟开始的时候，蚂蚁都在平面中的某个整点上。如果蚂蚁没有扛着蛋糕，它会在该点留下 2 单位的信息素，否则它会留下 5 单位的信息素。然后蚂蚁会在正北、正南、正东、正西四个方向中选择一个爬过去。
2. 选择方向的规则是：首先，爬完一个单位长度后到达的那个点上，不能有其他蚂蚁或是防御塔，并且那个点不能是蚂蚁上一秒所在的点（除非上一个时刻蚂蚁就被卡住，且这个时刻它仍无法动），当然，蚂蚁也不会爬出地图的边界（我们定义这些点为不可达点）。如果此时有多个选择，蚂蚁会选择信息素最多的那个点爬过去。
3. 如果此时仍有多种选择，蚂蚁先面向正东，如果正东不是可选择的某个方向，它会顺时针转90°，再次判断，如果还不是，再转 90°...直到找到可以去的方向。
4. 如果将每只蚂蚁在洞口出现的时间作为它的活动时间的第 1 秒，那么每当这只蚂蚁的活动时间秒数为 5 的倍数的时候，它先按规则 1~3 确定一个方向，面对该方向后逆时针转 90°，若它沿当前方向会走到一个不可达点，它会不停地每次逆时针转 90°，直到它面对着一个可达的点，这样定下的方向才是蚂蚁最终要爬去的方向。
5. 如果蚂蚁的四周都是不可达点，那么蚂蚁在这一秒内会选择停留在当前点。下一秒判断移动方向时，它上一秒所在点为其当前停留的点。
6. 你可以认为蚂蚁在选定方向后，瞬间移动到它的目标点，这一秒钟剩下的时间里，它就停留在目标点。
7. 蚂蚁按出生的顺序移动，出生得比较早的蚂蚁先移动。

然后，是一些有关地图的信息：

1. 每一秒，地图所有点上的信息素会损失 1 单位，如果那个点上有信息素的话。
2. 地图上某些地方是炮台。炮台的坐标在输入中给出。
3. 地图的长、宽在输入中给出，对于n*m的地图，它的左上角坐标为(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 的蚂蚁的血量为[4*1.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

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

Output

如果在第 秒或之前蚂蚁抢到了蛋糕，输出一行“”，其中为游戏结束的时间，否则输出“”。
如果游戏在 秒或之前结束，输出游戏结束时所有蚂蚁的信息，否则输出 秒后所有蚂蚁的信息。
格式如下：第一行是 个整数 ，表示此时活着的蚂蚁的总数。接下来 行，每行 个整数，依次表示一只蚂蚁的年龄（单位为秒）、等级、当前血量，以及在地图上的位置。输出按蚂蚁的年龄递减排序。