雅礼NOI2019集训题集

大家都笑出了声,这选手也太菜了吧
——雅礼NOI2019集训题集

6-20

A

题意:给出一棵树和序列w,求$val_x=\sum_{y} w_{dis(x,y)}$,$n \le 1e5,w \le 1e4$

请先思考后再展开

点分后,以深度为下标让一侧给另一侧做贡献,$a_i+=[x^{-i}] \sum b_j w_{-(i+j)}$,因为答案不大,FFT的精度可以接受,$O(nlog^2)$

B

题意:统计逆序对个数为K的n的排列数,$n,k \le 1e5$,模数1e9+7

请先思考后再展开

我就说怎么这么熟悉:51nod1020逆序排列 HAOI2009逆序对数列 「2017 山东一轮集训 Day7」逆序对

$f(n,k+i)+=f(n-1,k),i \in [1,n-1] \to F_n=F_{n-1} (\frac{1-z^n}{1-z})=\frac{ \prod_{i=1}^n (1-z^i) }{ (1-z)^n },ans=[z^k]F_n$

下面是$\sum_{i=0}^{\infty} C_{i+n-1}^{n-1} z^i$,上面是$[z^m]=\sum_{S \in {1,2,..n},sum(S)=m } (-1)^{|S|}$,可以根号解决(见套路集锦),code

C

题意:给出序列A,按照长度为第一关键字左端点为第二关键字给所有区间排序,用区间最大值替换区间后得到长度为$(n+1)n/2$的序列B,求其中所有区间的最大值之和,$n \le 2e5$

不感兴趣

6-22

A

题意:给出序列a,q次区间询问,对所有没有重复元素且模D相同的所有子区间的权值求和,权值定义为$max-min-(len-1)$,$n,q \le 3e5,a_i,D \le 1e7$

请先思考后再展开

一开始没注意到重复元素的限制,发现笛卡尔树随便在线做,后来发现从mx考虑不可能做现在的问题,估计是从端点考虑,离线询问+线段树+单调栈什么的,但当时稍微搞了搞都挺麻烦就想着后面再看吧,然后就并没有回来看的机会了。

赛后用当时的思路推了推就会了:记录每个位置作为左端点的贡献和,右移右端点,碰到区间右端点时$+=ask(l,r)$

对于一个确定的右端点,维护好单调栈,每个位置每次就是+=块尾,线段树的维护如果像我一样不熟练的选手可能要动动脑子

写成$old+A*(T_{out}-T_{in})=(old-T_{in}*A)+A*T_{out}$,独立维护old和A的和,弹出的时候两个变量都是区间加

写得比较奔放的$O(nlogn)$

B

题意:二分图两侧点数分别是$n,m \le 1e9$,在时间i(从0开始),会考虑$(i\%n,i\%m)$,如果某个已经被染色则另一个也会被染色,给出初始染色的节点(点数不超过1e5),求所有点都被染色的最短时间或无解

请先思考后再展开

核心观察:对于$(1,i)$,如果到这里的路径最早(因此一定已经染色)是在$(1,a)$,则下一步一定是$(2,a\%m)$,因为$(a+zn) \%m+km=i \%n$中z无意义;同理,如果从$(2,b)$过来,不会再经过其他的a

因此在计算一侧时,先把这一侧的起点搞去对面,再把对面的搞到这一侧的大环上,大环在增量m下会分解为gcd(n,m)个独立的环,如果某个环没有关键点就无解,对每个环考虑,从起始时间最小的关键点开始处理即可

C

题意:每次花费1的代价选若干对没有交集的二元组$(i<j)$然后交换所有二元组的下标上面的值来给排列排序,现在给出一个排列,其中k个地方是0表示任意,枚举所有满足条件的$k!$个排列并分别累计最小代价、得到最小代价的方案数(比较每回合选的二元组的集合完全一致),并将这两个数输出,其中方案数取模,$n \le 1e5,k \le 12$

请先思考后再展开

难点在k=0,需要恰当的观察(我暴力写得很水只能拍9以内,然后经过渣渣手玩+勇敢猜测+过了几千组拍,以为只有大小为2的环可以两两配对,快乐白给):对于一个大小为siz的环,排列的最小步数为$siz==2?1:2$,方案数为$siz==2?1:siz$,然后如果是多个大小为siz的环,可以选择一部分两两配对,配对来两次排序的方案数为siz;最后不同大小不能配对

因此把步数为0和1判掉后,k=0搜环跑个$dp(siz,i)=dp(siz,i-1)siz+(i-1)siz*dp(siz,i-2)$即可,预处理为$O(nln\ n)$,可以过k=8的部分分

