hitachi2020题解

Source

Social Infrastructure Information Systems Division, Hitachi Programming Contest 2020

hitachi2020

hitachi2020A Hitachi String

code

hitachi2020B Nice Shopping

code

hitachi2020C ThREE

题意:给出$n \le 2e5$的树,要求构造排列p,满足$\forall dis_{i,j}=3,p_i+p_j=0 \pmod 3或p_ip_j=0 \pmod 3$

请先思考后再展开

的确没想到,服输

显然就是限定了0、1、2的个数(牢记$[1] \ge [2] \ge [0]$),然后删掉所有0后是二分图

容易想到给树先黑白染色,然后我们希望通过一些调整(移动到另一个侧),使得所有1在一侧,2在另一侧,0任意

设较小的是A,另一个是B,如果$|A| \le [0]$,直接把所有A填为0,B就随便填了;而如果$|A|>[0],就意味着|A| \ge [1]$,可以把1给A,2给B,0随便填

看Cyanic的代码吧

hitachi2020D Manga Market

请先思考后再展开

rush失败……而且还忘记cmp里不能有=了

发现就是做若干次$t’=t*(a_i+1)+(b_i+1),最后t \le T+1$,因此a++,b++,T++

把多项式展开就是$\sum b_i \prod_{j>i} a_j$,直觉微扰:$b_1S+b_2Sa_1 \le b_2S+b_1Sa_2即b_2(a_1-1) \le b_1(a_2-1)$,此时1要在2后

因此排序后,就是基础的$dp(i,cnt)$表示选了cnt个a>1的地点,而a=1的单独抽出来,因此cnt是log级别的,$O(nlogn)$

code

hitachi2020E Odd Sum Rectangles

题意:构造一个大小为$(2^n-1)*(2^m-1)$的01矩阵,$n,m \le 10$,最大化$\sum_{子矩阵} 异或和$

请先思考后再展开

这种题肯定要先知道上界:$H=2^n-1,W=2^m-1,对于1 \le jl \le jr \le W,个数为(\sum_{i=0}^{H} s(1,i,jl,jr))*(\sum_{i=0}^{H} s(1,i,jl,jr) \oplus 1)$,也就是$\frac{W(W+1)}{2}*( \frac{H+1}{2} )^2$(可见应当使$H \ge W$)

当H=W的时候,给出一种构造方法:将n-1的答案放在四个角,中间的一行、一列,除了交点是1其他全是0。正确性很明显,核心思想就是中间的列使得01反转了,这样必定是数量相等的

而H>W只需要截取$H*H$的前W行即可,code

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