离谱,不知道现场判题机究竟多快,反正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))$。