2022牛客多校6_A题

\begin{aligned} &题意概述: 给长为n的数组a，构造一个循环节为m的循环序列使得连续a[i]个数中至少出现一次i(1<=i<=n) \\ \end{aligned}

\sum_{i=1}^{n}\frac{1}{a[i]} <= \frac{1}{2} \\ \sum_{i=1}^{n}\frac{m}{a[i]/2} <= m \\

\begin{aligned} &我们定义d_i = 2^{x_i},\space x_i满足2^{x_i}<=a_i<=2^{x_i+1}，那么\hspace{10.57cm}\\ \end{aligned}

a[i]/2 <= d[i] \\ \sum_{i=1}^{n}\frac{m}{d[i]}<=\sum_{i=1}^{n}\frac{m}{a[i]/2} <= m \\

\begin{aligned} &上述不等式说明对长为m的数组，平均每d[i]个数出现一次i，需要的位置数不超过m。\hspace{5cm} \\ &于是我们考虑原问题的加强版: 每连续d[i]个数中必出现一次i。\\ &首先我们对于d[i]进行从小到大的重排，其对应要出现的数记为val[i],并取循环节m = d[n]。\\ &构造思路:对于每个i，我们找到第一个未占用的pos_i后，将所有的pos_i+k*d[i]<m置为val[i]即可。\\ &PS: 找到第一个未占用的pos_i后,我们可以保证pos_i+k*d[i]也未被占用。\\ &证明: 假设pos_i+k*d[i]已经被占用过，则存在j<i,h>=0满足:\\ \end{aligned}

pos_i+k*d[i] = pos_j+h*d[j] \\

\begin{aligned} &由于d[j]|d[i]， 那么pos_i-pos_j是d[j]的倍数。\hspace{12cm}\\ &由于j比i先取, pos_j<pos_i,从而存在r > 0, pos_i = pos_j + r * d[j]\\ &那么pos_i也应当被占用过，与pos_i未被占用矛盾。因此假设不成立。\\ \end{aligned}

\begin{aligned} &构造举例：假设d[3]=\{2,4,8\} \quad val[3]=\{1,2,3\} \hspace{10.8cm}\\ &\hspace{2cm}\_ \quad \_ \quad \_ \quad \_ \quad \_ \quad \_ \quad \_ \quad \_ \\ &\hspace{2cm}1 \quad \_ \quad 1 \quad \_ \quad 1 \quad \_ \quad 1 \quad \_ \\ &\hspace{2cm}1 \quad 2 \quad 1 \quad \_ \quad 1 \quad 2 \quad 1 \quad \_ \\ &\hspace{2cm}1 \quad 2 \quad 1 \quad 3 \quad 1 \quad 2 \quad 1 \quad \_ \\ &\hspace{2cm}1 \quad 2 \quad 1 \quad 3 \quad 1 \quad 2 \quad 1 \quad 1 \\ &PS:\_的位置对条件没有贡献，全部填上1即可\\ \end{aligned}

第一次写题解，求dalao们轻喷。最后附上代码：

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


const int maxn = 2e6 + 20;
int t, n;

struct node{
    int id;
    int val;
    bool operator < (const node& z) const {
        return val < z.val;
    }
}a[maxn];

int dn2(int x) {
    int ret = 1;
    for(;ret<=x;ret<<=1);
    return (ret>>1);
}

int ans[maxn];
set<int> s;

signed main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i].val;
        a[i].val = dn2(a[i].val);
        a[i].id = i;
    }
    sort(a+1, a+n+1);
    int m = a[n].val;
    for(int i = 0; i < m; ++i) s.insert(i);
    for(int i = 1; i <= n; ++i) {
        int st = *s.begin();
        for(int p = st; p < m; p += a[i].val) {
            assert(s.count(p));
            if(s.count(p)) {
                s.erase(p);
                ans[p] = a[i].id;
            }
        }
    }
    for(int p : s) {
        ans[p] = 1;
    }
    cout << m << '\n';
    for(int i = 0; i < m; ++i) cout << ans[i] << " \n"[i==m-1];
    return 0;
}