一种构造法，居然过了？

vigza · 2023-11-06 00:56:05 · 题解

CF1355D

现在我们已知要构造一个长度为 n 的数组，且满足和为 S。要求找到一种构造方法，能使任何子串的和都不等于 K。

解法说明

观察

首先我们造一些样例，观察一下性质：

试图：

然后考虑它子串的可能获得的所有和。

很不幸，从 1 到 S 都覆盖了，所以这种构造不存在 K 满足题意。难道就不能构造出一种数列存在 K 吗？

再写一个试试：

然后考虑它子串的可能获得的所有和。

找 K 时，发现它没有 4，11，对比之前为啥这个构造是可以的？

发现因为再求子串和的时候，我们是对数列中的元素求所有组合情况，而数列一堆 1 会导致重复组合，导致产生子串和可能情况变少，而如果构造的每位数都不同，会很有可能导致 1 到 S 都被覆盖。

贪心

这时，我们便有一种贪心的猜想：让数列中出现的不同元素尽可能的少。所以能不能构造数列 \{1,1,1,1,...,S-(n-1)\}，使得它是所有数列中不同子串和的数量最少的，如果这个数列都不能找不到 K，是不是就能确定其他更具变化性的构造数列就更找不到 K 了？

值得顾虑的是，“\{1,1,1,1,...,S-(n-1)\}”等价于“子串和的可能数量最少”吗？

读者自证不难。

细化

推广开，不同元素只有两个，1 和 x=S-(n-1)，

通过组合，子串和覆盖的范围就会是 [1,n-1],[x,S]，那么是不是如果 x>n 的话，K 取 n 就能构造出来？

然后，居然过了？

Code

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, s;
    cin >> n >> s;
    int x = s - (n - 1);
    if (x > n) {
        cout << "YES" << endl;
        for (int i = 1;i <= n - 1;i++) cout << 1 << ' ';
        cout << x << endl << n;
        return;
    }
    cout << "NO";
}

int main() {
    // freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    int T = 1;
    while (T--) solve();
    return 0;
}

蟹蟹阅读~