题目所在比赛的地址在这里呀
A. Bark to Unlock
·述大意：
输入一个目标串。然后输入n(1<=n<=100)个串,询问是否可以通过这些串收尾相接或者它本身拼出目标串(比如ab rt 可拼出ab rt br ta),输出就是 Yes或者No。提到的串长度都为2。
·分析:
直接按照题目说的，一种是自己本身等于目标串，一种是两个串拼出了目标串所以前者O(n)后者O(n2),就没啦。
#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,t1,t2表示当前的时间是h时m分s秒(当然是12小时制),t1表示主人公所在钟面的位置,t2表示终点，此时时间静止。保证人和终点不会与指针重合。询问主人公是否可以在不经过任何指针的情况下到达t2(逆时针顺时针均可)。(1≤h≤12,0≤m,s≤59,1≤t1,t2 ≤12,t1≠t2).输出yes或者no就可以了。t1t2的单位是小时。
·分析：
直接想想其实就是三个指针将钟面分成三部分,询问t1t2是否在同一块。首先根据小学知识我们先统一单位。为了精确我们统一成钟面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 ≤105,1≤k ≤4), 表示n个题,k个队。接下来n行输入n个01串,第i行的01串,表示第i道题每个队是否做过，1表示做过，0表示没做过。询问是否存在一个题集(至少包含一个题，同一个题不能多选),使得每个队做过的题目数最不超过这个题集题目数的一半。如果存在输出YES否则NO。
·分析：
第一个遇到的问题一定是这样确定题集的题目个数。当然在比赛的时候没有足够的时间去推结论，所以就先胡乱地靠直觉丢出一个结论：如果存在符合要求的题集，那么一定可以有由一道题或者两道题构成。
基于上述调皮的结论，分开讨论。怎么才能满足一道题都可以呢？当然是这道题没有队伍做过(也就是0/1),这个判断就很简单。
对于两道题构成题集的情况如何处理？我们尝试枚举两道题,然后看看是否有一个队两道题都做过，如果是那么这个不合法，否则就合法了。但是有点小小失望地发现时间不能承受：O(n2)。因此考虑优化。
于是我们思考能否只枚举一道题，然后通过一个较快的方式找到满足条件的另一道题(当然如果没有就算了)。然后举例讨论：
归纳地说，要为当前枚举的这道题找到一个能够和它组成符合条件题集的题,那么他们状态的1必须在不同的位置上,也就是如果这题的某几位是1,那么另一道题这几位一定为0才行,当然其余位是没有限制的。但是想一想某几位为0,为1什么的可不可以用一个状态数组存下来，咋一看不行，其实由于这里的k非常小(k<=4),所以是可以枚举状态(集合)的。
因此,令s表示一个长度为k的二进制数(比如1010),num[s]表示满足在s的有1的位置上都是0的题目个数(比如0101)。那么我们每次枚举一个题(记状态为si)，就看一看num[si]是否大于零，如果大于0说明存在满足条件的题可以组成合法题集，直接输出就可以了。
最后呢就是预处理num数组,方法是对于每个读入的si,枚举子集si'然后进行num[si']++就可以啦。
#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个操作输入ai,bi表示将编号为ai和bi的串拼接起来(ai在左边)得到编号为n+i的串，并且每次操作后输出最大的k值满足新和成的串的子串包含所有的长度为k的01串。注意,合成原料可以是以前合成出来的串,但是保证aibi不同。读入的串总长度不超过100。
·分析：
似乎很难入手,因此就先想想暴力方法。
在没有合成的时候,怎样计算一个串满足条件的最大K值？最最最暴力的方法应该是从小到大枚举k,然后取出该串所有长度为k的子串,最后使用map维护去重记录个数,如果个数等于2k就继续向大的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>=2k
然后我们发现从小到大第一个不满足的是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