牛客2020多校round2

本文主要是介绍牛客2020多校round2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

先更第二场。第一场题解看哭了，不太全。

题目链接

https://ac.nowcoder.com/acm/contest/5667#question

A.All with Pairs

题意

$f(s1,s2)$定义为一个最大的数i，$s_{1...i}=t_{|t|-i+1...|t|}$。就是s和t的最长公共前后缀长度。给n个字符串，完了求：$$\sum _{i=1}^n\sum _{j=1}^{n}f{\left(s_i,s_j\right)}^2(\mathrm{m}\mathrm{o}\mathrm{d}998244353)$$

吐槽

这道题其实并不太难。但是场上过得人不多，完了我们没看，我觉得看了是能想出来的。

题解

答题思路是可以线性的枚举每个前缀，看看有多少个后缀和这个前缀相同(记作$cn{t}_i$)，这个字符串哈希就能搞定。完了答案加上这个前缀长度的平方乘上后缀个数就完了。但是这样不一定保证这些配对中这个前缀长度最大。现在想知道这个前缀能匹配，且最长的时候有几个后缀。然后发现只要一个前缀能匹配上一个后缀，那么这个前缀的next也能匹配上后缀的后缀。所以next那个地方应该减掉这个前缀的匹配数(这些匹配数在next那里多算了，因为在那里next并不是最长的前后缀)。注意一个i值在$nex{t}_i$那里减一次，因为现在这个$cn{t}_i$已经包含了之后的多算的了。$nex{t}_i$和kmp里的略有不同。这里表示1~i的最长公共前后缀长度。

AC代码(next板子)

