Problem

【Lydsy1704月赛】抵制克苏恩

Description

同学现在沉迷炉石传说不能自拔。他发现一张名为克苏恩的牌很不公平。
如果你不玩炉石传说，不必担心，同学会告诉你所有相关的细节。炉石传说是这样的一个游戏，每个玩家拥有一个点血量的英雄，并且可以用牌召唤至多个随从帮助玩家攻击对手，其中每个随从也拥有自己的血量和攻击力。
同学有很多次游戏失败都是因为对手使用了克苏恩这张牌，所以他想找到一些方法来抵御克苏恩。他去求助职业炉石传说玩家椎名真白，真白告诉他使用奴隶主这张牌就可以啦。
如果你不明白我上面在说什么，不必担心，同学会告诉你他想让你做什么。
现在同学会给出克苏恩的攻击力是，表示克苏恩会攻击次，每次会从对方场上的英雄和随从中随机选择一个并对其产生点伤害。
现在对方有一名克苏恩，你有一些奴隶主作为随从，每名奴隶主的血量是给定的。如果克苏恩攻击了你的一名奴隶主，那么这名奴隶主的血量会减少点，当其血量小于等于时会死亡，如果受到攻击后不死亡，并且你的随从数量没有达到，这名奴隶主会召唤一个拥有点血量的新奴隶主作为你的随从；如果克苏恩攻击了你的英雄，你的英雄会记录受到点伤害。你应该注意到了，每当克苏恩进行一次攻击，你场上的随从可能发生很大的变化。
同学为你假设了克苏恩的攻击力，你场上分别有点、点、点血量的奴隶主数量，你可以计算出你的英雄受到的总伤害的期望值是多少吗？

Input

输入包含多局游戏。
第一行包含一个整数，表示游戏的局数。
每局游戏仅占一行，包含四个非负整数，表示克苏恩的攻击力是，你有个点血量的奴隶主，个点血量的奴隶主，个点血量的奴隶主。
保证是小于的正数， 。

Output

对于每局游戏，输出一个数字表示总伤害的期望值，保留两位小数。

Problem

二分图

Description

神犇有一个个节点的图。
因为神犇是神犇，所以在T时间内一些边会出现后消失。
神犇要求出每一时间段内这个图是否是二分图。
这么简单的问题神犇当然会做了，于是他想考考你。

Input

输入数据的第一行是三个整数。
第行到第行，每行4个整数，表示第条边连接两个点，这条边在时刻出现，在第时刻消失。

Output

输出包含行。在第行中，如果第时间段内这个图是二分图，那么输出Yes，否则输出No。

Problem

【ONTAK2010】Peaks加强版

Description

在有座山峰，每座山峰有他的高度。
有些山峰之间有双向道路相连，共条路径，每条路径有一个困难值，这个值越大表示越难走。
现在有组询问，每组询问询问从点开始只经过困难值小于等于的路径所能到达的山峰中第高的山峰，如果无解输出。

Input

第一行三个数。
第二行个数，第个数为。
接下来行，每行个数，表示从到有一条困难值为的双向路径。
接下来行，每行三个数，表示一组询问。
，，，如果则不变。

Output

对于每组询问，输出一个整数表示答案。

Problem

【ONTAK2010】Peaks

Description

在有座山峰，每座山峰有他的高度。
有些山峰之间有双向道路相连，共条路径，每条路径有一个困难值，这个值越大表示越难走。
现在有组询问，每组询问询问从点开始只经过困难值小于等于的路径所能到达的山峰中第高的山峰，如果无解输出。

Input

第一行三个数。
第二行个数，第个数为。
接下来行，每行个数，表示从到有一条困难值为的双向路径。
接下来行，每行三个数，表示一组询问。

Output

对于每组询问，输出一个整数表示答案。

Problem

【TJOI2015】线性代数

Description

给出一个的矩阵和一个的矩阵。
求出一个的矩阵，使得最大，输出最大的值。

Input

第一行输入一个整数。
接下来行输入矩阵，第行第个数字代表.
接下来一行输入个整数，代表矩阵。
矩阵和矩阵中每个数字都是不超过的非负整数。

