P3277 [SCOI2011]飞镖

    • 20通过
    • 114提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 并查集 线段树 连通块 2011 四川 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    飞镖是在欧洲颇为流行的一项运动。它的镖盘上分为20个扇形区域,分别标有1到20的分值,每个区域中有单倍、双倍和三倍的区域,打中对应的区域会得到分值乘以倍数所对应的分数。

    例如打中18分里面的三倍区域,就会得到54分。

    另外,在镖盘的中央,还有”小红心“和”大红心“,分别是25分和50分。

    通常的飞镖规则还有一条,那就是在最后一镖的时候,必须以双倍结束战斗,才算获胜。也就是说,当还剩12分的时候,必须打中双倍的6才算赢,而打中单倍的12或者三倍的4则不算。

    特别的,”大红心“也算双倍(双倍的25)。在这样的规则下,3镖能解决的最多分数是170分(两个三倍的20,最后用大红心结束)。

    现在,lxhgww把原来的1到20分的分值变为了1到K分,同时把小红心的分数变为了M分(大红心是其双倍),现在lxhgww想知道能否在3镖内(可以不一定用满3镖)解决X分。同样的,最后一镖必须是双倍(包括大红心)。

    输入输出格式

    输入格式:

    输入的第一行是一个整数T,包括了T组数据。

    第二行是5个整数, $A_1,B_1,C_1,D_1,K_1$ ,表示第一组数据的镖盘是从1到 $K_1$ 分的,随后数据的镖盘由公式 $K_i=(A_1K^2_{i-1}+B_1K_{i-1}+C_1)mod D_1 + 20$ 决定,其中第 $i(1<i\le T)$ 组数据的镖盘是从1到 $K_i$ 分的。

    第三行是5个整数, $A_2,B_2,C_2,D_2,M_1$ ,表示第一组数据的小红心 $M_1$ 分的,随后数据的镖盘由公式 $M_i=(A_2M^2_{i-1}+B_2M_{i-1}+C_2)mod D_2 + 20$ 决定,其中第 $i(1<i\le T)$ 组数据的小红心是 $M_i$ 分。

    第四行是5个整数, $A_3,B_3,C_3,D_3,X_1$ ,表示第一组数据需要解决的分数是 $X_1$ 分的,随后数据的镖盘由公式 $X_i=(A_3X^2_{i-1}+B_3X_{i-1}+C_3)mod D_3 + 20$ 决定,其中第 $i(1<i\le T)$ 组数据需要解决的分数是 $X_i$ 分。

    输出格式:

    一行,包括一个数字,表示这T组数据中,能够被解决的数据数目。

    输入输出样例

    输入样例#1: 复制
    5
    1 2 2 10 20
    1 3 2 15 25
    2 2 5 200 170
    输出样例#1: 复制
    4

    说明

    对于30%的数据,保证 $1\le T\le 20$ , $20\le K1,M1,X1,D1,D2,D3\le 1000$

    对于100%的数据,保证 $1\le T\le 10^6$ , $20\le K1,M1,X1,D1,D2,D3\le 10^9$

    对于所有的数据,保证 $0\le A1,B1,A2,B2,C2,A3,B3,C3 \le 10^9$

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。