首页 > 代码库 > HDU 4814 Golden Radio Base
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 <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <cmath> #include <stack> #include <map> #include <ctime> #include <iomanip> #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<ULL,int> 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; }
HDU 4814 Golden Radio Base
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。