前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >能直接获得 EC-Final 入场券的 ICPC 西安邀请赛是何方神圣?

能直接获得 EC-Final 入场券的 ICPC 西安邀请赛是何方神圣?

作者头像
ACM算法日常
发布2021-12-20 18:06:49
2.1K0
发布2021-12-20 18:06:49
举报
文章被收录于专栏:ACM算法日常

相信大家都还记得曾经因为 EC-Final 名额的事情在群里舌战的同学和主办方。事情的起因就是,参加 ICPC 西安邀请赛的金牌队伍所在学校可以直接获得 EC-Final 名额。

西安邀请赛每年都会在西北工业大学举办,不过比赛和 EC-Final 的不同就在于,队伍实力没有 EC-Final 这么强,而且比赛会在学校的机房进行。

比赛的题目会由西北工业大学自己命题,为了让大家更直观的感受比赛的难度,我们今天来看看 2019 年西安邀请赛的题目(2019 ICPC China Xi'an Invitational Programming Contest)。

因为我们参与了线下赛,所以这里就没有代码分享了。

一点我们现场比赛的记录

  • 现场的座位非常挤。
  • 热身赛四点求面积这种题目都能锅,提前预感到了正赛锅会比较大。
  • 果然正赛连样例都能锅。
  • 题面表述乱七八糟,全靠连蒙带猜得知题意。
  • 评测队列积压严重。甚至

5 min 才能出结果。

  • E 题连 O(nq) 的暴力都能过,出题人造树的数据连个链都没有,怕是用脚造的数据。
  • 空调坏了,赛场热的(哔—)
  • 上完厕所回来会感觉机房的门相当于一个巨型暖气。

Problem A

贪心。签到。

Problem B

题意:求 \prod\limits_{i=1}^{n}\prod\limits_{j=1}^{n}\prod\limits_{k=1}^{n}m^{gcd(i,j)}[k | gcd(i,j)]

随便化一化式子就出来了,不过常数很紧。

题解:用欧拉降幂转化为求和 =\sum\limits_{k=1}^{n}kd(k)\sum\limits_{i=1}^{n/k}\sum\limits_{j=1}^{n/k}[gcd(i,j)==1] 相当于枚举 gcd(i,j)=k

注意到 \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[gcd(i,j)==1]=2\sum\phi(i)-1 直接用通用莫比乌斯反演会反演显然超时,这样考虑基数就能用杜教筛了。

线性筛预处理前 10^7d(i), \phi(i) ,大的 id(i) 可以用交换循环顺序+数论分块求。

Problem C

题意:给定一个圆,圆之外中心高度以下的部分不能被经过,圆内部也不能被经过,求圆上最低点到圆外中心高度之上任意一点的最短路。

题解:先把原点放到圆心,再把终点 x 坐标变成绝对值。

\frac {1}{4} \pi r 的路径是必走的,然后如果 x>r,从 (r,0) 直线走过去就可以了,如果 $x

Problem D

题意:将军战力有战力点数全部分成两边,有不能再同一边的两两的将军关系,求一种分配使得两边分差最小。

题解:肯定在哪里做到过。二分图染色,然后把小的那一堆两边加上,大的减小的值是一个新的物品,然后就是裸的背包。

Problem E

题意:支持树上某一点到根路径上所有点 and 一个值, or 一个值,链上做 nim 游戏。

题解:显然 nim 游戏就是求个异或。

常规操作,拆位。

and 一个值和 or 一个值,转换一下就是链上所有的数置 0/1 ,线段树维护就好了。

树上的链处理,树链剖分一下。

Problem I

题意:给定数列 a^{k},....,a^{k+n-1} (\mod p)n 其中 1 \le a_i \le 10^5 ,求是否有唯一的 a,p \le 10^{10}

题解:等比数列显然是不唯一的,周期出现但是不包含 1 显然是不存在的。

n \le 2显然是不唯一的。剩下的非等比数列一定存在 a[i]^2 \not = a[i-1]a[i+1] 然后发现 p | abs(a[i-1]a[i+1]-a[i]^2) 枚举素因数就能求 p 了,然后一个一个验证。

注意会爆 long long , exBSGS 判 k 是否存在也要改成快速乘。

Problem J

题意:给定一棵有 n 个节点的树,求这棵树上每条路径上,边权异或和为 0 的子路径的数量和。

题解:定义 dep(u)u 的深度(根节点深度为 0),son(u) 是以 u 为根的子树中的节点数,E(u,v)uv 的路径,F(u,v)uv 的路径的边权异或和。

我们可以按 u,v 的位置关系将所有 F(u,v)=0 分类:如果 uv 的祖先,这条路径对答案的贡献是 (n-son(w)) \times son(v) ,其中 wv u 路径上除 u 之外深度最深的节点。否则,这条路径对答案的贡献是 son(u) \times son(v)

我们发现,第二种路径可以拆成两条第一种路径,因此维护每个节点向上的第一种路径,并统计在此节点交汇的所有第二种路径的贡献,用启发式合并维护。

Problem L

题意:给定一个长度为 n ,每个元素均不同的序列,可以将偶数位和前面的奇数位互换,可以将前一半和后一半互换(如果有中间元素,中间元素不变),问可以从初始序列达到多少个不同的序列。

题解:找规律。对 n=1,3 的情况特判,剩下的情况里 n \%4=0 时答案是 41 时是 2n2 时是 n3 时是 12

Problem M

题意:可以给一个飞船升级,每次升级花费 c ,可以通过的路径长度 +\;d ,可以通过的边总数+\;e 。求最小的花费,能从 1 n

题解:二分最小的升级次数。

验证的时候从 1 开始 BFS ,所有能够拓展的边全部拓展,显然 BFS 先到的满足了通过边数最小的要求,可以拓展的边满足了可以通过的路径长度要求。

判断此时 1 n 是否联通即可。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-12-12,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 ACM算法日常 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一点我们现场比赛的记录
  • Problem A
  • Problem B
  • Problem C
  • Problem D
  • Problem E
  • Problem I
  • Problem J
  • Problem L
  • Problem M
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档