Problem

【Lydsy1704月赛】抵制克苏恩

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

Description

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

Input

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

Output

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

Read more »

Problem

二分图

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

Description

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

Input

输入数据的第一行是三个整数n,m,Tn,m,T
22行到第m+1m+1行,每行4个整数u,v,start,endu,v,start,end,表示第ii条边连接u,vu,v两个点,这条边在startstart时刻出现,在第endend时刻消失。

Output

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

Read more »

Problem

【ONTAK2010】Peaks加强版

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

Description

Bytemountains\mathrm{Bytemountains}NN座山峰,每座山峰有他的高度hih_i
有些山峰之间有双向道路相连,共MM条路径,每条路径有一个困难值,这个值越大表示越难走。
现在有QQ组询问,每组询问询问从点vv开始只经过困难值小于等于xx的路径所能到达的山峰中第kk高的山峰,如果无解输出1-1

Input

第一行三个数N,M,QN,M,Q
第二行NN个数,第ii个数为hih_i
接下来MM行,每行33个数a  b  ca\;b\;c,表示从aabb有一条困难值为cc的双向路径。
接下来QQ行,每行三个数v  x  kv\;x\;k,表示一组询问。
v=v  xor  lastansv=v\;\mathrm{xor}\;lastansx=x  xor  lastansx=x\;\mathrm{xor}\;lastansk=k  xor  lastansk=k\;\mathrm{xor}\;lastans,如果lastans=1lastans=-1则不变。

Output

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

Read more »

Problem

【ONTAK2010】Peaks

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

Description

Bytemountains\mathrm{Bytemountains}NN座山峰,每座山峰有他的高度hih_i
有些山峰之间有双向道路相连,共MM条路径,每条路径有一个困难值,这个值越大表示越难走。
现在有QQ组询问,每组询问询问从点vv开始只经过困难值小于等于xx的路径所能到达的山峰中第kk高的山峰,如果无解输出1-1

Input

第一行三个数N,M,QN,M,Q
第二行NN个数,第ii个数为hih_i
接下来MM行,每行33个数a  b  ca\;b\;c,表示从aabb有一条困难值为cc的双向路径。
接下来QQ行,每行三个数v  x  kv\;x\;k,表示一组询问。

Output

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

Read more »

Problem

【POI2015】Kinoman

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

Description

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

Input

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

Output

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

Read more »

Problem

【TJOI2015】线性代数

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

Description

给出一个N×NN\times N的矩阵BB和一个1×N1\times N的矩阵CC
求出一个1×N1\times N0101矩阵AA,使得D=(A×BC)×ATD=(A\times B-C)\times A^T最大,输出最大的DD值。

Input

第一行输入一个整数NN
接下来NN行输入BB矩阵,第ii行第jj个数字代表Bi,jB_{i,j}.
接下来一行输入NN个整数,代表矩阵CC
矩阵BB和矩阵CC中每个数字都是不超过10001000的非负整数。

Output

输出最大的DD

Read more »

Problem

【CTSC2017】吉夫特

时间限制:2  Sec\mathrm{2\;Sec}
空间限制:256  MB\mathrm{256\;MB}
简单的题目,既是礼物,也是毒药。
B\mathrm{B君}设计了一道简单的题目,准备作为 gift\mathrm{gift} 送给大家。
输入一个长度为 nn 的数列 a1,a2,,ana_1, a_2, \ldots, a_n
问有多少个长度大于等于 2 的不上升的子序列 ab1,ab2,,abka_{b_1}, a_{b_2}, \ldots ,a_{b_k} 满足
i=2k(abi1abi)mod2=(ab1ab2)×(ab2ab3)××(abk1abk)mod2>0\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
输出这个个数对 10000000071000000007 取模的结果。

输入格式

第一行一个整数 nn
接下来 nn 行,每行一个整数,这 nn 行中的第 ii 行,表示 aia_i

输出格式

一行一个整数表示答案。

Read more »

Problem

【SDOI2008】递归数列

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

Description

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

  • 对于iki\le kai=bia_i = b_i
  • 对于i>ki > kai=c1×ai1+c2×ai2++ck×aika_i=c_1\times a_{i-1} + c_2\times a_{i-2} + \cdots + c_k\times a_{i-k}

其中bib_icic_i (1ik)(1\le i\le k)是给定的自然数。写一个程序,给定自然数mnm \le n, 计算am+am+1+am+2++ana_m + a_{m+1} + a_{m+2} + \cdots + a_n, 并输出它除以给定自然数pp的余数的值。

Input

输入由四行组成。
第一行是一个自然数kk
第二行包含kk个自然数b1,b2,,bkb_1, b_2,\cdots,b_k
第三行包含kk个自然数c1,c2,,ckc_1, c_2,\cdots,c_k
第四行包含三个自然数m,n,pm, n, p

Output

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

Read more »

Problem

【JSOI2014】支线剧情

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

Background

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

Description

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

Input

输入一行包含一个正整数NN
接下来NN行,第ii行为ii号剧情点的信息:第一个整数为KiK_i,接下来KiK_i个整数对,Bi,jB_{i,j}Ti,jT_{i,j},表示从剧情点ii可以前往剧情点Bi,jB_{i,j},并且观看这段支线剧情需要花费Ti,jT_{i,j}的时间。

Output

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

Read more »

Problem

作诗

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

Description

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

Input

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

Output

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

Read more »