jsc2019-final题解

Source

第一回日本最強プログラマー学生選手権決勝
Japanese Student Championship 2019
jsc2019

好题:A、C、F、H

这一场基本是一些思维+数据结构题

不过提醒一下,出题人的习惯很鬼畜,所有编号从0开始,而且区间都是左闭右开……

jsc2019 A Equal Weight

题意(改):给出两个序列a和b,构造一组解满足$a_q-a_p=b_x-b_y,n,a_i,b_i \le 1e7$

请先思考后再展开

移项,判$vis[a_i+b_j]$,找到退出的话,复杂度为$O(a_i)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bitset<N> a[N],to[N],limit[N];char str[N];
void main()
{
int n=qread();
fo(i,1,n) {scanf("%s",str+1);fo(j,1,n) to[i][j]=str[j]-'0';}
fo(i,1,n) {scanf("%s",str+1);fo(j,1,n) limit[i][j]=str[j]-'0';}
fo(i,1,n) fo(j,1,n) if(to[i][j]) a[j]|=~limit[i];
fo(i,1,n) a[i]=~a[i];
fo(i,1,n)
{
bitset<N> tmp;tmp.reset();
fo(j,1,n) if(to[i][j]) tmp|=a[j];
fo(j,1,n) if(tmp[j]!=limit[i][j]) {puts("-1");return;}
}
fo(i,1,n){fo(j,1,n) write(a[i][j]);puts("");}
}

jsc2019 B Reachability

题意(改):有3n个点分成X,Y,Z三个部分,从X向Y连边,从Y向Z连边,现在告诉你X到Y的可达情况、X到Z的可达情况,构造⼀种合法的Y到Z的可达情况,$n \le 1e3$

请先思考后再展开

其实就是给出n个集合,i am the king给出n个限制形如集合的子集,并给出他们的并,构造每个集合具体元素

每个条件相当于提供补集作为不可达限制,bitset优化即可,$O(n*n*n/32)$

1
2
3
4
5
6
7
8
9
10
11
12
pr vis[N];int a[N],b[N];
void main()
{
int n=qread(),m=qread();
fo(i,1,n) a[i]=qread();fo(i,1,m) b[i]=qread();
fo(i,1,n) fo(j,1,m) if(vis[a[i]+b[j]]!=vis[0])
{
printf("%d %d %d %d",vis[a[i]+b[j]].FR-1,vis[a[i]+b[j]].SE-1,i-1,j-1);
return;
} else vis[a[i]+b[j]]=MP(i,j);
puts("-1");
}

jsc2019 C Maximize Minimum

题意:数轴$[0,L]$上X处放一个棋子,随后n次操作每次给出位置$A_i$反转上面是否有棋子(保证操作后至少两个),操作完询问美丽值,即可以选择一些移动到$L-A_i$(如果已经有就不能移动),希望让最接近的棋子尽量远。$n \le 2e5$

请先思考后再展开

考虑对一个局面如何求其美丽值,二分可行但意义不大,直接贪心,一定是排序后奇数左边偶数右边,然后再给最中间两个取min

用一个堆维护所有有贡献的距离,当插入时,设左边两个为a和b,右边两个为c和d,则断开$a \to c,b \to d$然后连上$a \to now,now \to d,b \to c$,$O(nlogn)$

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
struct Heap
{
priority_queue< ll,vc<ll>,greater<ll> > A,B;
void upd(){while(sz(A) and sz(B) and A.top()==B.top()) A.pop(),B.pop();}
void push(ll num,int op){GG(num<0)if(op)A.push(num);else B.push(num);}
ll top(){upd();return A.top();}
}hp;
int L;
multiset<ll> ss,real;
typedef multiset<ll>::iterator IT;
void solve(int num)
{
int op=!real.count(num);
if(op) real.insert(num); else real.erase(num);
num=min(num,L-num);
if(op) ss.insert(num);
IT now=ss.upper_bound(num);now--;
IT b=now,c=now;b--;c++;IT a=b,d=c;a--;d++;
ll fa=*a,fb=*b,fc=*c,fd=*d;
if(fc==INF+INF) hp.push(L-fb-fa,op^1),hp.push(L-num-fb,op);
else if(fd==INF+INF) hp.push(L-fc-fb,op^1),hp.push(L-fc-num,op);
hp.push(fc-fa,op^1);hp.push(fd-fb,op^1);
hp.push(num-fa,op);hp.push(fd-num,op);hp.push(fc-fb,op);
if(!op) ss.erase(now);
}
void main()
{
int n=qread();L=qread();
ss.insert(-INF-INF);ss.insert(-INF);ss.insert(INF+INF);ss.insert(1ll*INF+INF+INF);
hp.push(INF*4ll,1);hp.push(INF*4ll,1);
solve(qread());fo(i,1,n) solve(qread()),write2(hp.top());
}

