CH Round #54 - Streaming #5 (NOIP模拟赛Day1 解题报告.docxVIP

2016.10.25 解题报告Part.1 珠（beads） 水题一道，有坑。（因为变量没赋初值直接爆零了。。。TvT。。。）解题思路读入用string（等于没说），C党注意string相关函数的用法；把所给序列复制一遍，这样就能枚举环上的每个断点了；从左往右搜。设一个bool变量beg，有2打头为true，否则为false；一个计数变量cnt，记录当前合法的连续3的长度；ans记录最长的合法连续3的长度（这俩变量都不计2） s[i]==’2’beg==false： beg=true，跳过； s[i]!=’2’beg==false： 跳过； beg==trues[i]==’2’： 比较cnt和ans，更新ans；beg=true；cnt清零；跳过；s[i]==’3’： cnt++；跳过；其他：比较cnt和ans，更新ans；beg=false；cnt清零。从右往左搜，同上；注意：① 序列长度为1时，如果是2，输出2，否则非法（输出TvT） ② 序列中有单独的2时要特判。Part.2 免农（radit）改编自NOI2011第一试“兔农”一题，但是要比原题简单很多。。。原题需要矩乘求斐波那契数列类似物，但这道题只需要快速幂就能解决了。解题思路参考官方题解，就不再重复了while (m=n) //一定要加等号{if (tmp==1) //说明有一只免子落单了{ans=((power(2,m+1)+p-1)%p*power(2,n-m)%p)%p; //死掉一只免子，从这时往后就倍增，快速幂跑就行了coutans;return 0;}tmp=tmp*2%k; //找什么时候出现落单的免子m++;}Part.3 高维网络（cube）分情况讨论，很多很多情况。。。按照给出的测试点情报，理论上是可以拿到相当可观的分数的。本蒟蒻撑死跑到75分（虽然官方说这样搞应该可以搞到80分来着。。。），100分解法参考官方题解。。。Point.1 d==1 2点可过D==1的时候就是一条线啊！直接判断目标点到（0,0）之间有没有断开就行啦。。。这种情况下会有神奇的坑，如果算法不合适的话p==0可能会出错，最好特判一下。Point.2 d==2 p==0 4点可过（之所以不把p==0都列成一类主要是因为d==1太简单。。。）根据题意，相当于在图中绿色矩形框内由左下角走到右上角，本来是个典型的棋盘DP，然而既然没有不能走的点，根据数学原理，结果等于C(x+y,x)（或者C(x+y,y)二者相等）：一共走x+y步，其中有x步向右走。Point.3 d==2 p0 4点可过p0的时候，显然不能直接用组合数，那就老老实实跑DP吧。。。节省内存可以只开一个二维数组，如果不能走就设成-1，转移时跳过就好。（惭愧的是，第15个点并不能用这种解法跑出来，不想爆空间直接MLE就别作大死开100，000*100,000的数组。。。所以正解还是参考官方题解吧TAT。。。）Point.4 d==3 p==0 2点可过好吧分这么多情况实在太作死了。。。但为了多拿几分再麻烦也要无怨无悔才行。。。比如第13、14、16个点拿DP是没法跑的（炸内存），但拿组合数就可以过。三维的组合数算法一样，只不过每次有三个方向可以走，答案很显然。long long p1=C(n,sx)%mod;long long p2=C(n-sx,sy)%mod;ans=p1*p2%mod;Point.4 d==3 p0 3点可过还是棋盘型DP，第17个点同样搞不掉。。。三维数组开到100就快撑着了，100,000就不要想了。。。综上，靠着分类处理（骗分大法好！）可以搞掉15个点，剩下那5个。。。本蒟蒻实在啃不动，求大神指教。。。官方满分解法如下 （似乎是离散化后用一维数组跑，挺玄妙的。。。）