#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
int nx[1001000];
const int modd=998244353;
typedef unsigned long long ull;
map<ull,int> ma;
void getnx(unsigned int s1[],int n)
{nx[1]=0;for(int i=2,j=1;i<=n+1;)//next[i] 表示最大的x，满足s1[1 : x - 1] 是s1[1 : i - 1] 的后缀。即i失配该把i变成啥{nx[i]=j;while(j&&s1[j]!=s1[i])j=nx[j];j++,i++;}
}
char ss[1001000];
const int NN=1e5+10;
unsigned int* s[NN];
int lenth[NN];
int cnt[1001000];
const unsigned int jinzhi=31;
int main(){int n;scanf("%d\n",&n);for(int i=1;i<=n;i++){scanf("%s",ss+1);int len=strlen(ss+1);lenth[i]=len;s[i]=new unsigned int[len+2];for(int j=1;j<=len;j++){s[i][j]=ss[j]-'a'+1;}ull pow=1;ull ha=0;for(int j=len;j>=1;j--){ha=pow*s[i][j]+ha;pow*=jinzhi;ma[ha]+=1;}}long long ans=0;for(int i=1;i<=n;i++){int len=lenth[i];getnx(s[i],len);for(int j=1;j<=len;j++){//这里nxi变成1到i的最长公共前后缀长度。nx[j]=nx[j+1]-1;}ull ha=0;for(int j=1;j<=len;j++){ha=ha*jinzhi+s[i][j];cnt[j]=ma[ha];}for(int j=1;j<=len;j++){cnt[nx[j]]-=cnt[j];}for(int j=1;j<=len;j++){ans+=1ll*cnt[j]*j*j%modd;ans=ans%modd;}}printf("%lld\n",ans);return 0;
}

B.Boundary

题意

有一堆点。找到压到点最多的一定经过原点圆压住了多少点。

题解

这个思路绕个弯。直接枚举两点。反正过原点，三点确定圆。完了开个map啥的记录一下圆，往圆上加点就完了。或者统计同一个圆出现了几次。一个圆出现的次数应该是其上的点的不同点对数，即$$num=n(n-1)/2$$统计出num选最大值枚举n就行。然而我代码老wa，也不知道咋肥四。。。有会的大佬帮忙康康。

没AC代码

#include<cstdio>
#include<cstring>
#include<set>
#include<map>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int NN=1e4+10;
struct Circle
{double x,y;Circle(double a=0,double b=0):x(a),y(b){}void print(){printf("%lf %lf\n",x,y);}
}circ[2000010];
const double eps=0.00000001;
bool cmp_xy(Circle const &a,Circle const &b){if(a.x<b.x)return 1;else if(a.x==b.x&&a.y<b.y)return 1;return 0;
}//map<Circle,set<int>,cmp_xy> ma; 
double x[NN],y[NN];
int getres(long long kk){int i;for(i=2;1ll*i*(i-1)<kk;i++);return i;
}
double abss(double x){if(x<0)return -x;else return x;
}
int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lf%lf",x+i,y+i);}int ans=0;int cnt=0;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if((x[i]==0&&x[j]==0)||y[i]/x[i]==y[j]/x[j]){continue;}double k1,b1,k2,b2,xx,yy;if(y[i]==0){k2=-x[j]/y[j];b2=y[j]/2+x[j]*x[j]/2/y[i];xx=x[i]/2;yy=k2*xx+b2;}else if(y[j]==0){k1=-x[i]/y[i];b1=y[i]/2+x[i]*x[i]/2/y[i];xx=x[j]/2;yy=k1*xx+b1;}else{k1=-x[i]/y[i];b1=y[i]/2+x[i]*x[i]/2/y[i];k2=-x[j]/y[j];b2=y[j]/2+x[j]*x[j]/2/y[i];xx=(b2-b1)/(k1-k2);yy=k1*xx+b1;}circ[++cnt]=Circle(xx,yy);// neww.print();// for(set<int>::iterator k=ma[neww].begin();k!=ma[neww].end();++k){// 	printf("%d",*k);// }printf("\n");}}sort(circ+1,circ+cnt+1,cmp_xy);int num;for(int i=1;i<=cnt;i++){if(i>1&&abss(circ[i].x-circ[i-1].x)<=eps&&abss(circ[i].y-circ[i-1].y)<=eps)num++;else num=1;ans=max(ans,num);}printf("%d\n",getres(1ll*ans*2));return 0;
}

自闭了。

CD两题很水，不想写了

E.Exclusive OR

题意

给一个n长度序列，求出选出可重复的i个数的最大异或和。

吐槽

woc这题fwt数组要开long long。我没开wa到跳楼。比如所有2e5个数都是0，那异或卷积完就爆int了。要把每次卷积完的非零项统一成1，否则long long也爆。

题解

这个题关键是对秩的理解。数异或的秩和向量组的秩挺像的。构造线性基的方法其实本质是高斯消元。
注意秩的理解。每组数的异或秩的大小是这组数中线性无关数的最大个数。但是直接找出不好找，要用一直异或的办法找到线性基。这个题不需要构造线性基。秩是19，所以最多19个数一定能选出所有值。所以FWT跑19次。还有就是i次的答案一定不会小于i-2次的答案。所以大于19的次数就是离他最近的(最大的)，和它差2的整数倍次数的答案。

AC代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int N;
const int NN=2e5+10;
const int MM=(1<<19)+10;
long long a[MM],b[MM];
void FWT_or(long long *a,int opt)
{for(int i=1;i<N;i<<=1)for(int p=i<<1,j=0;j<N;j+=p)for(int k=0;k<i;++k)if(opt==1)a[i+j+k]=(a[j+k]+a[i+j+k]);else a[i+j+k]=(a[i+j+k]-a[j+k]);
}
void FWT_and(long long *a,int opt)
{for(int i=1;i<N;i<<=1)for(int p=i<<1,j=0;j<N;j+=p)for(int k=0;k<i;++k)if(opt==1)a[j+k]=(a[j+k]+a[i+j+k]);else a[j+k]=(a[j+k]-a[i+j+k]);
}
void FWT_xor(long long *a,int opt)
{for(int i=1;i<N;i<<=1)for(int p=i<<1,j=0;j<N;j+=p)for(int k=0;k<i;++k){long long X=a[j+k],Y=a[i+j+k];a[j+k]=(X+Y);a[i+j+k]=(X-Y);if(opt==-1)a[j+k]=1ll*a[j+k]/2,a[i+j+k]=1ll*a[i+j+k]/2;}
}
int ans[NN];
int main() {int n;scanf("%d",&n);int maxn=0;for(int i=1;i<=n;i++){int x;scanf("%d",&x);maxn=max(maxn,x);b[x]++;}for(N=1;N<maxn;N<<=1);N<<=1;a[0]=1;FWT_xor(b,1);for(int i=1;i<=19;i++){FWT_xor(a,1);for(int j=0;j<N;j++)a[j]=a[j]*b[j];FWT_xor(a,-1);for(int j=0;j<N;j++){if(a[j]>0){a[j]=1;ans[i]=j;}}}for(int i=1;i<=n;i++){if(i>19){if((i-19)%2){printf("%d ",ans[18]);}else{printf("%d ",ans[19]);}}else{printf("%d ",ans[i]);}}return 0;
}
/*
23
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 0 0 0 0 0
*/

G. Greater and Greater

吐槽

我发现多校给的时间空间限制真的玄学。这题开两个二维bitset会mle，开一个就不炸。也不知道为啥。开一个如果按照数据范围也是800m会爆炸的。服了。

AC代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<iostream>
using namespace std;
const int NN=150010;
const int MM=40001;
bitset<MM> s[MM];
int a[NN],b[MM],bb[MM];
int num1[NN];
bool cmp_b(int x,int y){return b[x]<b[y];
}
int so[MM];
int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",a+i);}for(int i=1;i<=m;i++){scanf("%d",b+i);bb[i]=b[i];so[i]=i;}sort(so+1,so+m+1,cmp_b);sort(bb+1,bb+m+1);for(int i=1;i<=m;i++){bitset <MM> I;I[so[i]-1]=1;s[i]=s[i-1]|I;}for(int i=1;i<=n;i++){num1[i]=upper_bound(bb+1,bb+m+1,a[i])-bb-1;}bitset<MM> cur;bitset<MM> lastcur;bitset<MM> Im;Im[m-1]=1;for(int i=0;i<m;i++)lastcur[i]=1;int ans=0;for(int i=n;i>=1;i--){cur=((lastcur>>1)|Im)&s[num1[i]];if(i<=n-m+1&&cur[0]==1){ans++;}lastcur=cur;}printf("%d\n",ans);return 0;
}

