当前位置:首页 >> 幼儿读物 >>

TYVJ8月月赛提高组难度官方题解


TYVJ 八月月赛提高组题解

1.括号匹配
解 法 一 : 模 拟 时间复杂度:O(NL) 预期得分:100 这道题是一道非常简单的栈结构题目。模拟一个栈,每次操作会改变的只有栈顶 元素,后括号弹栈,前括号入栈,如果遇到弹栈时候栈顶的前括号与当前的后括号不 匹配,就输出 FALSE;此外,如果栈空时要执行出栈操作,或括号序列遍历完成后栈 不空,也应输出 FALSE。否则输出 TRUE。下面说一下细节: 1.括号深度和出现次数。处理方案很多了…标程是在栈的 push 函数中,记录栈顶 的最大值和出现次数。 2.通配符。可以把#@?*&!分别等效为 2 个、4 个、8 个’/’和’\’, ’/’和’\’可以匹配 任意一个方向相反的括号。 3.常数。原本想卡常数,可 TYVJ 速度太快根本卡不住。标程测试点 5 用 Cena 测 得 950ms,在 TYVJ 上变成了 278ms

2 .冗余电 网
解 法 一 : 最 小 生 成 树 时间复杂度:O(Mlog M) 预期得分:100 最小生成树。Kruskal 计算最小生成树,然后统计并查集中树的个数,若多于 1, 则图不连通,统计输出无电可用村庄的个数,否则输出最少需要电线的长度。 注意:.输出数据要使用 int64,否则 80 分;

3.黄金矿工
解 法 一 : 搜 索 解 法 二 : 时间复杂度:O(N^4)~O(N^6) 预期得分:30~70 直接搜索,最暴力的裸搜大概会到 O(N^6),优化一下可以到 O(N^4)。 没有优化的 DP 大概也是 O(N^4),同样 70 分。

时间复杂度:O(N^3) 预期得分:100 本题实际上就是求最大子矩阵。其中,TNT 的权值为-∞。 注意细节:-∞不要太小,否则会下溢出。 (其实数据中还真没有…)

本题解仅保证方案的可行性,不保证方案的最优性

TYVJ 八月月赛提高组题解

动 态 规 划

1.预处理 sum[i][j]:前 i 行,第 j 列的和 2.DP,主要步骤见下: for i=1→n for j=i→n x=sum[j][1]-sum[i-1][1] max=x,f[i][j]=max for k=2→n x=sum[j][k]-sum[i-1][k] if(x<max+x)max=max+x else max=x if(f[i][j]<max)f[i][j]=max 最后说一点,不要忘记减去租金 10 元。据我所知,有神牛中弹了。

4.密码双锁
解 法 一: 构 子 造 锁 解 一 法 二: 二 进 制 时间复杂度:O(N) 或 O(log N) 预期得分:60 或 100 (假设不存在子锁二) 这实际上是个分形,可以直接找规律倍增构造序列。本方案是递推的,时间复杂 度较大,但可以改成递归,以减小时间复杂度。构造方法见附录一。 时间复杂度:O(log N) 预期得分:100 (假设不存在子锁二) 本题还可以从二进制角度考虑。通过观察可以发现:Ai 是(i-1)的二进制串中 1 的 个数,Bi 是(i-1)二进制串中把 0 去掉后构成的新二进制数转化的十进制数,这样 可以 O(log N)秒杀。注意输出数据要使用 unsigned __int64,否则 70 分。 如果还不明白,可以看黑书(第一版第 11 次印刷)P22-23

解 时间复杂度:O(P) 法 预期得分:70 (假设不存在子锁一) 一: n(n + 1) 递推公式非常简单: f ( n) = f ( n ? 1) + ,其中: f (1) = 1 。证明略。 子 递 2 锁 推 二 解 时间复杂度:O(1) (忽略高精度) 法 预期得分:100 (假设不存在子锁一) 二: n(n + 1)(n + 2) 其实看看 P 的范围, 就应该知道本题应该有通式。 通式: f ( n) = , 通 6 式 详细证明见附录二。这样,本题就变成了高精度计算,涉及加法、乘法和除法。 其实,高精除法是可以逃掉的。n,n+1,n+2 中,必有一数是 3 的倍数,至少有一数 是 2 的倍数,而 n 是在 unsigned __int64 范围内的,可以直接除掉。

为防止无 聊之人用 标程刷 A C 率, 标 程 和测试 数据就不 公开了 。 标程战况 参见附录 三 。 ( 应 该 会有虐 掉标程的 吧 ~ )
本题解仅保证方案的可行性,不保证方案的最优性

TYVJ 八月月赛提高组题解

附录 一
{An}构造方法: 0 0 1 1=0+1 0 1 1 2 1=0+1 2=1+1 0 1 1 2 1 2 2 3 1=0+1 2=1+1 2=1+1 3=2+1 …… {Bn}构造方法: 0 0 1 1=0*2+1 0 1 1 3 1=0*2+1 3=1*2+1 0 1 1 3 1 3 3 7 1=0*2+1 3=1*2+1 3=1*2+1 7=3*2+1 …… 明白了构造方法,就会发现,递归也可以做到 O(log n)。递归公式:

n ( <= k < n and k ∈ {k | k = 2 x , x ∈ N*}) 2 n Bn : f (n) = f (n ? k ) * 2 + 1 ( <= k < n and k ∈ {k | k = 2 x , x ∈ N*}) 2 An : f (n) = f (n ? k ) + 1
(没写错吧~)

本题解仅保证方案的可行性,不保证方案的最优性

TYVJ 八月月赛提高组题解

附录 二
1.公式( 公式(不解释) 不解释)
n (n + 1) 2 n(n + 1)(2n + 1) 12 + 2 2 + … + n 2 = 6 可以使用数学归纳法证明,此处略去。 1+ 2 +…+ n =

