专栏首页用户6093955的专栏Less Coin Tosses(Gym - 102346L)【打表+找规律】

Less Coin Tosses(Gym - 102346L)【打表+找规律】

L - Less Coin Tosses Gym - 102346L

题目链接

算法

打表+找规律

时间复杂度O(logN)

1.题意说的是给定你n位的二进制串,除了成对的(就是指那些1的个数相同或0的个数相同的),那些不成对的数有几个。比如n为3时,可以有000,001,010,011,100,101,110,111这八种二进制数,其中001可以与010配对,011可以与110配对,剩余的无法再配对,所以最后输出4。

2.看要求的数的范围2<=N<=10^18,非常大,所以说不可能暴力去做,一定存在某种规律。

3.既然成对的就是指二进制串中1的个数相同,那么我们可以用组合数的知识来解决。即从n位数中挑m位为1,看这样的数有几个,若为偶数,则说明没有不成对的,否则说明有落单的,这时加1即可。总结得出下列公式:

\[\displaystyle \sum_{i=0}^n (C_{n}^{i}\%2) \]

4.公式有了,问题来了,n这么大怎么算。对于这种题,很大可能性说明存在某种规律,如何找到规律,就需要打表实现。可以根据下列代码来打表。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
/*打表*/
const int N = 1000;
ll c[N][N];
int n;
ll res[N];
void init()
{
    for(int i = 0; i < N;i ++)
        for(int j = 0; j <= i; j++)
        {
            if(!j) c[i][j] = 1;
            else
                c[i][j] = (c[i-1][j] + c[i-1][j-1]);
        }
}
int main()
{
    init();
    for(int i = 2; i < N; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            res[i] += (c[i][j] % 2);
        }
        cout << "res[" << i << "] = " << res[i] << endl;
    }
}

由于没有取余导致后面的数溢出变成负数了,不过没有关系,我们只需要看前面几个数就能找到规律。

看上面这张图,仔细观察颜色相同的下划线标注的位置。好像成2的倍数的数他们的结果相同。好像还有点什么,那么我们就把每个数拆分成二进制数,找到他们在输出中的位置,仔细观察。

将上图中二进制数对应的结果进行比对,再与二进制数本身的特征加以比较,发现最终的结果与n对应的二进制数中的1的个数有关。由此,得出了最终规律。

5.总结一下,规律为n对应的二进制数中1的个数k,答案为2^k

C++代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
/*打表
const int N = 1000;
ll c[N][N];
int n;
ll res[N];
void init()
{
    for(int i = 0; i < N;i ++)
        for(int j = 0; j <= i; j++)
        {
            if(!j) c[i][j] = 1;
            else
                c[i][j] = (c[i-1][j] + c[i-1][j-1]);
        }
}
int main()
{
    init();
    for(int i = 2; i < N; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            res[i] += (c[i][j] % 2);
        }
        cout << "res[" << i << "] = " << res[i] << endl;
    }
}
*/
ll n;
int main()
{
    cin >> n;
    ll res = 1;
    while(n)
    {
        if(n & 1) res <<= 1;
        n >>= 1;
    }
    cout << res ;
    return 0;
}

代码中求组合数的模板来源于yxc大佬的数学知识模板

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【改革春风吹满地 HDU - 2036 】【计算几何-----利用叉积计算多边形的面积】

    我们都知道计算三角形的面积时可以用两个邻边对应向量积(叉积)的绝对值的一半表示,那么同样,对于多边形,我们可以以多边形上的一个点为源点,作过该点并且过多边形其他...

    _DIY
  • 蓝桥杯突击复习准备——部分算法汇总

    当然,上面这个状态转移方程不适用于a数组长度较大的情况。比如AcWing896. 最长上升子序列 II (AC代码,思路在代码中)

    _DIY
  • 【Pet HDU - 4707 】【利用并查集找深度】

    _DIY
  • 这道上台阶的编程题你会不会?(递归和迭代思想)

    one保存最后走1步,two保存最后走2步。循环迭代就是不断修改这两个(one,two)变量的值。

    Wizey
  • 迅雷2019秋招后台开发编程题题解

    有红黑两种颜色的方块积木,红色代表正数A,黑色代表负数B。选出17块积木排成一排,使得任意相邻7块积木之和都小于0。如何挑选才能使17块积木之和最大,最大值是多...

    武培轩
  • BZOJ1898: [Zjoi2005]Swamp 沼泽鳄鱼(矩阵快速幂)

    attack
  • codevs4919 线段树练习4

     时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果 题目描述 Description 给你N个数,有两...

    attack
  • LeetCode 949 Largest Time for Given Digits

    Given an array of 4 digits, return the largest 24 hour time that can be made.

    Yano_nankai
  • HDU-5558-Alice's Classified Message

    ACM模版 描述 ? 题解 image.png 参考博客:Gatevin’s blog 代码 #include <iostream> #include <alg...

    f_zyj
  • P1147 连续自然数和

    题目描述 对一个给定的自然数M,求出所有的连续的自然数段,这些连续的自然数段中的全部数之和为M。 例子:1998+1999+2000+2001+2002 = 1...

    attack

扫码关注云+社区

领取腾讯云代金券