4 条题解
-
-2
本文由GPT5.6撰写
题解
设二进制数为：
因为
所以这个数除以
3的余数等于：因此问题变成：
让奇数位置的 1 数量 − 偶数位置的 1 数量是
3的倍数。
贪心
我们从左往右确定每一位。
- 求字典序最大：优先尝试放
1 - 求字典序最小：优先尝试放
0 - 第一位不能放
0
假设当前尝试放了
x，那么剩下r个1。设剩下有
O个奇数位置、E个偶数位置。如果剩余的
1中有y个放在奇数位置，那么：个放在偶数位置，所以剩余贡献为：
其中：
我们只需要判断这个区间里是否存在一个
y，使最终的：因为只看模
3，所以实际上只需要检查最多 3 个y。
复杂度
每个位置只尝试
0/1两种情况，每次判断O(1)。所以：
空间复杂度：
核心代码
string work(int big){ int N=n+m,one=n,sum=0; string s; for(int i=1;i<=N;i++){ int O=(N+1)/2-(i&1),E=N/2-!(i&1); for(int x=big;x>=0;x--){ if((i==1&&x==0)||x>one) continue; int r=one-x; if(r>O+E) continue; int l=max(0,r-E),R=min(r,O); int t=(sum+(x?(i&1?1:-1):0))%3; if(t<0)t+=3; bool ok=0; for(int y=l;y<=min(R,l+2);y++) if((t+2*y-r)%3==0) ok=1; if(ok){ s+=x+'0'; one-=x; if(x) sum+=i&1?1:-1; break; } } } return one||sum%3?"-1":s; }一句话总结：利用
2≡-1 (mod 3)把整串转成奇偶位置计数，然后从左到右贪心，每次判断剩余的 1 能否补出模 3 的合法方案。-
sanhai @ 2026-9-16 17:25:53
这个讲解的不清楚：
补充一下
内容为AI生成 对，这里确实应该从**“二进制数怎么判断能不能被 3 整除”**开始讲，不应该直接丢一句
2≡-1 (mod 3)。1. 先看普通的十进制
比如十进制数：
实际上就是：
判断它除以某个数的余数，本质上就是看这些幂次对这个数的余数。
二进制也是完全一样的。
2. 二进制数怎么表示？
比如：
101101它表示：
$$1\times2^5+0\times2^4+1\times2^3+1\times2^2+0\times2^1+1\times2^0$$现在我们想判断它能不能被
3整除。也就是想知道：
除以
3的余数是多少。
3. 看 2 的幂除以 3 的余数
我们一个一个算：
你会发现规律：
2^0 2^1 2^2 2^3 2^4 2^5 1 2 1 2 1 2也就是说：
- 偶数次幂
%3 = 1 - 奇数次幂
%3 = 2
而：
其实就是说：
而
-1除以3也可以理解成余2。所以：
并不是一个很神秘的东西，就是：
2 和 -1 除以 3 的余数效果完全一样。
4. 所以二进制数可以变成“正负交替”
对于：
101101原本是：
$$1\times2^5+ 0\times2^4+ 1\times2^3+ 1\times2^2+ 0\times2+ 1$$因为：
2^5 ≡ -1 2^4 ≡ 1 2^3 ≡ -1 2^2 ≡ 1 2^1 ≡ -1 2^0 ≡ 1所以变成：
$$1\times(-1) +0\times1 +1\times(-1) +1\times1 +0\times(-1) +1\times1$$也就是：
所以：
可以被 3 整除。
实际上：
确实：
5. 最终得到一个非常好用的规律
对于二进制：
b1 b2 b3 b4 b5 b6 ...从左往右编号：
位置： 1 2 3 4 5 6 + - + - + -所以：
如果这个数是
3的倍数，那么原二进制数就是3的倍数。例如：
101101奇数位置：
1 1 0 1有
3个1。偶数位置：
0 1 0有
1个1。所以：
等等，这里要注意：上面按“从左往右位置”算时，正负号取决于总长度的奇偶性。
为了避免这个坑，最稳妥的方法是从右往左看：
101101 ↓ 位置：6 5 4 3 2 1 + - + - + -因为最低位
2^0一定是+。所以实际上判断规则是：
从右往左，奇数位的 1 加起来，偶数位的 1 减起来。
对于
101101：从右往左： 1 0 1 1 0 1 + - + - + -得到：
所以能被
3整除。
这道题里为什么有用？
因为我们构造的是
$$\boxed{\text{奇数位置的1数}-\text{偶数位置的1数}\equiv0\pmod3}$$01串，只需要知道：就能判断整个二进制数是否能被
3整除。于是原题就从：
构造一个巨大的二进制数，使它能被 3 整除
变成了：
把
n个 1 放到奇数、偶数位置，使两边数量之差是 3 的倍数。这就是后面贪心能够成立的关键。
- 偶数次幂
- 求字典序最大：优先尝试放
SanhaiAI
@ 2026-9-16 17:19:41