dp的逆元是容易不增加复杂度处理的,花费$bell(12)=4213597$枚举k条链的分组方案即可,$O(nlogn+k*bell(k))$

6-23

A

题意:n个球有着相同的高度限制$A \in [0,m]$,如果在一个高度不超过A的地方摔落就不会碎而可以再次使用,现在问在最坏情况下,猜测出A的最小实验次数,$n,m \le 5e3$

请先思考后再展开

神仙可以考虑设$dp(i,j)=i个球j次的高度上限,然后直接写下dp(i,j)=dp(i-1,j-1)+dp(i,j-1)+1$

一个就只能从小到大尝试,两个就可以分块,据此得到思路:考虑我现在剩下n个球,如果我有k次询问机会,最优方案一定是给第一个块分配n-1次(表示我在第二个快首做了一次询问然后碎了,因此一定在第一个块内),给第二个块分配n-2次(第一次询问没碎,第二次碎了)……即$g_{n,0}=1,g_{1,k}=k+1,g_{n,k}=\sum_{j=0}^{k-1} g_{n-1,j}$,$O(nlogn)$

1
2
3
4
5
6
fo(T,0,N-1) g[1][T]=T+1;fo(k,2,15){ g[k][0]=g[k-1][0];fo(T,1,N-1) g[k][T]=g[k][T-1]+g[k-1][T-1]; }
fo(T,1,qread())
{
int n=min(15ll,qread()),m=qread();
int ans=0;while(g[n][ans]<m+1) ans++;write2(ans);//m+1个可能取值
}

B

题意:交互题。存在一棵$n \le 1e5$点有根树,可以询问不超过3.5e6次$query(x,y)=[ x是y祖先 \to 1,y是x祖先 \to -1,otherwise \to 0 ]$,现在要在保证祖先总是比自己更早出现的前提下,输出任意一个序列

hint:数据不好造,出题人好像造得挺随意的

请先思考后再展开

链和菊花都很容易,二叉树可以不断把点集分裂给子树去做,每次取出覆盖所有人的一点作为根,$O(nlogn)$

然后我的想法是,随机一个点(对于上面的点而言,大概率是重儿子所在方向),把上面这条链拉出来,链以外的点在链上二分来分组到每层,然后每层去递归处理其他点(保留链上那一个点作为根会比较好写),这样复杂度看起来是每个点向上二分的次数为,被轻边覆盖的次数,即是一个非常不靠谱的$O(nlog^2)$

实测结果:n=1e5的二叉树就是链剖的最坏情况,次数约3.25e6

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
#include"tree.h"
vc<int> ans;
map<int,int> asked[N];
int Query(int x,int y)
{
if(asked[x].count(y))return asked[x][y];if(asked[y].count(x))return -asked[y][x];
return asked[x][y]=query(x,y);
}
void Div(vc<int> pt,int ALL=0)
{
int n=sz(pt),leaf=pt[rd(0,n-1)];
vc<int> link,oth;for(auto x:pt) if(x==leaf or Query(x,leaf)==1) link.PB(x); else oth.PB(x);
stable_sort(all(link),[&](int x,int y){return Query(x,y)==1;});int m=sz(link);vc< vc<int> > sub(m);
for(auto x:oth)
{
int pos=-1;for(int fl=0,fr=m-1;fl<=fr;){ int T=(fl+fr)/2;if(Query(link[T],x)==1) pos=T,fl=T+1; else fr=T-1; }
sub[pos].PB(x);
}
fd(i,m-1,0){ if(sz(sub[i])) sub[i].PB(link[i]),Div(sub[i]);if(i or ALL) ans.PB(link[i]); }
}
void solve(int n,int type)
{
vc<int> now;fo(i,1,n) now.PB(i);
Div(now,1);reverse(all(ans));
for(auto in:ans) submit(in);
}

C

CF704E Iron Man

6-24

A

题意:给出一棵$n \le 4e6$点有根树,点带权,从根出发k次且始终只能从父亲走向孩子,第一次到达某个节点可以获得上面的点权,求最大收益。时限1s,输入方式为某种无时间消耗的方式

请先思考后再展开

结论之间碰过,每次在k-1的方案基础上,直接添加净收益最大的路径

然后我就觉得小常数的zkw能过吧,卡了半天,还是要跑2.7s

正解确实没想到,按权值长链剖分,这样把所有链长度做个nth_element即可

B