jsc2019 D Minimize Maximum

题意:sbt给出两个序列满足$a_i \le b_i$,每次从后面插入一组a和b,每次求一个序列c满足$a_i \le c_i \le b_i,且最小化max\ c_i-c_{i-1}$,$n \le 2e5$

请先思考后再展开

明显二分mid,具体写出式子

$c_i=min(c_{i-1}+mid,b_i)=min_{j=1}^i b_j+(i-j)mid$

合法条件为:$\forall j<i, b_j+(i-j)mid \ge a_i,即mid \ge \frac{a_i-b_j}{i-j}$,即最大斜率,维护凸壳,三分即可

$O(nlog_{1.5}n)$

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
namespace Convex
{
pr q[N];int cnt;
void insert(int x,int y)
{
while(cnt>=2 and (q[cnt].SE-q[cnt-1].SE)/(q[cnt].FR-q[cnt-1].FR)>=(y-q[cnt].SE)/(x-q[cnt].FR) ) cnt--;
q[++cnt]=MP(x,y);
}
#define slope(pos) 1.0*(y-q[pos].SE)/(x-q[pos].FR)
int solve(int x,int y)
{
int fl=1,fr=cnt;double mx=-INF;
while(fr-fl>=20)
{
int ln=fr-fl+1,mid1=fl+ln/3,mid2=mid1+ln/3;GG(mid2>fr)
double a=slope(mid1),b=slope(mid2);GG(a==b)
if(a<b) chmax(mx,b),fl=mid1+1; else chmax(mx,a),fr=mid2-1;
}
fo(i,fl,fr) chmax(mx,slope(i));
return ceil(mx);
}
};
int a[N],b[N];
void main()
{
int n=qread();fo(i,1,n) a[i]=qread();fo(i,1,n) b[i]=qread();
Convex::insert(1,b[1]);int ans=-INF;
fo(i,2,n) chmax(ans,Convex::solve(i,a[i])),write2(ans),Convex::insert(i,b[i]);
}

jsc2019 E Nearest String

题意:可以花X的代价删除前或后一个字符,或花Y的代价在末尾加入一个字符,给出两个字符串集合A和B,对某个集合中每个求到另一个集合的最小距离(变成里面元素的代价),字符串总长5e5

请先思考后再展开

考虑如何从A到B,设B中最长的在A出现的前缀长度ln,肯定先删再加

因为会形成B的前缀,考虑ac自动机里面塞B,枚举A的前缀令后面的删掉

设当前在ac自动机上匹配到节点x,设ss表示trie子树内补齐成一个B的最短距离

则答案为$min_{fail链上y} ss(y)*Y+(|A|-dep_y)*X$,贡献拆一下就能预处理了,code

jsc2019 F Count Permutations Many Times

题意:给出长为n的序列a,q次询问一个区间,问有多少n的排列满足$\forall i \in [l,r], p_i \ne a_i,n,q \le 2e3$

请先思考后再展开

这题挺有趣的

显然容斥,如果选出集合有重复是没有意义的,从颜色角度考虑生成函数,设区间内c的出现次数为$cnt_c$

$F(x)=\prod_c (1+cnt_c x),ans=\sum_{i=0}^n (-1)^i(n-i)! [x^i]F(x)$

