2024 ICPC EC final游记+BEFL题解

B题. Roman Master

题意

给定一个只含大写I和大写V的字符串，需要寻找一个划分策略，使得划分之后的每个子串是罗马数字，且连续组合而成的数字最小

例如 IVIIVII划分为IV，II，VII，组合而成的数字为427

串长<=1e5，多组数据

题解

从后往前划分，尽量划分更长的罗马数字，这样可以让前面组合出来的数字位数更少，如果最后一位是V，则尽量找IV的组合，如果最后一位是I，则尽量组合III，如果前面还有V，则最好组合VIII，以此类推。

例如VIIIIIV，则先划分出IV，然后是III，再是VI，最后答案是634。

E题. Colorful Graph

题意

n种颜色的点，每种点有ai个，构造一张简单无向图（可以不连通），满足同色的点之间的最短距离大于等于d（无向图边权默认为1）

1<=n<=5e5，1<=d<=n，1<=ai<=1e9，sum(ai)<=1e9

题解

如果d等于1，那么直接所有的点一起做一个完全图即可。

如果d大于1，每种颜色的点各取一个，做一个无向完全图，这样肯定边数最大。

例如1 1 3?3?5?5?5，则可以构成1张点数为7的完全图，2张点数为5的完全图，2张点数为3的完全图

由于时间复杂度的限制，我们需要按点数对完全图分组，一组一组的计算就可以了。

但是在d=2的情况时，这些无向完全图之间还可以连一些边。

简单推一下式子：

设已构成的完全图总数为N，已构成完全图使用的点数sum，

设当前完全图组的完全图数为M，当前完全图组的一个完全图的点数m

ans+=完全图内边数：m*(m-1)/2 *M? +? 完全图间边数

完全图间边数=（sum-N）*? M*m

（因为是前面的完全图颜色集包含后面的完全图颜色集，所以当前完全图中的每一个点的颜色，一定会在之前的每一个完全图中出现，只要不连接相同颜色的点，就可以保证）

+完全图组之间的边数

完全图组之间的边数=M*(M-1)/2*m*(m-1)

最后累加起来就是答案了。

F题. Dot Product

题意

给出一个1~n的排列，只能交换相邻两个位置的数，请问需要至少交换多少次，才能让排列满足以下条件：

记当前排列为{ai}，产生的序列{i*ai}为不下降序列

1<=n<=5e5，多组数据

题解

首先发现若排列为1~n顺序排列，则{i*ai}一定满足条件

当只交换两个相邻的数时，该排列也满足条件

但是，如果交换过的两个数，再次与另外相邻的数发生交换时，排列就一定不会满足条件

例如初始序列(i-1)*(i-1)，i*i，(i+1)*(i+1)

交换前两个数(i-1)*i，i*(i-1)，(i+1)*(i+1)

再换后两个数(i-1)*i，i*(i+1)，(i+1)*(i-1)（此时后两个数大小关系已经不满足条件）

发现这个性质后，说明最后的序列一定是一个顺序排列只发生不重复交换后的排列

接下来就是构造一个策略，来以最少的步数达到目标排列。

记录每个数字当前的位置，每次查询当前未处理的最小的两个数字i、i+1的位置，如果i在i+1位置之前，则把i放到位置i，完成处理i。否则，将i+1放到位置i，i放到位置i+1，完成处理i、i+1。

实现方式可以使用树状数组单点删除+查询位置。

L题. Binary vs Ternary

题意

给定两个01串A、B，定义一次操作为，选定A中的一个子串，将其二进制视为三进制，然后将该三进制代表的数转化为二进制，替换原来的子串，有多种方案可以达到目的，只需要输出其中一种，需要判断无解情况。

例子1100100选中11，11在三进制下表示4，转换为二进制为100，则原串变为10000100。

1<=|A|、|B|<=64，多组数据

题解

构造题。

无解情况简单，1位数无法变成多位数，多位数无法变成一位数，一位数到一位数单独判断即可。

可以发现若初始串为11，则11->100，再选中10，100->110，这样我们就在保持11不变的情况下在末尾生成了一个0，若再多做一步11->100->110->111，就可以在末尾生成一个1

直到B串第三位都可以按上述方法生成。

由于A、B两个串都没有前导0，第一位一定为1，第二位为0时，把11变为100，再收缩00即可变为10；第二位为1时，保持11不变即可完成构造。

所以说11生万物（三生万物）

之后我们就需要把A变换为11，首先可以消除前导0，那么A串就变为了111……111000……000

然后将前面的11从后向前依次变为100，消除所有的非开头1，A串变成10000……0000

然后收缩后面的0，变成10，再变成11，完成构造。

游记

Day 0

热身赛被劝退，赶紧回酒店洗头转运

Day 1

开题队友做B，贪心wa了一发，找到反例就A了

然后看E，是个简单贪心+计数题，推推式子，1A

然后队友写K题，1A

然后是F，推了半天性质，想了半天策略，发现是分类讨论+树状数组，队友写，1A

再看L题，发现是构造+模拟，写了半个小时，1A

封榜后看J题，交互题，发现就是模拟dfs，走到父节点就回退，走完当前节点的边就回溯，但是一直超出步数，一直wa到比赛结束

后来跟cy，gzf大佬讨论，发现是少加了一个剪枝

这波是痛失银牌和3000元奖金

然后去了华为座谈会，点心很好吃，讲的都是耳熟能详的华为业绩和发展前景，印象最深刻的是一个技术主席上来讲了半个小时的JIT优化技术。

Day 2

满满的行程表 7：40起床

上午华为挑战赛，发现不会做，直接交了大暴力，出现了奇奇怪怪的错误爆零了，然后连续交了11发，工作人员看不下去了，最后两分钟跟我说我怎么一直在交热身赛的代码，乐死了2333333，然后最后一分钟交上去了，最后376分，200+名三等奖都没有

体验极差，xxx退钱！

下午跟hjx坐了一个小时地铁，去米哈游 朝 圣参观，很兴奋，但是只开放一楼，芙芙的七天神像还没修好（都不够我看的），十几分钟就逛完了，展出的东西好少。不过是免费参观，不亏。

晚上又坐了一个小时地铁去 正 太 广 场正大广场参加华为之夜，看到了东方明珠，还有高耸入云的建筑，出地铁站的瞬间就被震撼到了，感叹这才是真正的上海！

华为之夜两个小时，180+80+10+2个奖，800个人，愣是一个没中，纯纯罚坐两个小时，而且去的时候去还吃过晚饭了，看着满桌子的菜一口都吃不下了，但愿下次运气好一点（但愿下次还能参加2333333）