题意:有n个点,分为A、B两种类型,初始时i和i+1的边是向右的,m次操作:修改某点点权、翻转区间中所有边。每次操作后求多少个A类点是能够到达某个权值比他大的B类点的,$n,m \le 1e5,权值 \le 77$

题面没写权值的范围把所有人坑了

请先思考后再展开

如果没有翻转,线段树维护结构体存每种权值的数量,合并复杂度为权值种数

如果单点翻转,只需要记录最左边和最右边两个未闭合的极长段上的信息

区间翻转的话,平时就维护好这个区间翻转后的答案即可

C

题意:初始为0的长度为n的序列,给定操作集合,每次在操作集合中选一个作为长度,然后选这样长度的某个区间异或1,求最少的次数得到给定的目标序列,$P=pop_count(目标序列) \le 10,|oper| \le 100,n \le 1e4$

请先思考后再展开

我tm天秀啊,心里想着差分,默默做了个前缀和,对着题解中2k这个神秘数字懵逼……菜鸡能傍下大腿还是很重要的……

差分后就是有2k个1,每次选两个距离为ai的点反转,最后变成全0

如果看做是n个点,初始在2k个点上面有个棋子,每次走一步的距离在集合内选,两个棋子相遇就抵消了(相遇后不抵消显然亏),求让所有棋子消失的最小步数。那么背包一下长度对应的代价,然后跑个状压去考虑谁跟最小那个配对,$O(2^{2k}(2k))$

1
2
3
4
5
6
int n=qread(),k=qread(),L=qread();while(k--) hh[qread()]=1;fd(i,n,1) hh[i]^=hh[i-1],debug("%d",hh[i]);
k=0;fo(i,1,n) if(hh[i]) pos[++k]=i;if(k&1) pos[++k]=n+1,deb;
mem(g,0x3f);g[0]=0;while(L--){ int len=qread();fo(i,0,N-1-len) chmin(g[i+len],g[i]+1);fd(i,N-1,len) chmin(g[i-len],g[i]+1); }
mem(f,0x3f);f[bin(k)-1]=0;
fd(s,bin(k)-1,1){ int x=log2(s&-s);fo(y,x+1,k-1) if(s&bin(y)) chmin(f[s^bin(x)^bin(y)],f[s]+g[pos[y+1]-pos[x+1]]); }
write(f[0]==INF?-1:f[0]);

6-26

A

题意:给出n个数,保留最多数使得异或和为0,$n,maxnum \le 5e5$

请先思考后再展开

转化为最少数得到总异或和,最坏就是线性基的秩即log个,做集合幂级数的次幂,因为判断只要单点所以可以写成$O(b2^b)$

B

题意:给定常数$K \le 20$,定义一个积性函数f,满足$f(1)=1,\forall 质数p正整数e,f(p^e)=p^k$,求$\sum_{i=1}^n f(i),n \le 1e13$

请先思考后再展开

不会min25而且n太大,根号做法想不到,那就试试用杜教筛骗点分吧,不过也没发现什么优美的式子,就自闭了……

结果被告知是powerful number的例题

C

题意:简单无向图,给每个点分配$col_i \in [0,lim_i]$,问有多少种分配方案使得$\oplus_{i=1}^n col_i=C且\forall (x,y)\ \in E,col_x \ne col_y$。$n \le 15,lim \le 1e18$

请先思考后再展开

先考虑没有边的情况:注意到限制很强,假设正在实现函数$solve(lim_1..lim_n,C)$,找到这n+1个数中最高位b(不是一般性设$lim_n$是最大的lim)。如果$lim_{n,b}=0$直接无解;否则考虑枚举$col_{n,b}$,如果是0,只需要考虑这一位,下面的位可以唯一决定,做个$dp(i,0/1)$的dp即可,如果是1,递归为$solve(lim_1,lim_2,…lim_n-2^b,C-2^b)$。总复杂度为$O(n^2*bit)$,因为每次会给lim消掉一个个1,而且实际效率远远高于这个下界

有限制的时候容斥非法边集,会将点分为若干个col相等的组,考虑枚举组的划分去计算非法边集,方案数的话就是每个组内做个$O(n^22^n)$的连通dp(见集合幂级数中ln相关资料)。事先按照lim大小给所有点排序编号,对于每个组,大小为偶直接乘上$(lim_{mi}+1)$,大小为奇的话相当于贡献了编号最小那个点mi。设$dp(S,ss)=分组集合为S,每组贡献编号最小编号点集合ss$,考虑还没被考虑的编号最小点所属集合去转移。复杂度考虑枚举的编号最小点为i,左边部分S一定都是1,所以是$O(2^i*3^{n-i})$,求和发现是$O(3^n)$,dp完再对每个ss做上面无边的情况即可,$O(2^n*n^2*bit)$,code

