Nova_YZOJ新年欢乐赛题解

新年欢乐赛题解

题目机票

A. 这是一道大水题

B. 缘生意转

C. 绿豆沙冰

D. 泡妹子

E. 新年礼物

F. 脑回路

G. 在天愿作比翼鸟,在地共驾鹤望兰

H. Wahacer的Hack计划

I. 世界终将陷入黑暗


A题

前置技能点:bfs

简单的bfs

需要注意,因为Wahacer足够的灵活,所以如果有OIer直接就在Wahacer身边的话,Wahacer也可以直接逃脱

这句话的意思就是说,OIer一开始并不能抓住Wahacer,OIer还不能动,所以OIer对于Wahacer而言只是一个墙壁而已.

还真是一道大水题呢

B题

前置技能点:暴力胡搞

良心的12mango童靴已经写好了题解,详细可食用QvQ

http://www.cnblogs.com/12mango/p/8473650.html

C题

前置技能点:最短路图论相关

一道简单的最短路QvQ

c0per要去买绿豆沙冰.肯定是一来一回,为了节约时间,每次肯定要尽可能走最短路.

所以跑一遍spfa/Dijkstra都是可以的.

良心的c0per并没有卡spfa呢

D题

前置技能点:快速幂、费马小定理

需要求解这个公式\(S=((((a^a)^a)^a)^a····)^a\)

对于数据范围,我们可以发现\(n\)的上限可以到\(10^{18}\),一般的暴力或者是一般的快速幂是一定过不去的.

对于这个公式,我们可以先通过快速幂求出幂数,然后再快速幂一次求出答案.

但是幂数可能会很大.所以用一下费马小定理.

费马小定理

定义

​ 若\(p\)是素数,\(a\)为正整数,且\(gcd(a,p)==1\),则\( a^{p-1}\equiv 1(mod\ p) \)

证明

首先,\(p-1\)个整数\(a,2a,3a,···,(p-1)a\)中没有一个是\(p\)的倍数.并且他们当中都与\(p\)互质.

所以,\(a,2a,3a,···,(p-1)a\)对模\(p\)的同于既不为0,也没有两个同余相同,因此,这\(p-1\)个数对模\(p\)同余,一定是\(1,2,3,···,p-1\)的某种排列.

即\( a*2a*3a*···*(p-1)a\equiv 1*2*3*···*(p-1)(mod\ p) \)

化简可得.

\( a^{(p-1)}*(p-1)!\equiv (p-1)!(mod\ p) <=>a^{p-1}\equiv 1(mod\ p) \)(这一步化简可以看成威尔逊定理,同余式子中可以左右同除一个与模数互质的数,具体详见上文剩余系.)

也可以看做是\(a\)的逆元乘\(a^p\)与1关于\(p\)同余,因为\(p\)是个质数,所以也可以写成费马小定理的标准形式.

时间复杂度

\[ a^p\equiv a(mod\ p) \]

费马小定理可以用来求逆元,时间复杂度是快速幂的时间复杂度\(log_2n\)

所以就很简单啦

注意,对于快速幂的过程中,每个数字只能膜其对应的模数

E题

前置技能点:背包型动态规划相关

题意简介明了,就是一个简单的多重背包,但是难点在路径记录.

本题较有难度的考点就是动态规划中的路径记录.

多重背包嘛~也可以用二进制拆分优化一下.

单调队列优化?似乎数据范围已经允许了

在每次选择物品的时候记录一个\(path\).最后再反向递归查看就吼辣.

F题

10pts做法:

\(|S|=6\),随便暴力乱搞啊。

30pts做法:

其实回文什么的都是扯的。。。只要一段中出现奇数次的字符最多只有一个就合法。

设\(f[i]\)为考虑\(S\)前\(i\)个字符的答案,显然有\(DP\)式\(f[i]=min{f[j-1]}+1,{j<=i且子串[j,i]合法}\)。暴力判断是否合法即可。\(DP\)状态\(O(n)\),转移\(O(n^2)\),总复杂度\(O(n^3)\)。

