CF148C题解

ncwzdlsd · 2023-11-02 17:33:24 · 题解

要构造一个长度为 n 的数列，满足有 a 个数满足比它前面的所有数都大（\texttt{Oh}），有 b 个数满足比它前面的所有数的和都大（\texttt{Wow}）。

其中 a,b\leq 15,t\leq 50000。

先考虑如何满足 \texttt{Wow} 性质。由于上面的数据范围，一个公比为 2 的等比数列满足条件（等比数列求和公式 s_n=\dfrac{a_1(1-q^n)}{1-q}）。

然后再考虑 \texttt{Oh} 性质。在上面的基础上不断累加即可。

剩下的位全填 1。

对于无解的情况，当 n=a-1 且 a\neq 0 且 b=0 时无解，因为此时序列中会有数满足性质 b（即第二个数）。

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

int main()
{
    int n,a,b;cin>>n>>a>>b;
    if(n==1) cout<<1,exit(0);
    if(a==n-1) cout<<-1,exit(0);
    int s=n-a-b;
    if(!b)
    {
        for(int i=1;i<=s;i++) cout<<"1 ";
        for(int i=1;i<=a;i++) cout<<(s++)<<' ';
    }
    else
    {
        int t=1;cout<<t<<' ';
        for(int i=1;i<=b;i++) t+=t,cout<<t<<' ';
        for(int i=1;i<=a;i++) t++,cout<<t<<' ';
        for(int i=1;i<s;i++) cout<<1<<' ';
    }
    return 0;
}