竞赛讨论区 > 【题解】吉首大学2019年程序设计竞赛(重现赛)
头像
山海亦可平
编辑于 2019-07-16 09:42
+ 关注

【题解】吉首大学2019年程序设计竞赛(重现赛)

更详细的有代码的题解:link

弱鸡的题解肯定有许多不足,如有错误或更好的方法,欢迎巨佬们指出,感谢
某些题可能会在今明两天写详细点QAQ
A-SARS病毒 表示长度为i的合法字符串的数量,表示仅A的个数为奇数的字符串数量 表示仅C的个数为奇数的字符串数量,表示A, C个数都为奇数的字符串数量
很容易的可以推出状态转移方程组

可以从上面递推式中构建矩阵

就可以用矩阵快速幂来写啦
不过我们通过观察发现初始状态相同,而且以后迭代方程也相同,所以





迭代后可以得到
因为n比较大,记得欧拉降幂即可

其实还有更nb的解法得到最后表达式,用母函数 泰勒公式什么的,因为我不会,所以就不放上去了

B-干物妹小埋
树状数组求最长上升子序列:复制原数组,排序去重后,原数组从前往后扫,找到它在去重后数组的位置,树状数组维护的前i大的最长上升子序列
这道题只不过加了权值而已,同理

C-手机锁屏
很抱歉标程出了问题(已修改)
mp[i][j]表示i和j点之间是否有线,判断连线合法,之后再判断对称即可,但要注意有特殊情况,比如说序列是456的时候需要给mp[4][6]也加上一根线,比如说序列456328917,如果不加的话28连了线46没连会判不对称。

D-数列求和(嘤雄难度)
换元,迭代,错位相减,累加可以求得打表找规律
我们可以考虑先求出所有与不互质的和,再相减即为所求
预处理m的质因子,个数不多
与m不互质的肯定与m有共同的质因子,枚举出所有质因子的组合
假设,n中与m有k这个公约数的个数就有再用求和公式+容斥就可以得到对答案的贡献
E-多喝嘤料
模拟即可
H-蛇皮走位
模拟即可
F-天花乱坠
由几何关系很容易求出结果其实就是等比数列求和取极限

G-说能过那是假的
o表示目前O的总数,or表示目前OR的总数,orz表示目前ORZ的总数
为O时,o++
为R时, or+=o
为Z时,orz+=or
最终的orz即为所求

I-滑稽树上滑稽果
在这里插入图片描述

J-滑稽树下你和我
将一条边删去后,分成的两棵子树内的点都需要经过这条边才能到达另一棵子树,它对结果的贡献为

K-白山茶与红玫瑰
线段树维护区间前缀连续0/1、后缀连续0/1、区间最大连续0/1
因为偶数次翻转相当于没变,异或更新lazy标记
查询 左子树最大连续01、右子树最大连续01、左后缀+右前缀 三者取最大

全部评论

(4) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