Question

这三题c语言关于acm方面的题目，求帮忙解答一下，谢谢哈！！





Answer 1

你这些题数据范围其实都可以改大的= =，现在这个范围就比较水了...

其实我第三题没有看清楚= =，太模糊了...

 

第一题可以字符串Hash，或者用个map什么的，然后求出每个连续的长度为m的子串，丢到hash里面去看出没出现过就好了。总共最多n个子串嘛...

第二题，n<=1000，那么n^2就可以过了，所以你可以先求一个前缀异或和，然后枚举左右端点L,R，然后[L,R]的异或和=s[R]^s[L-1]，然后枚举的复杂度是n^2，所以就可以了...

第三题看不太清楚，最好有个文本啥的...那我就先只答前面两题了...

如果还是没听懂，可以追问。

 

第一题代码：字符串hash的代码，其实说实话是可以逐位比较的。

所以这份代码感觉有点丑，你应该可以打出更好的：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
struct Node{
 char s[110];
}a[110];
int n,m,ans=0;
int rec[110];
char ch[110];
bool used[110];
const int mod=1423333;
bool cmp(const Node &A,const Node &B){
 return strcmp(A.s,B.s)<0;
}
int main(){
 int kase;
 
 scanf("%d",&kase);
 
 while(kase--){
  scanf("%d",&m);
  scanf("%s",ch);
  n=strlen(ch);
  memset(used,0,sizeof(used));
  
  for(int i=0;i<n-m;i++){
   ll cnt=0;//字符串hash，将原串转化成一个27进制的数字来判断
   for(int j=0;j<m;j++)
    cnt=(cnt*27+ch[i+j]-'a')%mod;
   rec[i]=cnt;
   for(int j=0;j<i;j++)//如果之前出现过，就把之前的屏蔽掉
    if(rec[j]==rec[i]) used[j]=true;
  }
  
  int t=0;
  for(int i=0;i<=n-m;i++)
   if(!used[i]){
    t++;
    memset(a[t].s,0,sizeof(a[t].s));
    for(int j=0;j<m;j++)//把需要输出的存起来
     a[t].s[j]=ch[i+j];
   }
  sort(a+1,a+t+1,cmp);//按字典序排序
  for(int i=1;i<=t;i++)
   puts(a[i].s);
  
  putchar('\n');
 }
 
 return 0;
}

第二题代码：这个就比较简单易懂了，也感觉优美一些。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,ans;
int a[1010],s[1010];
int main(){
 int kase;
 
 scanf("%d",&kase);
 
 while(kase--){
  scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  for(int i=1;i<=n;i++) s[i]=s[i-1]^a[i];
  
  int ans=0;
  for(int L=1;L<=n;L++)
   for(int R=L;R<=n;R++)
    ans=max(ans,s[R]^s[L-1]);
  printf("%d\n",ans);
 }
 
 return 0;
}