h.Happy Triangle

题解

这题标答是手动平衡树的。但是这个题离线，直接线段树维护区间最小差值就完了。然而我的代码只跑过了50%的数据就挖了。有大佬帮忙康康评论一下。。。我把每个可能是数都按顺序映射到线段树的基本数组中，删除也安排了唯一的点删除，感觉巨对。想破头也不知道咋就挖了。

没AC代码

#include<cstdio>
#include<cstring>
#include<set>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
multiset<int> se;
const int NN=2e5+10;
int minn[NN<<2];
int left[NN<<2];
int right[NN<<2];
int op[NN],v[NN];
const int oo=1e9+10;
map <int,int>ma;
void up(int cur){if(left[cur<<1]==-1)left[cur]=left[cur<<1|1];else left[cur]=left[cur<<1];if(right[cur<<1|1]==-1)right[cur]=right[cur<<1];else right[cur]=right[cur<<1|1];minn[cur]=min(minn[cur<<1],minn[cur<<1|1]);if(left[cur<<1|1]!=-1&&right[cur<<1]!=-1)minn[cur]=min(minn[cur],left[cur<<1|1]-right[cur<<1]);
}
void inser(int cur,int l,int r,int p,int val){if(l==r){left[cur]=val;right[cur]=val;minn[cur]=oo;return;}int mid=(l+r)>>1;if(p<=mid)inser(cur<<1,l,mid,p,val);else inser(cur<<1|1,mid+1,r,p,val);up(cur);
}
void eras(int cur,int l,int r,int p){if(l==r){left[cur]=-1;right[cur]=-1;minn[cur]=oo;return;}int mid=(l+r)>>1;if(p<=mid)eras(cur<<1,l,mid,p);else eras(cur<<1|1,mid+1,r,p);up(cur);
}
int ans=oo,lastr=-1;
void get_min(int cur,int l,int r,int x,int y){if(x<=l&&r<=y){ans=min(ans,minn[cur]);if(left[cur]!=-1&&lastr!=-1){ans=min(ans,left[cur]-lastr);}lastr=right[r];return;}int mid=(l+r)>>1;if(x<=mid)get_min(cur<<1,l,mid,x,y);if(y>mid) get_min(cur<<1|1,mid+1,r,x,y);
}
struct pp{int v,id;pp(int a=0,int b=0):v(a),id(b){};
} num[NN];
bool cmp_v(pp x,pp y){if(x.v<y.v)return 1;else if(x.v==y.v&&x.id<y.id)return 1;else return 0;
}
int a[NN];
int main(){int cnt=0;memset(left,-1,sizeof(left));memset(right,-1,sizeof(right));int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&op[i],&v[i]);if(op[i]==1){num[++cnt].v=v[i];num[cnt].id=i;}}if(cnt<=1){for(int i=1;i<=n;i++)printf("No\n");return 0;}sort(num+1,num+cnt+1,cmp_v);for(int i=1;i<=cnt;i++){a[num[i].id]=i;}for(int i=1;i<=n;i++){if(op[i]==2){pp neww;neww.id=0;neww.v=v[i];a[i]=lower_bound(num+1,num+cnt+1,neww,cmp_v)-num+ma[v[i]];ma[v[i]]=ma[v[i]]+1;}else if(op[i]==3){pp neww;neww.id=0;neww.v=v[i];a[i]=lower_bound(num+1,num+cnt+1,neww,cmp_v)-num;}}for(int i=1;i<=(cnt<<2);i++)minn[i]=oo;for(int i=1;i<=n;i++){if(op[i]==1){inser(1,1,cnt,a[i],v[i]);se.insert(v[i]);}else if(op[i]==2){eras(1,1,cnt,a[i]);se.erase(se.find(v[i]));//直接erase掉vi不对}else{set<int>::iterator pos=se.upper_bound(v[i]);int aa=-1,b=-1;if(pos!=se.begin()){--pos;b=*pos;if(pos!=se.begin()){--pos;aa=*pos;}}if(aa!=-1&&b!=-1&&aa+b>v[i]){printf("Yes\n");continue;}ans=oo;lastr=-1;get_min(1,1,cnt,max(1,a[i]-1),cnt);if(ans<v[i]){printf("Yes\n");}else{printf("No\n");}}}return 0;
}
/*
13
3 1
3 2
3 3
1 4
1 4
1 5
2 4
2 4
3 2
3 1
1 4
3 2
3 1
*/

吐槽

卧槽上面那个代码手误了。线段树查询right[cur]写成right[r]了。就这居然能跑过50%的数据。服了。想了好几天，茶饭不思的。还以为有情况没考虑到。。。

AC代码

#include<cstdio>
#include<cstring>
#include<set>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
multiset<long long> se;
const long long NN=400100;
long long minn[NN<<2];
long long left[NN<<2];
long long right[NN<<2];
long long op[NN],v[NN];
const long long oo=2e9+10;
map <long long,long long>ma;
void up(long long cur){if(left[cur<<1]==-1)left[cur]=left[cur<<1|1];else left[cur]=left[cur<<1];if(right[cur<<1|1]==-1)right[cur]=right[cur<<1];else right[cur]=right[cur<<1|1];minn[cur]=min(minn[cur<<1],minn[cur<<1|1]);if(left[cur<<1|1]!=-1&&right[cur<<1]!=-1)minn[cur]=min(minn[cur],left[cur<<1|1]-right[cur<<1]);
}
void inser(long long cur,long long l,long long r,long long p,long long val){if(l==r){left[cur]=val;right[cur]=val;minn[cur]=oo;return;}long long mid=(l+r)>>1;if(p<=mid)inser(cur<<1,l,mid,p,val);else inser(cur<<1|1,mid+1,r,p,val);up(cur);
}
void eras(long long cur,long long l,long long r,long long p){if(l==r){left[cur]=-1;right[cur]=-1;minn[cur]=oo;return;}long long mid=(l+r)>>1;if(p<=mid)eras(cur<<1,l,mid,p);else eras(cur<<1|1,mid+1,r,p);up(cur);
}
long long ans=oo,lastr=-1;
void get_min(long long cur,long long l,long long r,long long x,long long y){if(x<=l&&r<=y){ans=min(ans,minn[cur]);if(left[cur]!=-1&&lastr!=-1){ans=min(ans,left[cur]-lastr);}lastr=right[cur];return;}long long mid=(l+r)>>1;if(x<=mid)get_min(cur<<1,l,mid,x,y);if(y>mid) get_min(cur<<1|1,mid+1,r,x,y);
}
struct pp{long long v,id;pp(long long a=0,long long b=0):v(a),id(b){};
} num[NN];
bool cmp_v(pp x,pp y){if(x.v<y.v)return 1;else if(x.v==y.v&&x.id<y.id)return 1;else return 0;
}
long long a[NN];
int main(){long long cnt=0;memset(left,-1,sizeof(left));memset(right,-1,sizeof(right));long long n;scanf("%lld",&n);for(long long i=1;i<=n;i++){scanf("%lld%lld",&op[i],&v[i]);if(op[i]==1){num[++cnt].v=v[i];num[cnt].id=i;}}if(cnt<1){for(long long i=1;i<=n;i++)printf("No\n");return 0;}sort(num+1,num+cnt+1,cmp_v);for(long long i=1;i<=cnt;i++){a[num[i].id]=i;}for(long long i=1;i<=n;i++){if(op[i]==2){pp neww;neww.id=0;neww.v=v[i];a[i]=lower_bound(num+1,num+cnt+1,neww,cmp_v)-num+ma[v[i]];ma[v[i]]=ma[v[i]]+1;}else if(op[i]==3){pp neww;neww.id=0;neww.v=v[i];a[i]=lower_bound(num+1,num+cnt+1,neww,cmp_v)-num;}}for(long long i=1;i<=(cnt<<2);i++)minn[i]=oo;for(long long i=1;i<=n;i++){if(op[i]==1){inser(1,1,cnt,a[i],v[i]);se.insert(v[i]);}else if(op[i]==2){eras(1,1,cnt,a[i]);se.erase(se.lower_bound(v[i]));//直接erase掉vi不对}else{set<long long>::iterator pos=se.upper_bound(v[i]);long long aa=-1,b=-1;if(pos!=se.begin()){--pos;b=*pos;if(pos!=se.begin()){--pos;aa=*pos;}}if(aa!=-1&&b!=-1&&aa+b>v[i]){printf("Yes\n");continue;}ans=oo;lastr=-1;get_min(1,1,cnt,max(1ll,a[i]-1),cnt);if(ans<v[i]){printf("Yes\n");}else{printf("No\n");}}}return 0;
}
/*
13
3 1
3 2
3 3
1 4
1 4
1 5
2 4
2 4
3 2
3 1
1 4
3 2
3 1
*/

I.Interval

这个题是个网格最小割。把区间弄成点，没有花钱限制的流量无穷，限制的流量是价格。完了源点是区间（1，n），汇点新建，所有大小为1的区间往汇点连正无穷的边。跑最小割。然而我的代码跑过了65%的数据就wa了。不知道为啥。。有大佬帮忙康康评论一下。。。。

没AC代码

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>using namespace std;
long long oo=2e9+10;
long long read(){long long x = 0; long long zf = 1; char ch = ' ';while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();if (ch == '-') zf = -1, ch = getchar();while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;
}const int NN=510;
const int MM=NN*NN;
const int VV=NN*NN;
struct Edge{int to;long long dis;
} edges[MM<<2];vector <int> con[VV];int cur[VV];
int edge_num=-1;
int n, m, s, t;void addEdge2(int from, int to, long long dis){edges[++edge_num].to = to;edges[edge_num].dis = dis;con[from].push_back(edge_num);
}void addEdge(int from, int to, long long dis){addEdge2(from, to, dis), addEdge2(to, from, 0);
}int d[VV];long long DFS(int u, long long flow){if (u == t) return flow;long long _flow = 0, __flow;int up=con[u].size();for (int i = cur[u]; i<up ; i++){int c_e=con[u][i];int v = edges[c_e].to;if (d[v] == d[u] + 1 && edges[c_e].dis > 0){__flow = DFS(v, min(flow, edges[c_e].dis));flow -= __flow;edges[c_e].dis -= __flow;_flow += __flow;edges[c_e^1].dis += __flow;if (!flow)break;}}if (!_flow) d[u] = -1;return _flow;
}bool BFS(){memset(d, -1, sizeof(d));queue<int> que; que.push(s);d[s] = 0; int u, _new;while (!que.empty()){u = que.front(), que.pop();int up=con[u].size();for (int i = 0; i<up; i++){int c_e=con[u][i];_new = edges[c_e].to;if (d[_new] == -1 && edges[c_e].dis > 0){d[_new] = d[u] + 1;que.push(_new);}}}return (d[t] != -1);
}long long dinic(){long long max_flow = 0;while (BFS()){for (int i = 1; i <= n; ++i) cur[i] = 0;max_flow += DFS(s, oo);if(max_flow>=oo)return max_flow;}return max_flow;
}
int c[NN][NN][2];
int id[NN][NN];
int main(){int n,m;scanf("%d%d",&n,&m);memset(c,-1,sizeof(c));long long maxn=0;for(int i=1;i<=m;i++){int x,y,co;char op[1];scanf("%d%d%s%d",&x,&y,op,&co);maxn+=co;if(op[0]=='L')c[x][y][0]=co;else c[x][y][1]=co;}oo=maxn+1;int v=0;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){id[i][j]=++v;}}for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(c[i][j][0]!=-1){addEdge(id[i][j],id[i+1][j],c[i][j][0]);}else addEdge(id[i][j],id[i+1][j],oo);if(c[i][j][1]!=-1){addEdge(id[i][j],id[i][j-1],c[i][j][1]);}else addEdge(id[i][j],id[i][j-1],oo);}}s=id[1][n];t=v+1;for(int i=1;i<=n;i++){addEdge(id[i][i],t,oo);}long long ans=dinic();if(ans>=oo){printf("-1\n");}else printf("%lld\n",ans);return 0;
}

这篇关于牛客2020多校round2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---