hdu4642
由于题意的规定，对于右下角的方格，如果开始为1，那么Alice每次都会把1变成0，Bob都会把0变成1，因此只可能是Alice赢，同理，当刚开始时为0，那么Alice只会使他变成1，Bob会把它变成0，因此只会是Bob赢。因此题意的关键就在矩阵右下角的数字为1还是为0
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N = 105;
int a[N][N];
int main()
{
int t,n,m;
cin>>t;
while(t--)
{
cin>>n>>m;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
scanf("%d",&a[i][j]);
}
}
if(a[n][m])cout<<"Alice"<<endl;
else cout<<"Bob"<<endl;
}
return 0;
}
hdu4639
这个题开始想歪了，想着用Kmp来做，用了两个KMP来找hehe，后来发现了对于重叠的hehe，他是一个斐波拉切数列，可以预处理；同时对于不是重叠的hehe，直接上2^n次方，就这样这个题目一直在wa，其实这个题目没必要这么复杂，本身hehe作为模式串就只有4个字节，而且题意也明确地说明了字符串的大小只有10086，因此可以直接暴力匹配。
一下是两次KMP的代码，wa
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#define mod 10007
#define maxn 11000
using namespace std;
typedef long long lint;
char s[maxn];
char p[maxn];
int next[maxn];
int slen;//模式串长度
int plen;//文本串长度
void get_next1()
{
int i=0;
int j=-1;
next[0]=-1;
while(i<=plen)
{
if(j==-1||p[i]==p[j])
{
++i;
++j;
if(p[i]!=p[j])next[i]=j;
else next[i]=next[j];
}
else j=next[j];
}
}
int kmp1()
{
int i=0;
int j=0;
int count=0;
while(i<slen&&j<plen)
{
if(j==-1||p[j]==s[i])
++i,++j;
else
j=next[j];
if(j>=plen)
{
count++;
j=next[j];
}
}
return count;
}
void get_next2()
{
int i=0,j=-1;
next[0]=-1;
while(i<plen)
{
if(j==-1||p[i]==p[j])
{
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
}
int kmp2()
{
int i=0,j=0;
int num=0;
while(i<slen)
{
if(j==plen)
{
num++;
j=0;
}
if(j==-1||s[i]==p[j])
{
i++;
j++;
}
else
j=next[j];
}
if(j==plen)
num++;
return num;
}
int ans[maxn];
void init()
{
ans[0]=1;
ans[1]=2;
for(int i=2;i<maxn; i++)
{
ans[i]=ans[i-2]+ans[i-1];
ans[i]=ans[i]%mod;
}
}
lint power(lint a,lint b)
{
lint ans=1;
while(b)
{
if(b&1)
{
ans=ans*a%mod;
b--;
}
b=b/2;
a=a*a%mod;
}
return ans;
}
int main()
{
freopen("C:\\Users\\Administrator\\Desktop\\in.txt" , "r" , stdin);
int n;
strcpy(p,"hehe");
int sum1,sum2;
int kk=1;
scanf("%d",&n);
while(n--)
{
scanf("%s",s);
plen=4;
slen=strlen(s);
get_next1();
sum1=kmp1();
get_next2();
sum2=kmp2();
// cout<<"sum1="<<sum1<<" "<<"sum2="<<sum2<<endl;
init();
int k=2*sum2-sum1;
cout<<"Case "<<kk++<<": "<<(ans[sum1-k]*power(2,k)%mod)%mod<<endl;
}
return 0;
}
以下是强哥的AC代码：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define lint __int64
const lint mod=10007;
char s[10100];
short C[5044][2523];
int main()
{
int n,m;
for(int i=1,j;i<5044;++i)
{
C[i][0]=1;
for(j=1;j*2<=i;++j)C[i][j]=(C[i-1][min(j,i-j-1)]+C[i-1][min(j-1,i-j)])%mod;
}
int t,T=1;
while(cin>>t)
{
while(t--)
{
cin>>s;
int size=strlen(s);
lint ans=1,temp;
int z,j;
for(int i=0; i<size;)
{
z=0;
while(i<size)
{
if(s[i]=='h'&&s[i+1]=='e')++z,i+=2;
else
{
++i;
break;
}
}
if(z<2)continue;
temp=1;
for(int k=1; 2*k<=z; ++k)
{
temp=(((temp%mod)+(C[(z-k)][min(k,z-2*k)])))%mod;
}
ans=((ans%mod)*(temp%mod))%mod;
}
cout<<"Case "<<T++<<": "<<ans<<endl;
}
}
return 0;
}
我自己的代码：
/***********1008************************
直接在字符串中查找he的个数，那么hehe的个数就是he的个数-1，就有通过斐波那契数列来累计，通过乘法原理就可以得到答案（类似于分段求解）
*************************************/
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#define mod 10007
#define maxn 10100
using namespace std;
typedef long long lint;
int ans[maxn];
char str[maxn];
void init()
{
ans[0]=1;
ans[1]=2;
for(int i=2; i<maxn; i++)
{
ans[i]=ans[i-1]+ans[i-2];
ans[i]=ans[i]%mod;
}
}
int main()
{
freopen("C:\\Users\\Administrator\\Desktop\\in.txt" , "r" , stdin);
int t;
init();
int len;
int sum;
lint num;
cin>>t;
for(int i=1; i<=t; i++)
{
cin>>str;
len=strlen(str);
num=1;
for(int j=0; j<len;)
{
sum=0;
while(j<len)
{
if(str[j]=='h'&&str[j+1]=='e')++sum,j+=2;
else
{
++j;
break;
}
}
if(sum<2)continue;
num=num*ans[sum-1]%mod;
}
cout<<"Case "<<i<<": "<<num<<endl;
}
return 0;
}