2019CCPC哈尔滨


离谱,不知道现场判题机究竟多快,反正A和E带log疯狂TLE产生大量垃圾时间导致打银了。

A. Artful Paintings

差分约束。考虑将黑色位置设为$1$,否则为$0$,设到第$i$个位置的前缀和为$S_i$,则

  • 对于第一种限制,满足$S_R-S_{L-1}\ge K$
  • 对于第二种限制,满足$S_N-S_R+S_{L-1}\ge K$,由于$S_N$有单调性,可以先二分答案。

显然这是一个差分约束系统,除了上述约束外还有$0\le S_i-S_{i-1}\le1,\ 0\le S_i $,建图判断如果有负环则不合法。

(题外话:SPFA全程TLE,Bellman-Ford直接AC,关于SPFA,它死了)

B. Binary Numbers

dp。显然,题目给出的函数$F_k(a,b)$意义就是$a$和$b$二进制$k$位的$LCP$长度,涉及到二进制$LCP$,应该能想到这是$01$字典树上的$LCA$。

【前置芝士:树上$x$个点中,$dfs$序最小和最大的两个点的$LCA$深度最小】

(放到这题里等价于任意$x$个数,最大和最小的两个数二进制$LCP$最大)

所以题目关于$F_{m-1}(A_i,k)$的那个限制就变成了

$\forall i\in[1,n]\ LCP(A_i,L_i)\ge LCP(A_{i-1},L_{i})\&\&LCP(A_i,R_i)\ge LCP(A_{i+1},R_{i})$

这种选一个受左右两个影响的题就是老dp了:

设$f_{i,j,k}$表示考虑前$i$个区间,$LCP(A_{i},L_{i+1})=j,LCP(A_{i},R_{i})=k$,枚举$[L_i,R_i]$区间选的数$x$,

令$a=LCP(x,L_i),b=LCP(x,R_{i-1}),c=LCP(x,L_{i+1}),d=LCP(x,R_i)$,

则当$a\ge j \&\& b\le k$时有转移:$f_{i-1,j,k}\longrightarrow f_{i,c,d}$

总复杂度$O(m^2\times2^m)$。

C. Competition in Swiss-system

读完题就会的大模拟,待读题。

G. Game Store

看样子好像是博弈+线性基,待补。

E. Exchanging Gifts

拓扑排序,摩尔投票法。建反图求出每个第一类操作的贡献,然后map$O(n\log n)$或摩尔投票法$O(n)$求众数。设众数出现次数$x$,总数为$n$,答案为$max(0,2x-n)$。

L. LRU Algorithm

hash or 字典树。关键结论:假设LRU过程中cache长度无限,则每一个合法询问必然是LRU过程中的一个前缀。

因此可以暴力维护cache无限长的LRU过程中所有可能的字符串并存储其哈希值,由于数据是$5000\times5000$,多个log会TLE,所以不如把所有前缀都存起来,然后对于每个询问$O(n)$check,总复杂度$O(n(n+q))$。