NIRVANA

Problem

【Lydsy1704月赛】抵制克苏恩

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

Description

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

Input

输入包含多局游戏。
第一行包含一个整数$T\;(T<100)$，表示游戏的局数。
每局游戏仅占一行，包含四个非负整数$K,A,B,C$，表示克苏恩的攻击力是$K$，你有$A$个$1$点血量的奴隶主，$B$个$2$点血量的奴隶主，$C$个$3$点血量的奴隶主。
保证$K$是小于$50$的正数，$A+B+C\le 7$ 。

Output

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

Problem

二分图

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

Description

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

Input

输入数据的第一行是三个整数$n,m,T$。
第$2$行到第$m+1$行，每行4个整数$u,v,start,end$，表示第$i$条边连接$u,v$两个点，这条边在$start$时刻出现，在第$end$时刻消失。

Output

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

Problem

【ONTAK2010】Peaks加强版

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

Description

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

Input

第一行三个数$N,M,Q$。
第二行$N$个数，第$i$个数为$h_i$。
接下来$M$行，每行$3$个数$a\;b\;c$，表示从$a$到$b$有一条困难值为$c$的双向路径。
接下来$Q$行，每行三个数$v\;x\;k$，表示一组询问。
$v=v\;\mathrm{xor}\;lastans$，$x=x\;\mathrm{xor}\;lastans$，$k=k\;\mathrm{xor}\;lastans$，如果$lastans=-1$则不变。

Output

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

Problem

【ONTAK2010】Peaks

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

Description

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

Input

第一行三个数$N,M,Q$。
第二行$N$个数，第$i$个数为$h_i$。
接下来$M$行，每行$3$个数$a\;b\;c$，表示从$a$到$b$有一条困难值为$c$的双向路径。
接下来$Q$行，每行三个数$v\;x\;k$，表示一组询问。

Output

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

Problem

【POI2015】Kinoman

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

Description

共有$m$部电影，编号为$1\sim m$，第$i$部电影的好看值为$w[i]$。
在$n$天之中（从$1\sim n$编号）每天会放映一部电影，第$i$天放映的是第$f[i]$部。
你可以选择$l,r\;(1\le l\le r\le n)$，并观看第$[l,r]$天内所有的电影。
如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。
你希望最大化观看且仅观看过一次的电影的好看值的总和。

Input

第一行两个整数$n,m\;(1\le m\le n\le 10^6)$。
第二行包含$n$个整数$f[1],f[2],…,f[n]\;(1\le f[i]\le m)$。
第三行包含$m$个整数$w[1],w[2],\cdots,w[m]\;(1\le w[j]\le10^6)$。

Output

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

Problem

【TJOI2015】线性代数

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

Description

给出一个$N\times N$的矩阵$B$和一个$1\times N$的矩阵$C$。
求出一个$1\times N$的$01$矩阵$A$，使得$D=(A\times B-C)\times A^T$最大，输出最大的$D$值。

Input

第一行输入一个整数$N$。
接下来$N$行输入$B$矩阵，第$i$行第$j$个数字代表$B_{i,j}$.
接下来一行输入$N$个整数，代表矩阵$C$。
矩阵$B$和矩阵$C$中每个数字都是不超过$1000$的非负整数。

Output

输出最大的$D$。

Problem

【CTSC2017】吉夫特

时间限制：$\mathrm{2\;Sec}$
空间限制：$\mathrm{256\;MB}$
简单的题目，既是礼物，也是毒药。
$\mathrm{B君}$设计了一道简单的题目，准备作为 $\mathrm{gift}$ 送给大家。
输入一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$
问有多少个长度大于等于 2 的不上升的子序列 $a_{b_1}, a_{b_2}, \ldots ,a_{b_k}$ 满足
$\prod_{i = 2}^k \binom{a_{b_{i-1}}}{a_{b_i}} \bmod 2= \binom{a_{b_1}}{a_{b_2}} \times \binom{a_{b_2}}{a_{b_3}} \times \cdots \times \binom{a_{b_{k-1}}}{a_{b_k}} \bmod 2 > 0$
输出这个个数对 $1000000007$ 取模的结果。

输入格式

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

输出格式

一行一个整数表示答案。

Problem

【SDOI2008】递归数列

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

Description

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

• 对于$i\le k$：$a_i = b_i$
• 对于$i > k$：$a_i=c_1\times a_{i-1} + c_2\times a_{i-2} + \cdots + c_k\times a_{i-k}$

其中$b_i$和 $c_i$ $(1\le i\le k)$是给定的自然数。写一个程序，给定自然数$m \le n$, 计算$a_m + a_{m+1} + a_{m+2} + \cdots + a_n$, 并输出它除以给定自然数$p$的余数的值。

Input

输入由四行组成。
第一行是一个自然数$k$。
第二行包含$k$个自然数$b_1, b_2,\cdots,b_k$。
第三行包含$k$个自然数$c_1, c_2,\cdots,c_k$。
第四行包含三个自然数$m, n, p$。

Output

输出一行一个正整数，表示$(a_m + a_{m+1} + a_{m+2} + \cdots + a_n) \bmod{p}$的值。

Problem

【JSOI2014】支线剧情

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

Background

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

Description

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

Input

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

Output

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

Problem

作诗

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

Description

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

Input

输入第一行三个整数$n,c,m$，表示文章字数、汉字的种类数、要选择$M$次。
第二行有$n$个整数，每个数$A_i$在$[1, c]$间，代表一个编码为$A_i$的汉字。
接下来$m$行每行两个整数$l$和$r$，设上一个询问的答案为$ans$(第一个询问时$ans=0$)，令$L=(l+ans)\mod{n+1}$, $R=(r+ans)\mod{n+1}$，若$L>R$，交换$L$和$R$，则本次询问为$[L,R]$。

Output

输出共$m$行，每行一个整数，第$i$个数表示$\mathrm{SHY}$第$i$次能选出的汉字的最多种类数。