牛客练习赛42

Source

牛客练习赛42

A

请先思考后再展开

其实最长的一段子串一定是最优答案

1
2
3
4
5
6
7
8
9
10
11
12
13
const int MAX_N=2e5+10;
char a[MAX_N],b[MAX_N];
void main()
{
scanf("%s%s",a+1,b+1);int n=strlen(a+1);
ll ans=0;
for(int i=1,j=0;i<=n;i++)
{
if(a[i]==b[i]) j++; else j=0;
chmax(ans,ll(j+2)*j);
}
printf("%lld",ans);
}

B

请先思考后再展开

显然所有数都选

1
2
3
4
5
6
7
8
9
10
11
12
const int MOD=1e8+7;
void main()
{
int n=qread();
ll a=0,b=0;
for(int i=1;i<=n;i++)
{
int x=qread();
a^=x;b+=x;
}
write((a+b)%MOD);
}

C

请先思考后再展开

这道题思路显然,就是把一个序列中相同值贡献到第一个上面
不过需要卡常,我的写法是,f表示前面存在这个值的行的对应乘积,然后g表示出现在了多少个行
时间复杂度为 $O(n^2)$

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
#define int int
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
int qread()
{
int ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(int num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
inline void chmax(ll &x,const ll y) {x=x>y?x:y;}
inline void chmin(ll &x,const ll y) {x=x<y?x:y;}
const int MOD=1e9+7;
void add(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
const int MAX_N=4e6+10;
const int mod=20030122;
struct Hash
{
int f[mod],g[mod];Hash(){memset(f,-1,sizeof f);}
int ask(int num,int &id)
{
int pos=num%mod;while(f[pos]>=0 and f[pos]!=num) pos=(pos+1==mod?0:pos+1);
if(f[pos]==num) return g[pos];
f[pos]=num;g[pos]=++id;return 0;
}
}hash;
int b[MAX_N],old[MAX_N],f[MAX_N],g[MAX_N];
int ti[MAX_N],ti2[MAX_N],cnt[MAX_N],nn[MAX_N];
void main()
{
int n=qread(),m=qread();
int id=0;
for(int i=1;i<=m;i++) for(int j=1;j<=n;j++)
{
int now=qread(),t=hash.ask(now,id);f[id]=1;
b[n*(i-1)+j]=(t==0?id:t);old[b[n*(i-1)+j]]=now;
}
nn[0]=1;for(int i=1;i<=m;i++) nn[i]=(ll)nn[i-1]*n%MOD;
int ans=0;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
int now=b[n*(i-1)+j];
add(ans,(ll)f[now]*nn[i-1-g[now]+m-i]%MOD*old[now]%MOD);
if(ti2[now]<i) ti2[now]=i,cnt[now]=1; else cnt[now]++;
}
for(int j=1;j<=n;j++)
{
int now=b[n*(i-1)+j];
if(ti[now]<i) ti[now]=i,f[now]=(ll)f[now]*(n-cnt[now])%MOD,g[now]++;
}
}
write(ans);
}
};
int main()
{
srand(time(0));
mine::main();
}

D

请先思考后再展开

