欢迎访问 生活随笔！
TAG聚合

生活随笔

当前位置： 首页 >

【无码专区5】01串（大讨论+构造）

发布时间：2023/12/3 59 豆豆
生活随笔 收集整理的这篇文章主要介绍了 【无码专区5】01串（大讨论+构造） 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

因为只有std，没有自我实现，所以是无码专区

主要是为了训练思维能力

solution才是dls正解，但是因为只有潦草几句，所以大部分会有我自己基于正解上面的算法实现过程，可能选择的算法跟std中dls的实现不太一样。

std可能也会带有博主自己的注释。

problem

多组数据，给定 n,mn,mn,m，构造一个 n+mn+mn+m 长度的 01 串。

  • 包含 nnn 个 111，mmm 个 000。
  • 将这个串看成二进制数后能被 333 整除。
  • 没有前导零，即高位第一位必须为 111。

分别输出字典序最大和最小的符合条件的 01 串。不存在就输出 -1。

T≤100,n,m≤1e5T\le 100,n,m\le 1e5T≤100,n,m≤1e5

我的想法

observation：二进制相邻两位若都是 111，则这两个位代表的 222 的幂的和一定是 333 的倍数。

证明：2i+2i−1=(2+1)⋅2i−1=3k2^i+2^{i-1}=(2+1)·2^{i-1}=3k2i+2i−1=(2+1)⋅2i−1=3k。

如果 nnn 为偶数。

  • 字典序最大一定是形如 1111...100...000 。

  • 字典序最小第一时间肯定会以为是 00...011..11 ，但是要求不能出现前导零。所以第一位固定为 111 后，其代表的幂次，2i2^i2i 取模 333 一定是 1/21/21/2。

    • 如果取模是 111，那么只需要某一位也为 111【2k≡2(mod3)2^k\equiv 2\pmod 32k≡2(mod3)】就又可以凑成倍数。形如 100...0010...0111..1111。
    • 如果取模是 222，那么只需要第一位也为 111就凑成倍数，形如 100..0011..111。

如果 nnn 为奇数。

  • 字典序最大。

    肯定也是前面一堆连续的 111，然后最后面的 333 个数的幂次都是取模为 111。

    形如 111..10..01..0100...00（最前面的连续 111 段长度肯定也是奇数）。

  • 字典序最小。

    首位是 111 没得跑。肯定也是后面一堆连续的 111，然后最前面的 333 个数的幂次都是取模为 111。

    形如 10...00010...010...011111...11（最后面的连续 111 段长度得是奇数）。

显然，偶数一定是有解的。奇数就不一定了，因为可能 111 个数不够。

solution

简单的讨论。

如果只有一个 111， 或者 111 的个数为奇数， 但 000 的个数不超过 111， 那么无解。

  • 只有一个 111， 显然无解。
  • 如果 111 的个数为奇数， 000 的个数是 000 个， 那么一定是 1111...111 这样， 无解。
  • 如果 111 的个数为奇数， 000 的个数是 111 个， 那么相当于 1111...1111 减去一个 111， 但是 1111...11111111...11111111...1111 模三余 000， 减去一个 111 之后模三不等于 000，所以无解。

如果 nnn 是偶数， 那么最大值一定是 1111000000 这样， 最小值首先放一个 111， 最后放 n−2n-2n−2 个 111，剩下的一个 111 用来和 第一个 111 之间放偶数个 000 保证能被 333 整除。

如果 nnn 是奇数，那么首先放 n−3n-3n−3 个 111，这部分能被 333 整除，然后放 10101，然后放若干个 000。最小值同理，开头放一个 111，末尾放 n−3n-3n−3 个 111，中间放 101，保证 1 和 101 中间有奇数个 000，这样前半部分也被整除了。

时间复杂度 O(n)O(n)O(n)。

std

#include <bits/stdc++.h> using namespace std;string mul(string a, int b) {string c;for (int i = 0; i < b; i++)c += a;return c; } string mx, mn;int main() {freopen("binary.in", "r", stdin);freopen("binary.out", "w", stdout);int T;scanf("%d", &T);while (T--) {int n, m;scanf("%d%d", &n, &m);if (n <= 1 || (n % 2 == 1 && m <= 1)) {mx = "-1";mn = "-1";} else {if (n % 2 == 0)mx = mul("1", n) + mul("0", m);elsemx = mul("1", n - 2) + "0101" + mul("0", m - 2);if (n % 2 == 0)mn = "1" + mul("0", m / 2 * 2) + "1" + mul("0", m % 2) + mul("1", n - 2);elsemn = "1" + mul("0", m / 2 * 2 - 1) + "101" + mul("0", m % 2) + mul("1", n - 3);}printf("%s\n%s\n", mx.c_str(), mn.c_str());} }

总结

以上是生活随笔为你收集整理的【无码专区5】01串（大讨论+构造）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。