【Codeforces Round 438 A B C D 四个题】

题目所在比赛的地址在这里呀

A. Bark to Unlock

·述大意：

输入一个目标串。然后输入n(1<=n<=100)个串,询问是否可以通过这些串收尾相接或者它本身拼出目标串(比如ab rt 可拼出ab rt br ta),输出就是 Yes或者No。提到的串长度都为2。

·分析:

直接按照题目说的，一种是自己本身等于目标串，一种是两个串拼出了目标串所以前者O(n)后者O(n²),就没啦。

 #include<stdio.h>

 #define go(i,a,b) for(int i=a;i<=b;i++)

 int n;char c[],s[][];

 int main()

 {

     scanf("%s %d",c,&n);

     go(i,,n){scanf("%s",s[i]);if(s[i][]==c[]&&s[i][]==c[]){puts("YES");return ;}}

     go(i,,n)go(j,,n)if(s[i][]==c[]&&s[j][]==c[]){puts("YES");return ;}

     puts("NO");return ;

 }//Paul_Guderian

B. Race Against Time

皮盘WA了…

·述大意：

一个时钟,输入h,m,s,t₁,t₂表示当前的时间是h时m分s秒(当然是12小时制),t1表示主人公所在钟面的位置,t₂表示终点，此时时间静止。保证人和终点不会与指针重合。询问主人公是否可以在不经过任何指针的情况下到达t₂(逆时针顺时针均可)。(1≤h≤12,0≤m,s≤59,1≤t₁,t₂ ≤12,t₁≠t₂).输出yes或者no就可以了。t₁t₂的单位是小时。

·分析：

直接想想其实就是三个指针将钟面分成三部分,询问t₁t₂是否在同一块。首先根据小学知识我们先统一单位。为了精确我们统一成钟面60格为单位,这里不是指的具体时间，因为此时时间静止，我们只关注各个指针的位置。然后我们以12时刻的位置为起点,就可以将钟面拉成一条线，那么我们要做的就是看一看区间(设t1<t2)[t1,t2)有多少个指针就行了。如果指针数为0或者3,那么当然是Yes啦(3意味着可以走另一边到达)。

当然这道题HACK点就在区间的开闭上。为什么是左闭右开？因为题目中提到不重合关系，所以如果有一个输入的指针在t1,就表明它是在t1向前一丢丢处，比如时针就是因为分针走了一段所以移动了一丢丢,因此为左闭。右开就同理了，指针偏出了t2所以不用计算在内。

 #include<stdio.h>

 int h,m,s,t1,t2;

 int main()

 {

     scanf("%d%d%d%d%d",&h,&m,&s,&t1,&t2);

     (h*=)%=;(t1*=)%=;(t2*=)%=;t1>t2?t1^=t2^=t1^=t2:;

     puts(((t1<=h&&h<t2)+(t1<=m&&m<t2)+(t1<=s&&s<t2))%==?"YES":"NO");return ;

 }//Paul_Guderian

C. Qualification Rounds

·述大意：
输入n,k(1≤n ≤10⁵,1≤k ≤4), 表示n个题,k个队。接下来n行输入n个01串,第i行的01串,表示第i道题每个队是否做过，1表示做过，0表示没做过。询问是否存在一个题集(至少包含一个题，同一个题不能多选),使得每个队做过的题目数最不超过这个题集题目数的一半。如果存在输出YES否则NO。

·分析：

第一个遇到的问题一定是这样确定题集的题目个数。当然在比赛的时候没有足够的时间去推结论，所以就先胡乱地靠直觉丢出一个结论：如果存在符合要求的题集，那么一定可以有由一道题或者两道题构成。

基于上述调皮的结论，分开讨论。怎么才能满足一道题都可以呢？当然是这道题没有队伍做过(也就是0/1),这个判断就很简单。
对于两道题构成题集的情况如何处理？我们尝试枚举两道题,然后看看是否有一个队两道题都做过，如果是那么这个不合法，否则就合法了。但是有点小小失望地发现时间不能承受：O(n²)。因此考虑优化。

于是我们思考能否只枚举一道题，然后通过一个较快的方式找到满足条件的另一道题(当然如果没有就算了)。然后举例讨论：

归纳地说，要为当前枚举的这道题找到一个能够和它组成符合条件题集的题,那么他们状态的1必须在不同的位置上,也就是如果这题的某几位是1,那么另一道题这几位一定为0才行,当然其余位是没有限制的。但是想一想某几位为0,为1什么的可不可以用一个状态数组存下来，咋一看不行，其实由于这里的k非常小(k<=4),所以是可以枚举状态(集合)的。
因此,令s表示一个长度为k的二进制数(比如1010),num[s]表示满足在s的有1的位置上都是0的题目个数(比如0101)。那么我们每次枚举一个题(记状态为si)，就看一看num[s_i]是否大于零，如果大于0说明存在满足条件的题可以组成合法题集，直接输出就可以了。

