主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
题解:P13008 【MX-X13-T3】「KDOI-12」只有失去光明,才能逃脱黑暗。
最后更新于 2025-07-31 13:52:54
作者
cflsfzh
分类
题解
题解
P13008
复制 Markdown
查看原文
删除文章
更新内容
**前言** 写这篇题解是为了纪念我做这个黄题时的【数据删除】,我真【数据删除】的【数据删除】。我试图用简单贪心无果,最终恼羞成怒用了我们珂爱的 dp。 **正文** 首先我们显然可以令 $x \leq y$,我们的目的是令 $x$ 等于 $y$,令 $x$ 为 $y-x$。我们把 $x$ 用二进制的形式表达出来,会是一个类似 0100110 形式,我们发现,其实我们只可能使用三种操作: - 最简单的,对于每一个第 $i$ 位上的 1,计入 $a_i$ 的贡献。 - 对于一个全是 1 的串,设最高位为 $r$,最低位为 $l$,计入贡献 $a_{r+1}+a_l$。 - 对于一个有 0 有 1 的串,如 1001110011,我们可以利用减的方法,让更高一位减去,即 10000000000-1=1111111111,然后 1111111111-0110001100=1001110011,其中至于如何计算 0110001100 的贡献,用前两种操作计算取最优的一种即可。 于是这道题基本上就做完了,讲一下实现:我们将 $x$ 的二进制的 01 串里的连续的 0 和 1 放在一起考虑(这样显然最优),如 1001110011 这个串,考虑为 1+00+111+00+11。对于一个都是相同数字的串,如果我们用第一种方法计算,那计算的贡献的最高位为串的最高位,如果我们用第二种的话,那计算的贡献的最高位为串的最高位的下一位,我们分开考虑,设 $awa[i][2]$,0 表示到了第 $i$ 个相同数字的串第一种情况的最小值,1 表示第二种的最小值,前两种操作的贡献很好考虑,于是在考虑是否用第三种操作向前合并即可,具体实现看代码。时间复杂度 $O(TK)$。 **code:** ```cpp #include<bits/stdc++.h> #define int long long #define pb push_back #define pii pair<int,int> #define fs first #define sc second #define il inline #define re register using namespace std; il int read() { re int x=0; re int ff=1; re char c=getchar(); while(c<'0'||c>'9'){ if(c=='-') ff=-1; c=getchar(); } while(c>='0'&&c<='9'){ x=x*10+c-'0'; c=getchar(); } return x*ff; } const int N=31; int t,x,y,k,a[N]; signed main() { t=read(); while(t--){ x=read(); y=read(); if(x>y)swap(x,y); k=read(); memset(a,0x3f3f,sizeof(a)); for(int i=0;i<=k;i++) a[i]=read(); for(int i=1;i<N;i++) a[i]=min(a[i-1]*2,a[i]); int awa[2][2]={0,0,0,0},l=0,lt=0,i=0,now=1,qwq=0,lt_qwq=0;x=y-x; while(!(x>>i&1)&&i<N)i++;l=i; for(;i<N;i++) if(x>>i&1){ if(now) qwq+=a[i]; else lt_qwq=min(qwq,a[i]+a[l]),lt=l,l=i,qwq=a[i],now=1; } else{ if(!now) qwq+=a[i]; else{ awa[1][0]=min(awa[0][0],awa[0][1])+qwq; awa[1][1]=min(awa[0][0],awa[0][1])+a[i]+a[l]; if(lt)awa[1][1]=min(awa[1][1],awa[0][1]-a[lt]+a[i]+lt_qwq); awa[0][0]=awa[1][0],awa[0][1]=awa[1][1]; lt_qwq=min(qwq,a[i]+a[l]),lt=l,l=i,qwq=a[i],now=0; } } printf("%lld\n",min(awa[0][0],awa[0][1])); } return 0; } ```
正在渲染内容...
点赞
1
收藏
0