网站做seo要多少钱,国外租车网站模板,aws wordpress ssl,线上销售平台如何推广因为只有std#xff0c;没有自我实现#xff0c;所以是无码专区
主要是为了训练思维能力
solution才是dls正解#xff0c;但是因为只有潦草几句#xff0c;所以大部分会有我自己基于正解上面的算法实现过程#xff0c;可能选择的算法跟std中dls的实现不太一样。
std可能…因为只有std没有自我实现所以是无码专区
主要是为了训练思维能力
solution才是dls正解但是因为只有潦草几句所以大部分会有我自己基于正解上面的算法实现过程可能选择的算法跟std中dls的实现不太一样。
std可能也会带有博主自己的注释。
problem
多组数据给定 n,mn,mn,m构造一个 nmnmnm 长度的 01 串。
包含 nnn 个 111mmm 个 000。将这个串看成二进制数后能被 333 整除。没有前导零即高位第一位必须为 111。
分别输出字典序最大和最小的符合条件的 01 串。不存在就输出 -1。
T≤100,n,m≤1e5T\le 100,n,m\le 1e5T≤100,n,m≤1e5 我的想法
observation二进制相邻两位若都是 111则这两个位代表的 222 的幂的和一定是 333 的倍数。 证明2i2i−1(21)⋅2i−13k2^i2^{i-1}(21)·2^{i-1}3k2i2i−1(21)⋅2i−13k。 如果 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());}
}
