学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1381

这个题目好像没给n和nc的范围，所以开始用hash有点纠结，不过这个题目还是用纯hash的方法做出来了，没想到还能这么快 15ms

因为数据量比较大，所以hash要想速度很快的话就一定要找到一个计算出hash函数的较快方法，我是按照nc+1进制来的，每次计算新

的hash值的时候就只、需要去除最高位，和加上最低位就能计算出来！

#include <iostream>
#include <string.h>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <stdio.h>
using namespace std;
#define maxn 16000010
bool hash[maxn];
int go[100];
char str[maxn];
int n,nc;
int main()
{
    int i,j,k,t;
    int len,ans,in;
    scanf("%d",&t);
    while(t--)
    {
        in=1;
        memset(go,0,sizeof(go));
        scanf("%d%d",&n,&nc);
        memset(hash,true,sizeof(hash));
        scanf("%s",str);
        len=strlen(str);
        for(i=0;i<len;i++)
        if(go[str[i]-'0'+1]==0)
        go[str[i]-'0'+1]=in++;
        ans=0;
        k=0;
        if(len<n)
        {
            printf("0\n");
            continue;
        }
        for(i=0;i<n;i++)
        ans=ans*nc+go[str[i]-'0'+1];
        hash[ans]=false;
        k++;
       // cout<<in-1<<endl;
        for(i;i<len;i++)
        {
            ans=ans-(int)pow(nc,n-1)*(go[str[i-n]-'0'+1]);
            ans=ans*nc+go[str[i]-'0'+1];
           // cout<<ans<<endl;
            if(hash[ans]) hash[ans]=false,k++;
        }
        printf("%d\n",k);
    }
    return 0;
}

HDU 4662 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4662

这个题目就是计算i的个数，i的个数一定是2^k个，先计算出u和i的个数，然后依次用2^k去减，判断结果是否能被6整除

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
#define maxn 111000
char str[maxn];
bool is_ok(int num_i,int num_u)
{

    int count=num_i+num_u*3,i;
    long long ans;//printf("%d",count);
    if(!(count&(count-1)))
    return 1;
    i=0;
    for(i=0;i<63;i++)
    {
        ans=pow(2,i);
        if(ans>count && (ans-count)%6==0)
        return 1;
    }
    return 0;
}
int main()
{
    int t,i,j,k;
    bool flag;
    int num_u,num_i;
    scanf("%d",&t);
    while(t--)
    {
        flag=false;
        num_u=num_i=0;
        scanf("%s",str);
        if(str[0]!='M' || str[1]==0)
        {
            printf("No\n");
            continue;
        }
        for(i=1;str[i];i++)
        if(str[i]=='I')
        num_i++;
        else if(str[i]=='U')
        num_u++;
        else
        {
            flag=true;
        }
        if(flag)
        {
            printf("No\n");
            continue;
        }
        if(is_ok(num_i,num_u))
        printf("Yes\n");
        else
        printf("No\n");
    }
    return 0;
}