猫史档案馆

经过我们JROI出题组的努力，AKJROI-2的Div3已经出好。

要参加的珂以在这里报名了。

本次比赛分为3个Div。Div3最简单，Div2其次，Div1最难。其中，Div3共3题，Div2分为两块，每一块3题，Div1共四题。

特别鸣谢出题人@ZH-Y-Q（Div3出题，Div2-D1出题）、@编程爵士MASTER_CodeLord（Div2-D1,Div2-D2,Div1出题，Div3数据修正）、@Apple的Siri哟、以及慕斯酱、min橙子和奆嘴喵

 

Div3考察：一次函数性质、十字交叉（浓度三角）、数位问题。

难度：入门、入门、普及/提高-

 

Div2-D1考察：最短路、莫比乌斯反演、模拟退火

Div2-D2考察：树形dp、平衡树、快速傅里叶变换

难度：提高+/省选-、省选/NOI-、省选/NOI-、提高+/省选-、省选/NOI-、NOI/NOI+/CTSC

 

Div1考察：AC自动机、网络流、平衡树、插头dp

难度：省选/NOI-、省选/NOI-、省选/NOI-、NOI/NOI+/CTSC

 

另：上次的Div1的题解咕了很久。下面附上简单的思路提示，题解后放。

T1：首先套积分公式，然后黑白染色使用二分图最大匹配

T2：O(n)筛出欧拉函数，然后使用快速幂套FFT大数乘，求出最后的模数，然后在sqrt(n^n)的渐进时间复杂度内判断是否是素数。最后在弄个FFT大数乘就可以了。因为涉及到大量快速傅里叶，所以码量大。但是没有思维难度。

T3：第一问用启发式广度优先搜索。第二问暴推式子。

T4：做法显然。因为大多数都是简单询问，能用线段树维护的都用线段树维护，不能维护的喵修改然后重新建树。几个式子推一推化简一下，n倍根号直接调用自带的power函数。

T5：第一问暴推式子。第二问按照字典序，不合法很好判断，所以直接把不合法的除掉，剩下的全输出就行了。

T6：这题难在建图。建立三棵线段树，分别维护单点到区间、区间到单点和任意传送。珂以看看我的博客中的线段树部分第一道例题，把建树稍微改一下就行了。（www.luogu.com.cn/blog/Jazzq喵/fu-za-shuo-ju-jie-gou）第一问以终点为起点，逆向跑一遍单源最短路即可。第二问无穷大，因为存在无数条花费无限精力的路径，但不存在负环。第三问求连通块，直接并查集。第四问为0，因为题目上已经说过不可能有负环了。第五问求最小环，把板子稍微修改一下就行了。