50pts做法:

可以先开一个二维bool数组预处理出转移合不合法。预处理复杂度\(O(n^2*26)\)。

出题的时候发现常数太小而且\(10000*10000\)的bool数组好像也开的下,貌似能跑过\(60pts\)的样子。。。

60pts做法:

考虑异或前缀和。把每个字符出现了偶数次/奇数次看成二进制下对应位的\(0/1\),那么任意一个子串的状态都可用\([0,226-1]\)中的某个数表示。搞个异或前缀和\(c[i]\),区间\([l,r]\)合法当且仅当\(c[l-1] xor c[r]\)为\(2\)的次幂或者\(0\)。用位运算技巧\(O(1)\)判断,复杂度\(O(n^2)\)。

10pts做法:

送分。。。只含\(‘a’\)和\(‘b’\),显然答案最多为\(2\),若\(‘a’\)和\(‘b’\)均出现奇数次则为\(2\),否则为\(1\)。

100pts做法:

考虑状压。

我们发现\(c[i]\)只有\(226\)种取值,设\(g[k]=min{f[i]}(c[i]==k)\),于是从左往右\(DP\),对于每一个\(g[c[i]]\)只有\(27\)种转移,即\(min{g[c[i]],g[c[i] xor 2ch]}(0\leq ch\leq25)\)。最后答案即为\(max(1,g[c[n]])\)。时间复杂度\(O(n*26)\),空间复杂度\(O(226)\),\(int\)数组大概\(256MB\),并不会\(MLE\)。

核心代码:

\(std\)

G题

前置技能点:最小生成树、树链剖分

……std后续更新qwq

H题

前置技能点:二分图匹配匈牙利算法或者最大流算法

这道题显而易见,要求一级和二级手段同时存在才算作一个合理的Hack.因为奇怪的限制,有些一级二级手段不能同时存在,所以就存在一个二分图匹配的模型.

对于这道题可以发现二分图匹配可以直接跑匈牙利qwq,并没有卡哦.
当然如果要考虑一下网络流的思想的话,这道题也是一个网络流的最大流裸题.

问题是,网络流怎么建图?

对于二分图匹配类似的模型,我们可以直接建立一个超级源点,然后将所有一级Hack手段与源点建立容量为1的边.建立一个超级汇点,将所有的二级Hack手段与汇点建立容量为1的边.对于一级和二级手段之间建立正常容量的边.然后直接搞一发Dinic,最大流就是其最大匹配辣.

I题

前置技能点:二分答案

这道题非常有意思呢.首先这个人是个智障可以开启多线程的变态任务.

其次需要结合一点点生活经验,日子只能一天一天过去.

虽然这个人可以直接开启多线程去体验未来的日子,但是日子只能一天天过去这个前提不能变.

这样简化一下可以发现就是一个简单的模型.

对于一个序列,有\(n\)个点,可以最多选择\(m\)个点作为开始,每次往后移动一个.问最少需要多久才能遍历完序列中的所有的点.

做法也很简洁.

因为度过一天就算一天,所以我们直接二分答案.

然后暴力检测.

如果在当前答案情况下如果可以达成,就把答案再往小更新,不行就往大更新.

如何暴力检测?

首先,我们需要让日子有序.需要保证日子是递增的.

在当前二分出来的答案中,如果前后的日子差比答案小了,那就是说需要多开一个线程,最后判断当前答案下的线程数和最多能开的线程数的大小.

问题是为什么要二分?

因为没有其他的解题思路了啊……

以及注意数据范围QAQ

感谢

感谢各位选手在新年当中也能来参加本次的比赛,感谢各位出题人给的各种神题Orz,感谢DOFY给的两道神题的ider,qwq

还有什么问题可以随便提出喔

G题的std看心情写吧qwq

Nova_YZOJ新年欢乐赛题解》有1个想法

发表评论

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