题解：P15650 [省选联考 2026] 摩卡串 / string
liujiaxi123456 · · 个人记录
前言：
高一，D2T1 没判
这应该是考场上最简单的思路（没有之一），应该不算严格正解，但是思路确实过于简单，性价比极高，应该还是有点价值。
思路：
观察大样例发现，答案似乎为：000...000 +
- 实际上，这样无法通过大样例 5，需要在
s 前面再加一段很 01 串。
注意到这两段都非常小，考虑先暴力枚举两段，然后再贪心的在前面加 0。
直接实现的话可以获得一定的分数（这个视实现区别很大，我个人在什么优化都没有的情况下大概得到了 80 分）。
优化与实现：
先说一下原本的实现逻辑：
- 枚举前后两段。
- 贪心的再前面加 0。
- 比较使用的是 z 函数。
一些比较重要的优化：
-
最优性剪枝。
-
如果前面段开头为 0 就不用测了。
-
加 0 的过程是可以二分的。
-
不要使用状压枚举，而是使用搜索，这样一旦当前值超了就可以直接返回。
主要就是这些剪枝，然后略微调参即可通过。
如果不想卡常，可以数据点分治，这样很容易就能通过。
如果在省选考场上实现这个做法，考虑到不能调参，大概应该能获得 80~90 分，考虑到这个算法几乎没有思维难度，应该是性价比非常高了。
Code：
没有使用数据点分治，所以比较丑，不算很卡，但是也不充裕。
#include <bits/stdc++.h>
using u64 = uint64_t; using i64 = int64_t; using u32 = uint32_t; using i32 = int32_t;
using ll = long long;
#ifdef LOCAL
// #define DEBUG
#endif
#ifdef DEBUG
#define printf(...) fprintf(stderr, __VA_ARGS__)
#define puts(s) fprintf(stderr, "%s\n", s)
#else
#define printf(...) (void(0))
#define puts(s) (void(0))
#endif
using namespace std;
bool ST;
const int Maxn = 8005;
const i32 INF32 = INT32_MAX/2-5;
namespace Josh_zmf {
int N, K, M, Case, NN, p;
char SS[Maxn], temp_t[Maxn]; string s;
char base_concat[Maxn * 3];
int z[Maxn * 3];
int base_len;
inline void precompute_z() {
base_len = NN + 1;
for(int i = 1; i <= NN; i++) base_concat[i] = s[i];
base_concat[base_len] = '#';
z[1] = base_len;
int L = 0, R = 0;
for(int i = 2; i <= base_len; i++) {
int R_i_1 = R - i + 1;
if(i <= R && z[i - L + 1] < R_i_1) z[i] = z[i - L + 1];
else {
z[i] = (R_i_1 > 0) ? R_i_1 : 0;
while(i + z[i] <= base_len && base_concat[z[i] + 1] == base_concat[i + z[i]]) z[i]++;
if(i + z[i] - 1 > R) { L = i; R = i + z[i] - 1; }
}
}
}
inline int robust_evaluate(int len_t) {
int len_c = base_len + len_t;
int L = 0, R = 0;
for(int i = base_len + 1; i <= len_c; i++) {
int R_i_1 = R - i + 1;
if(i <= R && z[i - L + 1] < R_i_1) {
z[i] = z[i - L + 1];
} else {
z[i] = (R_i_1 > 0) ? R_i_1 : 0;
while(i + z[i] <= len_c && base_concat[z[i] + 1] == base_concat[i + z[i]]) z[i]++;
if(i + z[i] - 1 > R) { L = i; R = i + z[i] - 1; }
}
}
int res = 0;
for(int i = 1; i <= len_t; i++) {
int k = z[base_len + i];
int rem = len_t - i + 1;
if(k < NN) {
if(k < rem && base_concat[base_len + i + k] < s[k + 1]) res += rem;
else res += (k < rem ? k : rem);
} else {
res += (NN - 1 < rem ? NN - 1 : rem);
}
}
return res;
}
inline int safe_check(char* test_str, int len_t) {
static char concat[Maxn * 3];
static int z_safe[Maxn * 3];
int len_c = base_len + len_t;
for(int i = 1; i <= base_len; i++) concat[i] = base_concat[i];
for(int i = 1; i <= len_t; i++) concat[base_len + i] = test_str[i];
int L = 0, R = 0;
for(int i = 2; i <= len_c; i++) {
int R_i_1 = R - i + 1;
if(i <= R && z_safe[i - L + 1] < R_i_1) z_safe[i] = z_safe[i - L + 1];
else {
z_safe[i] = (R_i_1 > 0) ? R_i_1 : 0;
while(i + z_safe[i] <= len_c && concat[z_safe[i] + 1] == concat[i + z_safe[i]]) z_safe[i]++;
if(i + z_safe[i] - 1 > R) { L = i; R = i + z_safe[i] - 1; }
}
}
int res = 0;
for(int i = 1; i <= len_t; i++) {
int k = z_safe[base_len + i];
int rem = len_t - i + 1;
if(k < NN) {
if(k < rem && test_str[i + k] < s[k + 1]) res += rem;
else res += (k < rem ? k : rem);
} else {
res += (NN - 1 < rem ? NN - 1 : rem);
}
}
return res;
}
int main() {
cin >> N >> K >> s;
s = ' ' + s;
if(N == 1 && s[1] == '0') return cout << "Impossible\n", 0;
NN = N;
p = 0;
for(int i = 1; i <= NN; i++) {
if (s[i] == '0') p++;
else break;
}
precompute_z();
int ans = INF32;
int max_T = 11;
int max_S = 16;
for(int T = 0; T <= max_T; T++) {
N = NN + T;
for(int i = 1; i <= NN; i++) base_concat[base_len + T + i] = s[i];
int start_mask = (T == 0) ? 0 : 1;
int step_mask = (T == 0) ? 1 : 2;
for(int MASK = start_mask; MASK < (1 << T); MASK += step_mask) {
if(N >= ans) break;
for(int I = 1; I <= T; I++) {
base_concat[base_len + I] = ((MASK >> (I - 1)) & 1) ? '1' : '0';
}
auto dfs_suffix = [&](auto& self, int current_len) -> void {
int M = N + current_len;
if (M >= ans) return;
ll now = robust_evaluate(M);
if (now > K) return;
if (now == K) {
ans = M;
for(int i = 1; i <= ans; i++) SS[i] = base_concat[base_len + i];
return;
}
ll current_now = now;
int i = 1;
for(; i <= p && i + M < ans; i++) {
int k_zero = i;
int lcp = 0;
while(lcp < M && k_zero + lcp < NN && base_concat[base_len + lcp + 1] == s[k_zero + lcp + 1]) lcp++;
if(k_zero + lcp == NN) current_now += (NN - 1);
else if(lcp == M) current_now += (k_zero + M);
else {
if(base_concat[base_len + lcp + 1] < s[k_zero + lcp + 1]) current_now += (k_zero + M);
else current_now += (k_zero + lcp);
}
if(current_now > K) break;
if(current_now == K) {
int candidate_ans = i + M;
if (candidate_ans < ans) {
for(int j = 1; j <= i; j++) temp_t[j] = '0';
for(int j = 1; j <= M; j++) temp_t[i + j] = base_concat[base_len + j];
if (safe_check(temp_t, candidate_ans) == K) {
ans = candidate_ans;
for(int j = 1; j <= ans; j++) SS[j] = temp_t[j];
}
}
break;
}
}
if (i > p && current_now < K && i + M < ans) {
if (p == NN) {
ll diff = K - current_now;
ll D = NN - 1;
if (D > 0 && diff % D == 0) {
ll x = diff / D;
int candidate_ans = i + x - 1 + M;
if (candidate_ans < ans) {
for(int j = 1; j <= i + x - 1; j++) temp_t[j] = '0';
for(int j = 1; j <= M; j++) temp_t[i + x - 1 + j] = base_concat[base_len + j];
if (safe_check(temp_t, candidate_ans) == K) {
ans = candidate_ans;
for(int j = 1; j <= ans; j++) SS[j] = temp_t[j];
}
}
}
} else {
ll target = K - current_now;
ll L = 1, R = min((ll)K, (ll)ans);
ll best_x = -1;
while(L <= R) {
ll mid = L + (R - L) / 2;
ll sum = mid * M + mid * (2LL * i + mid - 1) / 2;
if (sum == target) { best_x = mid; break; }
else if (sum < target) L = mid + 1;
else R = mid - 1;
}
if (best_x != -1) {
int valid_i = i + best_x - 1;
int candidate_ans = valid_i + M;
if (candidate_ans < ans) {
for(int j = 1; j <= valid_i; j++) temp_t[j] = '0';
for(int j = 1; j <= M; j++) temp_t[valid_i + j] = base_concat[base_len + j];
if (safe_check(temp_t, candidate_ans) == K) {
ans = candidate_ans;
for(int j = 1; j <= ans; j++) SS[j] = temp_t[j];
}
}
}
}
}
if (T + current_len < max_S) {
base_concat[base_len + M + 1] = '0';
self(self, current_len + 1);
base_concat[base_len + M + 1] = '1';
self(self, current_len + 1);
}
};
dfs_suffix(dfs_suffix, 0);
}
}
if(ans >= INF32 - 114) cout << "Impossible\n";
else {
for(int i = 1; i <= ans; i++) cout << SS[i];
cout << '\n';
}
return 0;
}
} bool ED;
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T; cin >> Josh_zmf::Case >> T;
while(T--) Josh_zmf::main();
cerr << "Time: " << 1000. * clock() / CLOCKS_PER_SEC << "ms\n";
cerr << "Static Memory: " << abs(&ED - &ST) / 1024 / 1024 << "MB\n";
}后话：
OI 生涯可能就到此为止了，明年可能来打个娱乐赛吧，祝好！