Output

输出最大的。

Problem

【POI2015】Kinoman

Description

共有部电影，编号为，第部电影的好看值为。
在天之中（从编号）每天会放映一部电影，第天放映的是第部。
你可以选择，并观看第天内所有的电影。
如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。
你希望最大化观看且仅观看过一次的电影的好看值的总和。

Input

第一行两个整数。
第二行包含个整数。
第三行包含个整数。

Output

输出观看且仅观看过一次的电影的好看值的总和的最大值。

Problem

【CTSC2017】吉夫特

时间限制：
空间限制：
简单的题目，既是礼物，也是毒药。
设计了一道简单的题目，准备作为 送给大家。
输入一个长度为 的数列
问有多少个长度大于等于 2 的不上升的子序列 满足

输出这个个数对 取模的结果。

输入格式

第一行一个整数 。
接下来 行，每行一个整数，这 行中的第 行，表示 。

输出格式

一行一个整数表示答案。

Problem

【SDOI2008】递归数列

Description

一个由自然数组成的数列按下式定义：

• 对于：
• 对于：

其中和 是给定的自然数。写一个程序，给定自然数, 计算, 并输出它除以给定自然数的余数的值。

Input

输入由四行组成。
第一行是一个自然数。
第二行包含个自然数。
第三行包含个自然数。
第四行包含三个自然数。

Output

输出一行一个正整数，表示的值。

Problem

【JSOI2014】支线剧情

Background

宅男非常喜欢玩游戏，比如仙剑，轩辕剑等等。不过喜欢的并不是战斗场景，而是类似电视剧一般的充满恩怨情仇的剧情。
这些游戏往往都有很多的支线剧情，现在想花费最少的时间看完所有的支线剧情。

Description

现在所玩的游戏中，一共有个剧情点，由到编号，第个剧情点可以根据的不同的选择，而经过不同的支线剧情，前往种不同的新的剧情点。当然如果为，则说明号剧情点是游戏的一个结局了。
观看一个支线剧情需要一定的时间。一开始处在号剧情点，也就是游戏的开始。显然任何一个剧情点都是从号剧情点可达的。此外，随着游戏的进行，剧情是不可逆的。所以游戏保证从任意剧情点出发，都不能再回到这个剧情点。
由于过度使用修改器，导致游戏的“存档”和“读档”功能损坏了，所以要想回到之前的剧情点，唯一的方法就是退出当前游戏，并开始新的游戏，也就是回到号剧情点。可以在任何时刻退出游戏并重新开始。
不断开始新的游戏重复观看已经看过的剧情是很痛苦，希望花费最少的时间，看完所有不同的支线剧情。

Input

输入一行包含一个正整数。
接下来行，第行为号剧情点的信息：第一个整数为，接下来个整数对，和，表示从剧情点可以前往剧情点，并且观看这段支线剧情需要花费的时间。

Output

输出一行包含一个整数，表示看完所有支线剧情所需要的最少时间。

Problem

作诗

Description

神犇虐完之后给傻X出了一题：
是T国的公主，平时的一大爱好是作诗。由于时间紧迫，作完诗之后还要虐，于是找来一篇长度为的文章，阅读次，每次只阅读其中连续的一段，从这一段中选出一些汉字构成诗。
因为喜欢对偶，所以规定最后选出的每个汉字都必须在里出现了正偶数次。而且认为选出的汉字的种类数（两个一样的汉字称为同一种）越多越好（为了拿到更多的素材！）。于是请安排选法。这种傻X当然不会了，于是向你请教……
问题简述：个数，组询问，每次问中有多少个数出现正偶数次。

Input

输入第一行三个整数，表示文章字数、汉字的种类数、要选择次。
第二行有个整数，每个数在间，代表一个编码为的汉字。
接下来行每行两个整数和，设上一个询问的答案为(第一个询问时)，令, ，若，交换和，则本次询问为。

Output

输出共行，每行一个整数，第个数表示第次能选出的汉字的最多种类数。