首页 > 其他分享 >牛牛的构造

牛牛的构造

时间:2023-01-07 14:01:15浏览次数:64  
标签:牛牛 构造 add hline array &-

牛牛的构造

链接:https://ac.nowcoder.com/acm/contest/49888/E
来源:牛客网

题意:

构造一个长度为 n 的排列,使得这个排列恰好存在 k 个二元组 [i, j] ,满足 1 ≤ i < j ≤ n && ai − aj​ = \(2 ^ x\) (x∈N)
如果不存在一个数组满足条件,输出 -1,如果存在多个数组都满足条件,输出任意一个数组即可

分析:

先考虑不能构造的情况:
对较小的数考虑:
n = 5 时,排列中所有可能的数对:

\[\begin{array}{|c|c|c|} \hline 5&->&1\\ \hline 5&->&3\\ \hline 5&->&4\\ \hline 4&->&2\\ \hline 4&->&3\\ \hline 3&->&1\\ \hline 3&->&2\\ \hline 2&->&1\\ \hline \end{array} \]

n = 6 时,排列中所有可能的数对:

\[\begin{array}{|c|c|c|} \hline 6&->&2\\ \hline 6&->&4\\ \hline 6&->&5\\ \hline 5&->&1\\ \hline 5&->&3\\ \hline 5&->&4\\ \hline 4&->&2\\ \hline 4&->&3\\ \hline 3&->&1\\ \hline 3&->&2\\ \hline 2&->&1\\ \hline \end{array} \]

n == 9时,排列中所有可能的数对:

\[\begin{array}{|c|c|c|} \hline 9&->&1\\ \hline 9&->&5\\ \hline 9&->&7\\ \hline 9&->&8\\ \hline 8&->&4\\ \hline 8&->&6\\ \hline 8&->&7\\ \hline 7&->&3\\ \hline 7&->&5\\ \hline 7&->&6\\ \hline ...&...&...\\ \hline \end{array} \]

可以发现只有当 n 取到 \(2 ^ k + 1\) 时,才会对数对的数量贡献值改变,由此计算每个 i 贡献值为:
add[i] = $\lfloor $log2(i - 1) \(\rfloor\) + 1
相加之后即为 n 个数能够造出的最多的满足条件的个数,大于直接"NO"
对与能构造出的情况,由于 i 的贡献值范围为 [1, add[n]],所以用类似于整数拼凑的方法必能选出若干个数递减放置得到答案,对于没有被选择的数,在最后递增输出就不会对答案产生影响

void solve()
{
    int sum = 0;
    cin >> n >> k;
    for (int i = 2; i <= n; i++)
    {
        add[i] = floor(log2(i - 1)) + 1;
        sum += add[i];
    }

    if (sum < k)
        cout << "-1" << endl;
    else
    {
        for (int i = n; i >= 2; i--)
        {
            if (k >= add[i])
            {
                st[i] = true;
                cout << i << " ";
                k -= add[i];
            }
            if (k <= 0)
                break;
        }

        for (int i = 1; i <= n; i++)
        {
            if (!st[i])
                cout << i << " ";
        }
        cout << endl;
    }
}

标签:牛牛,构造,add,hline,array,&-
From: https://www.cnblogs.com/Aidan347/p/17032549.html

相关文章

  • 洁净工程洁净室的气密构造
    洁净工程洁净室的气密构造。洁净工程洁净室与相邻房间之间包括不同洁净度等级的洁净室之间,洁净室与非洁净室之间以及洁净室与室外环境之间,根据洁净室特性均应保持规定的......
  • 模型驱动设计的构造块(下)——DDD
    3.领域对象的生命周期每个对象都有生命周期,如下图所示。对象自创建后,可能会经历各种不同的状态,直至最终消亡——要么存档,要么删除。当然很多对象是简单的临时对象,仅......
  • c#的构造函数及构造函数的调用
    C#构造函数的特性一、什么是C#构造函数?Construct,Function   C#构造函数是一种特殊的成员函数,它主要用于为对象分配存储空间,对数据成员进行初始化.   C#构造......
  • canvas德卡斯特里奥算法构造贝塞尔曲线可视化实现
    前言在现代js教程中看到通过德卡斯特里奥算法构造贝塞尔曲线的demo,觉得很有意思,尝试自己写一下目标效果如下吐槽一下,我看到文章底部才发现原来这里的demo是svg做的开......
  • CC6 牛牛的排序
    描述牛牛试图给一个长度为n整数数组排序,即实现一个voidsort(int*array,intn)输入描述:第一行输入一个正整数n,表示数组长度。第二行输入n个正整数,表示数组中每......
  • 析构函数 和 构造函数 和 base使用
    classA//基类First{~A()//析构函数{Console.WriteLine("~A()析构函数");}publicA(){......
  • C++11:移动构造函数
    1.拷贝构造函数中的深拷贝问题在C++98/03标准中,如果想用其它对象初始化一个同类的新对象,只能借助类中的拷贝构造函数。拷贝构造函数的实现原理很简单,就是为新对象复制......
  • C++:拷贝构造函数
    1.拷贝和拷贝构造函数拷贝和复制是一个意思,对应的英文单词都是copy。对于计算机来说,拷贝是指用一份原有的、已经存在的数据创建出一份新的数据,最终的结果是多了一份相同......
  • 勇敢牛牛向前冲——云开发组 二等奖
    江西师范大学  勇敢牛牛向前冲荣获2022年第五届“航天宏图&华为云杯”PIE软件开发者大赛云开发组二等奖 作品名称:基于PIE-Engine的寻乌县柑橘果园遥感监测系统团......
  • java中私有构造函数的作用
    使用私有构造函数强化singleton属性。方法一:公有的静态成员是一个final域,成员的声明很清楚的表达了这个类是一个singleton。publicclassElvis{publicstatic......