这是一道花了我2h的模拟题,主要是我去大力推柿子了,而且还看错题目的输出方式又重新推了一遍(不太熟练也是问题)
就先是递减序列,然后k为需要多少个顺序对,那么二分到第一个需要修改的位置,然后后面的部分一定是个递增的序列
然后你可以像我这样sb地推差比数列的柿子,也可以直接矩乘

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
#define int int
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
inline void chmax(ll &x,const ll y) {x=x>y?x:y;}
inline void chmin(ll &x,const ll y) {x=x<y?x:y;}
const int MOD=1e9+7;
void add(ll &x,ll y) {x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
ll qpower(ll x,int e)
{
ll ans=1;
while(e)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
ll inv(ll x) {return qpower(x,MOD-2);}
ll T(ll n) {return n*(n-1)/2;}//debug 不能取模
ll A;
ll g(ll n) {return (qpower(A,n+1)+MOD-1)*inv(A-1)%MOD;}//等比数列
ll f(ll n) {return (qpower(A,n+1)*n%MOD+MOD-g(n)+1)*inv(A-1)%MOD;}//差比数列,递减
void main()
{
ll n=qread(),k=T(n)-qread();A=n+1;
int l=1,r=n,pos=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(k<=T(mid)) pos=mid,r=mid-1;
else l=mid+1;
}
int ned=k-T(pos-1);
ll ans=ll(pos-ned)*qpower(A,n-pos+1)%MOD;
if(pos+1<=n) add(ans, ((g(n-pos)-1)*(n+1)%MOD+MOD-f(n-pos))%MOD );
int a=pos-ned-1,b=pos;
if(1<=a) add(ans, f(a)*qpower(A,n-pos+1)%MOD );
if(a+2<=b) add(ans, (f(b)+MOD-f(a+1))*qpower(A,n-pos)%MOD );
write(ans);
}
};
int main()
{
srand(time(0));
mine::main();
}

E

请先思考后再展开

显然先离散化
我们需要统计的是【子树内至少一个关键点】的节点-虚树根节点深度+1

