【题解】吉首大学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、左后缀+右前缀 三者取最大

全部评论
有大佬帮忙看一下我 iiii 题代码哪里有问题吗,模队一直超时,不知道哪里有问题😫 https://paste.ubuntu.com/p/rksM5V32zR/
点赞 回复 分享
发布于 2019-07-16 19:45
点赞 回复 分享
发布于 2019-07-15 14:02
a题 如果用矩阵快速幂 1e(1e5)的话 有什么降幂的方法么 欧拉降幂这里还可行么??没降过矩阵快速幂的幂 貌似矩阵龟速幂要3e5-4e5次...
点赞 回复 分享
发布于 2019-07-15 10:42
c题我看了一下别人ac的代码,我算出来的答案和他不一样,我的第一个序列就不在ac的序列里面,这个序列是152839764,但是我感觉这个序列是合法的
点赞 回复 分享
发布于 2019-07-14 17:37

相关推荐

TCL前端笔试题目:以下是一些 TCL 华星前端笔试题目:以下关于 HTML5 语义化标签的说法,错误的是?在 CSS 中,以下哪个属性用于设置元素的定位方式?以下哪种不是前端性能优化的常见方法?当使用 Flex 布局时,以下哪个属性用于设置子元素在主轴上的对齐方式?简答题请简述 HTML、CSS 和 JavaScript 在前端开发中的作用分别是什么,以及它们之间的关系。解释一下什么是浏览器的回流(reflow)和重绘(repaint),并说明如何避免或减少它们对性能的影响。列举三种你熟悉的前端框架,并简要说明它们的特点和适用场景。如何实现一个响应式布局,使其在不同屏幕尺寸的设备上都能有良好的显示效果?请列举至少两种常用的技术或方法。描述一下 JavaScript 中事件冒泡和事件捕获的概念,并说明如何阻止事件冒泡。编程题请使用 HTML 和 CSS 创建一个简单的导航栏,要求包含至少三个导航项,并且当鼠标悬停在导航项上时,有相应的样式变化。编写一个 JavaScript 函数,实现对一个数组进行去重操作,返回去重后的新数组。用 HTML、CSS 和 JavaScript 实现一个简单的轮播图效果,要求可以自动播放,并且用户能够手动切换图片。TCL实业2025届春招正式启动!【公司简介】✅聚焦智能终端业务,主要涵盖显示、智能家电、创新业务及家庭互联网等全品类智能消费电子产品及服务✅业务遍及160多个国家和地区,全球有20个智能制造基地,2023年,TCL实业实现营业总收入1203.2亿元【招聘岗位】研发技术类、产品设计类、市场营销类、智能制造类、供应链类、财务金融类、综合管理类(TCL实业和TCL华星共用招聘系统,两家子公司一共只能投递两个岗位)【工作地点】深圳、惠州、中山、上海、武汉、西安等全国各地及海外城市TCL实业【内推链接】https://wecruit.hotjob.cn/SU6491506a2f9d24316e91b81b/mc/position/campus?acotycoCode=pchbbd&recruitType=1&isLimitShowPostScope=1【内推码】pchbbd(🌟内推投递,简历优先筛选,面试流程加快,TCL期待你的加入!)大家投递完可以在评论区打上姓名缩写+岗位,我来确认有没有内推成功喽                                                                                                                                                                                                                                                                                                                                                                                                                                                   
点赞 评论 收藏
分享
元戎启行24届秋招二面经(70分钟),摘自优秀牛油(1)项目介绍以及问题(2)RTOS系统的核心运行方式,相关信号量,互斥量等问题(3)RTOS系统任务是如何调度的,优先级问题(4)中断概念,如何中断,RTOS中的硬中断如何工作,软中断如何工作(5)RTOS系统运行中硬中断发生时,RTOS系统会如何处理(6)RTOS系统中的存在两个软中断时,系统会怎么处理(7)RTOS系统运行的环境是如何?一般在什么样的处理器运行(8)IIC的运行方式?IIC从机地址是如何配置的?主机地址是如何配置的?(9)运行过程中,如果新的IIC设备接入,主机和从机如何交换地址?(10)UART的协议,一共多少根总线,每根线的作用是什么,有什么线是不用接的?(11)UART协议一般是使用什么接口来包装的?(12)RS232和RS485的电气特性?差分电平是多少,分别对应什么逻辑?(13)linux系统中,挂载驱动最核心的东西是什么?(14)linux中,驱动是如何运行的,依赖着什么?(15)linux中如果有一个IIC设备,他的挂载流程是什么?设备树起到了什么作用?(16)你还熟悉哪些片上资源?简述SPI编程题:一道数学题目附加:(1)如何计算出计算的误差(2)如何减少时间复杂度(17)反问🔥智能驾驶!元戎启行!这些岗位热招中!25届春招补招!✅ 热招岗位:研发,职能,安全,规划,商务,市场,项目,感知,基础框架等80+个岗位✅ 已与多家车企量产合作,共同推进十余款车型的落地,2025年将有超20万辆进入消费市场✅ 人员规模超1000人,研发占比84%,清北/CMU/谷歌/微软等顶尖人才云集校招投递链接:https://app.mokahr.com/m/campus-recruitment/deeproute/145894#/home实习投递链接:https://app.mokahr.com/su/dcizug【内推码】NTAW9FW 【需手动填写】(填写推荐码优先筛选,加速流程)大家投递完可以在评论区打上姓名缩写+岗位(比如PM+LJJ),我来确认有没有内推成功喽                                                                    
点赞 评论 收藏
分享
04-26 23:17
已编辑
门头沟学院 C++
不鸣科技(服务器开发实习生)一面(40分钟)1.父类指针怎么调用子类的虚函数?2.析构函数需要是虚函数吗?3.父类指针析构子类对象会调用父类的析构吗?4.父类指针析构子类对象时,子类string成员、子类、父类的析构顺序?(没理解清楚,回答不是很好,应该先析构string、子类的析构、父类的析构)5.vector扩容的机制?6.vector拷贝行为可以怎么优化?(移动语义)7.如何在map中遍历删除指定的元素?8.给你一系列的元素,每个元素有一个权重,怎么让取到的元素概率和元素的权重呈比例?(没回答出来,加权随机选择,前缀和+二分查找)9.浮点数如何判断相等?(不知道,浮点数近似存储,因此不能直接==,fabs(a - b) 10.手撕一个stack,提供push、pop、top、getMin接口反问:1.技术栈(C++和Lua)2.什么时候出结果二面(45分钟)1.面试官介绍了下面试主要内容,说后面还会有业务三面2.子类、父类、子类的成员类,它们的构造顺序?3.类成员的初始化顺序?4.为什么按照声明顺序而不是初始化列表顺序?从设计者的角度考虑为什么这么设计(开放性问题,面试官对我的回答不太满意,最后给提示,函数重载是一个原因)5.类中的成员类实例存储在栈上还是在堆上?(分情况)6.基类的析构函数为什么建议是虚函数?7.如何判断浮点数是否相等?8.基于内存对齐规则,如何设计一个类?9.在map中如何在遍历过程中删除元素?10.说说条件断点和数据断点?还有的忘了反问:1.不足的地方(思维能力要提高)后续:五分钟后约三面(以为是HR面,结果被告知三面也是技术面)三面(25min)1.问了下感兴趣的技术方向(操作系统、数据库)好那就聊聊操作系统2.进程调度算法有哪些?3.进程和线程的区别?4.线程会共享进程的哪些资源?5.线程栈空间?6.说一说内联函数?7.函数调用的步骤?反问:1.不足之处 2.实习生培养方案后续:三面挂了三面那么短就觉得不太对劲果然是g了timeline:4.15 投递4.18 一面4.23 二面4.24 三面4.25 感谢信
点赞 评论 收藏
分享
评论
4
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务