danihao123's Blog

很有意思的思考题。

这道题通过特殊情况我们可以猜想，假设最近两个不同色块距离为[tex]x[/tex]（这是半闭半开序列长度），则答案为[tex]n-x+1[/tex]。然而事实就是如此。

代码：

/**************************************************************
    Problem: 3725
    User: danihao123
    Language: C++
    Result: Accepted
    Time:216 ms
    Memory:1796 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000001;
char buf[maxn];
int main(){
    int n;
    register int i,now;
    char last_s=0;
    scanf("%s",buf);
    n=strlen(buf);
    register int ans=n;
    for(i=0;i<n;i++){
        if(buf[i]!='*'){
            if(last_s){
                if(buf[i]!=last_s){
                    ans=min(ans,i-now);
                    last_s=buf[i];
                    now=i;
                }else{
                    now=i;
                }
            }else{
                last_s=buf[i];
                now=i;
            }
        }
    }
    printf("%d\n",n-ans+1);
    return 0;
}

这题应该注意到，斐波纳契函数增长速度很快，[tex]10^9[/tex]以下的斐波纳契函数值很少，所以可以打表。这样，问题就迎刃而解了。

代码：

/**************************************************************
    Problem: 3713
    User: danihao123
    Language: C++
    Result: Accepted
    Time:20 ms
    Memory:828 kb
****************************************************************/
 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int fib[46]={0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170};
bool check(int n){
    int m=sqrt(0.5+n);
    if(binary_search(fib,fib+46,n))
        return true;
    register int i;
    for(i=2;i<=m;i++){
        if(!(n%i) && binary_search(fib,fib+46,i)){
            if(binary_search(fib,fib+46,n/i))
                return true;
        }
    }
    return false;
}
int main(){
    int T,n;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        if(check(n))
            puts("TAK");
        else
            puts("NIE");
    }
    return 0;
}