做题送分！（10分）！加油！这题简单！！！ - C语言论坛

第 2 楼

得分: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] );
}