6-28

A

题意:$n \le 2e3$个带标号的人,i号有个数字ai,求分组方案(组不带标号),使得每组的大小不超过组内a的最小值

请先思考后再展开

对某个确定的表示每组大小的有序序列考虑怎么计数,从大到小处理,这样就很好判断在我能选的人中还剩多少

同时处理一个大小的所有组,$dp(sum,lst)=已经选了sum个,上个siz为lst$,加个后缀和优化,$O(n^2ln)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int n=qread();fo(i,1,n) a[i]=qread();sort(a+1,a+n+1);
fo(i,1,n) can[i]=n-(lower_bound(a+1,a+n+1,i)-a)+1;PRE();
dp[0][n+1]=1;
fo(i,0,n)
{
fd(lst,n,1) add(dp[i][lst],dp[i][lst+1]);
fo(j,1,n-i)
{
ll pw=1,V=facinv[j];
fo(k,1,(n-i)/j) if(k*j<=can[j]-i)
{
pw=pw*V%MOD;ll cc=Comb( can[j]-i,j*k )*fac[j*k]%MOD*pw%MOD*facinv[k]%MOD;
add(dp[i+j*k][j],dp[i][j+1]*cc%MOD);
}
}
}write(dp[n][1]);

B

题意:有一个大小为$n \le 100$的方棋盘,现在指定$m \le 10$个位置不能放棋子,其他地方每个位置最多一个,且每行、每列、每条长度为n的对角线都必须有至少一个棋子,问方案数模10007

反复检查多次题意都没注意到——总共n个棋子

请先思考后再展开

如果没有每行每列恰一个这个限制,我只能想到一个$O(n^22^{m+4})$的巨烦做法,现在就好做很多了

直接容斥这m个条件中w个上面有子(判一下上面的限制),然后现在就是在已经确定了w个的情况下放棋子

两条对角线都有=总-左斜无-右斜无+都无,总就是$(n-w)!$,某斜无就容斥至少若干位置有,$\sum_{z=0}^{n-w} (-1)^z C_{n-w}^z (n-w-z)!$

都无的话,可以把X上,分4个一组($(i,i),(i,n-i+1),(n-i+1,i),(n-i+1,n-i+1)$)去做背包,因为只有同组内会有影响,$O(2^m*(2^4n+n^2))$

C

题意:$mod=998244353,z=2mod+1$。从$(0,0)$出发,每步在三种情况中选一种执行:$\frac{A}{z}$的概率向上一步,$\frac{B}{z}$的概率向上一步,$1-\frac{A}{z}-\frac{B}{z}$的概率结束游戏。另有$K \le 50$个给定位置的坑(横坐标不超过$M \le 1e3$,保证不会两维都是D倍数),碰到就立刻结束游戏。如果走完第$n \le 1e18$步依然没结束就强制结束。求经过的坐标中两维都是$D \le 1e3$倍数的期望次数

请先思考后再展开

为了写起来好看用生成函数,不是必要的,下文中的出现的多项式取模只是为了表示指数取模,实现时就是手动循环卷积

设$[z^i]F_a=走a步中向右i次$,那么$ans=[x^0] \sum_{iD \le n} F_{iD} \bmod (z^D-1)$

如果没有坑,$F_a=F_{a-1}(Bz+A)=(Bz+A)^a$,求出$H=(Bz+A)^D=\sum_{i=0}^D (C_D^i B^i A^{D-i}) z^i$后,倍增即可求出这个等比数列和($S_{2n}=S_n*(H^n+1)$),NTT优化就是$O(nlog^2)$

有坑时,坑$(x,y)相当于要特殊处理[z^x]F_{x+y}$,将这些特殊的时刻断开得到若干极长段$[l,r]$,段内可以直接做上面没坑的过程(同时维护$F_a$)。现在问题就是要在关键点去掉非法的路径,那就要我们维护真实的,到达这个坑的方案数,然后在$F_a \bmod (z^D-1)$中对应位置减掉。考虑到坑的横坐标在M内,另外维护$F_a \bmod x^{M+1}$即可(得到后自己也要清为0)。$O((D+m)log^2K)$

6-29

A