无脑分治ntt是$O(qnlog^2n)$,应该过不去;区间询问套个莫队,多项式与二项式做乘除法是线性的,$O(n^{5/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
const int B=45;
struct Qes{int l,r,id;}qes[N];bool cmp(Qes a,Qes b){return a.l/B<b.l/B or (a.l/B==b.l/B and a.r<b.r);}ll ans[N];
int n,a[N],cnt[N];ll f[N];
void move(int pos,int op)
{
fo(i,1,n) f[i]=mm(f[i]+MOD-f[i-1]*cnt[a[pos]]%MOD);
cnt[a[pos]]=mm(cnt[a[pos]]+MOD+op);//debug 隐式的减法
fd(i,n,1) f[i]=mm(f[i]+f[i-1]*cnt[a[pos]]%MOD);
}
ll fac[N];
void main()
{
fac[0]=1;fo(i,1,N-1) fac[i]=fac[i-1]*i%MOD;
n=qread();int q=qread();fo(i,1,n) a[i]=qread()+1;
fo(i,1,q){int l=qread()+1,r=qread();qes[i]=(Qes){l,r,i};}sort(qes+1,qes+q+1,cmp);
int fl=1,fr=1;f[0]=1;f[1]=1;cnt[a[1]]=1;
fo(i,1,q)
{
while(fl<qes[i].l) move(fl++,-1);while(fl>qes[i].l) move(--fl,1);
while(fr<qes[i].r) move(++fr,1);while(fr>qes[i].r) move(fr--,-1);
fo(j,0,n) add(ans[qes[i].id],(j&1?MOD-1:1)*fac[n-j]%MOD*f[j]%MOD );
}
fo(i,1,q) write2(ans[i]);
}

jsc2019 G Nearest String

题意:n个点的树,维护初始为空的点集S(保证询问的时候不为空),q天每天反转一个点x的状态,最后输出每条边共有多少天在点集S的虚树内,$n \le 2e5$

请先思考后再展开

一个经典结论:对于一个点集的虚树,就是dfs序上相邻两点即最前后两点路径的和,且每条边会被统计恰好两次

于是dfs序上维护点集,每次就是加入、删除$O(1)$条路径,可以用树上差分实现统计,$O(nlogn)$,复杂度瓶颈为set

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
vc<pr> to[N];int dfnid=0,dfn[N],rev[N],dep[N],ff[N][30];
void pre(int x,int fa)
{
rev[dfn[x]=++dfnid]=x;
dep[x]=dep[fa]+1;ff[x][0]=fa;fo(i,1,20) ff[x][i]=ff[ff[x][i-1]][i-1];
for(auto y:to[x]) if(y.FR!=fa) pre(y.FR,x);
}
int getlca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
fd(i,20,0) if(bin(i)<=dep[x]-dep[y]) x=ff[x][i];
if(x==y) return x;
fd(i,20,0) if(ff[x][i]!=ff[y][i]) x=ff[x][i],y=ff[y][i];
return ff[x][0];
}
int sum[N],ans[N];
void push(int x,int fa)
{
for(auto y:to[x]) if(y.FR!=fa) push(y.FR,x),sum[x]+=(ans[y.SE]=sum[y.FR]);
}
void solve(int x,int y,int val) {sum[x]+=val;sum[y]+=val;sum[getlca(x,y)]-=val*2;}
set<int> ss;typedef set<int>::iterator IT;//circle
void main()
{
int n=qread(),q=qread();
fo(i,1,n-1){int x=qread()+1,y=qread()+1;to[x].PB(MP(y,i));to[y].PB(MP(x,i));}pre(1,0);
fd(tim,q,1)
{
int x=qread()+1,op=(ss.count(dfn[x])?-1:1);
if(sz(ss)==1 and op>0){solve(rev[*ss.begin()],x,tim*op*2);ss.insert(dfn[x]);continue;}
if(sz(ss)==2 and op<0){ss.erase(dfn[x]);solve(rev[*ss.begin()],x,tim*op*2);continue;}
if(op>0) ss.insert(dfn[x]);//sz>=3
IT now=ss.find(dfn[x]),tl=now,tr=now;
if(now==ss.begin()) tl=--ss.end(); else tl--;
tr++;if(tr==ss.end()) tr=ss.begin();
solve(rev[*tl],rev[*tr],-tim*op);
solve(rev[*tl],x,tim*op);solve(x,rev[*tr],tim*op);
if(op<0) ss.erase(dfn[x]);
}
push(1,0);fo(i,1,n-1) write2(ans[i]/2);
}

jsc2019 H Distinct Integers

题意:⽀持单点修改,区间询问有多少个子区间的数字两两不同,$n,q \le 5e5$

请先思考后再展开

不同数字,套路地求出nxt表示这个位置的数下一次出现位置,对于一个左端点l,$r \le min_{i=l}^{n-1} nxt_i$

于是对于区间$[fl,fr]$,合法子区间个数就是$\sum_{l=fl}^{fr} min(min_{i=l}^{fr} nxt_i,fr+1)-l$,只需要求出区间后缀min的和

考虑已知nxt序列如何求答案,考虑分治求

1
2
3
4
solve(l,r,以kr开始的后缀min)=
[l=r] min(kr,nxt[l])
[kr<=min(mid+1..r)] solve(l,mid,kr)+(r-mid)*kr
[otherwise] solve(l,mid,min(mid+1..r))+solve(mid+1,r,kr)

于是可以用李超树解决,调用solve的复杂度为$O(logn)$,线段树上将询问区间分成log段,故$O(nlog^2n)$

现在考虑修改操作,最多修改3个位置,需要最小值、维护右儿子答案,调用log次solve

总复杂度$O(nlog^2n+nlog^2n)$

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
ll ans;
namespace SGT
{
#define lc x*2
#define rc x*2+1
#define mid (l+r)/2
ll ltag[N*4];int mi[N*4];
ll solve(int x,int l,int r,int kr)
{
if(l==r) return min(mi[x],kr);
if(kr<=mi[rc]) return solve(lc,l,mid,kr)+ll(r-mid)*kr;
return ltag[x]+solve(rc,mid+1,r,kr);
}
int ask(int x,int l,int r,int fl,int fr,int kr)//返回min(区间,kr)
{
if(l==fl and r==fr) {ans+=solve(x,l,r,kr);return min(mi[x],kr);}
if(fr<=mid) return ask(lc,l,mid,fl,fr,kr);
if(fl>mid) return ask(rc,mid+1,r,fl,fr,kr);
int tmp=ask(rc,mid+1,r,mid+1,fr,kr);
return ask(lc,l,mid,fl,mid,tmp);
}
void change(int x,int l,int r,int pos,int num)
{
if(l==r) {mi[x]=num;return;}
if(pos<=mid) change(lc,l,mid,pos,num);
else change(rc,mid+1,r,pos,num);
mi[x]=min(mi[lc],mi[rc]);ltag[x]=solve(lc,l,mid,mi[rc]);
}
};
int n,a[N];set<int> pos[N];typedef set<int>::iterator IT;
int getright(set<int> &a,IT b){b++;return b==a.end()?n+1:*b;}
void main()
{
n=qread();int q=qread();
fo(i,1,n) a[i]=qread(),pos[a[i]].insert(i);
fo(i,1,n) SGT::change(1,1,n,i,getright(pos[a[i]],pos[a[i]].find(i)));
while(q--)
{
int op=qread(),x=qread(),y=qread();
if(!op)
{
x++;IT now=pos[a[x]].find(x);
if(now!=pos[a[x]].begin()) {int right=getright(pos[a[x]],now);SGT::change(1,1,n,*(--now),right);}
pos[a[x]].erase(x);a[x]=y;pos[a[x]].insert(x);
now=pos[a[x]].find(x);SGT::change(1,1,n,x,getright(pos[a[x]],now));
if(now!=pos[a[x]].begin()) SGT::change(1,1,n,*(--now),x);
}
else
{
int fl=x+1,fr=y;
ans=0,SGT::ask(1,1,n,fl,fr,fr+1);
write2(ans-1ll*(fl+fr)*(fr-fl+1)/2);
}
}
}

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