长安大学ACM协会

A协纳新啦！啦！！啦！！！长安大学ACM-ICPC协会纳新啦！期待你的加入！！！新一届的纳新工作又开始啦，我们还准备了有趣的题目和小礼品哦！不管你是哪个学院，不管你是哪个专业喜欢算法，喜欢挑战的萌新们还等什么，赶快加入我们吧！！ FAQ$Q:$ 什么是 $ACM \; ICPC$ 吖？$A:$ 这是国际大学生程序设计竞赛的简称啦~也就是说，如果你水平足够的话是可以参加每年一次的世界总决赛的(orz…)。 $Q:$ 那A协是干嘛的吖？$A:$ 我们是一群喜欢算法的萌新。啊，不对，泥萌才是萌新！我们只是算法爱好者~那泥萌喜欢算法嘛&_&喜欢就加入我们吧！ $Q:$ 什么是C语言？什么是算法？什么是程序设计？$A:$ 你需要看这个嘛，还有这个。或许看一道题目你能更清晰的了解ACM-ICPC，点这里。 $Q:$ 比赛形式是什么样的吖？$A:$ 正式比赛中，是最多三个人一支队伍，共同使用一台电脑，解决约十道题目。可以携带任何纸质资料，题目为英文描述。在提交某道题目的答案后几分钟内即可出现是否通过此题目的结果。关于培训在上学期，我们会有C语言培训课。所以，不 ...

北方大学多校联合训练第十一场（长安大学）简要题解

发表于2017-05-14

北方大学多校联合训练第十一场（长安大学）简要题解 A.Palindrome先把相邻的同字母段合并，跑一遍马拉车，注意只有长度和字母均相等才继续扩展。统计答案的时候再考虑两侧可能还有一段字母相同但是长度不同，取两边长度较小者。 B.Triangles小于三个点的情况答案为零。考虑三个点的情况，由于三点不共线，必然构成一个三角形。现加入第四个点，若其在原三角形外部，则称其为外点，可以新构造$1$个三角形；若其在原三角形内部，则称其为内点，可以新构造$3$个三角形。故要尽可能让更多的点成为内点。假设这$n$个点的凸包上有$m$个点，这$m$个点必然只能是外点，将凸包剖分成$m - 2$个三角形后，剩余$n - m$个点均为内点，答案即为$3n - 2m - 2$。 C.XOR Queries若询问固定$[L, R]$，那么可以用字典树维护$[L, R]$之间所有数的二进制表示，每次询问$(A, B)$只要在树上统计一遍即可。那么对于不同的$[L, R]$，可以用线段树或者类似的离线分治将询问区间分成$log$个然后在每个字典树上分别统计再求和。莫队维护字典树转移应该也可以通过本题。 ...