A. 绿绿与串串
solution
生成字符串的方式决定了: 当字符串中的某个奇回文串的左端为开头, 或右端为结尾时, 这个奇回文串的中间的位置就是其中一个长度.
时间复杂度:\(O(n)\)
B. 赛艇
solution
将路径也弄成一个矩阵, 然后压位判断.
时间复杂度:\(O(\frac{1}{64}n^2m^2)\)
F. 密码学第三次小作业
solution
一看它给了两个式子就知道不是暴力分解质因子.
中间有一个很特别的性质:\((e_1, e_2)=1\), 也就是说存在 \(s_1e_1+s_2e_2=1\)
\[m (mod N)=m^{s_1e_1+s_2e_2} (mod N)=c_1^{s_1} c_2^{s_2} (mod N)\]
注意 \(s_1, s_2\) 是一正一负, 所以还要求某个数的逆元.
时间复杂度:\(O(logn)\)
I. 城市地铁规划
solution
跟树的度有关的就想到 \(prufer\) 序列, 树的每个数的度等于在该序列的出现次数加一. 所以可以用一个 \(n^2\) 的 \(dp\) 求出最大值, 并得出对应的 \(prufer\) 序列, 就可以还原一棵树.
时间复杂度:\(O(n^2)\)
J. 弗雷兹的玩具商店
solution
维护一个 \(60\) 个域的线段树, 每次询问做一次背包.
时间复杂度:\(O(nm+qmlogn)\)
K. 蛋糕
solution
数学题, 找规律, 也可以进行降维类比.
时间复杂度:\(O(1)\)
L. 生生不息
solution
打表.
M. 为最美的那位献上花朵
solution
第一题的输入样例的最后一个单词.
来源: http://www.bubuko.com/infodetail-2619209.html