最后呢就是预处理num数组,方法是对于每个读入的s_i,枚举子集s_i'然后进行num[s_i']++就可以啦。

 #include<stdio.h>

 #define go(i,a,b) for(int i=a;i<=b;i++)

 int n,k,a[],_,num[],S;

 int main()

 {

     scanf("%d%d",&n,&k);

     go(i,,n)

     {

         go(j,,k)scanf("%d",&_),(a[i]<<=)+=_;S=a[i]^((<<)-);

         for(int s=S;s;s=S&(s-))num[s]++;

         if(!a[i]){puts("YES");return ;}

     }

     go(i,,n)if(num[a[i]]){puts("YES");return ;};puts("NO");return ;

 }//Paul_Guderian

D. Huge Strings

·述大意：

输入n,m(1<=n,m<=100)表示有n个01串。接下来输入这n个串。然后输入m个操作,第i个操作输入a_i,b_i表示将编号为ai和bi的串拼接起来(ai在左边)得到编号为n+i的串，并且每次操作后输出最大的k值满足新和成的串的子串包含所有的长度为k的01串。注意,合成原料可以是以前合成出来的串,但是保证a_ib_i不同。读入的串总长度不超过100。

·分析：

似乎很难入手,因此就先想想暴力方法。

在没有合成的时候,怎样计算一个串满足条件的最大K值？最最最暴力的方法应该是从小到大枚举k,然后取出该串所有长度为k的子串,最后使用map维护去重记录个数,如果个数等于2^k就继续向大的k重复上述步骤,否则就说明K值最大为k-1。当然了,这里的思想就是找出所有子串,看是否含有所有长度为k的01串。类似的，反过来，也就是我们枚举每个长度为k的01串,看是否存在于该串的子串中,如果都在,那也是满足的。(两种暴力显得很美妙)

上面说了一大包可能会使你感到失落,原因是它仅适用于没有合成的时候,而且它们还是BruteForce。别灰心,好的思想总会发光！

然后我们思考两串拼接的情况。为了便于讨论，我们依旧借用上文暴力方法的一个思想——先固定k,然后看k是否满足。两个串拼起来，长度为k的串最多会增加多少种呢(最多指的是没有重复)？如图：

因此,每次增加最多会出现k个新串(就是左端点从p1移到a串末尾共k个串)，这照应了出题人的一句话：

……Once we obtain a new string as a concatenation of two old ones, the only new substrings can arise on the border of these two strings……

到目前为止还是很暴力,为啥我们总是说这些方法暴力？是什么最影响时间复杂度？我们列举一下，一下操作很耗时间：枚举k大小,枚举k长度子串,map映射子串/在串中寻找子串……我们发现其实时间复杂度是和k有很大关系的。但是到头来我们其实并不知道k的范围……

我们尝试弄出k的范围。

根据上文讨论的两种情况，可以得出(记住所有原串加起来最多100)：

①在所有的原串中,长度为k的子串在原串中最多100个。

②每次拼接最多增加k个新串,最多合并100次,则会增加串k*100个。

因此长度为k的串在最优情况下(即没有重复)则会大约有100+k*100个。

此时如果k是合法的,必须像题目说的那样,要包含所有长度为k的01串。

也就是：

100+k*100>=2^k

然后我们发现从小到大第一个不满足的是k=10。因此k的范围实际上是小于等于9的。

由于每次拼接我们发现只会在乎边界上长度k的区域,所以保存串的时候只需要保存长度为10的前后缀用于拼接时产生新串就可以了。

最终的做法是二分k值(k太小了,直接从小到大枚也都可以),然后我们记录当前合成的串的左右来源,并且此处记录拼接产生的新串(恩，这里你可以使用较快的unordered_map维护判重),然后沿着左右串继续分成左右串并重复上述操作，知道最后dfs到的串是输入的原串就停止。这样做可以缩去不必要的部分从而加速,由于dfs对于每个串访问一次，合并时长度为20(左右加起来),所有原串加起来不超过100,时间很稳定。

