当前位置:首页 >> 学科竞赛 >>

CTSC2013 Day2


CTSC 2013 Day2

2013 年 4 月 10 日 8:00-13:00

题目名称 文件名 每个测试点时限 测试点数目 每个测试点分值 内存限制 是否有部分分 题目类型

猴子大战 monkey 2秒 10 10 256MB 否 传统

因式分解 factor 6秒 10 10 512M

B 否 传统

组合子逻辑 logic 1秒 10 10 128MB 否 传统

注意:最终测试时,将开启 -O2 优化开关。

本次 CTSC 规则略有修改:例如删去了提交答案题,纸质题面给出小数据, 网页题面给出大数据,比赛中的即时评测会返回第一个点的得分情况。

第 1 页,共 9 页

猴子大战
(Author : 陈许旻)
【问题描述】 小 Q 和小 M 最近发明了一种卡牌游戏,叫猴子大战。 游戏最初小 Q 和小 M 各会取得一部分猴子牌。每局游戏,他们两个需要分别等概率地 从自己的猴子牌中抽取一张进行战斗。 获胜的一方将获得双方的猴子牌。 如果一方获得了所 有的猴子牌,则该方获得整场游戏的胜利。否则游戏将一直进行下去。 在进行了若干场比赛以后,小 Q 和小 M 算出了一张胜率表,为每张猴子牌之间进行战 斗双方获胜的概率。由于每场战斗一定会决出胜负,而且胜率不受先后顺序的影响,因此对 于任意的两张猴子牌 A 和 B, A 战胜 B 的概率加 B 战胜 A 的概率为 1。 由于自己老是输给小 M,小 Q 开始怀疑自己每次拿到的猴子牌是否能获得胜利。他希 望求出自己拿到的每种猴子牌组合的获胜的概率。 由于小 Q 接下来还有在 CD 市体育中心数以万计的运动计划,因此这个问题只能交给 你来解决了。 【输入格式】 输入的第一行包含两个正整数 n 和 m, 表示猴子牌的总张数和需要求的猴子牌组合的个 数。 接下来有 n 行,每行包含 n 个实数,每个实数保留了两位小数。这 n 行中,其中第 i 行 第 j 列的数为 , ,表示第 i 张猴子牌战胜第 j 张猴子牌的概率。保证 , + , = 1。特别 地, , = 0.5,没有特殊意义。 最后又 m 行。每行包含一个长度为 n 的无空格分隔的 01 串,表示一个猴子牌的组合。 其中第 i 个字符如果为 0,表示最初第 i 张牌在小 M 处,否则表示在小 Q 处。 【输出格式】 输出 m 行,每行一个实数,四舍五入保留八位小数(请强制输出八位浮点数) ,一次表 示每个给定的猴子牌组合下小 Q 获胜的概率。 【样例输入】 34 0.50 0.60 0.40 0.40 0.50 0.70 0.60 0.30 0.50 110 011 111 000 【样例输出】 0.71304348 0.66086957
第 2 页,共 9 页

1.00000000 0.00000000 【评分方法】 你的答案的每一行如果与我们给定的参考答案的差别均不超过 2 × 10?6 ,则获得该测 试点的得分,否则不得分。 参考答案保证与真实值的差别不超过 10 ^ -8, 因此如果你输出的答案保证与真实值差别 不超过2 × 10?6 — 10?8 ,才能保证正确。 【数据规模及约定】 对于每组数据, n 的取值如下 测试点编号 1 2 3 4 5 n n=2 n=5 n=7 n=8 n = 10 测试点编号 6 7 8 9 10 n n = 20 n = 40 n = 60 n = 80 n = 100

对于 100%的数据,保证 1 ≤ n ≤ 100,1 ≤ m ≤ ≤ , ≤ 1, , 恰好 包含 2 位小数,且 , + , = 1.表示猴子牌组合的 01 串长度均为 n,且不含其他字符。

n2 。0

, 的生成方式为:在某个环境下,使用某个随机数种子,持续调用某语言生成整数的
伪随机函数直到时钟函数达到 1 秒,接下来取连续的若干个随机函数值对 101 取模再除以 100,作为输入数据中的蛮子 i < j 的 , 。该生成过程只启动一次,既不会出现看到数据以 后重新生成数据的情况。以上操作的目的是希望 , 的每个取值几乎等概率且不受人控制, 你可以不必理会这段话。 【样例输入 大】 8 30 0.50 0.50 0.09 0.32 0.89 0.40 0.28 0.10 0.50 0.50 0.84 0.22 0.44 0.76 0.57 0.08 0.91 0.16 0.50 0.52 0.53 0.10 0.54 0.15 0.68 0.78 0.48 0.50 0.74 0.60 0.36 0.86 0.11 0.56 0.47 0.26 0.50 0.80 0.14 0.58 0.60 0.24 0.90 0.40 0.20 0.50 0.30 0.10 0.72 0.43 0.46 0.64 0.86 0.70 0.50 0.67 0.90 0.92 0.85 0.14 0.42 0.90 0.33 0.50 00110000 11111111 00101110 10111111 00000001 10000111 10010000 01000111 00000000
第 3 页,共 9 页

00001110 10011011 00011101 00100101 10001001 00100011 00110110 00011100 11000101 00000011 10101100 10101111 10101110 10011110 10000000 00101000 01111111 11110111 11011110 11011111 01101010 【样例输出 大】 0.29140506 1.00000000 0.45354680 0.89451866 0.17131288 0.51739409 0.26965898 0.55382457 0.00000000 0.36274987 0.72782462 0.53353762 0.33800692 0.32608325 0.46324305 0.56843541 0.36222475 0.42174219 0.37244612 0.32146442 0.69391054
第 4 页,共 9 页

0.52259766 0.63240885 0.06905086 0.17651645 0.93094914 0.91428048 0.73789019 0.90920307 0.48313103

第 5 页,共 9 页

因式分解
(Author : 钟沛林)
【问题描述】 通过代数基本定理,我们知道若计算重根,一个 n 次的多项式在复数域内恰好有 n 个 零点(函数值为 0 的点)。 现给定一个整系数多项式 F[x], 它的 n 个零点恰好都是有理数(即可 以写成两个整数相除的形式);同时,若我们把它所有的非零零点(函数自变量不为 0,函数 值为 0)去重, 则可以得到 r 个互不相同的非零零点, 其中第 i 个非零零点可以被表示成下式:

sgni ?

qi pi

式中 sgni 表示第 i 个零点的符号, pi 和q i 为互质的两个正整数。 现在告诉你 F[x],要求你输出将他因式分解后的形式。 【输入格式】 输入只有一行,包含多项式 F[x]。 多项式一定是如下的形式:

an x^n + an ?1 x^n ? 1 + ? a1 x + a0
次数一定为从高到低,其中 a i 为整数,并且若 a i 为 0,则省略该项,若 a i 为负数,则省 略之前的加号,若 a i 的绝对值为 1 且 i 不为 0,则不输出 1,并且保证 a n 不为 0. 详见样例输入。 【输出格式】 输出一行,表示因式分解后的形式,格式如下:

an (x + u1 /v1 )^t1 (x + u2 /v2 )^t2 … (x + us /vs )^ts
其中 u, v 互质,且 v 为正整数。 其中 ui /vi 从大到小排列,若 ui /vi = 0 则该项为 x^ ti ,若ui /vi 为负数,则省略加号, 若vi 为 1,则省略 /vi 。 若ti 为 1 则省略^ ti 。 若a n 为± 1 则将 1 省略。 详见样例输出。 【样例输入 1】 8x^7-258x^5+2112x^3-512x 【样例输出 1】 8(x-4)^2(x-1/2)x(x+1/2)(x+4)^2 【样例输入 2】 -x^2+2x-1
第 6 页,共 9 页

【样例输出 2】 -(x-1)^2 【数据规模与约定】 测试点编号 1 2 3 4 5 6 7 8 9 10 多项式最高次数 2 4 7 10 12 35 39 46 80 50
r r

互异零点数 2 4 7 10 12 5 5 4 2 1

系数范围(绝对值)

≤ 10 ≤ 100 ≤ 10 ^ 6 ≤ 10 ^ 7 ≤ 10 ^ 16 ≤ 10 ^ 24 ≤ 10 ^ 68 ≤ 10 ^ 104 ≤ 10 ^ 12 ≤ 10 ^ 316

pi ,q i 满足: pi ≤ 106 ,
i=1 i=1

q i ≤ 106

