|
#2
rjsp2022-07-26 14:26
做题送分！（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] ); } |
题目描述
输入一个整数n，输出仅由0和1组成的长度为n的字符串，并且其中不含有三个连续的相同子串。仅需输出方案总数。
输入
一个整数，表示字符串长度n(n<=40)
输出
一个整数，表示所有满足条件的字符串的个数。
样例
输入复制
2
输出复制
4
来源
递归
加油
[此贴子已经被作者于2022-7-25 19:21编辑过]