BZOJ 3107 [cqoi2013]二进制a+b 分类讨论

题意: 给定a,b,c，把a,b,c二进制重构，使得a+b=c，如果新的c的长度比原来3个数的最长的长度还要长的话则视为无解，，求最小的新的c。 解析: 大爷的分类讨论之2. 以下为吐槽

> 考试出3个分类讨论你敢信？> 卧槽上一篇题解那个题是t1> 直到剩20分钟我才意识到我看错题了nnd！> 还好思路清晰大脑没有短路，一顿调试debug倒是A了T1> 卧槽T2这东西简直。> 范围显然正解不是dp,肯定是某种黑科技构造什么的！> 分类讨论！md自己手玩构造错三段！还好我会拍23333> t3 aaqqz 我无力吐槽…

不妨把a看作a的1的个数，把b看作b的1的个数，把c看作c的1的个数，最长限制为n位。 现在令a=9,b=4,n=inf 然后考虑分类讨论 一、c=1 a=0000111111111 b=0111000000001 c=a+b=1000000000000 如此构造即可。 二、1

;int n,a,b,c;int sta[N],top;int main(){scanf(“%d%d%d”,&a,&b,&c);int cnta=0,cntb=0,cntc=0;int weishu;weishu=0;while(a){if(a&1)cnta++;weishu++;a>>=1;}n=max(n,weishu);weishu=0;while(b){if(b&1)cntb++;weishu++;b>>=1;}n=max(n,weishu);weishu=0;while(c){if(c&1)cntc++;weishu++;c>>=1;}n=max(n,weishu);a=cnta,b=cntb,c=cntc;if(a<b)swap(a,b);if(c==1){for(int i=1;i<a+b;i++)sta[++top]=0;sta[++top]=1;if(top>n)puts(“-1”);else {int ans=0;for(int i=n;i>=1;i–)ans<<=1,ans+=sta[i];printf(“%d\n”,ans);}}else if(c>1&&c<=b){sta[++top]=0;for(int i=1;i<c;i++)sta[++top]=1;int tmp1=a-c,tmp2=b-c;for(int i=1;i<=tmp1+tmp2;i++)sta[++top]=0;sta[++top]=1;if(top>n)puts(“-1”);else {int ans=0;for(int i=n;i>=1;i–)ans<<=1,ans+=sta[i];printf(“%d\n”,ans);}}else if(c>b&&c<=a){for(int i=1;i<=c-b;i++)sta[++top]=1;sta[++top]=0;for(int i=1;i<b;i++)sta[++top]=1;for(int i=1;i<=a-c;i++)sta[++top]=0;sta[++top]=1;if(top>n)puts(“-1”);else {int ans=0;for(int i=n;i>=1;i–)ans<<=1,ans+=sta[i];printf(“%d\n”,ans);}}else if(c>a&&c<a+b){for(int i=1;i<=c-a;i++)sta[++top]=1;int tmp=b-(c-a);for(int i=1;i<=a-tmp;i++)sta[++top]=1;sta[++top]=0;for(int i=1;i<=tmp;i++)sta[++top]=1;if(top>n)puts(“-1”);else {int ans=0;for(int i=n;i>=1;i–)ans<<=1,ans+=sta[i];printf(“%d\n”,ans);}}else if(c==a+b){for(int i=1;i<=a+b;i++)sta[++top]=1;if(top>n)puts(“-1”);else {int ans=0;for(int i=n;i>=1;i–)ans<<=1,ans+=sta[i];printf(“%d\n”,ans);}}else puts(“-1”);}

这一次是一个告别，或者一个永远的告别，