2.证明过程( 证明过程(不唯一) 不唯一)
设n为大三角形边长。(为了清晰,我们分步推导) 设Ak ,i 为边长为k的正立子三角形在第i层(" 层" 指上顶点所在位置,详见图)的个数, 由三角形网格性质易知: ?i (n - k + 1 ≥ i,0 < k ≤ n, n ∈ N*) Ak ,i = ? ?0 (n - k + 1 < i,0 < k ≤ n, n ∈ N*) 设B k 为边长为k的子三角形总个数,则: B k = ∑ A k,i = 1 + 2 + … + k =
i =1 n

1 2 k +k 2

(

) )]

设C n 为大三角形所有子三角形个数(n为大三角形边长),则: C n = ∑ Bi =
i =1 n

1 (1 + 2 + … + n ) + 12 + 2 2 + … + n 2 2

[

(

1 ? n (n + 1) n(n + 1)(2n + 1) ? + ? 2? 6 ? 2 ? n(n + 1)(n + 2) (n ∈ N *) = 6 =
此公式也可以由递推公式累加得到,本处略。

本题解仅保证方案的可行性,不保证方案的最优性

TYVJ 八月月赛提高组题解

附录 三
1.括号匹配 http://www.tyvj.cn:8080/Record_Show.asp?id=557619
#01: Accepted (0ms, 21720KB) #02: Accepted (0ms, 21720KB) #03: Accepted (0ms, 21720KB) #04: Accepted (43ms, 21720KB) #05: Accepted (278ms, 21720KB) Accepted / 100 / 321ms / 21720KB

2. 冗余电网 http://www.tyvj.cn:8080/Record_Show.asp?id=557626
#01: Accepted (0ms, 3324KB) #02: Accepted (0ms, 3324KB) #03: Accepted (0ms, 3348KB) #04: Accepted (43ms, 3336KB) #05: Accepted (137ms, 3324KB) Accepted / 100 / 181ms / 3348KB

3.黄金矿工 http://www.tyvj.cn:8080/Record_Show.asp?id=557631
#01: Accepted (0ms, 28608KB) #02: Accepted (0ms, 28608KB) #03: Accepted (0ms, 28608KB) #04: Accepted (0ms, 28608KB) #05: Accepted (0ms, 28608KB) #06: Accepted (0ms, 28608KB) #07: Accepted (0ms, 28608KB) #08: Accepted (43ms, 28608KB) #09: Accepted (75ms, 28608KB) #10: Accepted (59ms, 28608KB) Accepted / 100 / 178ms / 28608KB

4.密码双锁 http://www.tyvj.cn:8080/Record_Show.asp?id=557650
#01: Accepted (0ms, 220KB) #02: Accepted (0ms, 220KB) #03: Accepted (0ms, 220KB) #04: Accepted (0ms, 220KB) #05: Accepted (0ms, 220KB) #06: Accepted (0ms, 220KB) #07: Accepted (0ms, 220KB) #08: Accepted (0ms, 220KB) #09: Accepted (0ms, 220KB) #10: Accepted (0ms, 220KB) Accepted / 100 / 0ms / 220KB

总用时:680ms

本题解仅保证方案的可行性,不保证方案的最优性


相关文章:
TYVJ8月月赛提高组难度官方题解.pdf
TYVJ8月月赛提高组难度官方题解 - TYVJ 八月月赛提高组题解 1.括号匹
tyvj首届月赛题解.pdf
TYVJ 首届月赛试题题解报告 2011 年 1 月青蛙跳荷叶时间及空间复杂度 时间...TYVJ8月月赛提高组难度官... 5页 1下载券 喜欢此文档的还喜欢 tyvj...
信息tyvj题库前80道题解.pdf
信息tyvj题库前80道题解_理学_高等教育_教育专区。...背景 Background NOIP2007 年提高组第一题 描述 ...月月赛 铜牌第一道 描述 Description 示出了一个...
tyvj第五届月赛题解.pdf
TYVJ3 月月赛试题解题报告 2011 年 3 月最美妙的矩阵时间及空间复杂度 时间...tyvj部分题解 191页 1下载券 TYVJ8月月赛提高组难度官... 5页 1下载券...
tyvj第三届月赛题解.pdf
TYVJ 二月月赛第二场试题题解报告 2011 年 2 月猫咪的进化时间及空间复杂度...tyvj__部分题解代码 78页 免费 TYVJ8月月赛提高组难度官... 5页 1下载...
tyvj第二届月赛题解.pdf
TYVJ 二月月赛第一试题解报告 2011 年 2 月 9 日火焰巨魔的惆怅时间及空间...TYVJ8月月赛提高组难度官... 5页 1下载券 喜欢此文档的还喜欢 tyvj...
2017年信息学竞赛考试方式.doc
2017 年 11 月 12 日(周日),提高组 8:30-12:...1、题库方面首推 USACO(美国的赛题),usaco 写完...3、 国内广受 NOIP 级别选手喜欢的国内 OJ (Tyvj...
题解报告.doc
TYVJ 首届月赛试题题解报告 2011 年 1 月青蛙跳荷叶时间及空间复杂度
动态规划试题.doc
http://www.tyvj.cn:8080/Problem_Show.asp?id=...月月赛 铜牌第一道 描述 Description 示出了一个...提高组 第一道 描述 Description 在 Mars 星球上,...
16年五一OI金牌班(noip)_图文.pdf
信息学题库: www.tyvj.cn 第一部分:2016 年五一...选取突出典型的 NOIP 难度的 最短路的几种算法以及...NOIP2010,提高组一等奖, NOIP2011 提高组一等奖, ...
更多相关标签: