前言

队名:想想双一流该怎么做

时间:2026.10.18

题目质量:中等

赛站体验:拉完了

热身赛

热身赛的题其实是我觉得正个赛站中最好的一个
下面的题解按照难度顺序,补题链接目前没找到

B

题意

给定dx出题的代价,以及他能使用的费用,需要出的题目数量,求他还要额外找几题来凑数

解法

纯签到,只要两行就能解决的题目,这里不解释

A

好题

题意

交互题,隐藏一个二进制串,每次询问一组l,r,返回

可以询问n次,然后问你最终二进制串,得不到答案直接说-1就行

解法

需要手玩一些样例

注意到当你询问长度为1的区间时,什么都得不到

因为0和1都返回1

接下来是长度为2的

1
2
3
4
10 得到3
00 得到2
01 得到3
11 得到2

可以发现,长度为2的能得到两个位置是否相同,这个信息是十分重要的
这样就意味着,我们只需要确定序列中任意一个元素就行了
所以接下来的长度,我们希望用最少的代价确定一个或一些元素

接下来是长度为3的

1
2
3
4
5
6
7
8
000 得到3
001 得到3
010 得到3
011 得到3
100 得到3
101 得到3
110 得到3
111 得到3

什么有效信息也得不到,因此得出结论,长度小于3的啥也得不到

接下来是长度为4的

根据前面的推导,我们知道了长度为2能得到相邻两个是否相等这个信息,
那么考虑询问所有2得到的所有可能性,也是8种,然后考察使用询问4这个步骤是否有效

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 000 
0000 询问4得到4
1111 询问4得到4
001
0001 询问4得到5
1110 询问4得到7
010
0011 询问4得到6
1100 询问4得到6
011
0010 询问4得到5
1101 询问4得到7
100
1000 询问4得到5
0111 询问4得到7
101
1001 询问4得到6
0110 询问4得到6
110
1011 询问4得到7
0100 询问4得到5
111
1010 询问4得到6
0101 询问4得到6

可以看出,AAB或BBA这两者形式的就能唯一确定4元组的信息,所以只要出现这种形式的一定有解

那么如果不出现的是否一定无解呢?

好吧其实我也不知道怎么证明,但是这个结论确实是正确的

C

题意

通信题
给定一个3e5长度的二进制串,你把这个加密成一个800×800的二进制矩阵,然后系统选择一些格子修改(01反转一部分格子),但是修改的格子,两两之间互不八连通,然后把矩阵还你,你需要得到原来的二进制串

思路

这题其实挺难的,因为两者的信息率已经是1:1了,而且随便变换一下,格子数量就不够了,所以肯定是要把原数据直接塞进去

然后考虑8连通不会改变什么,这里还是很好想到的,搞一个2×2的矩阵,这个矩阵全黑或全白,修改一个还是能看出来的,但是这样的话,矩阵只能表示1.6e5的信息,显然是不够的

1
2
3
11    10
11 -> 11
显然可以恢复,这是因为只会修改一个位置,而且只有全黑白的能复原

所以我们不能加密,而是把原始信息放进去,再想办法设计一些特殊的校验位,借助前面的这个性质,来实现加密

这题其实我没有想出来,GPT给的方案是,下面搞一行异或前缀

1
2
1001010100001010
1110011000001100

为什么这样是可行的?

此时取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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void solve(){
  ll n; cin>>n;
  string s[4]; cin>>s[0]>>s[1]>>s[2]>>s[3];
  ll cnt[4]={0,0,0,0};
  ll rat[4]={2000,2000,2000,2000};
  for(int i=0;i<n;i++){
    for(int w=0;w<4;w++){
      if(s[w][i]=='H') cnt[w]++;
      else cnt[w]=0;
      if(s[w][i]=='J') rat[w]-=50;
      if(s[w][i]=='A') rat[w]-=100;
      if(s[w][i]=='M') rat[w]-=200;
      if(cnt[w]==100){
        cnt[w]=0;
        for(int k=0;k<4;k++){
          if(rat[k]==-1) continue;
          if(w==k) continue;
          rat[k]+=30;
        }
      }
    }
    for(int w=0;w<4;w++)
      if(rat[w]<=0) rat[w]=-1;
      else if(rat[w]>=2000) rat[w]=2000;
  }
  for(int i=0;i<4;i++) cout<<max(0ll,rat[i])<<" "; cout<<endl;
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void dfs(ll l,ll r){
  if(l+1==r){
    ans[l]='(',ans[r]=')';
    return;
  }
  if(a[l]!=a[l+1]){
    ll x=p[l],y=p[l+1];
    a[y]=a[x],p[y]=x,p[x]=y;
    ans[l]='(',ans[l+1]=')';
    dfs(l+2,r);
    return;
  }
  if(a[l]!=a[r]){
    ll x=p[l],y=p[r];
    a[y]=a[x],p[y]=x,p[x]=y;
    ans[l]='(',ans[r]=')';
    dfs(l+1,r-1);
    return;
  }
}

构造合法性证明

要证明这个思路是正确的,只需要证明这个递归每一次都是子问题,并且最小子问题有解就行,这其实就是数学归纳法了

但是是子问题这个在前面的递归设计中已经讲解了,所以这个构造一定得环

然后为什么得到合法括号序列,

因为每次要么是()+S要么是(+S+),所以一定合法

H

这个题目是一个来自塔的题目,能起金属化或者覆甲,然后考虑最少防住的代价

注意到金属化是一直都有的,所以不如直接在所有回合开始前起,然后在每一个回合起刚好的覆甲

那么这里其实可以发现,只需要枚举金属化的数量就行了,当金属化的量确定时,覆甲的数量一定时确定的

显然,要是够了,那么就不用起了,否则,需要起能防住的甲

然后要是前一回合的覆甲加上当前的甲不够,需要再起对应的覆甲

接下来,我们对每一个位置进行分析,看看和金属化的关系

情况1

上一个位置完全帮不上,那么只有一次转折,前面每起一点金属化,就可以少起一点覆甲,之后完全不需用起.

情况2

完全帮上,不起

情况3

帮上部分,一定会在金属化多到一定时刻时,前面帮不上了,这时就需要起更多的覆甲了,然后再完全超过时,不需要起覆甲

可以发现每一位置都是一个分段一次函数,自变量是金属化,应变量是覆甲

那么我们能否直接叠加这些一次函数得到两者的关系呢?

那么我们需要分析每个位置是否是独立的.

独立性分析

因为每个位置要是甲不够了,都会起足,而每一次又是根据上一次计算的,剩余甲的数量一直是前一次的攻击减金属化,所以独立

对每一段的分析

详细懒得证明了,反正每一段都是单调的,所以可以直接枚举所有端点,然后取最小值

参考代码

实现时注意中间会溢出,结果不溢出虽然

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const ll N=5e5+10;
i128 a[N],b[N];
void solve(){
  i128 n,x,y,maxn=0; read128(n),read128(x),read128(y);
  map<i128,i128> change;// change记录的是每一个位置覆甲的变化率,以及在什么时候变化
  for(int i=1;i<=n;i++) read128(a[i]),read128(b[i]);
  i128 pre=0,pos=0,f=0;//这里发现一个问题,因为要是这么计算的话,如果前面的覆甲把当前的超过了,后面的会使用的并不是上一个
  for(int i=1;i<=n;i++){
    maxn=max(maxn,b[i]
    i128 give=pre-(a[i]-pos);// 当前还剩余的覆甲数量
    if(give<0){
      change[0]--;// 完全帮不上时,每次多起一点金属化,覆甲就可以少起一点
      change[b[i]]++;// 注意这里记录的是覆甲折线函数的斜率变化
      pre=b[i];// 这个位置还剩pre点覆甲
      pos=a[i];// 上一次起满覆甲的位置是pos
      f+=b[i];// 计算初始代价
      continue;
    }
    if(give>=b[i]) continue;// 完全帮上,0折点
    change[give]--;// 当前面的覆甲帮不上忙的时候,这里每起一点金属化,覆甲可以少起一点
    change[b[i]]++;// 当完全超过时,又不需要金属化了
    pre=b[i],pos=a[i],f+=b[i]-give;
  }
  // 这里,覆甲的函数为折线一次函数的因是,每次起的覆甲都是起满的,要是上一次的不够了,这次还会补上,所以每个位置都是满足前面的讨论的
  // 因此每个位置的代价都是折线一次函数,叠加就是覆甲的代价函数了
  // 最后再和金属化的代价合并,发现还是折线一次函数,所以只要算每个折线的端点的代价就行
  i128 mnn=maxn*x,nowk=0,lastp=0;// minn初始值选择了结束时的值,也就是完全不适用覆甲,只使用金属化
  for(auto[p,k]:change){// 取所有端点的最小值
    f+=(p-lastp)*nowk,nowk+=k,lastp=p;
    minn=min(minn,f*y+p*x);// 起x点金属化,f点覆甲的代价
  }
  print128(minn); puts("");
}