做着玩一玩...... 10分钟看起来很短......但是每道题多花10分钟......就会GG. TAT 比赛时完成A-E. F需要感性理解想一想. G题算是上上场 Educational Round 某题的扩展版. 当时就看到有神犇用费用流来做. 嘿嘿, 果然把上次的代码粘了一遍...... ^_^ 然而我的建图太过 naive......修改了一下, 以点数多几倍的代价把边数从
列不等式, 取整.
B. Permutation Game
C. Sofa Thief
读了一遍题, 不知道它在讲什么......做完D, 又读了几遍题......
n*m 的方格图, d个物品, 每个物品占两个相邻的格子: (x1,y1), (x2,y2). 每个格子至多被一个物品占用. 对于A!=B, 如果存在A的某个格子(xi,yi), B的某个格子(xj,yj), 使得xi<xj, 就称A在B左边; yi<yj, 就称A在B上面. 右边, 下面的定义类似. A可以既在B的左边/上面, 又在B的右边/下面. 给出左边,右边,上面,下面的物品数量, 求符合它们的物品编号, 或报告无解. 有解保证解唯一. (1≤d≤10^5, 1≤坐标≤10^5)
对上下左右分别做前缀和即可. 注意, 求答案的时候可能得减去自己.
D. Multicolored Cars
Alice 和 Bob 又开始玩游戏了! 每辆车有颜色. A,B各选一个不同的颜色, 如果一辆该颜色的车开过, 对应计数器++. 如果每一时刻A的计数器严格大于B, 则A赢; 如果每一时刻B的计数器非严格大于A, 则B赢; 否则, 平局. 已知A选的颜色和颜色序列, 问B选什么颜色能赢, 或报告无解. (1≤n≤10^5, 1≤颜色编号≤10^6, 保证如果有解, 存在[1,10^6]内的解)
显然, 序列中出现的颜色不会差于没出现的颜色 (如果序列中只出现了A则无解). 随着A的出现, 颜色被逐步淘汰. 一个简单的想法是用小根堆维护(出现次数,颜色), 每次出现A, 弹掉一些元素.
事实上, 时间复杂度可以做到线性. 淘汰并非只能在出现A的时候进行. 对于某个还未被淘汰的颜色x, 如果cnt[x] < cnt[A], 则它被淘汰, 否则++cnt[x]. 最后, 对所有没被淘汰的颜色再做一次检查即可. 这样, 出现一次A之后, 一个该被淘汰的y, 要么在下一次出现时淘汰, 要么在最后的检查时淘汰.
看到skipher同学在WA了很多发之后改成一个暴力......好神啊......想了想, 发现时间复杂度也是线性的......
关键在于if (vec[i].size()<vec[A].size()) return false; 设vec[A]被扫了k次, 那么vec[A].size()<=n/(k+1). Orz
E. Card Game Again
一个长度为n的正整数序列a, 删掉前面x个元素和后面y个元素, 留下一个非空序列, 其元素之积为k的倍数. x,y可以为0. 求(x,y)的数目. (1≤n≤10^5, 1≤k,ai≤10^9)
如果区间A包含一个区间B, 其元素之积是k的倍数, 那么A的元素之积亦是k的倍数. 所以, 对于固定的左端点, 可以二分查找最小的右端点. 倒序枚举x, 用树状数组查询前缀积模k.
two-pointers似乎有可行性, 但是做不了除法......质因数分解? 根号复杂度吃不消啊......Tutorial提醒我们, 只用求出k的质因子的幂.
F. Level Generation
q个询问, 求n个点的简单无向图的最大边数, 要求桥边不少于总边数的一半. (1≤q≤10^5, 1≤n≤2*10^9)
这个数据范围只允许二分或O(1)计算. 怎样验证m条边是否可行呢?
假设有k条桥边. 对边双缩点后, 得到一棵k个节点的树. 把所有边双挪到一个叶子节点形成一个点双, 再把树换成一条(k-1)条边的链. 边的总数, 桥边的数量均不会变化. 所以, 我们可以只考虑这样的结构: 一个点双拖着一条尾巴~
设点双的大小为x, 则尾巴的长度为 n-x. 这一结构最多能容纳 x(x-1)/2 + n-x 条边. 当x≥1, 尾巴越短, 能容纳的边越多. 因此, 不妨令 n-x=ceil(m/2). 对于x≥1, m条边可行, 当且仅当 x(x-1)/2 ≥ floor(m/2).
三分也是可以的. 我们要求的是 n-x + min(x(x-1)/2, n-x) 的最大值, 它是关于x的单峰函数. (呃......令 x(x-1)/2 = n-x, 我们可以直接解出最大值在何处取得)
G. Four Melodies
一个长度为n的序列, 选出4个不相交的子序列, 使得: 对于每个子序列, 每个元素的下个元素要么在模7意义下跟它相等, 要么两者之差的绝对值等于1. 求子序列长度之和的最大值. (4≤n≤3*10^3)
最大费用最大流. 对元素的每个取值建一条链, 边数和点数就都是O(n)的了.