询问离线到右端点上,按从小到大的顺序access右端点,涂上这次的颜色
则每个点的颜色即子树最大值,而我目前能出现的也只有r以内的,所以只要mx>=l即可
这个可以树状数组统计,比较套路,时间复杂度为 $O(nlog^2n+qlogn)$

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
// #include<unordered_map>
using namespace std;
int bin[40],lg[1<<21];
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
#define vc vector
inline void chmax(int &x,const int y) {x=x>y?x:y;}
inline void chmin(int &x,const int y) {x=x<y?x:y;}
const int MAX_N=1e5+10;
struct BIT
{
int bit[MAX_N];BIT(){memset(bit,0,sizeof bit);}
int lowbit(int x) {return x&-x;}
void add(int x,int c) {while(0<x and x<MAX_N) bit[x]+=c,x+=lowbit(x);}
int sum(int x) {int ans=0;while(x>=1) ans+=bit[x],x-=lowbit(x);return ans;}
}bit;
struct LCT
{
struct Nod{int son[2],fa,col,siz;bool tg;}p[MAX_N];
LCT(){memset(p,0,sizeof p);for(int i=1;i<MAX_N;i++) p[i].siz=1;}
#define lc p[x].son[0]
#define rc p[x].son[1]
void pushup(int x) {p[x].siz=1+p[lc].siz+p[rc].siz;}
void pushdown(int x) {if(p[x].tg) p[x].tg=0,p[lc].col=p[rc].col=p[x].col,p[lc].tg=p[rc].tg=1;}
#define son(x) (p[p[x].fa].son[1]==x)
bool isrt(int x) {return p[p[x].fa].son[son(x)]!=x;}
void rotate(int x)
{
int f=p[x].fa,ff=p[f].fa;if(!isrt(f)) p[ff].son[son(f)]=x;
int w=son(x),ts=p[x].son[w^1];p[x].son[w^1]=f;p[f].son[w]=ts;
p[x].fa=ff;p[f].fa=x;if(ts) p[ts].fa=f;pushup(f);pushup(x);
}
int tmp[MAX_N];
void splay(int x)
{
int tot=0,t=x;while(!isrt(t)) tmp[++tot]=t,t=p[t].fa;
pushdown(t);for(int i=tot;i>=1;i--) pushdown(tmp[i]);
for(int fa=p[x].fa;!isrt(x);rotate(x),fa=p[x].fa)
if(!isrt(fa)) son(x)^son(fa)?rotate(x):rotate(fa);
}
void access(int x,int col)
{
int lst=0,tmp=x;
while(x>0)
{
splay(x);
bit.add(p[x].col,-p[lc].siz-1);
p[x].son[1]=lst;if(lst) p[lst].fa=x;pushup(x);
lst=x;x=p[x].fa;
}
splay(tmp);p[tmp].tg=1;p[tmp].col=col;
bit.add(col,p[tmp].siz);
}
}lct;
vector<int> son[MAX_N];
int dep[MAX_N],mm[MAX_N*2][21],dfn[MAX_N],id=0;
void dfs(int x,int fa)
{
dep[x]=dep[fa]+1;lct.p[x].fa=fa;dfn[x]=++id;mm[id][0]=x;
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t];if(y==fa) continue;
dfs(y,x);mm[++id][0]=x;
}
}
int gmin(int x,int y) {return dep[x]<dep[y]?x:y;}
int getlca(int x,int y)
{
x=dfn[x],y=dfn[y];if(x>y) swap(x,y);
int t=lg[y-x+1];return gmin(mm[x][t],mm[y-bin[t]+1][t]);
}
int gg[MAX_N][21];
int gettop(int l,int r)
{
int t=lg[r-l+1];return getlca(gg[l][t],gg[r-bin[t]+1][t]);
}
int tmp[MAX_N],a[MAX_N],rk[MAX_N];//映射
bool cmp(int x,int y) {return a[x]<a[y];}
vector<pr> qes[MAX_N];int ans[MAX_N*5];
void main()
{
int n=qread(),q=qread();
for(int i=1;i<=n;i++) a[tmp[i]=i]=qread();
sort(tmp+1,tmp+n+1,cmp);sort(a+1,a+n+1);
for(int i=1;i<=n;i++) rk[tmp[i]]=i;
for(int i=2;i<=n;i++) {int x=rk[qread()],y=rk[qread()];son[x].PB(y),son[y].PB(x);}
dfs(1,0);
for(int i=1;i<=20;i++) for(int j=1;j<=id-bin[i]+1;j++) mm[j][i]=gmin(mm[j][i-1],mm[j+bin[i-1]][i-1]);
for(int i=1;i<=n;i++) gg[i][0]=i;
for(int i=1;i<=20;i++) for(int j=1;j<=n-bin[i]+1;j++) gg[j][i]=getlca(gg[j][i-1],gg[j+bin[i-1]][i-1]);
for(int i=1;i<=q;i++)
{
int l=lower_bound(a+1,a+n+1,qread())-a;
int r=upper_bound(a+1,a+n+1,qread())-a-1;
qes[r].PB(MP(l,i));
}
for(int r=1;r<=n;r++)
{
lct.access(r,r);
for(int t=0;t<(int)qes[r].size();t++)
{
int l=qes[r][t].FR,id=qes[r][t].SE;
if(l<=r) ans[id]=bit.sum(r)-bit.sum(l-1)-(dep[gettop(l,r)]-1);
}
}
for(int i=1;i<=q;i++) writeln(ans[i]);
}
};
int main()
{
srand(time(0));
bin[0]=1;for(int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;
lg[1]=0;for(int i=2;i<(1<<21);i++) lg[i]=lg[i>>1]+1;
mine::main();
}

F

请先思考后再展开

如果不强制在线,可以把询问和原树的点放在一起,建虚树,然后换根dp,复杂度下界为n(笛卡尔树什么的……)
现在强制在线的话,就是需要在线地找到离原树某个点最近的点,这个在套路集锦-树-6里面有
时间复杂度为nlogn,空间为n
或者暴力树剖+二分找,时间为log方

然后你也可以动态点分治,每个点开个map记录去子树内这个颜色,最小距离,时间为log方,空间为nlogn
时间换空间的手写hash,每个节点的模数根据子树大小设定,以10倍为例,时间nlogn,空间10nlogn
此做法好写好调,虽然不优秀但本题不卡(upd:个屁……卡了好久)

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
// #include<unordered_map>
using namespace std;
int bin[40],lg[1<<21];
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
#define vc vector
inline void chmax(int &x,const int y) {x=x>y?x:y;}
inline void chmin(int &x,const int y) {x=x<y?x:y;}
const int MAX_N=4e5+10;
struct Hash
{
vector<pr> mp;int mod;
void getmod(int mm) {mod=mm;mp.resize(mm);for(int t=0;t<mm;t++) mp[t]=MP(-1,-1);}
int ask(int num,int val)
{
int pos=num%mod;
while(mp[pos].FR!=-1 and mp[pos].FR!=num) pos=(pos==mod-1?0:pos+1);
if(mp[pos].FR==num) {chmin(mp[pos].SE,val);return mp[pos].SE;}
if(val!=INF) mp[pos]=MP(num,val);return -1;
}
}hash[MAX_N];
// unordered_map<int,int> hash[MAX_N];
vector<int> son[MAX_N];
int dep[MAX_N],dfn[MAX_N],id=0;
int mm[MAX_N*2][21];int gmin(int x,int y) {return dep[x]<dep[y]?x:y;}
void dfs(int x,int fa)
{
dep[x]=dep[fa]+1;dfn[x]=++id;mm[id][0]=x;
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t];if(y==fa) continue;
dfs(y,x);mm[++id][0]=x;
}
}
int getlca(int x,int y)
{
x=dfn[x],y=dfn[y];if(x>y) swap(x,y);
int t=lg[y-x+1];return gmin(mm[x][t],mm[y-bin[t]+1][t]);
}
int getdis(int x,int y) {return dep[x]+dep[y]-2*dep[getlca(x,y)];}
int G,gg[MAX_N],ff[MAX_N],all;
bool v[MAX_N];int siz[MAX_N],siz2[MAX_N];
vector<int> cc[MAX_N];
void insert(int x,int fa,int dis,int top)
{
for(int t=0;t<(int)cc[x].size();t++)
{
int col=cc[x][t];
hash[top].ask(col,dis);
// if(hash[top].count(col)) hash[top][col]=min(hash[top][col],dis);
// else hash[top][col]=dis;
}
siz[x]=1;
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t];if(y==fa or v[y]) continue;
insert(y,x,dis+1,top);siz[x]+=siz[y];
}
}
void getrt(int x,int fa)
{
siz[x]=1;gg[x]=0;siz2[x]=cc[x].size();
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t];if(y==fa or v[y]) continue;
getrt(y,x);siz[x]+=siz[y];chmax(gg[x],siz[y]);siz2[x]+=siz2[y];
}
chmax(gg[x],all-siz[x]);
if(gg[x]<gg[G]) G=x;
}
void solve(int x)
{
v[x]=1;
getrt(x,0);
hash[x].getmod(siz2[x]*10+1);
insert(x,0,0,x);
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t];if(v[y]) continue;
G=0;all=siz[y];getrt(y,x);ff[G]=x;solve(G);
}
}
void main()
{
int n=qread(),m=qread(),q=qread();
for(int i=1;i<=n-1;i++) {int x=qread(),y=qread();son[x].PB(y);son[y].PB(x);}
dfs(1,0);
for(int i=1;i<=20;i++) for(int j=1;j<=2*n-bin[i]+1;j++) mm[j][i]=gmin(mm[j][i-1],mm[j+bin[i-1]][i-1]);
for(int col=1;col<=m;col++)
{
int siz=qread();//这里一步步跳上去会tle,O(1)lca居然比压栈还慢……
while(siz--) cc[qread()].PB(col);
}
G=0;gg[0]=INF;all=n;getrt(1,0);solve(G);
int lst=0;
while(q--)
{
int x=(qread()+lst)%n+1,col=(qread()+lst)%m+1;
int ans=n,y=x;
while(y!=0)
{
// if(hash[y].count(col)) chmin(ans,hash[y][col]+getdis(x,y));
int t=hash[y].ask(col,INF);if(t>=0) chmin(ans,t+getdis(x,y));
y=ff[y];
}
writeln(lst=ans);
}
}
};
int main()
{
srand(time(0));
bin[0]=1;for(int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;
lg[1]=0;for(int i=2;i<(1<<21);i++) lg[i]=lg[i>>1]+1;
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/145e.html
转载请注明出处,谢谢!