【样例输入 大】 3471669046846136046501981x^16+523705101892702183583476074x^15-4217047551173 6822251046719791x^14+1154700113321007935575518213810x^13-1525585119224600954815 1164015605x^12+99166092441431509593886082283198x^11-252943893149267918788703854 873893x^10-21090741362454393977165098185618x^9-744504531988547875370750460900x^ 8-14556479621520611267680614120x^7-170558365363069027452907248x^6-11983388321528 98113421152x^5-4675893106661778820032x^4-7817710219819447680x^3 【样例输出 大】 3471669046846136046501981(x-167/13)^5x^3(x+2/171)^7(x+215)

第 7 页,共 9 页

组合子逻辑
(Author : 顾昱洲)
【问题描述】 组合子逻辑是 Moses Sch? nfinkel 和 Haskell Curry 发明的一种符号系统,用于消除数理 逻辑中对于变量的需要。本题考察一种与真实世界的组合子演算略有差别的组合子系统。 一个组合子项是下列形式之一: P (E1 E2 ) 其中 P 表示一个基本函数, E1 以及E2 表示一个组合子项(可以相同)。 不满足以上形式的 表达式均非组合子项。 我们将一个组合子项 E 的参数个数 np(E)如下: np(P) = 基本函数 P 的参数个数; np(( E1 E2 )) = np( E1 ) - 1。 本题中,我们用一个正整数同时表示一个基本函数,以及该基本函数的参数个数。 对于一个组合子项 E,如果它和它包含的所有组合子项的参数个数 np 均为正整数,那 么我们称这个 E 为范式。 我们经常组合子项简化表示: 如果一个组合子项 E 含有连续子序列(… ((E1 E2 ) E3 ) … En ) (其中 n ≥ 3),其中 Ek 表示组合子项(可以是简化表示的),那么将该部分替换为( E1 E2 E3 … En ),其他部分不变,得到表达式 E 的一个简化表示。一个组合子项可以被简化表示 多次。 给定一个基本函数序列, 问至少需要添加多少对括号, 才能使得该表达式成为一个范式 的简化表示(即满足范式的性质); 如果无论如何怎样添加括号, 均不能得到范式的简化表示, 输出-1。 【输入格式】 第一行包含一个正整数 T,表示有 T 次询问。 接下来 2T 行。 第 2k 行有一个正整数 nk ,表示第 k 次询问的序列中基本函数的个数。 第 2k + 1 行有 nk 个正整数,其中第 i 个整数表示序列中第 i 个基本函数。 【输出格式】 输出 T 行,每行一个整数,表示对应询问的输出结果。 【样例输入】 2 5 32132 5 11111 【样例输出】
第 8 页,共 9 页

3 -1 【样例说明】 第一次询问: 一个最优方案是(3 (2 1) (3 2))。 可以证明不存在添加括号对数更少的方案。 第二次询问:容易证明不存在合法方案。 【数据规模和约定】 令 TN 表示输入中所有 nk 的和。 测试点编号 1 2 3 4 5 6 7 8 9 10 【样例输入 大】 1 2000000 …(限于字数此处省略 2 ~ 2000001 共 2000000 个空格隔开的数字,约 14MB) 【样例输出 大】 18 规模 T ≤ 30, nk ≤ 3 T ≤ 30, nk ≤ 15 TN ≤ 100 TN ≤ 500 TN ≤ 2000 TN ≤ 5000 TN ≤ 5000 TN ≤ 1000000 TN ≤ 2000000 TN ≤ 2000000

第 9 页,共 9 页


相关文章:
清华大学2013信息学优秀高中生夏令营报名表
(例 成绩 NOI2012 CTSC2013 APIO2013 铜牌) 银牌) 国内金 牌) 其他说明: ...2013清华大学信息学夏令... 暂无评价 2页 免费 清华大学2013年“全国优......
2013年“微软杯”全国中学生 信息学特长生夏令营报名表
1/2 相关文档推荐 南开大学2013年全国中学生... 暂无评价 2页 免费 2013年...CTSC2013 如 APIO2013 如 NOIP2012 如 2013 冬令营 成 铜牌 银牌 国内金牌 ...
更多相关标签:
noip2013day2 | noip2013提高组day2 | ctsc 2014 | ctsc2016 | ctsc 100 | ctsc2009 | 公式编辑器ctsc | ctsc2004公式编辑器 |