Wow!暴力变成了正解!

 #include<stdio.h>

 #include<iostream>

 #include<unordered_map>

 #define go(i,a,b) for(int i=a;i<=b;i++)

 using namespace std;

 const int N=;string a[N][],s,_;

 int n,m,l,r,lim,ans,L[N],R[N],len[N],cnt;

 bool vis[N];unordered_map<string,int>S;

 void dfs(int I,int k)

 {

     if(vis[I])return;vis[I]=;

     if(L[I]==){go(i,,len[I]-k)S[s=a[I][].substr(i,k)]==?S[s]++,cnt++:;return;}

     int Len=(_=a[L[I]][]+a[R[I]][]).length();

     go(i,,Len-k)S[s=_.substr(i,k)]==?S[s]++,cnt++:;

     dfs(L[I],k);dfs(R[I],k);

 }

 bool check(int k,int n)

 {

     go(i,,n+m)vis[i]=;S.clear();cnt=;

     dfs(n,k);return cnt==(<<k);

 }

 int main()

 {

     scanf("%d",&n);go(i,,n)

     {

         cin>>a[i][];a[i][]=a[i][];

         L[i]=R[i]=;len[i]=a[i][].length();

     }

     scanf("%d",&m);go(i,n+,n+m)

     {

         scanf("%d%d",L+i,R+i);

         a[i][]=a[L[i]][];

         if(len[L[i]]<=)a[i][]=a[i][]+a[R[i]][];

         if(a[i][].length()>=)a[i][]=a[i][].substr(,);

         a[i][]=a[R[i]][];

         if(len[R[i]]<=)a[i][]=a[L[i]][]+a[i][];

         if(a[i][].length()>=)a[i][]=a[i][].substr(a[i][].length()-,);

         go(l,,)if(!check(l,i)){printf("%d\n",l-);break;}

     }

     return ;

 }//Paul_Guderian

当然这道题不止这一种解法。但都是基于k<10这个结论。另外两种：

(一)奇妙法

在CF的提交记录上可以清晰看见有很多人使用了这个方法，时间仅需15ms,可以算是最快的方法了，但是其中关于字符串长度的截取的取值500的正确性如何证明性大米饼至今没有找到方法(某学长似乎出了一组数据WA了这个解法)。

 #include<string>

 #include<stdio.h>

 #include<iostream>

 #include<algorithm>

 #define go(i,a,b) for(int i=a;i<=b;i++)

 using namespace std;const int N=;

 string c[N],s;int ans[N],n,m;

 int Brute_Force()

 {

     go(i,,)go(k,,<<i)

     {

         s="";go(j,,i-)(<<j)&k?s+='':s+='';

         if(c[n].find(s)==-)return i-;

     }

 }

 int main()

 {

     ios::sync_with_stdio();

     cin>>n;go(i,,n)cin>>c[i],ans[i]=;

     cin>>m;while(m--)

     {

         int a,b;cin>>a>>b;c[++n]=c[a]+c[b];

         if(c[n].size()>)c[n]=c[n].substr(,)+c[n].substr(c[n].size()-,);

         ans[n]=max(Brute_Force(),max(ans[a],ans[b]));cout<<ans[n]<<endl;

     }

     return ;

 }//Paul_Guderian

【大米饼代码】

(二)官方题解

由于k很小,可以直接使用数组或者bitset维护当前串含有的子串的状态,两串合并时一同合并状态即可完成转移。关于如何同时维护每种长度的串是否出现时bitset有一些构造技巧(in the code)。

 #include<bits/stdc++.h>

 #define go(i,a,b) for(int i=a;i<=b;i++)

 #define ro(i,a,b) for(int i=a;i>=b;i--)

 using namespace std;const int N=,lim=;

 struct C{int len;string L,R;bitset<>vis;}s[N];

 string S;int st[N],n,Add,m,a,b;

 int main()

 {

     st[]=;go(i,,)st[i]=st[i-]+(<<(i-));

     scanf("%d",&n);

     go(i,,n){cin>>S;s[i].len=S.length();s[i].vis.reset();

     go(j,,s[i].len-){Add=;

     go(k,j,s[i].len-){if(k>=j+lim)break;Add=(Add*)+S[k]-'';

     s[i].vis.set(st[k-j+]+Add);}}

     if(s[i].len>lim)s[i].L=S.substr(,lim),s[i].R=S.substr(s[i].len-lim),s[i].len=lim;

     else s[i].L=s[i].R=S;}

     scanf("%d",&m);

     go(i,n+,n+m)

     {

         cin>>a>>b;S=s[a].R+s[b].L;s[i].len=s[a].len+s[b].len;s[i].vis=s[a].vis|s[b].vis;

         go(j,,(int)S.size()-){Add=;

         go(k,j,s[i].len-){if(k>=j+lim)break;Add=(Add*)+S[k]-'';s[i].vis.set(st[k-j+]+Add);}}

         if(s[i].len>lim)

         {

             if(s[a].len<lim)s[i].L=S.substr(,lim);else s[i].L=s[a].L;

             if(s[b].len<lim)s[i].R=S.substr((int)S.size()-lim);else s[i].R=s[b].R;

             s[i].len=lim;

         }

         else s[i].L=s[i].R=S;

         int res=;

         ro(k,lim-,)

         {

             int flag=;

             go(j,st[k],st[k]+(<<k)-)flag&=s[i].vis[j];

             if(flag){res=k;break;}

         }

         cout<<res<<endl;

     }

     return ;

 }//Paul_Guderian

【大米饼代码】

Life's a little bit messy. We all make mistakes. No matter what type of animal you are, change starts with you.————Judy·Hopps

巴特西

【Codeforces Round 438 A B C D 四个题】

最新文章

热门文章