zerotrac #1 能力赛(NOIP普及+提高难度)

OI - Unofficial

From zerotrac


小时

尚未报名

送分题-A*B Problem 29/82 From
信心题-随机游走 5/25 From
一眼题-手机号码 3/9 From
暴力题-空袭 4/26 From
附加题-轴上行走 8/25 From

C++党请注意!!!本场比赛需用%lld读入和输出long long类型的数字!!!评测在Linux下进行!!!

·NOIP提高组难度

4个小时 4道题 大家肯定都能AK

有原题

upd1 题目名称添加完毕

upd2 P1,2,3已上传,P3数据+标程已上传

upd3 P1,2数据+标程已上传

upd4 P4数据+标程已上传 大家积极报名

upd5 题目在网盘http://pan.baidu.com/share/link?shareid=3726270945&uk=1275570103,比赛签公布密码(Hint:密码是只有小写字母的长度为9的英文单词,大家可以猜一猜^_^)

upd6 分数排名实时公布

upd7 密码是birthmark

upd8 加了一道题

upd9 提醒某些人,别抄程序。

upd10 下次我会控制比赛难度的。。。三道难度和这次Prob A一样的题目。。。

upd11 题解

总体情况:

题目出得有点难了。。。下次我降低难度。。。
Prob A:AC人数最多的一道题
暴力20分 标算100分
Prob B:SCOI2009 迷路
搜索20~30分 DP70分 标算100分
Prob C:JS省队集训jyy出的模拟赛Prob 1
没人做这道题。。。 标算100分
Prob D:JS省队集训gsh出的模拟赛Prob 3
直接暴力50分 四分树50分 链表75分 标算100分
Prob E:就是Codeforces Round #191 Div.2 Prob E
搜索20分 DP80分 标算100分

Prob A
如果有Python语言,你可以直接输出a*b%p,否则告诉你,Pascal和C++再算a*b的时候,已经溢出了。
拿20分的人竟然不去写高精度。。。真是丧心病狂。。。
正解是这样的:
快速幂会吧?不会的自行百度。。。
a^b=(a^(b/2))^2 若b为偶数 a^b=(a^(b/2))^2*a 若b为奇数
那同理,a*b=(a*(b/2))*2 若b为偶数 a*b=(a*(b/2))*2+a 若b为奇数
不就没了吗。。。

Prob B
我只是把题面改了一下,把模数改了一下。。。
然后有人直接交标程连模数都不改。。。
其实就是裸的矩阵乘法。。。

Prob C
DP和自动机都可以做,自动机我不会。。。我就说DP的方法了。。。
dp[i][x1][x2][x3][x4][x5]为前i位,第i-5~i-1位的数字分别为x1,x2,x3,x4,x5的方法数
它可以从dp[i-1][x0][x1][x2][x3][x4]转移得到,x0=0~9
那么考虑以x5结尾的5个数字串,它们中如果有一个能被连续读出且为不幸运的数字串,那么dp[i][x1][x2][x3][x4][x5]=0
否则dp[i][x1][x2][x3][x4][x5]=sigma(dp[i-1][x0][x1][x2][x3][x4]) x0=0~9

注意特判,如果"1"为不幸运的数字串,那么答案为0

Prob D
裸的二维线段树(树套树)(二维树状数组)啊。。。
二维线段树不会的自行百度。。。
标程我给的是二维树状数组。。。
首先开一个bool数组表示每一个建筑有没有被摧毁,建筑按照建造的时间依次编号
在二维线段树的每个节点上挂个链表,链表里面就是包含这个节点的建筑的编号
每次询问时,如果搜到了某个节点,就把这个节点的链表顺序扫一遍,如果有建筑没有被摧毁,那么答案+1,并且在bool数组里面把它标记为摧毁
扫一遍之后就把这个节点的链表完全删除,因为链表中的建筑要么是之前已经被摧毁了,要么是这一次刚被摧毁的

Prob E
最水的Prob E之一。。。
最多24个点。。。想到了什么?状压DP^_^
用一个24位的二进制数表示每张卡片是否已经用过,1表示用过,0表示没用过
状态的转移就是dp[x]=sigma(dp[y]),y是把x中的某一个1改成0的数,如果位置x有陷阱那么dp[x]=0
状态有2^n种,扫描某一种状态中的1的位置要n次
复杂度为O(2^n*n)。。。好像会超时。。。
怎么办。。。树状数组有没有听过。。。没听过的自行百度。。。
(其实骗你的,这道题不需要数据结构,但是要用到树状数组中的lowbit操作)
lowbit(x)=x&(-x) Pascal是x and (-x) 这个操作可以把x最末尾的1找到
例如lowbit(24)=8,就表示24的二进制11000中,最末尾的1表示的十进制数为8
这样可以起到常数优化的作用。。。就不会超时了。。。