程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4814 Golden Radio Base

HDU 4814 Golden Radio Base

編輯：C++入門知識

HDU 4814 Golden Radio Base

很顯然是個進制轉換的題，根據題意有a^2 = a + 1 -> a^n = a^(n-1) + a^(n-2)，這樣就能消除兩個連續1。

另，a^3 = a^2 + 1 = 2*a+2 = 2*(a+1) = 2*a。這樣就可以將悉數轉化為01。

10^9大約是2^30,所以總長度不超高150，直接模擬就好了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#pragma comment(linker, "/STACK:1024000000");
#define EPS (1e-6)
#define LL long long
#define ULL unsigned long long
#define _LL __int64
#define INF 0x3f3f3f3f
#define Mod 1000000007
#define Seed 31

using namespace std;

ULL hash[100010];
ULL K;

char s[100010];

map ma;

int main()
{
    int n,m,l,i,j;

    while(scanf("%d %d",&m,&l) != EOF)
    {
        scanf("%s",s);

        for(n = strlen(s), i = n-1 ,hash[n] = 0;i >= 0; --i)
            hash[i] = hash[i+1]*Seed + (s[i]-'a'+1);
        for(K = Seed,i = 2;i <= l; ++i)
            K *= Seed;
//        for(i = 0;i < n-l; ++i)
//            printf("i = %d hash = %I64u\n",i,hash[i]-hash[i+l]*K[l]);
        ULL tmp;
        int anw = 0;
        for(i = 0;i < l && m*l+i < n; ++i)
        {
            ma.clear();

            for(j = i;j < m*l+i;j += l)
                ma[hash[j] - hash[j+l]*K]++;

            if(ma.size() == m)
                anw++;

            for(j = m*l+i;j+l <= n; j += l)
            {
                ma[hash[j-m*l]-hash[j-m*l+l]*K]--;
                if(ma[hash[j-m*l]-hash[j-m*l+l]*K] == 0)
                    ma.erase(hash[j-m*l]-hash[j-m*l+l]*K);

                ma[hash[j] - hash[j+l]*K]++;

                if(ma.size() == m)
                    anw++;
            }
        }
        printf("%d\n",anw);
    }

    return 0;
}

上一頁:UVA10519 - !! Really Strange !!(數論+高精度)
下一頁:[數據結構]線段樹

C++入門知識

LeetCode 58 Length of Last Word（最後單詞的長度）

LeetCode 58 Length of Last Wor

Windows API 九九乘法表 [未完待續]

了解程度：目前為止還只是找到了可以添加邏輯代碼的地方

微軟等數據結構與算法面試100題第三題

第三題題目：輸入一個整型數組，數組裡面有正數也有負

c++簡單的分形

BZOJ 2648(SJY擺棋子-KD_Tree)

BZOJ 2648(SJY擺棋子-KD_Tree) &n

LeetCode_Valid Sudoku

LeetCode_Valid Sudoku 一.題目 V