2020牛客暑期多校训练营(第二场)

7.13 补了好多好多题的牛客2

A-All with Pairs

题意

定义函数 $f(s,t)$ 为 $s$ 前缀和 $t$ 后缀的最长相同长度。给定 $n$ 个串,求两两 $f$ 和。

思路

对每个前缀后缀进行哈希,计算每个前缀对应的后缀有几个,但是直接算有重复,要靠 $next$ 去重(题解讲得挺清楚的其实)。

坑点

卡单模数哈希,气死了,贴了双哈希代码,堂堂正正过题好吧

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6 + 5;
const int mod = 998244353;
const ll inf = 1e9;
int seed[2]={18052103,27174403},bas[2][maxn];
ll hs[maxn];
char s[maxn];
int len[maxn],ind[maxn],nex[maxn],sub[maxn];
map<ll,int>aaa;
int solve(){
int n,ans(0); sc(n); ind[1]=bas[0][0]=bas[1][0]=1;
rep(j,0,2) rep(i,1,maxn) bas[j][i]=1ll*bas[j][i-1]*seed[j]%mod;
rep(i,1,n+1){
scs(s+ind[i]);
len[i]=strlen(s+ind[i]);
ind[i+1]=ind[i]+len[i];
ll th[2]={0,0}; dep(j,len[i]-1,0){
rep(k,0,2){
th[k]=1ll*th[k]*seed[k]%mod+(s[j+ind[i]]-'a'+1);
if(th[k]>=mod) th[k]-=mod;
} aaa[th[0]*inf+th[1]]++;
} mst(th,0); rep(j,0,len[i]){
rep(k,0,2){
th[k]+=1ll*bas[k][j]*(s[j+ind[i]]-'a'+1)%mod;
if(th[k]>=mod) th[k]-=mod;
} hs[ind[i]+j]=th[0]*inf+th[1];
}
}
rep(i,1,n+1){
int k=0,tl=len[i]; nex[ind[i]]=0;
rep(j,ind[i]+1,ind[i+1]){
while(k&&s[j]!=s[k+ind[i]]) k=nex[k+ind[i]-1];
if(s[j]==s[k+ind[i]]) k++; nex[j]=k;
}
dep(j,ind[i+1]-1,ind[i]){
ans+=1ll*(aaa[hs[j]]-sub[j])*tl%mod*tl%mod;
if(ans>=mod) ans-=mod; tl--;
sub[nex[j]+ind[i]-1]+=aaa[hs[j]]; // 直接减也会减重复
}
} return pf("%d\n",ans);
}
int main(){
/* int _; sc(_); while(_--) */ solve();
}

B-Boundary

题意

给定 $n$ 个点,问最多有几个点能在过原点的同一个圆上。

思路

先枚举一个点 $P$ ,再枚举所有点 $A$ ,根据角度和 $A$ 相对 $OP$ 位置统计个数,取最大值。

坑点

  1. $mx$ 初始值要 $1$ ,保证至少有一个点。我代码在一个点/全部点共线的情况执行不到 $mx$ 的赋值
  2. $(double)tmp1 / tmp2$ 不要写成 $1.0 * tmp1 / 1.0 * tmp2$(小庄血泪之痛呜呜呜)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
#define pf printf
#define scl(x) scanf("%lld", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
typedef long long ll;
struct point{
ll x,y,d;
}p[2005];
void solve(){
ll n,mx=1; scl(n); rep(i,0,n){
ll x,y; scl(x),scl(y);
p[i].x=x,p[i].y=y;
p[i].d=x*x+y*y;
} rep(i,0,n){
map<double,ll>aaa;
rep(j,0,n){
if(i==j) continue;
ll cr=p[i].x*p[j].y-p[j].x*p[i].y;
if(!cr) continue; cr=cr<0?-1:1;
ll tx=p[i].x-p[j].x;
ll ty=p[i].y-p[j].y;
ll dt=tx*tx+ty*ty; // |AP|
ll del=p[j].d+dt-p[i].d,re=4ll*dt*p[j].d; // 余弦定理
ll op=del<0?-1:del?1:0,ff=1;
ff=op*cr==1?-1:op*cr?1:0; del*=ff*del;
double tt=(double)del/re;
ll res=++aaa[tt];
mx=max(mx,res+1);
}
} pf("%lld\n",mx);
}
int main(){
/* int _; sc(_); while(_--) */ solve();
}

