HihoCoder 1873 Frog and Portal（二进制拆分）

最新推荐文章于 2020-10-03 14:49:34 发布

ToRe.

最新推荐文章于 2020-10-03 14:49:34 发布

阅读量662

点赞数

分类专栏： # 思路文章标签：思路二进制

本文链接：https://blog.csdn.net/j2_o2/article/details/84074201

版权

思路专栏收录该内容

11 篇文章

订阅专栏

探讨了青蛙从0点跳跃至200点的路径计数问题，通过放置传送门改变路径选择，利用二进制拆分与自环概念，构造特定算法解决路径计数。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目链接

题意

一只青蛙想从0点到200点，在1-199上每点存在荷叶，荷叶上可以放置传送门，从某点立即瞬移到另一个点，一个点只有一个传送门。青蛙每次可以跳一步或者两步。
问从0到200存在m个方案数的传送门放置方法

思路

首先无传送门显然方案数是斐波那契数列

点	1	2	3	4	5	6	7	8	9
方案数	1	2	3	5	8	13	21	34	54
3点传送门指向本身	1	2	×	2	2	4	6	10	16
3和7指向本身	1	2	×	2	2	4	×	4	4

所以可以将方案数进行二进制拆分。
需要构造传送门让某点选和自环分别代表二进制两种情况。
下面给出构造方法，√代表此点选或不选，×代表必须不选

√选代表连到199，不选代表自环

点	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
方案数	√（0位）	1	1	2	×	2	√（1位）	2	2	4	×	4	√（2位）	4	4	8

最多大概只需要31*6+1，最后让197和198自环保证无法从其他地方到200，如此构造即可，详见代码。

代码

#include <stdio.h>

#define ll long long

int main()
{
    ll n;
    while(~scanf("%lld",&n))
    {
        printf("66\n198 198\n197 197\n");
        for(ll i = 0; i < 32; ++i)
        {
            printf("%lld %lld\n",6*i+5,6*i+5);
            if(n&(1<<i)) printf("%lld %lld\n",6*i+1,199);
            else printf("%lld %lld\n",6*i+1, 6*i+1);
        }
    }
    return 0;
}