十二省联考2019

4/6

还有几天就2020省选了,才意识到整个OI生涯还不曾vp过省选题,赶紧补一补

D1

「十二省联考 2019」异或粽子

题意:长为$n \le 5e5$的序列,元素$<2^{32}$,选出$k \le 2e5$个不同的区间,区间贡献为其异或和,最大化区间贡献之和,2s

请先思考后再展开

$[l,r] \to b_r \oplus b_{l-1}$

二分第k大的区间是多大,维护字典树去check,$O(loga*nloga)$

由于k很小,得出后再做一次,暴力地往每个答案去找出来,$O(kloga)$

如果数据有梯度分数不少,很好写就先写了,结果忘记前缀异或调了一场(暴力也写错),赛后code,80pt(事实证明并没有梯度)


注意到k这么小却没怎么用,考虑换成k相关做法。k优区间,其实和超级钢琴差不多

查询最优点就是在可持久化字典树上查,$O(nlogn+klog^2)$

「十二省联考 2019」字符串问题

请先思考后再展开

每个a连向指向的b(给定),b指向自己是其前缀的那些a,再加个超级源,得到图,那么就是在上面拓扑排序判环,没有就是dag上最长路,可以在拓扑排序的过程中做

那么发现我们需要的大概率是优化建图,主要是b连向a的的部分

由于大部分都满足,$|b| \le |a|$,先考虑这种情况

先考虑SA,因为有那个限制,后缀排序后向一个区间内所有a连边(a挂在其左端点处,给每个左端点建立辅助点连向这个左端点的所有a),边数$O(nb*log)$

而如果没有$|b| \le |a|$,就是再加一维,主席树优化建图,边数$O(nb*log^2)$

考虑到多组数据,看上去不太行,考虑下sam会怎样


转化为反串中,条件改为后缀,将a挂在后缀树对应点上,每个点内排序

那么b需要向一个点内一段后缀(长度递增意义上),以及子树内所有点连边

那么树上每个点连向孩子,挂在点内的搞个辅助性的后缀连边即可

发现边数是$O(na+nb)$的,很稳,完整代码

关键代码:

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
int pos[N];//prefix
vc<int> go[N];//tree
int ct[N],lis[N],ff[N][20];
void build()
{
n=strlen(str+1);reverse(str+1,str+n+1);fo(i,1,n) pos[i]=insert(str[i]-'a');
fo(i,0,n) ct[i]=0;fo(x,1,id) ct[p[x].len]++;fo(i,1,n) ct[i]+=ct[i-1];fd(x,id,1) lis[ct[p[x].len]--]=x;
fo(i,1,id){ int x=lis[i];ff[x][0]=p[x].fail;fo(t,1,19) ff[x][t]=ff[ff[x][t-1]][t-1]; }
fo(x,2,id) go[p[x].fail].PB(x);
}
int find(int l,int r){ int x=pos[r];fd(t,19,0) if(p[ff[x][t]].len>=r-l+1) x=ff[x][t];return x; }
vc<pii> on[N];//on={pos,id}
void ad(int l,int r,int id){ on[find(l,r)].PB(MP(r-l+1,id)); }
vc<int> pt[N];//suffix
void build2(int x,int up)
{
sort(all(on[x]));
fo(t,0,sz(on[x])-1)
{
++Xid;if(t>0) G::ins(Xid-1,Xid,0); else if(t==0 and up) G::ins(up,Xid,0);
pt[x].PB(Xid),G::ins(Xid,on[x][t].SE,on[x][t].FR);
}
int self=++Xid;pt[x].PB(self);if(sz(on[x])) G::ins(Xid-1,self,0); else if(up) G::ins(up,self,0);
fo(t,0,sz(go[x])-1){ int y=go[x][t];build2(y,self); }
}
void ask(int l,int r,int id)
{
int x=find(l,r);
G::ins(id, pt[x][ lower_bound(all(on[x]),MP(r-l+1,0))-on[x].begin() ] ,0);
}

「十二省联考 2019」骗分过样例

没时间做了qwq

D2

因为一开始滚动数组偷懒,又没有判好有的组为空的情况,而且一开始的代码是k=0的,调了非常非常久

结果就是直到过了4h才过A的大样例,最后rush了B的60分

估分:100+60+0

实际:100+50+0

还好后面两题不算很水且暴力巨多分,不然我估计就会产生不可翻盘的差距了

赛后不限时OI赛制vp得分:100+75+(口胡)

「十二省联考 2019」皮配

题意

有0,1,2,3四个导师
01为阵营0,不超过c0人;23为阵营1,不超过c1人;
02为派系0,不超过d0人;13为派系1,不超过d1人;
分c组,共n个点,每个点选导师,第i个点代表si个人
其中k个点要去掉其中某个选择
同组必须选择相同的阵营
对合法方案计数
$M=max(c0,c1,d0,d1) \le 2500,n<=1e3,k<=30,si<=10$

请先思考后再展开

记总和S,将阵营看作行,派系看作列
相当于,第一行满足,$S-c1 \le x \le c0$;第一列满足,$S-d1 \le x \le d0$
首先暴力有20pt
对于k=0,行和列相当于分别按照组和学校选两次,分别做两次dp即可,$O(nS)$,40pt
对于k个人的情况,分配列的dp只给非特殊学校分配
把含有特殊学校的组拿出来,分别考虑放第一行还是第二行,做两次dp
$dp(tim,sum,i)=$要处理的第tim组,第一行当前数量,第一列当前数量
其中行是按组记的,列只考虑特殊学校,即数组大小为$30*2500*300$,时间复杂度同

code

「十二省联考 2019」春节十二响

题意:给定一棵$n \le 2e5$的有根树,树上每点有点权。将所有点分为若干组,要求每组内任意两点没有祖先关系,最小化每组最大值之和

请先思考后再展开

对于链,点1一定是单独,相当于二分图
每次取出全局最大值,肯定要对答案有贡献,将其和另一侧当前最大值匹配起来,一换一即可,15pt

猜个结论,每次选当前最大点,考虑取剩下哪些点和它放一组,从大往小扫剩下的点,能加入组中就直接加入
发现能过拍(与$O(3^n)$拍,不算小了),复杂度为$O(n^2log)或O(n^2)$,共计75pt,code


「十二省联考 2019」希望

题意:n点无根树,无边权,统计合法的,长度为k的数组,数组元素可能重复或相交,元素内容为树上联通点集
方案合法条件为,存在点x,使得对于数组中任意一个集合,x在集合内,且满足集合中任意点y,$dis(x,y) \le L$
$n \le 1e6,k \le 10$

没时间了qwq

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