ICPC西安站回顾
前言
队名:想想双一流该怎么做
时间:2026.10.18
题目质量:中等
赛站体验:拉完了
热身赛
热身赛的题其实是我觉得正个赛站中最好的一个
下面的题解按照难度顺序,补题链接目前没找到
B
题意
给定dx出题的代价,以及他能使用的费用,需要出的题目数量,求他还要额外找几题来凑数
解法
纯签到,只要两行就能解决的题目,这里不解释
A
好题
题意
交互题,隐藏一个二进制串,每次询问一组l,r,返回
可以询问n次,然后问你最终二进制串,得不到答案直接说-1就行
解法
需要手玩一些样例
注意到当你询问长度为1的区间时,什么都得不到
因为0和1都返回1
接下来是长度为2的
1 | 10 得到3 |
可以发现,长度为2的能得到两个位置是否相同,这个信息是十分重要的
这样就意味着,我们只需要确定序列中任意一个元素就行了
所以接下来的长度,我们希望用最少的代价确定一个或一些元素
接下来是长度为3的
1 | 000 得到3 |
什么有效信息也得不到,因此得出结论,长度小于3的啥也得不到
接下来是长度为4的
根据前面的推导,我们知道了长度为2能得到相邻两个是否相等这个信息,
那么考虑询问所有2得到的所有可能性,也是8种,然后考察使用询问4这个步骤是否有效
1 | 000 |
可以看出,AAB或BBA这两者形式的就能唯一确定4元组的信息,所以只要出现这种形式的一定有解
那么如果不出现的是否一定无解呢?
好吧其实我也不知道怎么证明,但是这个结论确实是正确的
C
题意
通信题
给定一个3e5长度的二进制串,你把这个加密成一个800×800的二进制矩阵,然后系统选择一些格子修改(01反转一部分格子),但是修改的格子,两两之间互不八连通,然后把矩阵还你,你需要得到原来的二进制串
思路
这题其实挺难的,因为两者的信息率已经是1:1了,而且随便变换一下,格子数量就不够了,所以肯定是要把原数据直接塞进去
然后考虑8连通不会改变什么,这里还是很好想到的,搞一个2×2的矩阵,这个矩阵全黑或全白,修改一个还是能看出来的,但是这样的话,矩阵只能表示1.6e5的信息,显然是不够的
1 | 11 10 |
所以我们不能加密,而是把原始信息放进去,再想办法设计一些特殊的校验位,借助前面的这个性质,来实现加密
这题其实我没有想出来,GPT给的方案是,下面搞一行异或前缀
1 | 1001010100001010 |
为什么这样是可行的?
此时取s[i]=r1[i]^r2[i]^r2[i-1],并假设r2[0]=0,因为错误不八连通,所以要是第一行发生错误了,这个值一定为1,第二行发生错误了,会得到两个连续的1,这样可以唯一定位错误
因为,要是不发生错误的话,s[i]应该为0,前缀异或的性质
如果改了原始数据,那么下面的他就不能改了,所以得到s[i]=1,
要是改下面的,会影响连续两位,所以得到两个1
最后,由于修改时有间隔的,所以要么是单独的11,要么是单独的1,这样就唯一确定修改位置了
比赛的物资
据说别的赛站的选手的牌子是有名字的,西安站没有反正
然后比赛没有刷新笔,
总之西瓜大还是太偏僻了我说,学校这真没多少东西,食堂关键还挺神秘,饭票的30元并不完全等于30元,然后第一顿去迟了,吃了啥也不是的自助餐,30=9,下次再也不会这么干了
其实可以去教练的餐厅吃,但是忘记了,下次一定
最后根据群u消息发现可以拿票去超市兑换,换了30元的零食(不管,反正我感觉还是亏了)
相反,注意到赞助商的物资很不错,甚至有fufu
正式赛复盘
正是赛感觉确实是一个大的,但是其实我们也不够强,还是没有做到把所有我们会的题在短时间内写完,前面网络赛打的好其实就是这么做到的,CCPC那次更好是因为做出了一道我们能力边缘的题,最近几次的效果不够好,但是,粗略的算一下罚时发现,我们要拿到银其实这样就行了
怎么说呢,目前来看我们应该是能在赛场出4-5题的,要是只会4题的话,得少吃点罚时
然后我感觉我自己单挑铜牌题还是有一点困难,如果有队友给我确认思路的话那又不一定了,我还是更善于实现目前而言
最近vp的几次比赛加上西安站,铜牌题只有一次在我手上,大部分时间我是写签到的,但是这次西安站签到也不在我手上,所以我实际上只贡献了0.5题,相反我们队的主力做了2题
不知道是不是我后面知道了签到的坑,我补的时候感觉毫无压力就过了,vp的几次签到题我写也都还是算稳的,虽然不是很快
然后我队友和我一样,喜欢偷偷出点神秘错误,一般找不到的那种,比如上次我队友在vp武汉不开long long,说计算量好像不会爆,以及西安站inf不够大,导致dp卡了两小时
我当时没懂他的式子,但是帮他优化了,赛后测试发现其实除了inf其他都对了,到最后我只能换转移方程,进行更多的防御型编程
我这个人呢,为什么会有神秘错误呢,一般是两种,一种是逻辑混乱,处理实际不对,还有一种是防御性过强了,反而出bug了,比如写线性基写了个右移65位(已老实),剩下的错误只能是我不会的了
最后还是希望我自己能在赛场上单干出一个铜牌题,留一到两个小时和队友一起做一道银牌题
正式赛题解
补题链接The 2026 ICPC Asia Xi’an Regional Contest 补题
(注意到当前评价为-890)
M
这个的话按题目意思模拟就行了,但是注意必须等所有人的这一轮打击计算完成了再结算,包括给队友回血救活这一步
别急,这题最阴的点是,你队友死了,还能给你回血,注意一下就行(所以dx你真的玩过音游吗就出题,反正这种机制我第一次见)
代码:
1 | void solve(){ |
C
这个是我插手的题目
队友print出来的不在我这里,但是赛后我们知道,后面我帮他化简以后,就已经是正确的式子了
这题根据数据范围,显然发现是一个dp题,类似于编辑距离的那种
这题的关键点是确定当前这一个数字是从哪里来的,通过这个思路就能推导出正确的式子了
设dp[i][j]表示b的第i位由a的第j位转移过来的,并且前i位填完的最小代价
然后枚举当前b中这个数字是从a中哪里转移过来的,修改这个的代价显然是abs(a_j-b_i)*y
接下来考虑转移,那么唯一能考虑的就是上一个位置从什么地方转移而来了
分类讨论
第一个位置
首先枚举b的第一个位置的时候,一定要复制一次,然后要把所有其他的都删完
1 | for(int i=1;i<=n;i++) dp[1][i]=x+abs(b[1]-a[i])*y+(n-1)*z; |
后面的位置
因为根据我们的dp逻辑,除了第一个,后面的要么再复制一段,要么直接使用上一次复制的段
要是上一次选择的转移的在这次选择前面,那么不需要再次复制,反之,需要再次复制,
要是直接用上一次的,相当于少删一次;若再复制一次,也要删掉别的没用的
1 | dp[i][j]=min(pre[j-1]-z+abs(b[i]-a[j])*y,suf[j]+(n-1)*z+x+abs(b[i]-a[j])*y); |
写的时候需要注意一点技巧,比如转移的pre[j-1]可能到0,需要防御一下
上限的计算
1e6*1e9*3000=3e18
最大来源是修改,需要修改3000次,每次代价为1e6,每个最多修改1e9,当时队友算错是因为忘记乘1e6好像?反正挺奇怪的,我也没看出来
J
这道题我只参与了翻译,但是不会做,构造这种很需要猜的感觉我就没想出过几次
做法
这里讲一下题解的做法
对于当前区间,要是头和下一个不一样,那么直接连,否则和最后的连,然后把他们的另外一个端点设置为相同,此时数列中,每个元素又敲好出现两次,所以是一个子问题,可以递归
然后递归处理,直到只剩下两个点,最后直接相连
参考实现
1 | void dfs(ll l,ll r){ |
构造合法性证明
要证明这个思路是正确的,只需要证明这个递归每一次都是子问题,并且最小子问题有解就行,这其实就是数学归纳法了
但是是子问题这个在前面的递归设计中已经讲解了,所以这个构造一定得环
然后为什么得到合法括号序列,
因为每次要么是()+S要么是(+S+),所以一定合法
H
这个题目是一个来自塔的题目,能起金属化或者覆甲,然后考虑最少防住的代价
注意到金属化是一直都有的,所以不如直接在所有回合开始前起,然后在每一个回合起刚好的覆甲
那么这里其实可以发现,只需要枚举金属化的数量就行了,当金属化的量确定时,覆甲的数量一定时确定的
显然,要是够了,那么就不用起了,否则,需要起能防住的甲
然后要是前一回合的覆甲加上当前的甲不够,需要再起对应的覆甲
接下来,我们对每一个位置进行分析,看看和金属化的关系
情况1
上一个位置完全帮不上,那么只有一次转折,前面每起一点金属化,就可以少起一点覆甲,之后完全不需用起.
情况2
完全帮上,不起
情况3
帮上部分,一定会在金属化多到一定时刻时,前面帮不上了,这时就需要起更多的覆甲了,然后再完全超过时,不需要起覆甲
可以发现每一位置都是一个分段一次函数,自变量是金属化,应变量是覆甲
那么我们能否直接叠加这些一次函数得到两者的关系呢?
那么我们需要分析每个位置是否是独立的.
独立性分析
因为每个位置要是甲不够了,都会起足,而每一次又是根据上一次计算的,剩余甲的数量一直是前一次的攻击减金属化,所以独立
对每一段的分析
详细懒得证明了,反正每一段都是单调的,所以可以直接枚举所有端点,然后取最小值
参考代码
实现时注意中间会溢出,结果不溢出虽然
1 | const ll N=5e5+10; |