首页 > 代码库 > codechef 两题

codechef 两题

2024-07-14 13:56:21   216人阅读

前面做了这场比赛，感觉题目不错，放上来。

A题目：对于数组A[],求A[U]&A[V]的最大值，因为数据弱，很多人直接排序再俩俩比较就过了。

其实这道题类似百度之星资格赛第三题XOR SUM，不过他求得是XOR最大值，原理类似。。

B:KMP居然写搓了，后来一直改，题目放个链接好了：http://www.codechef.com/LTIME14/problems/TASHIFT。

我么可以对B字符串复制一下，然后再对A字符串求出NEXT数组，再匹配的过程中求出匹配最大长度时的位置，

刚开始我没想到这种做法，然后是先求出NEXT数组，然后二分，具体看代码。CODECHEF好像不能赛后交，代码的正确性。。

 1 T#include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set>10 #include<list>11 #define inf 0x3f3f3f12 typedef long long ll;13 using namespace std;14 char s[1234567];15 char ss[1234567];16 int next[1234567];17 int n;18 19 void kmp()20 {21     int k=-1,i=0;22     memset(next,0,sizeof(next));23     next[0]=-1;24     while (i<n)25     {26         if (k==-1||s[k]==s[i])27            next[++i]=++k;28         else k=next[k];29     }30 }31 32 int getkmp(int x)33 {34     int k=0,i=0;35     while (i<(2*n-1)&&k<x)36     {37         if (k==-1||ss[i]==s[k])38         {39             k++;i++;40         }41         else k=next[k];42     }43     if (k==x) return i-x;44     return -1;45 }46 47 48 int main()49 {50     scanf("%d",&n);51     scanf("%s%s",s,ss);52     kmp();53     int ans=0;54     for (int i=n;i<n+n-1;i++) ss[i]=ss[i-n];55     ss[n+n-1]=‘\n‘;56     int h=0,t=n;57 58     for (int o=0;o<40;o++)59      {60        int  mid=(h+t)/2;61         if (getkmp(mid)!=-1) {h=mid;ans=getkmp(mid);}62         else t=mid;63      }64  printf("%d\n",ans);65  return 0;66 }
View Code

另外附百度之星XOR SUM的01字典树代码：

 

 1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #include<math.h> 5 #include<string> 6 using namespace std; 7 #define N 3333333 8 int next[N][2],end[N]; 9 int pos;10 void add(int cur,int k) {11     next[pos][0]=next[pos][1]=0;12     end[pos]=0;13     next[cur][k]=pos++;14 }15 16 int cal(int x)17 {18     int cur=0;19     for (int i=30;i>=0;i--){20         int k=((1<<i)&x)?0:1;21         if (next[cur][k]) cur=next[cur][k];22         else cur=next[cur][1-k];23     }24     return end[cur];25 }26 27 int main()28 {29     int T;30     scanf("%d",&T);31     for (int o=1;o<=T;o++)32     {33         int n,m;34         scanf("%d%d",&n,&m);35         pos=1;36         memset(next[0],0,sizeof(next[0]));37         for (int i=0;i<n;i++) {38             int x;39             scanf("%d",&x);40             int cur=0;41             for (int j=30;j>=0;j--)42             {43                 int  k=0;44                 if ((1<<j)&x) k=1;45                 if (next[cur][k]==0) add(cur,k);46                 cur=next[cur][k];47             }48             end[cur]=x;49         }50         printf("Case #%d:\n",o);51         for (int i=0;i<m;i++){52           int x;53           scanf("%d",&x);54           int ans=cal(x);55           printf("%d\n",ans);56         }57     }58     return 0;59 }
View Code

 


联系
我们