【题解】牛客小白月赛15

#include<bits/stdc++.h> usingnamespacestd; constintN=110*1100; constintM=1024*1024+10; intnxt[N][26],fail[N],endd[N]; inttot=0; voidInsert(char*s) {     intlen=strlen(s);     intu=0;     for(inti=0; i<len; i++)     {         intid=s[i];         if(nxt[u][id]==0) nxt[u][id]=++tot;         u=nxt[u][id];     }     endd[u]=1; } intquery(char*s,intlen) {     intret=0,u=0;     for(inti=0; i<len; i++)     {         intt=nxt[u][s[i]];         u=t;         if(endd[t])         {             ret=i+1;             if(i+1==len)                 break;             if(nxt[t][s[i+1]]==0)                 u=0;         }         if(t==0)             break;     }     returnret; } charstr[1100][110],s[50*M]; intn,m; charsnew[100*M]; intp[100*M];   intminn(intx,inty) {     returnx>y?y:x; } intmaxn(intx,inty) {     returnx>y?x:y; } intinit(intlen) {     snew[0]='$',snew[1]='#';     intj=2;     for(inti=0; i<len; i++)     {         snew[j++]=s[i];         snew[j++]='#';     }     snew[j]='\0';     returnj; } intMan(intlen) {     intmax_len=-1,id,mx=0;     for(inti=1; i<len; i++)     {         if(i<mx)             p[i]=minn(p[2*id-i],mx-i);         else             p[i]=1;         while(snew[i-p[i]]==snew[i+p[i]])             p[i]++;         if(mx<i+p[i])             id=i,mx=i+p[i];         max_len=maxn(max_len,p[i]-1);     }     returnmax_len; }   intmain() {     scanf("%d%d",&n,&m);     for(inti=1; i<=n; i++)     {         scanf("%s",str[i]);         Insert(str[i]);     }     while(m--)     {         scanf("%s",s);         intlen=query(s,strlen(s));         intlen1=Man(init(len));         printf("%d %d\n",len,len1);     }     return0; } I题有毒吧，这道题1M究竟有多大，而且开了这么大才44MS       你确定没有错

标程都不给一个吗🙄

A如何排序，排序后如何配对，谢谢

f题很神奇，数据重配之后我代码一样的交上去一会儿AC,一会儿超时，完全看测评机心情

出题人能否给出标程捏

还有H中的l，r不保证l<r的哦

 出题人不仅A和H数据出锅，请问F题n,m<=500000，n根号能过？不仅能过，连n方的都给过了。做出的5人中只有我一人写的是n根号 

 先把能单独跳的算出来，再把（y+x>=s）的放在一起，按x排序。剩下的把x存进一个multiset里，然后把刚才那些从大到小贪一下，不能踩别人的就放进set里

b诡异的因数 暴力试除法，强力试除即可。 c表单 由于数据的问题读入的操作可能不是1,2 一个预处理，每次清0即可 d分数的运算 加减法通分，乘除法直接做。 g ftos的测试 ##题解 可以发现，只修改一个数，所以如果有解，这个数一定减少了的值， 又因为没有修改，所以我们可以在一开始预处理的值，然后我用的是分块， 对于这个差值我们进行块内排序处理，然后每次询问我可以块内二分upper和lower 然后在找到满足减少了的解的数量，对于边角料暴力就OK了 然后我们发现找到的这个数量有两种情况： ###情况一 这个数量=0，即无解 这好办，输出"Error" ###情况二 数量>0，有可能有唯一解，也有可能有多个解，如 因为比较小，所以我们桶排+块内二分判断头尾的是否相同。 如果做出来这些解的都是相同的输出"pass" 否则输出"INF" 这样做至少还有桶排清零的大常数，但是在内还是能卡过去的。 ##关于数据 数据是随机的，但是为了不全是Error，我们手动修改了数据。 ##其他解法 线段树应该也是可以的，我们维护和，然后方法与分块差不多，时间复杂度 但是线段树代码太长了，本人懒得打（逃 如果有更好的解法敬请指出。 h 数据结构题 分块，块内排序二分找相同。很经典的题了。线段树也同样可以。 j 开挂 首先，我们发现 有没有觉得后面这个东西很熟?其实这个询问就是求区间的数两两相乘的和。 但是好像还是没法算啊！ 我们再观察这个东西，又可以发现 其实就是区间和的平方减掉区间平方和的。 对于区间加，线段树维护一下和与平方和就好了，时间复杂度小到爆炸(实际的话因为数据随机，后面个点每个点标程跑的不到，开都是出题人良心了)。 这个公式的来源其实就是 然后移项一下，提个式子，分解一下就是这道题了。