模拟DAY6

模拟DAY6

题目:NOIP模拟测试题(day2).pdf
无密码

T1题解:
集训的时候松爷讲过……(然而一开始并没有想起来正解)
先用埃拉托斯特尼筛法筛出0~sqrt(2147483647)的素数表,然后用这个素数表筛l~r的区间,O(nloglogn)完成任务
//所以说是棵题?

AC代码:

T2题解:
显然的找规律题,可是计算过程爆int就跪了……
对于一个数n,我们显然要考虑他的每一位对答案的贡献,也可能会把它分类为个位十位百味来考虑,去找由个位到十位(也就是n和10n之间有什么联系)
举一个2和20的例子:
2的答案是3,20的答案是102
对于20来说,我们可以把它看做00~19~20,也就是在十位数字为0~2-1时,他的个位数字循环了2次,所以个位数字的贡献就是452;再考虑十位数字,0~2-1时,每一个数字都连续出现10次,所以去掉20这个数本身(因为他并没有循环个位数字),十位数字对答案的贡献就是10(0+1);在考虑这个数本身,也就是没有参与个位数循环的20,只要单独把它的贡献算出来加到答案里即可(因为计算单个数的贡献的O(位数))
类比下来,我们就可以找到这个规律了:
对于一个数n,设它的答案为S[n]
假如他%10等于0,我们去掉它的末位0得到x,那么S[n]=45x+10S[x-1]+n的贡献;
假如他%10不等于0,就可以枚举得到的整数到n的剩余几个数直接计算他的贡献(如通过12得到了120,121、122、123通过枚举加入答案即可),这样的复杂度依然是很小的。
//一定不要天真的以为答案看long long 就可以了,过程爆int你可就gg了哦!(像我一样?)

AC代码:

T3题解:
正常的人来说(比如我),会想到dfs传一个数组,数组中记录当前没堆该拿第几张牌,这没什么问题,而且也能AC,但是……
但是这会TLE啊!而且显然我们需要记忆化啊!像我开的结构体数组就没法记忆化啊(因为map是用红黑树储存,需要定义小于号,也正是因此它的复杂度才是log)
那怎么办呢?
我们都会想到状压啊!我们可以想象这是一个五进制数,那么用int就可以记录了(最多为444444444(5),也就是5^9-1)然后开vis什么的也炒鸡方便(状压天下第一!)
虽然我被五进制搞得一脸蒙蔽……:
要取某一位的数:如对x取第i位,return x%ksm[i+1]/ksm[i]即可(类比10进制)
要把某一位+1,:return x+ksm[i]
所以其实还是很简单的!

//考试的时候被存图卡死……,因为身为一个字符串,它的后面有一个\0,这是需要一个位置的……

AC代码:

0

发表评论

电子邮件地址不会被公开。 必填项已用*标注