C-Cover the Tree

题意

给定一棵树,用最少的链覆盖树的每一条边(不同链可重叠,可只覆盖一个点)。

思路

最少的链数一定是叶节点两两相连,所以最少链数为( 叶节点数 $+1$ )$/2$ 。然后难就难在怎么将叶节点两两配对,看了题解意识到可以用 $DFS$ 序,将叶节点按 $DFS$ 序排列后分为前后两半按顺序配对就可以啦

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 2e5 + 5;
const int mod = 998244353;
int in[maxn],q[maxn],vis[maxn];
vector<int>vv;
int solve(){
srand(time(0));
int n; sc(n); rep(i,1,n){
int u,v; sc(u); sc(v);
in[u]++; in[v]++;
} if(n==1) return pf("1 1\n");
rep(i,1,n+1) if(in[i]==1)
vv.push_back(i);
int sz=vv.size(),cnt(0);
rep(i,0,sz){
int t=rand()%sz;
while(vis[t]) t=rand()%sz;
q[cnt++]=vv[t];
vis[t]++;
}
pf("%d\n",(sz+1)/2);
rep(i,0,sz){
pf("%d %d\n",q[i],q[i+1]);
if(sz%2&&!i) continue; i++;
} return pf("\n");
}
int main(){
/* int _; sc(_); while(_--) */ solve();
}

D-Duration

题意

求秒数差

思路

乘一下加一下减一下

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
#define pf printf
using namespace std;
int solve(){
int a,b,c,t1,t2;
scanf("%d:%d:%d",&a,&b,&c);
t1=a*3600+b*60+c;
scanf("%d:%d:%d",&a,&b,&c);
t2=a*3600+b*60+c;
return pf("%d\n",abs(t1-t2));
}
int main(){
/* int _; sc(_); while(_--) */ solve();
}

E-Exclusive OR

题意

给定长度 $n$ 的数组 $a$ ,求选择 $1-n$ 个数时最大异或和。

思路

数据范围在 $2^{18}$ ,所以 $i\geq 20$ 时有 $ans[i]=a[i-2]$。前 $20$ 个用异或卷积求(但 $fwt$ 我可能也讲不来)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
const int maxn = 2e5 + 5;
const int N = 1 << 18;
int a[N],b[N],ans[maxn];
void fwt_xor(int *a,int op){
for(int i=1;i<N;i<<=1)
for(int j=0;j<N;j+=i<<1)
for(int k=0;k<i;++k){
int x=a[j+k],y=a[i+j+k];
a[j+k]=x+y,a[i+j+k]=x-y;
if(op==-1) a[j+k]/=2,a[i+j+k]/=2;
}
}
void solve(){
int n; sc(n); rep(i,1,n+1){
int t; sc(t); a[t]=1;
} fwt_xor(a,1); b[0]=1;
rep(i,1,20){
fwt_xor(b,1);
rep(j,0,N) b[j]*=a[j];
fwt_xor(b,-1);
rep(j,0,N) if(b[j]) ans[i]=j,b[j]=1;
} rep(i,20,n+1) ans[i]=ans[i-2];
rep(i,1,n+1) pf("%d ",ans[i]);
}
int main(){
/* int _; sc(_); while(_--) */ solve();
}

F-Fake Maxpooling

题意

给定一矩阵 $A$ ,其中第 $(i, j)$ 位上对应的数字是 $lcm(i, j)$ ,求对于整个矩阵中的每个k×k大小的子矩阵中最大值之和。

思路

首先对矩阵进行预处理,直接暴力求的复杂度是 $O(nmlogn)$,看题解之后用线性方法优化到了 $O(nm)$ 。然后滑动窗口对 $A$ 的每一行求出区间 $(j-k,j)$ 的最大值(利用单调队列进行求解),并储存在 $g[i,j]$ 中(因为这题内存卡的比较紧,所以重复利用了一下之前的 $g$ 数组),然后对纵向用同样的方式求出 $(g[i-k][j],g[i][j])$ 的最大值,所得的结果就是子矩阵的最大值,然后求个和答案就出来啦。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 2e5 + 5;
const int mod = 998244353;
int a[5005][5005],q[5005*5005];
int solve(){
int n,m,k; sc(n); sc(m); sc(k); ll ans(0);
rep(i,1,n+1) rep(j,1,m+1) a[i][j]=i/__gcd(i,j)*j;
if(k==1) rep(i,1,n+1) rep(j,1,m+1) ans+=a[i][j];
if(k==1) return pf("%lld\n",ans);
q[0]=1e9; rep(i,1,n+1){
int l=1,r=0; rep(j,1,m+1){
while(a[i][j]>q[r]) --r;
q[++r]=a[i][j];
while(r-l+1>k) l++;
a[i][j]=q[l];
}
}
rep(j,k,m+1){
int l=1,r=0; rep(i,1,n+1){
while(a[i][j]>q[r]) --r;
q[++r]=a[i][j];
while(r-l+1>k) l++;
a[i][j]=q[l];
if(i>=k) ans+=1ll*a[i][j];
}
} return pf("%lld\n",ans);
}
int main(){
/* int _; sc(_); while(_--) */ solve();
}

G-Greater and Greater

题意

给定长度为 $n$ 的数组 $a$ 和长度为 $m$ 的数组 $b$ ,问 $a$ 有几个长度为 $m$ 的连续子段满足任意 $a_{l+i}>b_i$ 。

思路

考虑用 $bitset$ 且反向求解。将 $a$ 、$b$ 排序后,枚举 $b[i]$ ,$cur$ 维护 $a$ 中小于 $b[i]$ 的下标,右移对应位数$-1$ 得到在 $a$ 中的状态,或起来得到 $ans$ 。最后计算在 $1$ ~ $(n-m+1)$ 中 $ans$ 为 $0$ 的个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
typedef pair<int,int> pii;
const int maxn = 2e5 + 5;
pii a[maxn],b[maxn];
bitset<maxn>ans,cur;
#define f first
#define s second
int solve(){
int n,m; sc(n); sc(m);
rep(i,1,n+1) sc(a[i].f),a[i].s=i;
rep(i,1,m+1) sc(b[i].f),b[i].s=i;
sort(a+1,a+n+1); sort(b+1,b+m+1);
int k=1; rep(i,1,m+1){
while(k<=n&&a[k].f<b[i].f)
cur.set(a[k].s),k++;
ans|=cur>>(b[i].s-1);
} int cnt(0);
rep(i,1,n-m+2) if(!ans[i]) cnt++;
return pf("%d\n",cnt);
}
int main(){
/* int _; sc(_); while(_--) */ solve();
}

J-Just Shuffle

题意

给一个数组 $a$ 求置换 $k$ 次能得到 $a$ 的数组,$k$ 是大质数。

思路

找出 $a$ 的所有环,对每个环求逆元。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn],ans[maxn],vis[maxn];
void solve(){
int n,k; sc(n); sc(k);
rep(i,1,n+1) sc(a[i]);
rep(i,1,n+1) if(!vis[i]){
vector<int>vv; int q=a[i],cnt(0); // 找环
while(!vis[q]) vv.push_back(q),vis[q]++,q=a[q];
int sz=vv.size(),inv; rep(j,0,sz)
if(1ll*k*j%sz==1) inv=j;
rep(i,0,sz) ans[vv[i]]=vv[(i+inv)%sz];
} rep(i,1,n+1) pf("%d ",ans[i]);
}
int main(){
/* int _; sc(_); while(_--) */ solve();
}