这题是有迹可循的!下面从一个思考者的角度讲述解题方法。
首先这两条限制很奇怪,但感觉都是很强的性质。所以这道题光想入手都是比较难的,先考虑怎么入手。
第二条限制相对简单,先考虑第二条限制。我们注意到,如果一个串的数字全是 \(1\),显然可以满足限制一。那限制二我们考虑将一个 \(1\) 变成 \(0\) 达到。考虑变第一个 \(1\),发现有烦人的性质一,考虑把第 \(k\) 个 \(1\) 变成 \(0\),并将末尾变成 \(0\),这可以解决 \(2k\le n\) 的情况。
若 \(2k>n\) 怎么办?我们考虑找到一个恰当的位置塞下唯一的那个子串,但是我手玩了亿点点方案都没能解决,怎么办?这道题最厉害的地方来了,别忘了 \(n,k\) 奇偶性相同,而一共有 \(n-k+1\) 个位置可以塞下满足性质二的串,我们对前 \(n-k+1\) 个位置进行思考,我们发现,位置个数是奇数,我们把正中间的 \(1\) 变成 \(0\),其它位置不变,这样性质二就满足了。对于性质 \(1\),我们发现每隔 \(\frac{n-k}{2}\) 个 \(1\) 中塞一个 \(0\) 就能满足性质一,然后一个很优美的构造方法就这样想出来啦!
事实上,这道题我一共想了一小时,而真正有进展的只有寥寥几分钟,这种题虽然很巧妙,但还是希望这种题不要在正赛考场中出现。。
代码:
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++ i)
#define rrp(i, l, r) for (int i = r; i >= l; -- i)
#define pii pair <int, int>
#define eb emplace_back
#define id(x, y) m * ((x) - 1) + (y)
#define ls p << 1
#define rs ls | 1
using namespace std;
constexpr int N = 1e5 + 5;
constexpr double PI = acos (-1.0);
typedef long long ll;
typedef unsigned long long ull;
inline int rd () {
int x = 0, f = 1;
char ch = getchar ();
while (! isdigit (ch)) {
if (ch == '-') f = -1;
ch = getchar ();
}
while (isdigit (ch)) {
x = (x << 1) + (x << 3) + ch - 48;
ch = getchar ();
}
return x * f;
}
int n, k;
char s[N];
int32_t main () {
// freopen ("1.in", "r", stdin);
// freopen ("1.out", "w", stdout);
n = rd (), k = rd ();
int o = (n - k) / 2 + 1, i;
for (i = 1; i + o - 1 <= n; i += o) {
rep (j, 1, o - 1) putchar ('1');
putchar ('0');
}
for (; i <= n; ++ i) putchar ('1');
}
标签:限制,位置,substring,define,这道题,考虑,unique,minimal,性质
From: https://www.cnblogs.com/lalaouyehome/p/18509240