#include #include #include using namespace std;

bool checkValid(int a, int b, int c, int d, vector& zeros, vector& ones) { int len = zeros.size(); for (int i = 0; i < len; i++) { if (zeros[i] > a || ones[i] > b || zeros[len + i] > c || ones[len + i] > d) { return false; } } return true; }

string generateString(int a, int b, int c, int d, vector& zeros, vector& ones) { string res; int len = zeros.size(); for (int i = 0; i < len; i++) { int cntZero = min(a, zeros[i]); int cntOne = min(b, ones[i]); a -= cntZero; b -= cntOne; c -= min(c, zeros[len + i]); d -= min(d, ones[len + i]); res += string(cntZero, '0') + string(cntOne, '1'); } res += string(a, '0') + string(b, '1'); return res; }

string constructString(int a, int b, int c, int d) { vector zeros(4, 0); vector ones(4, 0); for (int i = 0; i < 4; i++) { zeros[i] = a % 2; ones[i] = b % 2; a /= 2; b /= 2; }

if (!checkValid(a, b, c, d, zeros, ones)) {
    return 'impossible';
}
return generateString(a, b, c, d, zeros, ones);

}

int main() { int a, b, c, d; cin >> a >> b >> c >> d; string res = constructString(a, b, c, d); cout << res << endl; return 0; }

C++ 算法:构造满足子序列出现次数的 01 字符串

原文地址: https://www.cveoy.top/t/topic/plTI 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录