| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1205 人关注过本帖
标题:做题送分!(10分)!加油!这题简单!!!
只看楼主 加入收藏
op123
Rank: 6Rank: 6
等 级:贵宾
威 望:21
帖 子:170
专家分:461
注 册:2022-6-4
结帖率:100%
收藏
已结贴  问题点数:10 回复次数:2 
做题送分!(10分)!加油!这题简单!!!
1824 - 【提高】01string
题目描述
输入一个整数n,输出仅由0和1组成的长度为n的字符串,并且其中不含有三个连续的相同子串。仅需输出方案总数。

输入
一个整数,表示字符串长度n(n<=40)
输出
一个整数,表示所有满足条件的字符串的个数。

样例
输入复制
2
输出复制
4

来源
递归

加油

[此贴子已经被作者于2022-7-25 19:21编辑过]

搜索更多相关主题的帖子: 输入 复制 输出 整数 字符串 
2022-07-25 17:34
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:10 
做题送分!(10分)!加油!这题简单!!!
那你来问个啥?
不懂的话,就虚心向大家求教。论坛上谁也不认识谁,不需要充大尾巴狼

先写个代码死算(C++语言)
程序代码:
#include <iostream>
#include <functional>
#include <chrono>
#include <format>

template<class F, class... Args>
constexpr std::invoke_result_t<F,Args...> elapsed_time( F&& f, Args&&... args ) noexcept(std::is_nothrow_invocable_v<F, Args...>)
{
    using namespace std::chrono;

    auto format_duration = []( const auto& dur ) noexcept(true)
    {
        auto ns = duration_cast<nanoseconds>(dur).count();
        std::cout << std::format( "elapsed time: {:02}:{:02}:{:02}.{:03}'{:03}'{:03}"
            , ns/3600000000000
            , ns%3600000000000/60000000000
            , ns%60000000000/1000000000
            , ns%1000000000/1000000
            , ns%1000000/1000
            , ns%1000/1 ) << " (" << dur << ")\n";
    };

    auto t_start = high_resolution_clock::now();
    if constexpr ( std::is_void_v<std::invoke_result_t<F,Args...>> )
    {
        std::invoke( std::forward<F>(f), std::forward<Args>(args)... );
        auto t_end = high_resolution_clock::now();
        format_duration( t_end-t_start );
    }
    else
    {
        auto result = std::invoke( std::forward<F>(f), std::forward<Args>(args)... );
        auto t_end = high_resolution_clock::now();
        format_duration( t_end-t_start );
        return result;
    }
}

//#include <limits>
#include <bit>
#include <cassert>
using namespace std;

constexpr unsigned long long foo( unsigned n ) noexcept(true)
{
    // 从高位到地位依次检查是否存在三个连续的相同序列
    auto triple = []( unsigned long long m, int fp=std::numeric_limits<int>::max() ) noexcept(true) -> int
    {
        const int bs = (int)std::bit_width( m ); // 此序列m的位数
        for( int i=std::min(bs-3,fp); i>=0; --i )
        {
            for( int w=1; w<=(bs-i)/3; ++w )
            {
                auto a = (m>>(i+0*w)) & ((1ull<<w)-1);
                auto b = (m>>(i+1*w)) & ((1ull<<w)-1);
                auto c = (m>>(i+2*w)) & ((1ull<<w)-1);
                if( a==b && b==c )
                    return i;
            }
        }
        return -1;
    };

    if( n == 0 )
        return 1;
    assert( n <= std::numeric_limits<unsigned long long>::digits );
    unsigned long long count = 0;
    for( unsigned long long i=(1ull<<(n-1)); ((i>>(n-1))&1)!=0; ++i ) // 因为“0变为1,1变为0,是两个等价的序列”,所以只取1开头的序列即可
    {
        int r = triple( i, (int)std::bit_width(i^(i-1))-1 );
        if( r == -1 )
            ++count;
        else
            i |= (1ull<<r)-1;
    }

    return 2*count;
}

constexpr void test( unsigned n ) noexcept(true)
{
    for( unsigned i=0; i<=n; ++i )
        cout << "foo(" << i << ") = " << foo(i) << '\n';
}

int main( void )
{
    elapsed_time( test, 40 );
}


输出结果
foo(0) = 1
foo(1) = 2
foo(2) = 4
foo(3) = 6
foo(4) = 10
foo(5) = 16
foo(6) = 24
foo(7) = 36
foo(8) = 56
foo(9) = 80
foo(10) = 118
foo(11) = 174
foo(12) = 254
foo(13) = 378
foo(14) = 554
foo(15) = 802
foo(16) = 1168
foo(17) = 1716
foo(18) = 2502
foo(19) = 3650
foo(20) = 5324
foo(21) = 7754
foo(22) = 11320
foo(23) = 16502
foo(24) = 24054
foo(25) = 35058
foo(26) = 51144
foo(27) = 74540
foo(28) = 108664
foo(29) = 158372
foo(30) = 230800
foo(31) = 336480
foo(32) = 490458
foo(33) = 714856
foo(34) = 1041910
foo(35) = 1518840
foo(36) = 2213868
foo(37) = 3226896
foo(38) = 4703372
foo(39) = 6855388
foo(40) = 9992596
elapsed time: 00:00:03.107'916'100 (3107916100ns)


看一下输出结果,没有什么规律,耗时3秒也有点儿长,于是代码改为(C语言):
程序代码:
#include <stdio.h>

int main( void )
{
    unsigned n;
    scanf( "%u", &n );

    const unsigned map[] = { 1, 2, 4, 6, 10, 16, 24, 36, 56, 80, 118, 174, 254, 378, 554, 802, 1168, 1716, 2502, 3650, 5324, 7754, 11320, 16502, 24054, 35058, 51144, 74540, 108664, 158372, 230800, 336480, 490458, 714856, 1041910, 1518840, 2213868, 3226896, 4703372, 6855388, 9992596 };
    printf( "%u\n", map[n] );
}
2022-07-26 14:26
op123
Rank: 6Rank: 6
等 级:贵宾
威 望:21
帖 子:170
专家分:461
注 册:2022-6-4
收藏
得分:0 
回复 2楼 rjsp
嗯......我会
2022-07-26 20:30
快速回复:做题送分!(10分)!加油!这题简单!!!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.019760 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved