首页 > 代码库 > 学校2016双基竞赛 4/10
学校2016双基竞赛 4/10
１、华东交通大学2016年ACM“双基”程序设计竞赛 ４／１０
０３ ![技术分享]()
总结：找规律的题，二叉树的先序遍历，从根节点向下一直到叶子节点，判断路径上的左右子树(向左，序号增1，向右，序号增加(左子树的节点个数))
总结：找规律的题，二叉树的先序遍历，从根节点向下一直到叶子节点，判断路径上的左右子树(向左，序号增1，向右，序号增加(左子树的节点个数)) ０４ 题意：((a-b)*c+d*e)/f=k，给定K的值，一共有多少种不同整数的组合(a,b,c,d,e,f)使公式成立（-50≤a,b,c,d,e,f≤50） 总结：重点是将公式转为(a-b)*c=k*f-d*e，将复杂度从O(n^6)化为O(n^3)。 一开始用map，结果超时，看来map存取花时间多。
０５ 题意：给出a,b,c，求(a^b)*c%mod，( mod=1e9+7，b<=10^100000 )。 总结：好题，欧拉定理，大数取模，快速幂。
０７ 题意：给出多场球赛的开始、结束时间，要看完所有比赛，但一台电脑同一时间只能看一场比赛，求要多少电脑。 总结：一开始用贪心，但超时。 这题只要在开始时间＋１，结束时间－１，然后计算最大的前缀和就可以了。
０８ 题意：给出n个数，ans=min(a,b)*abs(pos_a-pos_b)，输出ans的最大值。 总结：要善于找规律。题目的范围都是1e6，所以ans的值主要是以abs(pos_a-pos_b)为主。 做法：O(n)处理，注意开LL，取数列的左右界l,r，得到初始答案ans，每次取min(a[l],a[r])的一侧向中心遍历，当找到更大的数时，能更新则更新答案，当l>r结束，输出ans。
０６、０９压轴题，不会。先贴出学长的题解吧
6.这个题如果不是强制在线那么只需要维护一个字典树就行了。强制在线的话就维护一个树上的可持久化字典树就行了。
9.数据出得水，验题的时候没人写，其实暴力就可过。
标称做法是：后缀数组处理出sa数组和height数组，再对height建立RMQ来O(1)求出lcp(l,r)；在每次查询的时候找到当前k串在sa数组中的位置以及在height数组中与其lcp长度为len(k)所能覆盖范围，
二分就可以得到向左向右延伸范围L,R，在这个范围里面我们只要1~n里面出现过的次数，就是相当于在一个任意区间内求出里面包含了多少个不同的数，这个用主席树解决。。或者可以后缀自动机之类的也可做。
学校2016双基竞赛 4/10
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。