最難解的數學題，本周題解(9.12)

例題 POJ 1200 Crazy Search

解題思路: 將N個字符串分別轉換成數字 然后按照 NC進制轉換為 10進制

然后開一個標記數組進行標記(判定唯一性) 這樣大大縮短了 時間
1600萬-- 26個小寫字母組合 再怎么 也不會太多
但是 不知道 到底是怎么推出的公式來的 進制轉換為10進制(很神奇~~)

AC代碼如下:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string.h>
#include<set>
using namespace std;
const int maxn=16000006;
char a[maxn];
bool hash[maxn];
int num[205];
int main() 
{int n,m;while(~scanf("%d%d",&n,&m)){memset(num,0,sizeof(num));memset(hash,0,sizeof(hash));scanf("%s",a);int len=strlen(a);int cnt=0;for(int i=0;i<len;i++)if(!num[a[i]])num[a[i]]=cnt++;int ans=0;for(int i=0;i<=len-n;i++){int sum=0;for(int j=i;j<=i+n-1;j++)sum=sum*m+num[a[j]];if(!hash[sum]){ans++;hash[sum]=1;}}cout<<ans<<endl;}return 0;
}

例題 POJ 1961 Period

解題思路: 就是kmp里的求next數組 然后依次掃一遍看是否出現循環節

AC代碼如下:

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1000000+10;
int next[maxn];
string str;
int main()
{int n;int ans=0;while(cin>>n&&n){ans++;cin>>str;next[0]=next[1]=0;for(int i=1;i<n;i++){int j=next[i];while(j&&str[i]!=str[j])j=next[j];next[i+1]=(str[i]==str[j])?j+1:0;}cout<<"Test case #"<<ans<<endl;for(int i=2;i<=n;i++){int len=i-next[i];if(next[i]>0&&!(i%len))cout<<i<<" "<<i/len<<endl;}cout<<endl;}return 0;
}