题意:给出两个长度为n的字符串$S_1,T_1$,两个长度为m的字符串$S_2,T_2$,其中$S_1$可以在游戏开始前任意排列。游戏目标是用最少的步数把$S_1变成T_1$,每一步可以选择$满足S_1[i]=T_2[j]的(i,j),swap(S_{1}[i],S_2[j])$,无解-1,$n,m \le 4e5$,字符集为小写字母

请先思考后再展开

注意到交换后$S_2[j]=T_2[j]$,所以相当于m个操作只能用一次且相互独立

那现在就是用最少的步数从一个集合搞成另一个集合,费用流去平衡数量,点数只有26

B

题意:给出一个排列,每次选一个子序列保留顺序全部移动到最前面,最小次数地排序并输出一种方案,$n \le 3e3$

请先思考后再展开

操作一个集合相当于让其他数后置,考虑排列的逆($p_{a_i}=i$),用二进制考虑的话可以看做是给不操作的数的位置前面添加个1,然后新序列就是按照新位置排序

下面给出方案,有了上面铺垫后感性理解应该是最优的方案了:贪心地将其分为数量最少的若干连续段,每个连续段可以看做一组,这个组以后总是整体出现。那么相当于给这些组排序,如果直接相邻两组中左边那个选右边那个不选,就能够消除这两组间的矛盾而合并成同一个组(而且这个矛盾一定存在),因此这样做的步数就是段数的二进制长度。实现的时候可以从0开始编号便于确定是否选

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int a[N],ans,pos[N];vc<int> in[N];
vc<int> now;void out(int id){for(auto i:in[id]) now.PB(i);}
void main()
{
int n=qread();fo(i,1,n) pos[a[i]=qread()]=i;
int id=0;in[id].PB(pos[1]);fo(i,2,n) id+=(pos[i-1]>pos[i]),in[id].PB(pos[i]);
int ans=log2(id)+1;write2(ans);fo(i,1,n) write1(a[i]);puts("");
fo(i,0,ans-1){
now.clear();fo(t,0,id) if((t>>i)%2==0) fo(z,0,sz(in[t])-1) now.PB(in[t][z]);
sort(all(now));for(auto t:now) write1(a[t%bin(13)]);//选的前置
now.clear();fo(t,0,id) if((t>>i)%2==1) fo(z,0,sz(in[t])-1) now.PB(in[t][z]),in[t][z]|=bin(14+i);
sort(all(now));for(auto t:now) write1(a[t%bin(13)]);//不选,因此修改对应位置
puts("");
}
}

C

题意:给出一个$n*m$表格,$[0,nm-1]$每个数出现一次,用不超过1e5步排序为$a_{i,j}=(i-1)m+(j-1)$,每步可以将一行或一列shift任意次(行右shift就是每个数右移,末尾数放第一个),$n,m \le 100$

请先思考后再展开

感觉这题很神仙啊,题解又很短,搞了很久……

下文前提为判掉n或m=1,另外感觉这三步走的框架下,具体的方法是很多的,每步独立,下面给出的都是我第一反应想到的(虽然这第一反应的到来可能花了几万年),所以不喜欢可以随意替换

如果看作行shift只在第0行做,那么把其他行填好是容易的:

1
2
3
4
5
fo(i,m,n*m-1){
int x=pos[i].FR,y=pos[i].SE;
if(y==i%m) D(y,-x),R(0,-1),D(y,x-i/m),R(0,1),D(y,i/m);
else D(y,-x),D(i%m,-i/m),R(0,i%m-y),D(i%m,i/m),D(y,x);
}

剩下的这一行我们以0为参照物依次放置1到m-2,如果都成功m-1自然会到达正确位置

1
2
3
4
5
6
7
fo(i,1,m-2)
{
if(i==m-2 and a[0][(pos[0].SE+m-2)%m]==m-1) break;//0 1 2... m-1 m-2,这个break没看懂可跳过
R(0,-pos[i].SE);D(0,1);R(0,m-pos[0].SE-i);D(0,-1);//成功放到指定位置,但top位置变成路人
int go=(pos[i+1].FR>0?i+2:i+1);assert(go<m);
R(0,-pos[go].SE);D(0,1);R(0,-pos[(n-1)*m].SE);D(0,-1);//把路人随便放到一个空位,并把top转上来
}R(0,-pos[0].SE);

除了这个break一切看起来都很正常,问题就是在于i=m-2的时候可能发现手上路人是m-1而go找到的会是top所以不能搞

所以我们及时break出来后的局面就是0 1 2... m-1 m-2,解决这个问题颇费了番功夫而题解没有展开讲(所以不排除搞复杂了)

至于为毛n和m都是奇数的时候无解,我并没有一个合理的解释

完整代码

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