2018 Multi-University Training Contest 1 比赛记录

Author Avatar
Sakits 7月 23, 2018

被演了,成功成为一个没A掉T2266题队…
enter image description here

A. Maximum Multiple

solved by reek. 00:20:22(+)

  显然为了让积尽量大x,y,zx,y,z应该尽量接近,那个不定方程只有三个解:

n3+n3+n3=nn2+n4+n4=nn2+n3+n6=n\begin{gathered} \frac{n}{3}+\frac{n}{3}+\frac{n}{3}=n\\ \frac{n}{2}+\frac{n}{4}+\frac{n}{4}=n\\ \frac{n}{2}+\frac{n}{3}+\frac{n}{6}=n \end{gathered}

  第三个显然没啥用,分是否能被3344整除即可…

B. Balanced Sequence

unsolved.

  玄学贪心,先考虑相邻两组括号,按消除多的拼,如果一样多显然左括号多的往前丢更优,不会证正确性…
  以后贪心题可以考虑代码里丢多种贪心策略最后答案取最优…

bool operator < (poi a, poi b)
{
	int x=min(a.l, b.r), y=min(a.r, b.l);
	return x>y || (x==y && a.l>b.l);
}

C. Triangle Partition

solved by reek. 01:11:40(+2)

  因为保证三点不共线,直接把点按xx排序三个三个配就好了,显然可以用垂直与yy轴的线把这些三角形分隔开,一定不会相交。

D. Distinct Values

solved by Driver_Lao. 00:58:37(+4)

  字典序最小显然从左往右贪心,每次填下能填的最小的数,用set随便维护一下即可。

E. Maximum Weighted Matching

unsolved.

F. Period Sequence

unsolved.

G. Chiaki Sequence Revisited

solved by Sakits. 03:02:50(+4)

  上来打完表差不多10min10min就会做了,结果细节题调了3h3h
  打了个表可以发现ii出现的次数为log2(lowbit(i))log_2(lowbit(i)),那么题目要求的就是:

i×log2(lowbit(i)),  log2(lowbit(i))n\sum i\times log_2(lowbit(i)), \ \ \sum log_2(lowbit(i))\leq n

  考虑求最大的ii为多少。
  一开始想一位一位尝试填11看是否可填。推了一下发现第xx位(从11开始编号)要填11,需要保证nn至少有2x12^x-1个数,能填就把nn减去2x12^x-1,但是最后最大的ii实际上是所有2x12^x-1的和n\geq n的最小的数,这个比较难处理,所以考虑二分。
  二分之后如果用上述方法check是log2nlog^2n的,大概会被卡,但是转化一下式子可以得到一个数yy2x12^x-1的和实际上是2y2y-yy11的个数),这个可用__builtin_popcountll()来做到O(1)O(1),比赛的时候用的是__builtin_popcount()查了1h1h
  得到最大的ii之后,把log2(lowbit(i))log_2(lowbit(i))相同的ii一起处理,也就是每次需要求钦定最低位的11log2(lowbit(i))log_2(lowbit(i))<n<n的数的和,这个把nn右移ii位后减一下移回来最后加上最低位的11就好了,对于=n=n的数单独处理即可。

H. RMQ Similar Sequence

solved by Sakits. 04:23:58(+4)

  因为BB数组里两个数相同的概率为00,所以BB实际上可以看成是一个排列,并且每一种排列的出现概率为1n!\frac{1}{n!},每种排列的期望权和为n2\frac{n}{2}
  然后问题转化成了求有多少个与AA数组 RMQRMQ相似 的排列,先找到AA数组里最大的数,然后以这个数把序列分成两半,左右两边递归即可,设左区间的方案为F(lt)F(lt),右区间的方案为F(rt)F(rt),当前区间方案为F(x)F(x),左区间大小为sizeltsize_{lt},当前区间大小为sizexsize_x,则递归完左右区间可以推出F(x)F(x)

F(x)=F(lt)×F(rt)×(sizex1sizelt)F(x)=F(lt)\times F(rt)\times \binom{size_x-1}{size_{lt}}

  就是左区间的方案数 乘 右区间的方案数 乘 剩下的数放在左右两区间的方案数。
  实际上就是AABB的笛卡尔树相等求符合笛卡尔树的排列。

I. Lyndon Substring

unsolved.

  论文题,被安排的明明白白的…

J. Turn Off The Light

unsolved.

K. Time Zone

solved by Mczhuang. 01:56:08(+10)

  签到题…罚时起飞…